Constructively proving that the integers are countable

[aneeshm]

For the mathematicians among us.

In my Theory of Computation paper (yesterday), one question we were asked was to prove that the set of integers is countable.

Now this wasn't something I had studied as part of ToC per se, nor had I expected anything of the sort to be part of the paper, but because of an interest in general mathematics, I remembered an argument presented in Baby Rudin by ordering the integers like this:

0,1,-1,2,-2,....

and the naturals in the natural order:

1,2,3,4,5,....
and wrote that.

What Rudin had not explicitly provided was the construction of the bijection between them, so I had to do that on my own.

Assuming that Ni is the ith natural, and Ii the ith integer in our ordering, the mapping from the naturals to the integers:

Ii=((-1)^Ni)*floor(Ni/2)

and from the integers to the naturals:

Ni=
1, for Ii=0
mod(Ii*2) + (mod(Ii)-Ii)/2*mod(Ii), for all other integers

I had no idea what level of rigour was expected, so I gave it everything possible. Is that sufficient as an answer to the question, or did I go way overboard? And much more importantly, is the answer correct?

[Solver]

You can order those integers but it's easier to sketch a proof if you let them be separate sets.

Say, Zp is the set of non-negative integers = {0, 1, 2...}, and Zn is the set of negative integers = {-1, -2, ...}. If you map the sets to the natural number set N, you get bijections. For Zp, you get a N -> Zp map, where element x from N maps to x-1 from Zp, as in:

1 -> 0
2 -> 1
3 -> 2
...

Then for Zn, you get a N->Zn map where x from N maps to -x from Zn, as in:

1 -> -1
2 -> -2
...

Since the set of integers Z = Zn + Zp, it's a union of two sets. Zn and Zp have been proven to be countable, so a union of them is also a countable set. I don't think including a proof of that would be needed?

Disclaimer: this is not official advice

[Grandpa Troll]

Wow, do I have lots to learn

I use Integers in establishing standard deviations but hats off to you folks

Theoritical values based upon dry rodded unit weights, volumes and specific gravities are enough to keep old Gramps entertained

Seriously, I congratulate you folks on these levels of Math

[Solver]

I may be wrong, but I think that KH is the only person here to actually do serious math. Applied math in a chemistry/computer science/architecture, etc. course can't really be compared to that.

[Grandpa Troll]

Originally posted by Solver
I may be wrong, but I think that KH is the only person here to actually do serious math. Applied math in a chemistry/computer science/architecture, etc. course can't really be compared to that.

Amen

[Kuciwalker]

Originally posted by Solver
I may be wrong, but I think that KH is the only person here to actually do serious math. Applied math in a chemistry/computer science/architecture, etc. course can't really be compared to that.

Yes, you're wrong.

[Kuciwalker]

Re: Constructively proving that the integers are countable

Originally posted by aneeshm
I had no idea what level of rigour was expected, so I gave it everything possible. Is that sufficient as an answer to the question, or did I go way overboard? And much more importantly, is the answer correct?

Yes, your answer is fine. That's the canonical proof, actually.

[Solver]

What, do you do (advanced) non-applied math?

[Kuciwalker]

I'm pretty much done with my math degree. (3 courses left)

Even if I don't count, we have Lul Thyme (doing his math PhD), JM, and Ramo, to name a few.

[Solver]

Okay. Then I am quite wrong

[Kuciwalker]

Also, proving that things are countable isn't "advanced non-applied math". It's more like first-year course material for any major likely to touch the idea of infinite sets. (CS math physics w/e)

[Solver]

I know, I wasn't implying this to be advanced level, I was expressing my surprise that you do advanced stuff

[KrazyHorse]

LulThyme is the only serious mathematician here. I am a distant second to him.

Kuci, Ramo and (dare I say it) even JM are behind me.

[Dauphin]

Can we constructively prove that integers are Indo-European?

[KrazyHorse]

Originally posted by Kuciwalker
I'm pretty much done with my math degree. (3 courses left)

What are the precise course requirements?

If you have only 3 courses left I'm surprised because you seem to be a bit weak on algebra for that.

I personally don't claim to have an undergrad math degree. I almost have one (was missing 2 or 3 courses from my uni's requirements).

Then again, I've noticed that American technical undergrad requirements are significantly lower than what I'm used to (in the major, while requiring more humanities etc)

Basically, after the first year courses our requirements were 20 courses in the major over 3 years.

I took the "joint honours in mathematics and physics" which required 27 courses over those same 3 years. We got to skip a couple of physics classes in favour of math classes, and there were already some math requirements in the physics program, so I was close to the math program requirements.