Proof of Countability of ℚ: Bijection from A to ℕ

In summary: But you don't have to restrict it. You can directly deduce from it that ##\mathbb{Q}## is countable. And then use the proof to show that it is infinite. This would be a proof that ##\mathbb{Q}## is countable by definition.
  • #1
Danijel
43
1
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 (*)?
 
Physics news on Phys.org
  • #2
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.
 
Last edited:
  • #3
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.
 
  • #4
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.
 
  • #5
Okay, perhaps the professor got it from some well known math book.
 
  • #6
The book by K.Kuratowski, A.Mostowski, Set Theory, is mentioned in the bibliography.
 
  • #7
Danijel said:
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".
 
  • Like
Likes jedishrfu
  • #8
fresh_42 said:
##\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.
 
Last edited by a moderator:
  • #9
Danijel said:
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.
 

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

What is the significance of proving the countability of ℚ?

The proof of countability of ℚ is significant because it shows that the set of rational numbers, which includes all positive and negative fractions, can be put into a one-to-one correspondence with the set of natural numbers. This means that there are the same number of rational numbers as there are natural numbers, and it is possible to count and list all of the rational numbers.

What is a bijection and how does it relate to the proof of countability of ℚ?

A bijection is a function that maps each element in one set to a unique element in another set. In the proof of countability of ℚ, we use a bijection to show that there is a one-to-one correspondence between the set of rational numbers and the set of natural numbers. This means that for every rational number, there is a unique natural number that corresponds to it.

How is the proof of countability of ℚ different from the proof of countability of ℕ?

The proof of countability of ℕ involves showing that the set of natural numbers can be put into a one-to-one correspondence with the set of positive integers. In contrast, the proof of countability of ℚ involves showing that the set of rational numbers can be put into a one-to-one correspondence with the set of natural numbers. This is a more complex proof because the set of rational numbers is infinite and includes both positive and negative numbers.

What are the practical applications of the proof of countability of ℚ?

The proof of countability of ℚ has several practical applications in mathematics and computer science. It is used to show that the set of rational numbers is a countable set, which is useful in understanding the size and structure of infinite sets. It is also used in creating algorithms and data structures for efficiently storing and manipulating rational numbers in computer programs.

What are the limitations of the proof of countability of ℚ?

The proof of countability of ℚ only shows that there is a one-to-one correspondence between the set of rational numbers and the set of natural numbers. It does not provide any information about the order or structure of the rational numbers. Additionally, the proof assumes that the set of natural numbers is already countable, which is a separate proof that must be established.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
278
Replies
15
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
801
  • Calculus and Beyond Homework Help
Replies
1
Views
591
  • Calculus and Beyond Homework Help
Replies
3
Views
938
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
7K
Back
Top