Why do we run in diagonals when proving that $mathbb{Q}$ is countable?
$begingroup$
Why do we index the elements like this
but not finishing the 1/x elements and then going through 2/x then 3/x...
discrete-mathematics elementary-set-theory rational-numbers
edited 13 hours ago
user21820
39.4k543155
asked 14 hours ago
stackmodernstackmodern
412
New contributor
stackmodern is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
|
show 5 more comments
$begingroup$
Why do we index the elements like this
but not finishing the 1/x elements and then going through 2/x then 3/x...
discrete-mathematics elementary-set-theory rational-numbers
edited 13 hours ago
user21820
39.4k543155
asked 14 hours ago
stackmodernstackmodern
412
New contributor
stackmodern is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
2
$begingroup$
If you tried to "finish" the $1/x$ elements, then you would have already used up your whole list, without a chance to list fractions like $2/3$, $2/5$, etc. You have to take a bit at a time from each column.
$endgroup$
– Joppy
14 hours ago
2
$begingroup$
This is not really an answer to your question, so I am leaving it as a comment, but I think it is still useful to point out: the real "explanation" of why we aren't doing that is simply because 1) we don't have to(!), we can choose whatever way we like of going through the rationals, and 2) the way we chose here does the job we want it to do.
$endgroup$
– Will R
14 hours ago
3
$begingroup$
You can't "finish" the $frac{1}{x}$- elements, since there are infinitely many of them
$endgroup$
– Peter Melech
14 hours ago
1
$begingroup$
May be You want to use the fact that a countable union of countable sets is countable, but You would have to use a diagonal argument (or rather this sweeping method) to prove this!
$endgroup$
– Peter Melech
14 hours ago
1
$begingroup$
Think of the rational numbers as guests in Hilbert's Hotel. If you put $frac 1 1$ in room $1$, $frac 1 2$ in room $2$ and so on, putting $frac 1 n$ in room $n$, then which room number do you put $frac 2 1$ in ?
$endgroup$
– gandalf61
14 hours ago
|
show 5 more comments
$begingroup$
Why do we index the elements like this
but not finishing the 1/x elements and then going through 2/x then 3/x...
discrete-mathematics elementary-set-theory rational-numbers
edited 13 hours ago
user21820
39.4k543155
asked 14 hours ago
stackmodernstackmodern
412
New contributor
stackmodern is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Why do we index the elements like this
but not finishing the 1/x elements and then going through 2/x then 3/x...
discrete-mathematics elementary-set-theory rational-numbers
discrete-mathematics elementary-set-theory rational-numbers
edited 13 hours ago
user21820
39.4k543155
asked 14 hours ago
stackmodernstackmodern
412
New contributor
stackmodern is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 13 hours ago
user21820
39.4k543155
asked 14 hours ago
stackmodernstackmodern
412
New contributor
stackmodern is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 13 hours ago
user21820
39.4k543155
edited 13 hours ago
user21820
39.4k543155
edited 13 hours ago
user21820
39.4k543155
39.4k543155
asked 14 hours ago
stackmodernstackmodern
412
New contributor
stackmodern is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 14 hours ago
stackmodernstackmodern
412
asked 14 hours ago
stackmodernstackmodern
412
412
New contributor
stackmodern is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
stackmodern is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
stackmodern is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
2
$begingroup$
If you tried to "finish" the $1/x$ elements, then you would have already used up your whole list, without a chance to list fractions like $2/3$, $2/5$, etc. You have to take a bit at a time from each column.
$endgroup$
– Joppy
14 hours ago
2
$begingroup$
This is not really an answer to your question, so I am leaving it as a comment, but I think it is still useful to point out: the real "explanation" of why we aren't doing that is simply because 1) we don't have to(!), we can choose whatever way we like of going through the rationals, and 2) the way we chose here does the job we want it to do.
$endgroup$
– Will R
14 hours ago
3
$begingroup$
You can't "finish" the $frac{1}{x}$- elements, since there are infinitely many of them
$endgroup$
– Peter Melech
14 hours ago
1
$begingroup$
May be You want to use the fact that a countable union of countable sets is countable, but You would have to use a diagonal argument (or rather this sweeping method) to prove this!
$endgroup$
– Peter Melech
14 hours ago
1
$begingroup$
Think of the rational numbers as guests in Hilbert's Hotel. If you put $frac 1 1$ in room $1$, $frac 1 2$ in room $2$ and so on, putting $frac 1 n$ in room $n$, then which room number do you put $frac 2 1$ in ?
$endgroup$
– gandalf61
14 hours ago
|
show 5 more comments
2
$begingroup$
If you tried to "finish" the $1/x$ elements, then you would have already used up your whole list, without a chance to list fractions like $2/3$, $2/5$, etc. You have to take a bit at a time from each column.
$endgroup$
– Joppy
14 hours ago
2
$begingroup$
This is not really an answer to your question, so I am leaving it as a comment, but I think it is still useful to point out: the real "explanation" of why we aren't doing that is simply because 1) we don't have to(!), we can choose whatever way we like of going through the rationals, and 2) the way we chose here does the job we want it to do.
$endgroup$
– Will R
14 hours ago
3
$begingroup$
You can't "finish" the $frac{1}{x}$- elements, since there are infinitely many of them
$endgroup$
– Peter Melech
14 hours ago
1
$begingroup$
May be You want to use the fact that a countable union of countable sets is countable, but You would have to use a diagonal argument (or rather this sweeping method) to prove this!
$endgroup$
– Peter Melech
14 hours ago
1
$begingroup$
Think of the rational numbers as guests in Hilbert's Hotel. If you put $frac 1 1$ in room $1$, $frac 1 2$ in room $2$ and so on, putting $frac 1 n$ in room $n$, then which room number do you put $frac 2 1$ in ?
$endgroup$
– gandalf61
14 hours ago
2
2
$begingroup$
If you tried to "finish" the $1/x$ elements, then you would have already used up your whole list, without a chance to list fractions like $2/3$, $2/5$, etc. You have to take a bit at a time from each column.
$endgroup$
– Joppy
14 hours ago
$begingroup$
If you tried to "finish" the $1/x$ elements, then you would have already used up your whole list, without a chance to list fractions like $2/3$, $2/5$, etc. You have to take a bit at a time from each column.
$endgroup$
– Joppy
14 hours ago
2
2
$begingroup$
This is not really an answer to your question, so I am leaving it as a comment, but I think it is still useful to point out: the real "explanation" of why we aren't doing that is simply because 1) we don't have to(!), we can choose whatever way we like of going through the rationals, and 2) the way we chose here does the job we want it to do.
$endgroup$
– Will R
14 hours ago
$begingroup$
This is not really an answer to your question, so I am leaving it as a comment, but I think it is still useful to point out: the real "explanation" of why we aren't doing that is simply because 1) we don't have to(!), we can choose whatever way we like of going through the rationals, and 2) the way we chose here does the job we want it to do.
$endgroup$
– Will R
14 hours ago
3
3
$begingroup$
You can't "finish" the $frac{1}{x}$- elements, since there are infinitely many of them
$endgroup$
– Peter Melech
14 hours ago
$begingroup$
You can't "finish" the $frac{1}{x}$- elements, since there are infinitely many of them
$endgroup$
– Peter Melech
14 hours ago
1
1
$begingroup$
May be You want to use the fact that a countable union of countable sets is countable, but You would have to use a diagonal argument (or rather this sweeping method) to prove this!
$endgroup$
– Peter Melech
14 hours ago
$begingroup$
May be You want to use the fact that a countable union of countable sets is countable, but You would have to use a diagonal argument (or rather this sweeping method) to prove this!
$endgroup$
– Peter Melech
14 hours ago
1
1
$begingroup$
Think of the rational numbers as guests in Hilbert's Hotel. If you put $frac 1 1$ in room $1$, $frac 1 2$ in room $2$ and so on, putting $frac 1 n$ in room $n$, then which room number do you put $frac 2 1$ in ?
$endgroup$
– gandalf61
14 hours ago
$begingroup$
Think of the rational numbers as guests in Hilbert's Hotel. If you put $frac 1 1$ in room $1$, $frac 1 2$ in room $2$ and so on, putting $frac 1 n$ in room $n$, then which room number do you put $frac 2 1$ in ?
$endgroup$
– gandalf61
14 hours ago
|
show 5 more comments
2 Answers
2
active
oldest
votes
$begingroup$
Whatever method you choose of indexing the rationals, it has to satisfy the following basic property: for every rational number $x/y,$ there must be some positive integer $n$ such that $x/y$ is indexed by $n$ (slightly formally: there must exist $ninmathbb{N}$ such that $nmapsto x/y$).
Let's attempt what you are describing. You are saying that we should start with $1/1,$ then go to $1/2,$ then $1/3,$ and so on; "and then" move on to $2/1,$ $2/2,$ etc.
Here's my problem with that. The indexing procedure you are describing takes each positive integer $n$ and maps it to $1/n$: $1$ maps to $1/1,$ $2$ maps to $1/2,$ and so on. So, here's my question to you: under your procedure, which positive number $n$ indexes $2/1$?
Note, as I said in the first paragraph, that in order for your procedure to be a proper procedure, there must be some value of $n$ so that $2/1$ is indexed by $n.$ You claim that your procedure is a proper indexing procedure; now you have to tell me what the value of $n$ is.
I'm sure that if you meditate on this you will see what the problem is. There is no such value of $n,$ so what you are attempting to do simply will not work; your procedure does not get through all the rationals, it only ever goes through the first row of the table. This is what people mean in the comments when they say that you "run out" of integers.
answered 14 hours ago
Will RWill R
6,69731429
$endgroup$
$begingroup$
This makes everything clear. Thank you for this answer.
$endgroup$
– stackmodern
14 hours ago
$begingroup$
@stackmodern: If you think your question is answered, then don't forget to click the tick to accept the answer you think is best.
$endgroup$
– Will R
9 hours ago
add a comment |
$begingroup$
Simply because you cannot "finish" the elements $dfrac1x$, and you would never index $dfrac2x$.
answered 14 hours ago
Yves DaoustYves Daoust
130k676229
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
stackmodern is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3148066%2fwhy-do-we-run-in-diagonals-when-proving-that-mathbbq-is-countable%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Whatever method you choose of indexing the rationals, it has to satisfy the following basic property: for every rational number $x/y,$ there must be some positive integer $n$ such that $x/y$ is indexed by $n$ (slightly formally: there must exist $ninmathbb{N}$ such that $nmapsto x/y$).
Let's attempt what you are describing. You are saying that we should start with $1/1,$ then go to $1/2,$ then $1/3,$ and so on; "and then" move on to $2/1,$ $2/2,$ etc.
Here's my problem with that. The indexing procedure you are describing takes each positive integer $n$ and maps it to $1/n$: $1$ maps to $1/1,$ $2$ maps to $1/2,$ and so on. So, here's my question to you: under your procedure, which positive number $n$ indexes $2/1$?
Note, as I said in the first paragraph, that in order for your procedure to be a proper procedure, there must be some value of $n$ so that $2/1$ is indexed by $n.$ You claim that your procedure is a proper indexing procedure; now you have to tell me what the value of $n$ is.
I'm sure that if you meditate on this you will see what the problem is. There is no such value of $n,$ so what you are attempting to do simply will not work; your procedure does not get through all the rationals, it only ever goes through the first row of the table. This is what people mean in the comments when they say that you "run out" of integers.
answered 14 hours ago
Will RWill R
6,69731429
$endgroup$
$begingroup$
This makes everything clear. Thank you for this answer.
$endgroup$
– stackmodern
14 hours ago
$begingroup$
@stackmodern: If you think your question is answered, then don't forget to click the tick to accept the answer you think is best.
$endgroup$
– Will R
9 hours ago
add a comment |
$begingroup$
Whatever method you choose of indexing the rationals, it has to satisfy the following basic property: for every rational number $x/y,$ there must be some positive integer $n$ such that $x/y$ is indexed by $n$ (slightly formally: there must exist $ninmathbb{N}$ such that $nmapsto x/y$).
Let's attempt what you are describing. You are saying that we should start with $1/1,$ then go to $1/2,$ then $1/3,$ and so on; "and then" move on to $2/1,$ $2/2,$ etc.
Here's my problem with that. The indexing procedure you are describing takes each positive integer $n$ and maps it to $1/n$: $1$ maps to $1/1,$ $2$ maps to $1/2,$ and so on. So, here's my question to you: under your procedure, which positive number $n$ indexes $2/1$?
Note, as I said in the first paragraph, that in order for your procedure to be a proper procedure, there must be some value of $n$ so that $2/1$ is indexed by $n.$ You claim that your procedure is a proper indexing procedure; now you have to tell me what the value of $n$ is.
I'm sure that if you meditate on this you will see what the problem is. There is no such value of $n,$ so what you are attempting to do simply will not work; your procedure does not get through all the rationals, it only ever goes through the first row of the table. This is what people mean in the comments when they say that you "run out" of integers.
answered 14 hours ago
Will RWill R
6,69731429
$endgroup$
$begingroup$
This makes everything clear. Thank you for this answer.
$endgroup$
– stackmodern
14 hours ago
$begingroup$
@stackmodern: If you think your question is answered, then don't forget to click the tick to accept the answer you think is best.
$endgroup$
– Will R
9 hours ago
add a comment |
$begingroup$
Whatever method you choose of indexing the rationals, it has to satisfy the following basic property: for every rational number $x/y,$ there must be some positive integer $n$ such that $x/y$ is indexed by $n$ (slightly formally: there must exist $ninmathbb{N}$ such that $nmapsto x/y$).
Let's attempt what you are describing. You are saying that we should start with $1/1,$ then go to $1/2,$ then $1/3,$ and so on; "and then" move on to $2/1,$ $2/2,$ etc.
Here's my problem with that. The indexing procedure you are describing takes each positive integer $n$ and maps it to $1/n$: $1$ maps to $1/1,$ $2$ maps to $1/2,$ and so on. So, here's my question to you: under your procedure, which positive number $n$ indexes $2/1$?
Note, as I said in the first paragraph, that in order for your procedure to be a proper procedure, there must be some value of $n$ so that $2/1$ is indexed by $n.$ You claim that your procedure is a proper indexing procedure; now you have to tell me what the value of $n$ is.
I'm sure that if you meditate on this you will see what the problem is. There is no such value of $n,$ so what you are attempting to do simply will not work; your procedure does not get through all the rationals, it only ever goes through the first row of the table. This is what people mean in the comments when they say that you "run out" of integers.
answered 14 hours ago
Will RWill R
6,69731429
$endgroup$
Whatever method you choose of indexing the rationals, it has to satisfy the following basic property: for every rational number $x/y,$ there must be some positive integer $n$ such that $x/y$ is indexed by $n$ (slightly formally: there must exist $ninmathbb{N}$ such that $nmapsto x/y$).
Let's attempt what you are describing. You are saying that we should start with $1/1,$ then go to $1/2,$ then $1/3,$ and so on; "and then" move on to $2/1,$ $2/2,$ etc.
Here's my problem with that. The indexing procedure you are describing takes each positive integer $n$ and maps it to $1/n$: $1$ maps to $1/1,$ $2$ maps to $1/2,$ and so on. So, here's my question to you: under your procedure, which positive number $n$ indexes $2/1$?
Note, as I said in the first paragraph, that in order for your procedure to be a proper procedure, there must be some value of $n$ so that $2/1$ is indexed by $n.$ You claim that your procedure is a proper indexing procedure; now you have to tell me what the value of $n$ is.
I'm sure that if you meditate on this you will see what the problem is. There is no such value of $n,$ so what you are attempting to do simply will not work; your procedure does not get through all the rationals, it only ever goes through the first row of the table. This is what people mean in the comments when they say that you "run out" of integers.
answered 14 hours ago
Will RWill R
6,69731429
answered 14 hours ago
Will RWill R
6,69731429
answered 14 hours ago
Will RWill R
6,69731429
answered 14 hours ago
Will RWill R
6,69731429
6,69731429
$begingroup$
This makes everything clear. Thank you for this answer.
$endgroup$
– stackmodern
14 hours ago
$begingroup$
@stackmodern: If you think your question is answered, then don't forget to click the tick to accept the answer you think is best.
$endgroup$
– Will R
9 hours ago
add a comment |
$begingroup$
This makes everything clear. Thank you for this answer.
$endgroup$
– stackmodern
14 hours ago
$begingroup$
@stackmodern: If you think your question is answered, then don't forget to click the tick to accept the answer you think is best.
$endgroup$
– Will R
9 hours ago
$begingroup$
This makes everything clear. Thank you for this answer.
$endgroup$
– stackmodern
14 hours ago
$begingroup$
This makes everything clear. Thank you for this answer.
$endgroup$
– stackmodern
14 hours ago
$begingroup$
@stackmodern: If you think your question is answered, then don't forget to click the tick to accept the answer you think is best.
$endgroup$
– Will R
9 hours ago
$begingroup$
@stackmodern: If you think your question is answered, then don't forget to click the tick to accept the answer you think is best.
$endgroup$
– Will R
9 hours ago
add a comment |
$begingroup$
Simply because you cannot "finish" the elements $dfrac1x$, and you would never index $dfrac2x$.
answered 14 hours ago
Yves DaoustYves Daoust
130k676229
$endgroup$
add a comment |
$begingroup$
Simply because you cannot "finish" the elements $dfrac1x$, and you would never index $dfrac2x$.
answered 14 hours ago
Yves DaoustYves Daoust
130k676229
$endgroup$
add a comment |
$begingroup$
Simply because you cannot "finish" the elements $dfrac1x$, and you would never index $dfrac2x$.
answered 14 hours ago
Yves DaoustYves Daoust
130k676229
$endgroup$
Simply because you cannot "finish" the elements $dfrac1x$, and you would never index $dfrac2x$.
answered 14 hours ago
Yves DaoustYves Daoust
130k676229
answered 14 hours ago
Yves DaoustYves Daoust
130k676229
answered 14 hours ago
Yves DaoustYves Daoust
130k676229
answered 14 hours ago
Yves DaoustYves Daoust
130k676229
130k676229
add a comment |
add a comment |
stackmodern is a new contributor. Be nice, and check out our Code of Conduct.
stackmodern is a new contributor. Be nice, and check out our Code of Conduct.
stackmodern is a new contributor. Be nice, and check out our Code of Conduct.
stackmodern is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3148066%2fwhy-do-we-run-in-diagonals-when-proving-that-mathbbq-is-countable%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
$begingroup$
If you tried to "finish" the $1/x$ elements, then you would have already used up your whole list, without a chance to list fractions like $2/3$, $2/5$, etc. You have to take a bit at a time from each column.
$endgroup$
– Joppy
14 hours ago
2
$begingroup$
This is not really an answer to your question, so I am leaving it as a comment, but I think it is still useful to point out: the real "explanation" of why we aren't doing that is simply because 1) we don't have to(!), we can choose whatever way we like of going through the rationals, and 2) the way we chose here does the job we want it to do.
$endgroup$
– Will R
14 hours ago
3
$begingroup$
You can't "finish" the $frac{1}{x}$- elements, since there are infinitely many of them
$endgroup$
– Peter Melech
14 hours ago
1
$begingroup$
May be You want to use the fact that a countable union of countable sets is countable, but You would have to use a diagonal argument (or rather this sweeping method) to prove this!
$endgroup$
– Peter Melech
14 hours ago
1
$begingroup$
Think of the rational numbers as guests in Hilbert's Hotel. If you put $frac 1 1$ in room $1$, $frac 1 2$ in room $2$ and so on, putting $frac 1 n$ in room $n$, then which room number do you put $frac 2 1$ in ?
$endgroup$
– gandalf61
14 hours ago