Proof that Q is countable

  • Thread starter radou
  • Start date
  • #1
radou
Homework Helper
3,134
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:

Answers and Replies

  • #2
Jack Pullen
3
0
What about f(1, 2) and f(2, 4)? I don't think f is one-to-one.
 
  • #3
JSuarez
402
1
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
Jack Pullen
3
0
What about the H. L. Royden method of showing countability, showing that the set is the range of a sequence?
 
  • #5
hamzah
1
0
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:

Suggested for: Proof that Q is countable

  • Last Post
4
Replies
126
Views
4K
Replies
10
Views
1K
Replies
1
Views
2K
  • Last Post
Replies
12
Views
1K
  • Last Post
Replies
22
Views
1K
  • Last Post
Replies
11
Views
2K
MHB Set proof
  • Last Post
Replies
5
Views
656
  • Last Post
Replies
1
Views
316
  • Last Post
Replies
10
Views
844
Top