Show that $mathbb{Q}times mathbb{Q}$ is denumerable [duplicate]
$begingroup$
This question already has an answer here:
Is $mathbb Q times mathbb Q $ a denumerable set? [duplicate]
1 answer
Cartesian Product of Two Countable Sets is Countable [closed]
3 answers
I am new to functions and relations, and with some concepts I am not so familiar. I have a question in an homework:
Show that $mathbb{Q} timesmathbb{Q}$ is denumerable.
From what I understood, denumerable means that it is infinitively countable. There are some posts on the web about this topic, but I am still not understanding their explanation, maybe because they are not explained so easily (for me).
From what I understood, a set is denumerable if there's a relation with the natural numbers (but I am still not understanding what is this relation).
I have heard also about equinumerous sets (contain a bijective function = onto + one-to-one function), but I cannot relate this information with the problem to try to solve it.
functions discrete-mathematics
asked Dec 19 '14 at 1:20
nbronbro
2,41653173
$endgroup$
marked as duplicate by Ilmari Karonen, Thomas Andrews, Przemysław Scherwentke, Moishe Cohen, Ivo Terek Dec 19 '14 at 2:18
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
|
show 6 more comments
$begingroup$
This question already has an answer here:
Is $mathbb Q times mathbb Q $ a denumerable set? [duplicate]
1 answer
Cartesian Product of Two Countable Sets is Countable [closed]
3 answers
I am new to functions and relations, and with some concepts I am not so familiar. I have a question in an homework:
Show that $mathbb{Q} timesmathbb{Q}$ is denumerable.
From what I understood, denumerable means that it is infinitively countable. There are some posts on the web about this topic, but I am still not understanding their explanation, maybe because they are not explained so easily (for me).
From what I understood, a set is denumerable if there's a relation with the natural numbers (but I am still not understanding what is this relation).
I have heard also about equinumerous sets (contain a bijective function = onto + one-to-one function), but I cannot relate this information with the problem to try to solve it.
functions discrete-mathematics
asked Dec 19 '14 at 1:20
nbronbro
2,41653173
$endgroup$
marked as duplicate by Ilmari Karonen, Thomas Andrews, Przemysław Scherwentke, Moishe Cohen, Ivo Terek Dec 19 '14 at 2:18
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
$begingroup$
Do you understand the proof that $Bbb Q$ is denumerable?
$endgroup$
– David
Dec 19 '14 at 1:22
$begingroup$
@David I think the only think I understood is the visual representation: $x$ and $y$ contain respectively the $numerator$ and $denominator$...
$endgroup$
– nbro
Dec 19 '14 at 1:24
$begingroup$
If you know that $mathbb Ntimes mathbb N$ is denumarable, and $mathbb Q$ is denumerable, you can prove this very quickly.
$endgroup$
– Thomas Andrews
Dec 19 '14 at 1:26
1
$begingroup$
Here is a proof that $Bbb Q$ is denumerable. I suggest you make absolutely sure you understand this, then come back to your question.
$endgroup$
– David
Dec 19 '14 at 1:27
1
$begingroup$
"From what I understood, a set is denumerable if there's a relation with the natural numbers (but I am still not understanding what is this relation)." A set is denumerable if there is a bijection between the set and the natural numbers. (That is, a set is denumerable if it is equinumerous with $mathbb{N}$.)
$endgroup$
– Trold
Dec 19 '14 at 1:29
|
show 6 more comments
$begingroup$
This question already has an answer here:
Is $mathbb Q times mathbb Q $ a denumerable set? [duplicate]
1 answer
Cartesian Product of Two Countable Sets is Countable [closed]
3 answers
I am new to functions and relations, and with some concepts I am not so familiar. I have a question in an homework:
Show that $mathbb{Q} timesmathbb{Q}$ is denumerable.
From what I understood, denumerable means that it is infinitively countable. There are some posts on the web about this topic, but I am still not understanding their explanation, maybe because they are not explained so easily (for me).
From what I understood, a set is denumerable if there's a relation with the natural numbers (but I am still not understanding what is this relation).
I have heard also about equinumerous sets (contain a bijective function = onto + one-to-one function), but I cannot relate this information with the problem to try to solve it.
functions discrete-mathematics
asked Dec 19 '14 at 1:20
nbronbro
2,41653173
$endgroup$
This question already has an answer here:
Is $mathbb Q times mathbb Q $ a denumerable set? [duplicate]
1 answer
Cartesian Product of Two Countable Sets is Countable [closed]
3 answers
I am new to functions and relations, and with some concepts I am not so familiar. I have a question in an homework:
Show that $mathbb{Q} timesmathbb{Q}$ is denumerable.
From what I understood, denumerable means that it is infinitively countable. There are some posts on the web about this topic, but I am still not understanding their explanation, maybe because they are not explained so easily (for me).
From what I understood, a set is denumerable if there's a relation with the natural numbers (but I am still not understanding what is this relation).
I have heard also about equinumerous sets (contain a bijective function = onto + one-to-one function), but I cannot relate this information with the problem to try to solve it.
This question already has an answer here:
Is $mathbb Q times mathbb Q $ a denumerable set? [duplicate]
1 answer
Cartesian Product of Two Countable Sets is Countable [closed]
3 answers
functions discrete-mathematics
functions discrete-mathematics
asked Dec 19 '14 at 1:20
nbronbro
2,41653173
asked Dec 19 '14 at 1:20
nbronbro
2,41653173
edited Dec 16 '18 at 14:20
nbro
asked Dec 19 '14 at 1:20
nbronbro
2,41653173
asked Dec 19 '14 at 1:20
nbronbro
2,41653173
asked Dec 19 '14 at 1:20
nbronbro
2,41653173
2,41653173
marked as duplicate by Ilmari Karonen, Thomas Andrews, Przemysław Scherwentke, Moishe Cohen, Ivo Terek Dec 19 '14 at 2:18
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Ilmari Karonen, Thomas Andrews, Przemysław Scherwentke, Moishe Cohen, Ivo Terek Dec 19 '14 at 2:18
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
$begingroup$
Do you understand the proof that $Bbb Q$ is denumerable?
$endgroup$
– David
Dec 19 '14 at 1:22
$begingroup$
@David I think the only think I understood is the visual representation: $x$ and $y$ contain respectively the $numerator$ and $denominator$...
$endgroup$
– nbro
Dec 19 '14 at 1:24
$begingroup$
If you know that $mathbb Ntimes mathbb N$ is denumarable, and $mathbb Q$ is denumerable, you can prove this very quickly.
$endgroup$
– Thomas Andrews
Dec 19 '14 at 1:26
1
$begingroup$
Here is a proof that $Bbb Q$ is denumerable. I suggest you make absolutely sure you understand this, then come back to your question.
$endgroup$
– David
Dec 19 '14 at 1:27
1
$begingroup$
"From what I understood, a set is denumerable if there's a relation with the natural numbers (but I am still not understanding what is this relation)." A set is denumerable if there is a bijection between the set and the natural numbers. (That is, a set is denumerable if it is equinumerous with $mathbb{N}$.)
$endgroup$
– Trold
Dec 19 '14 at 1:29
|
show 6 more comments
1
$begingroup$
Do you understand the proof that $Bbb Q$ is denumerable?
$endgroup$
– David
Dec 19 '14 at 1:22
$begingroup$
@David I think the only think I understood is the visual representation: $x$ and $y$ contain respectively the $numerator$ and $denominator$...
$endgroup$
– nbro
Dec 19 '14 at 1:24
$begingroup$
If you know that $mathbb Ntimes mathbb N$ is denumarable, and $mathbb Q$ is denumerable, you can prove this very quickly.
$endgroup$
– Thomas Andrews
Dec 19 '14 at 1:26
1
$begingroup$
Here is a proof that $Bbb Q$ is denumerable. I suggest you make absolutely sure you understand this, then come back to your question.
$endgroup$
– David
Dec 19 '14 at 1:27
1
$begingroup$
"From what I understood, a set is denumerable if there's a relation with the natural numbers (but I am still not understanding what is this relation)." A set is denumerable if there is a bijection between the set and the natural numbers. (That is, a set is denumerable if it is equinumerous with $mathbb{N}$.)
$endgroup$
– Trold
Dec 19 '14 at 1:29
1
1
$begingroup$
Do you understand the proof that $Bbb Q$ is denumerable?
$endgroup$
– David
Dec 19 '14 at 1:22
$begingroup$
Do you understand the proof that $Bbb Q$ is denumerable?
$endgroup$
– David
Dec 19 '14 at 1:22
$begingroup$
@David I think the only think I understood is the visual representation: $x$ and $y$ contain respectively the $numerator$ and $denominator$...
$endgroup$
– nbro
Dec 19 '14 at 1:24
$begingroup$
@David I think the only think I understood is the visual representation: $x$ and $y$ contain respectively the $numerator$ and $denominator$...
$endgroup$
– nbro
Dec 19 '14 at 1:24
$begingroup$
If you know that $mathbb Ntimes mathbb N$ is denumarable, and $mathbb Q$ is denumerable, you can prove this very quickly.
$endgroup$
– Thomas Andrews
Dec 19 '14 at 1:26
$begingroup$
If you know that $mathbb Ntimes mathbb N$ is denumarable, and $mathbb Q$ is denumerable, you can prove this very quickly.
$endgroup$
– Thomas Andrews
Dec 19 '14 at 1:26
1
1
$begingroup$
Here is a proof that $Bbb Q$ is denumerable. I suggest you make absolutely sure you understand this, then come back to your question.
$endgroup$
– David
Dec 19 '14 at 1:27
$begingroup$
Here is a proof that $Bbb Q$ is denumerable. I suggest you make absolutely sure you understand this, then come back to your question.
$endgroup$
– David
Dec 19 '14 at 1:27
1
1
$begingroup$
"From what I understood, a set is denumerable if there's a relation with the natural numbers (but I am still not understanding what is this relation)." A set is denumerable if there is a bijection between the set and the natural numbers. (That is, a set is denumerable if it is equinumerous with $mathbb{N}$.)
$endgroup$
– Trold
Dec 19 '14 at 1:29
$begingroup$
"From what I understood, a set is denumerable if there's a relation with the natural numbers (but I am still not understanding what is this relation)." A set is denumerable if there is a bijection between the set and the natural numbers. (That is, a set is denumerable if it is equinumerous with $mathbb{N}$.)
$endgroup$
– Trold
Dec 19 '14 at 1:29
|
show 6 more comments
2 Answers
2
active
oldest
votes
$begingroup$
Since you already know that the rationals are denumerable, they can be enumerated as $r_1,r_2,r_3,ldots,$. Therefore all pairs of rationals can be arranged in a table
$$defp#1#2{(r_{#1},r_{#2})}
matrix{p11&p12&p13&cdotscr p21&p22&p23&cdotscr
p31&p32&p33&cdotscr vdots&vdots&vdotscr}$$
This table can then be turned into a list diagonal by diagonal, exactly as in the standard proof that $Bbb Q$ is denumerable. Therefore $Bbb Qtimes Bbb Q$ is denumerable.
answered Dec 19 '14 at 1:42
DavidDavid
69k667130
$endgroup$
$begingroup$
By pairs of rationals, you mean, for example, $frac{1}{2}, frac{1}{2}$, resulted by the cartesian product of $mathbb{Q} times mathbb{Q}$?
$endgroup$
– nbro
Dec 19 '14 at 1:48
$begingroup$
Yes, these are pairs of rationals. The important thing to note is that it's really exactly the same as the argument you have seen already.
$endgroup$
– David
Dec 19 '14 at 2:01
add a comment |
$begingroup$
The relation that's needed with the natural numbers $mathbb{N}$ has to be a 'bijection', which means a one-to-one correspondence. In practice, that means that a set $S$ is denumerable (or 'countable' as it's more often called) if you can define a scheme for labelling every element of the set with a natural number, so that no natural number is used more than once.
To show $mathbb{Q}times mathbb{Q}$ is denumerable I would proceed in two steps.
(1) prove that if a set $S$ is countable then $Stimes S$ is countable.
(2) show a bijection between $mathbb{Q}$ and $$mathbb{N}times mathbb{N}$
To prove (1), lay out all elements of $Stimes S$ in a grid that takes up one quarter of the number plane, such that the element $(S_i,S_j)$ takes up the grid point with coordinates $(i,j)$, where $S_i$ is the element that has been assigned label $i$. Then imagine a path that goes as follows:
(0,0), (1,0),(0,1),(0,2),(1,1),(2,0),(3,0),(2,1),(1,2),(0,3),(0,4),(1,3),(2,2),(3,1),(4,0),(5,0),(4,1)....
For any specified grid point, this zigzag path must eventually reach it, so we can label the elements of $Stimes S$ by how many steps along the zig-zag path one has to go to get to that point.
(2) Is easier. First prove that the signed integers $mathbb{Z}$ are countable, by the alternating path on the number line 0,1,-1,2,-2,3,-3,....
THen we know $mathbb{Q}$ is a subset of $mathbb{Z}timesmathbb{Z}$, since a rational number is defined as the ratio of two integers where the denominator is nonzero.
answered Dec 19 '14 at 1:37
Andrew KirkAndrew Kirk
18810
$endgroup$
$begingroup$
How do you handle fractions with the same value like $1/2$ and $2/4$? Or asked the other way round what rational is given by $(0,0)$? What by $(1,1)$?
$endgroup$
– mvw
Dec 19 '14 at 1:43
$begingroup$
One solution is to use the Schroder Bernstein THeorem, which says that if two sets each have an injection into the other, there is a bijection between them. Since S-B is lengthy to prove, a shorter approach is to look at the zigzag line that traverses the 2D grid of pairs of integers, allocating natural numbers to them as it goes. All we need do is change the allocation algorithm so that it allocates no number to a grid point if its second coordinate (the denominator) is zero, or if the ratio has already been covered by a previously labelled pair (eg (2,4) has been covered by (1,2) or (-1,-2))
$endgroup$
– Andrew Kirk
Dec 19 '14 at 11:02
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Since you already know that the rationals are denumerable, they can be enumerated as $r_1,r_2,r_3,ldots,$. Therefore all pairs of rationals can be arranged in a table
$$defp#1#2{(r_{#1},r_{#2})}
matrix{p11&p12&p13&cdotscr p21&p22&p23&cdotscr
p31&p32&p33&cdotscr vdots&vdots&vdotscr}$$
This table can then be turned into a list diagonal by diagonal, exactly as in the standard proof that $Bbb Q$ is denumerable. Therefore $Bbb Qtimes Bbb Q$ is denumerable.
answered Dec 19 '14 at 1:42
DavidDavid
69k667130
$endgroup$
$begingroup$
By pairs of rationals, you mean, for example, $frac{1}{2}, frac{1}{2}$, resulted by the cartesian product of $mathbb{Q} times mathbb{Q}$?
$endgroup$
– nbro
Dec 19 '14 at 1:48
$begingroup$
Yes, these are pairs of rationals. The important thing to note is that it's really exactly the same as the argument you have seen already.
$endgroup$
– David
Dec 19 '14 at 2:01
add a comment |
$begingroup$
Since you already know that the rationals are denumerable, they can be enumerated as $r_1,r_2,r_3,ldots,$. Therefore all pairs of rationals can be arranged in a table
$$defp#1#2{(r_{#1},r_{#2})}
matrix{p11&p12&p13&cdotscr p21&p22&p23&cdotscr
p31&p32&p33&cdotscr vdots&vdots&vdotscr}$$
This table can then be turned into a list diagonal by diagonal, exactly as in the standard proof that $Bbb Q$ is denumerable. Therefore $Bbb Qtimes Bbb Q$ is denumerable.
answered Dec 19 '14 at 1:42
DavidDavid
69k667130
$endgroup$
$begingroup$
By pairs of rationals, you mean, for example, $frac{1}{2}, frac{1}{2}$, resulted by the cartesian product of $mathbb{Q} times mathbb{Q}$?
$endgroup$
– nbro
Dec 19 '14 at 1:48
$begingroup$
Yes, these are pairs of rationals. The important thing to note is that it's really exactly the same as the argument you have seen already.
$endgroup$
– David
Dec 19 '14 at 2:01
add a comment |
$begingroup$
Since you already know that the rationals are denumerable, they can be enumerated as $r_1,r_2,r_3,ldots,$. Therefore all pairs of rationals can be arranged in a table
$$defp#1#2{(r_{#1},r_{#2})}
matrix{p11&p12&p13&cdotscr p21&p22&p23&cdotscr
p31&p32&p33&cdotscr vdots&vdots&vdotscr}$$
This table can then be turned into a list diagonal by diagonal, exactly as in the standard proof that $Bbb Q$ is denumerable. Therefore $Bbb Qtimes Bbb Q$ is denumerable.
answered Dec 19 '14 at 1:42
DavidDavid
69k667130
$endgroup$
Since you already know that the rationals are denumerable, they can be enumerated as $r_1,r_2,r_3,ldots,$. Therefore all pairs of rationals can be arranged in a table
$$defp#1#2{(r_{#1},r_{#2})}
matrix{p11&p12&p13&cdotscr p21&p22&p23&cdotscr
p31&p32&p33&cdotscr vdots&vdots&vdotscr}$$
This table can then be turned into a list diagonal by diagonal, exactly as in the standard proof that $Bbb Q$ is denumerable. Therefore $Bbb Qtimes Bbb Q$ is denumerable.
answered Dec 19 '14 at 1:42
DavidDavid
69k667130
answered Dec 19 '14 at 1:42
DavidDavid
69k667130
answered Dec 19 '14 at 1:42
DavidDavid
69k667130
answered Dec 19 '14 at 1:42
DavidDavid
69k667130
69k667130
$begingroup$
By pairs of rationals, you mean, for example, $frac{1}{2}, frac{1}{2}$, resulted by the cartesian product of $mathbb{Q} times mathbb{Q}$?
$endgroup$
– nbro
Dec 19 '14 at 1:48
$begingroup$
Yes, these are pairs of rationals. The important thing to note is that it's really exactly the same as the argument you have seen already.
$endgroup$
– David
Dec 19 '14 at 2:01
add a comment |
$begingroup$
By pairs of rationals, you mean, for example, $frac{1}{2}, frac{1}{2}$, resulted by the cartesian product of $mathbb{Q} times mathbb{Q}$?
$endgroup$
– nbro
Dec 19 '14 at 1:48
$begingroup$
Yes, these are pairs of rationals. The important thing to note is that it's really exactly the same as the argument you have seen already.
$endgroup$
– David
Dec 19 '14 at 2:01
$begingroup$
By pairs of rationals, you mean, for example, $frac{1}{2}, frac{1}{2}$, resulted by the cartesian product of $mathbb{Q} times mathbb{Q}$?
$endgroup$
– nbro
Dec 19 '14 at 1:48
$begingroup$
By pairs of rationals, you mean, for example, $frac{1}{2}, frac{1}{2}$, resulted by the cartesian product of $mathbb{Q} times mathbb{Q}$?
$endgroup$
– nbro
Dec 19 '14 at 1:48
$begingroup$
Yes, these are pairs of rationals. The important thing to note is that it's really exactly the same as the argument you have seen already.
$endgroup$
– David
Dec 19 '14 at 2:01
$begingroup$
Yes, these are pairs of rationals. The important thing to note is that it's really exactly the same as the argument you have seen already.
$endgroup$
– David
Dec 19 '14 at 2:01
add a comment |
$begingroup$
The relation that's needed with the natural numbers $mathbb{N}$ has to be a 'bijection', which means a one-to-one correspondence. In practice, that means that a set $S$ is denumerable (or 'countable' as it's more often called) if you can define a scheme for labelling every element of the set with a natural number, so that no natural number is used more than once.
To show $mathbb{Q}times mathbb{Q}$ is denumerable I would proceed in two steps.
(1) prove that if a set $S$ is countable then $Stimes S$ is countable.
(2) show a bijection between $mathbb{Q}$ and $$mathbb{N}times mathbb{N}$
To prove (1), lay out all elements of $Stimes S$ in a grid that takes up one quarter of the number plane, such that the element $(S_i,S_j)$ takes up the grid point with coordinates $(i,j)$, where $S_i$ is the element that has been assigned label $i$. Then imagine a path that goes as follows:
(0,0), (1,0),(0,1),(0,2),(1,1),(2,0),(3,0),(2,1),(1,2),(0,3),(0,4),(1,3),(2,2),(3,1),(4,0),(5,0),(4,1)....
For any specified grid point, this zigzag path must eventually reach it, so we can label the elements of $Stimes S$ by how many steps along the zig-zag path one has to go to get to that point.
(2) Is easier. First prove that the signed integers $mathbb{Z}$ are countable, by the alternating path on the number line 0,1,-1,2,-2,3,-3,....
THen we know $mathbb{Q}$ is a subset of $mathbb{Z}timesmathbb{Z}$, since a rational number is defined as the ratio of two integers where the denominator is nonzero.
answered Dec 19 '14 at 1:37
Andrew KirkAndrew Kirk
18810
$endgroup$
$begingroup$
How do you handle fractions with the same value like $1/2$ and $2/4$? Or asked the other way round what rational is given by $(0,0)$? What by $(1,1)$?
$endgroup$
– mvw
Dec 19 '14 at 1:43
$begingroup$
One solution is to use the Schroder Bernstein THeorem, which says that if two sets each have an injection into the other, there is a bijection between them. Since S-B is lengthy to prove, a shorter approach is to look at the zigzag line that traverses the 2D grid of pairs of integers, allocating natural numbers to them as it goes. All we need do is change the allocation algorithm so that it allocates no number to a grid point if its second coordinate (the denominator) is zero, or if the ratio has already been covered by a previously labelled pair (eg (2,4) has been covered by (1,2) or (-1,-2))
$endgroup$
– Andrew Kirk
Dec 19 '14 at 11:02
add a comment |
$begingroup$
The relation that's needed with the natural numbers $mathbb{N}$ has to be a 'bijection', which means a one-to-one correspondence. In practice, that means that a set $S$ is denumerable (or 'countable' as it's more often called) if you can define a scheme for labelling every element of the set with a natural number, so that no natural number is used more than once.
To show $mathbb{Q}times mathbb{Q}$ is denumerable I would proceed in two steps.
(1) prove that if a set $S$ is countable then $Stimes S$ is countable.
(2) show a bijection between $mathbb{Q}$ and $$mathbb{N}times mathbb{N}$
To prove (1), lay out all elements of $Stimes S$ in a grid that takes up one quarter of the number plane, such that the element $(S_i,S_j)$ takes up the grid point with coordinates $(i,j)$, where $S_i$ is the element that has been assigned label $i$. Then imagine a path that goes as follows:
(0,0), (1,0),(0,1),(0,2),(1,1),(2,0),(3,0),(2,1),(1,2),(0,3),(0,4),(1,3),(2,2),(3,1),(4,0),(5,0),(4,1)....
For any specified grid point, this zigzag path must eventually reach it, so we can label the elements of $Stimes S$ by how many steps along the zig-zag path one has to go to get to that point.
(2) Is easier. First prove that the signed integers $mathbb{Z}$ are countable, by the alternating path on the number line 0,1,-1,2,-2,3,-3,....
THen we know $mathbb{Q}$ is a subset of $mathbb{Z}timesmathbb{Z}$, since a rational number is defined as the ratio of two integers where the denominator is nonzero.
answered Dec 19 '14 at 1:37
Andrew KirkAndrew Kirk
18810
$endgroup$
$begingroup$
How do you handle fractions with the same value like $1/2$ and $2/4$? Or asked the other way round what rational is given by $(0,0)$? What by $(1,1)$?
$endgroup$
– mvw
Dec 19 '14 at 1:43
$begingroup$
One solution is to use the Schroder Bernstein THeorem, which says that if two sets each have an injection into the other, there is a bijection between them. Since S-B is lengthy to prove, a shorter approach is to look at the zigzag line that traverses the 2D grid of pairs of integers, allocating natural numbers to them as it goes. All we need do is change the allocation algorithm so that it allocates no number to a grid point if its second coordinate (the denominator) is zero, or if the ratio has already been covered by a previously labelled pair (eg (2,4) has been covered by (1,2) or (-1,-2))
$endgroup$
– Andrew Kirk
Dec 19 '14 at 11:02
add a comment |
$begingroup$
The relation that's needed with the natural numbers $mathbb{N}$ has to be a 'bijection', which means a one-to-one correspondence. In practice, that means that a set $S$ is denumerable (or 'countable' as it's more often called) if you can define a scheme for labelling every element of the set with a natural number, so that no natural number is used more than once.
To show $mathbb{Q}times mathbb{Q}$ is denumerable I would proceed in two steps.
(1) prove that if a set $S$ is countable then $Stimes S$ is countable.
(2) show a bijection between $mathbb{Q}$ and $$mathbb{N}times mathbb{N}$
To prove (1), lay out all elements of $Stimes S$ in a grid that takes up one quarter of the number plane, such that the element $(S_i,S_j)$ takes up the grid point with coordinates $(i,j)$, where $S_i$ is the element that has been assigned label $i$. Then imagine a path that goes as follows:
(0,0), (1,0),(0,1),(0,2),(1,1),(2,0),(3,0),(2,1),(1,2),(0,3),(0,4),(1,3),(2,2),(3,1),(4,0),(5,0),(4,1)....
For any specified grid point, this zigzag path must eventually reach it, so we can label the elements of $Stimes S$ by how many steps along the zig-zag path one has to go to get to that point.
(2) Is easier. First prove that the signed integers $mathbb{Z}$ are countable, by the alternating path on the number line 0,1,-1,2,-2,3,-3,....
THen we know $mathbb{Q}$ is a subset of $mathbb{Z}timesmathbb{Z}$, since a rational number is defined as the ratio of two integers where the denominator is nonzero.
answered Dec 19 '14 at 1:37
Andrew KirkAndrew Kirk
18810
$endgroup$
The relation that's needed with the natural numbers $mathbb{N}$ has to be a 'bijection', which means a one-to-one correspondence. In practice, that means that a set $S$ is denumerable (or 'countable' as it's more often called) if you can define a scheme for labelling every element of the set with a natural number, so that no natural number is used more than once.
To show $mathbb{Q}times mathbb{Q}$ is denumerable I would proceed in two steps.
(1) prove that if a set $S$ is countable then $Stimes S$ is countable.
(2) show a bijection between $mathbb{Q}$ and $$mathbb{N}times mathbb{N}$
To prove (1), lay out all elements of $Stimes S$ in a grid that takes up one quarter of the number plane, such that the element $(S_i,S_j)$ takes up the grid point with coordinates $(i,j)$, where $S_i$ is the element that has been assigned label $i$. Then imagine a path that goes as follows:
(0,0), (1,0),(0,1),(0,2),(1,1),(2,0),(3,0),(2,1),(1,2),(0,3),(0,4),(1,3),(2,2),(3,1),(4,0),(5,0),(4,1)....
For any specified grid point, this zigzag path must eventually reach it, so we can label the elements of $Stimes S$ by how many steps along the zig-zag path one has to go to get to that point.
(2) Is easier. First prove that the signed integers $mathbb{Z}$ are countable, by the alternating path on the number line 0,1,-1,2,-2,3,-3,....
THen we know $mathbb{Q}$ is a subset of $mathbb{Z}timesmathbb{Z}$, since a rational number is defined as the ratio of two integers where the denominator is nonzero.
answered Dec 19 '14 at 1:37
Andrew KirkAndrew Kirk
18810
answered Dec 19 '14 at 1:37
Andrew KirkAndrew Kirk
18810
answered Dec 19 '14 at 1:37
Andrew KirkAndrew Kirk
18810
answered Dec 19 '14 at 1:37
Andrew KirkAndrew Kirk
18810
18810
$begingroup$
How do you handle fractions with the same value like $1/2$ and $2/4$? Or asked the other way round what rational is given by $(0,0)$? What by $(1,1)$?
$endgroup$
– mvw
Dec 19 '14 at 1:43
$begingroup$
One solution is to use the Schroder Bernstein THeorem, which says that if two sets each have an injection into the other, there is a bijection between them. Since S-B is lengthy to prove, a shorter approach is to look at the zigzag line that traverses the 2D grid of pairs of integers, allocating natural numbers to them as it goes. All we need do is change the allocation algorithm so that it allocates no number to a grid point if its second coordinate (the denominator) is zero, or if the ratio has already been covered by a previously labelled pair (eg (2,4) has been covered by (1,2) or (-1,-2))
$endgroup$
– Andrew Kirk
Dec 19 '14 at 11:02
add a comment |
$begingroup$
How do you handle fractions with the same value like $1/2$ and $2/4$? Or asked the other way round what rational is given by $(0,0)$? What by $(1,1)$?
$endgroup$
– mvw
Dec 19 '14 at 1:43
$begingroup$
One solution is to use the Schroder Bernstein THeorem, which says that if two sets each have an injection into the other, there is a bijection between them. Since S-B is lengthy to prove, a shorter approach is to look at the zigzag line that traverses the 2D grid of pairs of integers, allocating natural numbers to them as it goes. All we need do is change the allocation algorithm so that it allocates no number to a grid point if its second coordinate (the denominator) is zero, or if the ratio has already been covered by a previously labelled pair (eg (2,4) has been covered by (1,2) or (-1,-2))
$endgroup$
– Andrew Kirk
Dec 19 '14 at 11:02
$begingroup$
How do you handle fractions with the same value like $1/2$ and $2/4$? Or asked the other way round what rational is given by $(0,0)$? What by $(1,1)$?
$endgroup$
– mvw
Dec 19 '14 at 1:43
$begingroup$
How do you handle fractions with the same value like $1/2$ and $2/4$? Or asked the other way round what rational is given by $(0,0)$? What by $(1,1)$?
$endgroup$
– mvw
Dec 19 '14 at 1:43
$begingroup$
One solution is to use the Schroder Bernstein THeorem, which says that if two sets each have an injection into the other, there is a bijection between them. Since S-B is lengthy to prove, a shorter approach is to look at the zigzag line that traverses the 2D grid of pairs of integers, allocating natural numbers to them as it goes. All we need do is change the allocation algorithm so that it allocates no number to a grid point if its second coordinate (the denominator) is zero, or if the ratio has already been covered by a previously labelled pair (eg (2,4) has been covered by (1,2) or (-1,-2))
$endgroup$
– Andrew Kirk
Dec 19 '14 at 11:02
$begingroup$
One solution is to use the Schroder Bernstein THeorem, which says that if two sets each have an injection into the other, there is a bijection between them. Since S-B is lengthy to prove, a shorter approach is to look at the zigzag line that traverses the 2D grid of pairs of integers, allocating natural numbers to them as it goes. All we need do is change the allocation algorithm so that it allocates no number to a grid point if its second coordinate (the denominator) is zero, or if the ratio has already been covered by a previously labelled pair (eg (2,4) has been covered by (1,2) or (-1,-2))
$endgroup$
– Andrew Kirk
Dec 19 '14 at 11:02
add a comment |
1
$begingroup$
Do you understand the proof that $Bbb Q$ is denumerable?
$endgroup$
– David
Dec 19 '14 at 1:22
$begingroup$
@David I think the only think I understood is the visual representation: $x$ and $y$ contain respectively the $numerator$ and $denominator$...
$endgroup$
– nbro
Dec 19 '14 at 1:24
$begingroup$
If you know that $mathbb Ntimes mathbb N$ is denumarable, and $mathbb Q$ is denumerable, you can prove this very quickly.
$endgroup$
– Thomas Andrews
Dec 19 '14 at 1:26
1
$begingroup$
Here is a proof that $Bbb Q$ is denumerable. I suggest you make absolutely sure you understand this, then come back to your question.
$endgroup$
– David
Dec 19 '14 at 1:27
1
$begingroup$
"From what I understood, a set is denumerable if there's a relation with the natural numbers (but I am still not understanding what is this relation)." A set is denumerable if there is a bijection between the set and the natural numbers. (That is, a set is denumerable if it is equinumerous with $mathbb{N}$.)
$endgroup$
– Trold
Dec 19 '14 at 1:29