Is It Possible to Embed the Set of Rational Numbers in a Countable Set?

  • Thread starter radou
  • Start date
  • Tags
    Proof
In summary, The conversation discusses how to prove that the set Q of all rational numbers is countable. One method is to show that there is a 1-1 mapping between the set of natural numbers and the set of strictly positive rational numbers, and since N*N is countable, the set of strictly positive rational numbers is countable. This can then be extended to show that the set of all rational numbers, including negative and zero, is countable. Another method mentioned is using H. L. Royden's method of showing countability by showing that the set is the range of a sequence. This can be achieved by defining a function f: Q+ to N*N*N such that f(n/m) = (n,m, gcd
  • #1
radou
Homework Helper
3,149
8
Is this proof OK?.. Thanks in advance.

So, we have to proove that the set Q of all rational numbers is countable.
Let's first look at strictly positive rational numbers. We can form the sets
[tex]S_{i}=\left\{s_{i1}, s_{i2}, \dots \right\}=\left\{\frac{1}{i}, \frac{2}{i}, \dots \right\}[/tex]. The union of these sets equals the set of strictly positive rational numbers. Now, we automatically know that some rational number [tex]\frac{k}{l}[/tex] is an element of the set [tex]S_{l}[/tex], and, since there is a 1-1 mapping between every set [tex]S_{i}[/tex] and the set of natural numbers N, we conclude [tex]s_{lk}=\frac{k}{l} \in S_{l}[/tex]. Now, since [tex]f(k, l) = \frac{k}{l}[/tex] is a 1-1 mapping defined on [tex]N\times N[/tex], and since [tex]N\times N[/tex] is countable, we conclude that the set of all strictly positive rational numbers is countable. Further on, there obviously exists a 1-1 mapping between this set and the set of all strictly negative rational numbers. Hence, the set of all strictly negative rational numbers
is countable, too. So, the union of the set of strictly positive, strictly negativerational numbers, and the set containing only zero {0}, is countable, since a finite or countable union of a finite or countable family of finite or countablesets is finite or countable.

P.S. Sorry the thread appeared twice, but I had some posting problems (as well as editing problems, logging on problems, etc.. contacted admin. )
 
Last edited:
Physics news on Phys.org
  • #2
What about f(1, 2) and f(2, 4)? I don't think f is one-to-one.
 
  • #3
JP is right: your sets Si are not disjoint so, in order to pass from an injective function from each Si to Q, more is needed: you must define an equivalence relation in their union, and then check that you can define f in the equivalence classes.

But why not going the other way around? You have a natural injective function from N to each of the Si's, and Q is the countable union of these; from this you may conclude that Q is countable.
 
  • #4
What about the H. L. Royden method of showing countability, showing that the set is the range of a sequence?
 
  • #5
OK , you may use f : Q+ to N*N*N such that f(n\m)=(n,m,gcd(n,m))this is an embedding of Q+ in countable set
 
Last edited:

What does it mean for something to be "countable"?

Being countable means that there exists a one-to-one correspondence between the elements of a set and the natural numbers (1, 2, 3, ...). Essentially, it means that the set can be put into a list and each element can be assigned a unique number.

How do you prove that Q (the set of rational numbers) is countable?

The standard proof for showing that Q is countable involves constructing a listing of all the rational numbers in a specific order. This can be done by organizing them into a grid pattern and then "snaking" through the grid, assigning a unique number to each rational number. This shows that every rational number can be mapped to a unique natural number, proving that Q is countable.

Why is it important to prove that Q is countable?

Proving that Q is countable is important because it is a fundamental result in mathematics and has important implications for other areas of study. It also helps us understand the concept of infinity and the different types of infinity that exist.

Can you give an example of a set that is not countable?

Yes, the set of real numbers (R) is an example of a set that is not countable. This is because there is no way to list all the real numbers in a systematic way, and it has been proven that there is no one-to-one correspondence between the real numbers and the natural numbers.

Are there any practical applications of proving that Q is countable?

Yes, the concept of countability is used in various fields such as computer science, statistics, and physics. For example, in computer science, countability is important for understanding the efficiency and complexity of algorithms. In statistics, it is used to analyze and interpret data. In physics, it helps in understanding the concept of discrete versus continuous systems.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
884
  • Set Theory, Logic, Probability, Statistics
Replies
16
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
2
Replies
55
Views
4K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
455
Back
Top