Undergrad Proof of Countability of ℚ: Bijection from A to ℕ

[Danijel]

I know there are many proofs of this I can google, but I am interested in a particular one my book proposed. Also, by countable, I mean that there is a bijection from A to ℕ (*), since this is the definition my book decided to stick to. The reasoning is as follows:
ℤ is countable, and so iz ℤxℤ. Since ℤ*=ℤ\{0}⊂ℤ, ℤxℤ*⊂ℤxℤ, ℤxℤ* is countable (since every infinite subset of a countable set is also countable). Now, from the construction of ℚ, we know that ℚ=ℤxℤ*|_~, ℚ is the image of τ:ℤxℤ*→ℚ, so ℚ is either finite or countable. Since ℤ⊂ℚ, ℚ is countable.
I understand everything except the part "ℚ is the image of τ:ℤxℤ*→ℚ, so ℚ is either finite or countable"(**), since this is not proven anywere. Maybe it is obvious, but I haven't grasped it. I've found few similar proofs of this statement, but they all consider A being countable if there's an injection from A to ℕ, whereas my book insists on a bijection. So my question is, how do I deduce (**) from (*)?

 

[Danijel]

So, I thought about this, and this is what I have concluded. Since there is a surjection from ℤxℤ* to ℚ, then there is injection from S⊂ℤxℤ* to ℚ, which means that there is a bijection from S to ℚ. Since ℤ⊂ℚ, ℚ is infinite, but then S is infinite too. Since S is an infinite subset of a countable set, it is also a countable set. Now, since there is a bijection from S to ℚ, it follows that there is a bijection from ℚ to ℕ, so ℚ is countable by the definition. Is this right? However, I still don't know about the part"finite or countable", since I have only considered the countable.

 

[jedishrfu]

What book are you referring to? and what pages?

This may help another poster in answering your question. Calling @fresh_42

Also, try not to post twice in a row and instead just edit your original post with the additional content.

 

[Danijel]

This book is in Croatian, and you can say it is not really a book, more like a compilation of notes made by one of our professors.
Also, sorry for posting twice. I didn't know about the convention.

 

[jedishrfu]

Okay, perhaps the professor got it from some well known math book.

 

[Danijel]

The book by K.Kuratowski, A.Mostowski, Set Theory, is mentioned in the bibliography.

 

[fresh_42]

I know there are many proofs of this I can google, but I am interested in a particular one my book proposed. Also, by countable, I mean that there is a bijection from A to ℕ (*), since this is the definition my book decided to stick to. The reasoning is as follows:
ℤ is countable, and so iz ℤxℤ. Since ℤ*=ℤ\{0}⊂ℤ, ℤxℤ*⊂ℤxℤ, ℤxℤ* is countable (since every infinite subset of a countable set is also countable). Now, from the construction of ℚ, we know that ℚ=ℤxℤ*|_~, ℚ is the image of τ:ℤxℤ*→ℚ, so ℚ is either finite or countable. Since ℤ⊂ℚ, ℚ is countable.
I understand everything except the part "ℚ is the image of τ:ℤxℤ*→ℚ, so ℚ is either finite or countable"(**), since this is not proven anywere. Maybe it is obvious, but I haven't grasped it. I've found few similar proofs of this statement, but they all consider A being countable if there's an injection from A to ℕ, whereas my book insists on a bijection. So my question is, how do I deduce (**) from (*)?

$\tau$ is a projection, so it is neither injective (subset) nor bijective (equal). $\mathbb{Q}= \mathbb{Z}\times \mathbb{Z}^*/ \sim$ where the equivalence is defined by $(a,b)\sim (c,d) \Longleftrightarrow ad=bc$. This means, that $\operatorname{im}\tau = \mathbb{Q}$ has at most as many elements as $\mathbb{Z} \times \mathbb{Z}^*$ has, possibly less. That's where the possibility of finite many comes into play and why $\mathbb{Z}\subseteq \mathbb{Q}$ is needed as an argument, to rule this out.

The proof doesn't establish a direct bijection as required for $(*)$. Instead it uses properties of subsets and images under mappings. These properties have to be proven first and that's where the connection to $(*)$ occurs. If you want to deduce it directly from there, you'll have to use another proof or combine all previous statements to a long, new one: "If $B \subseteq A$ and $A$ is countable then $B$ is countable." + "If $A$ is countable and $f\, : \, A \longrightarrow B$ is a projection, then $B$ is countable." + "the proof above".

 

[Danijel]

$\tau$ is a projection, so it is neither injective (subset) nor bijective (equal). $\mathbb{Q}= \mathbb{Z}\times \mathbb{Z}^*/ \sim$ where the equivalence is defined by $(a,b)\sim (c,d) \Longleftrightarrow ad=bc$. This means, that $\operatorname{im}\tau = \mathbb{Q}$ has at most as many elements as $\mathbb{Z} \times \mathbb{Z}^*$ has, possibly less. That's where the possibility of finite many comes into play and why $\mathbb{Z}\subseteq \mathbb{Q}$ is needed as an argument, to rule this out.

The proof doesn't establish a direct bijection as required for $(*)$. Instead it uses properties of subsets and images under mappings. These properties have to be proven first and that's where the connection to $(*)$ occurs. If you want to deduce it directly from there, you'll have to use another proof or combine all previous statements to a long, new one: "If $B \subseteq A$ and $A$ is countable then $B$ is countable." + "If $A$ is countable and $f\, : \, A \longrightarrow B$ is a projection, then $B$ is countable." + "the proof above".

So is my 2nd post incorrect? I know that the given projection is not injective, but it is surjective. Can we then restrict it to an injective one, and get a new function from a subset of the domain to the codomain? From here it follows that the second set is either finite or countable. Anyways, thank you for your reply.

 

[fresh_42]

So is my 2nd post incorrect? I know that the given projection is not injective, but it is surjective. Can we then restrict it to an injective one, and get a new function from a subset of the domain to the codomain?

Yes, that's what the equivalence relation does. It restricts all pairs of $\mathbb{Z}\times \mathbb{Z}^*$ to equivalences classes, because $\frac{1}{2}=\frac{2}{4}=\ldots$ Of course you can also count those quotients as different, in which case you get a bijection, but to count $\frac{0}{1}$ and $\frac{0}{z}$ as $\mathbb{Z}^*-$many elements isn't very convincing.

From here it follows that the second set is either finite or countable. Anyways, thank you for your reply.