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 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)^i)*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?

 

[warpus]

well, all you gotta do is map 2n for the positive integers, and 1-2n for the negative ones

i'm not sure if you went overboard or if you're wrong, but it's one of the two

 

[Atticus]

Aneeshm, rigor is not the same thing as formalism. Rudin doesn't present only argument, but also the bijection, he just doesn't give explicit formula for it.

Your function isn't that easy to read, and I didn't bother even to try understand what it is about (what is mod? You use Ni to define Ii and Ii to define Ni?). You seem to think (and don't be embarassed, it's common among first/second year students) that function has to be expressed with a single explicit formula, and if it is not, it would be less rigorous.

Proof's purpose is to convince the reader about theorem and help him understand it. Making them complex in order to be formal doesn't serve this purpose.

If you inisist on doing an explicit formula, there's a lot easier one too, do you want try again, or shall I reveal it?

 

[nihilistic]

But isn't that far too obvious? You wrote a whole paper based whose content takes about 5 seconds of thought?

 

[nihilistic]

Proof's purpose is to convince the reader about theorem and help him understand it. Making them complex in order to be formal doesn't serve this purpose.

That's where "the exercise is left to the reader" come from.

If you inisist on doing an explicit formula, there's a lot easier one too, do you want try again, or shall I reveal it?

I think his N -> Z is simple enough, but written in a way that does make it technically non-simple and regrettably wrong. However, his Z -> N seemed simply horrendous. Anyway, here are the correct formulas in what I think seemed the simplest form possible:

z_i = - ((-1)^n_i)*floor(n_i/2)

note 2 things:
1. the negative sign
2. this describes z_i as a function purely of n_i, not as a function of both n_i and i

n_i = abs(3z_i - 1) - floor(abs(z_i - 1/3))

 

[Atticus]

Oh, I read too quickly Aneeshm's post (and have been awake a little too long). I thought that Ni was somehow used in Ii, and there's a reason for that misunderstanding too: why prove that there is a bijection from Z to N, if it is already proved that there is a bijection from N to Z? Why use notation n_i to the "i:th natural number"? Isn't it a bit superfluous?

EDIT: I'll add what I think would be a good answer for that:

Define f:N->Z: f(n)=(-1)^n floor(n/2).

Spoiler f is injection: :

If it weren't there would be k and n in N such that f(n)=f(k), and therefore |f(n)|=|f(k)|, that is floor(n/2)=floor(k/2). This is possible only if n=k+1 or k=n+1 (and neither of them is 0), and then f(n) and f(k) have different signs.

Spoiler f is surjection: :

Take k in Z. If k > 0, then
k= (-1)* ^(2k) floor(2k/2)=f(2k).
If k<0, then
k=(-1)^(1-2k) floor ((1-2k)/2)= f (1-2k).
If k=0, k=f(1).

Because f is both injection and surjection, it is a bijection.

EDIT2: Please note that to be rigorous, it's essential to show that the function you give is indeed a bijection. Often in showing that injection f:A->B is a surjection amounts to the same thing as finding out it's inverse function, but finding out explicit formula for it can be just too confusing, and the method I give above, going through different possibilities, is more clear and convincing.