Help proving there is a sequence of rational numbers
$begingroup$
I'm trying to prove the following:
Let $Bbb Q$ be the countable set of rational numbers and ${x_n}_{n=1}^infty$ be a sequence such that for every q $in$ $Bbb Q$ there is a $n in Bbb N$ with $x_n = q$. Prove that there is such a sequence ${x_n}$.
My initial thoughts for an attempt at a solution:
We know that $|Bbb Q| = |Bbb N|$ by the Cantor Theorem. Further, I can show that there is a bijection between $Bbb Q$ and $Bbb N$.
If I define ${x_n}_{n=1}^infty$ as some relation between $(p,q) in Bbb Z times Bbb Z$, will ths properly prove that such a sequence exists?
real-analysis proof-writing rational-numbers natural-numbers
$endgroup$
add a comment |
$begingroup$
I'm trying to prove the following:
Let $Bbb Q$ be the countable set of rational numbers and ${x_n}_{n=1}^infty$ be a sequence such that for every q $in$ $Bbb Q$ there is a $n in Bbb N$ with $x_n = q$. Prove that there is such a sequence ${x_n}$.
My initial thoughts for an attempt at a solution:
We know that $|Bbb Q| = |Bbb N|$ by the Cantor Theorem. Further, I can show that there is a bijection between $Bbb Q$ and $Bbb N$.
If I define ${x_n}_{n=1}^infty$ as some relation between $(p,q) in Bbb Z times Bbb Z$, will ths properly prove that such a sequence exists?
real-analysis proof-writing rational-numbers natural-numbers
$endgroup$
$begingroup$
For an explicit bijection, see -math.stackexchange.com/questions/7643/…
$endgroup$
– Thomas Shelby
Dec 9 '18 at 17:15
1
$begingroup$
Thanks Thomas! This is wonderful to see!
$endgroup$
– user624612
Dec 9 '18 at 17:20
$begingroup$
What is the definition of an infinite sequence ${x_n}_{nin Bbb N} $? It's a function $ f$ with domain $Bbb N,$ except we write $x_n$ for $f(n)$..... And $|Bbb Q|=|Bbb N$| is an abbreviation for, or an equivalent to, the statement that there exists a bijection $f:Bbb Nto Bbb Q.$ And that's all there is to it.
$endgroup$
– DanielWainfleet
Dec 9 '18 at 20:19
$begingroup$
You may enjoy the small book Stories About Sets, by Vilenkin.
$endgroup$
– DanielWainfleet
Dec 9 '18 at 20:22
add a comment |
$begingroup$
I'm trying to prove the following:
Let $Bbb Q$ be the countable set of rational numbers and ${x_n}_{n=1}^infty$ be a sequence such that for every q $in$ $Bbb Q$ there is a $n in Bbb N$ with $x_n = q$. Prove that there is such a sequence ${x_n}$.
My initial thoughts for an attempt at a solution:
We know that $|Bbb Q| = |Bbb N|$ by the Cantor Theorem. Further, I can show that there is a bijection between $Bbb Q$ and $Bbb N$.
If I define ${x_n}_{n=1}^infty$ as some relation between $(p,q) in Bbb Z times Bbb Z$, will ths properly prove that such a sequence exists?
real-analysis proof-writing rational-numbers natural-numbers
$endgroup$
I'm trying to prove the following:
Let $Bbb Q$ be the countable set of rational numbers and ${x_n}_{n=1}^infty$ be a sequence such that for every q $in$ $Bbb Q$ there is a $n in Bbb N$ with $x_n = q$. Prove that there is such a sequence ${x_n}$.
My initial thoughts for an attempt at a solution:
We know that $|Bbb Q| = |Bbb N|$ by the Cantor Theorem. Further, I can show that there is a bijection between $Bbb Q$ and $Bbb N$.
If I define ${x_n}_{n=1}^infty$ as some relation between $(p,q) in Bbb Z times Bbb Z$, will ths properly prove that such a sequence exists?
real-analysis proof-writing rational-numbers natural-numbers
real-analysis proof-writing rational-numbers natural-numbers
asked Dec 9 '18 at 17:01
user624612
$begingroup$
For an explicit bijection, see -math.stackexchange.com/questions/7643/…
$endgroup$
– Thomas Shelby
Dec 9 '18 at 17:15
1
$begingroup$
Thanks Thomas! This is wonderful to see!
$endgroup$
– user624612
Dec 9 '18 at 17:20
$begingroup$
What is the definition of an infinite sequence ${x_n}_{nin Bbb N} $? It's a function $ f$ with domain $Bbb N,$ except we write $x_n$ for $f(n)$..... And $|Bbb Q|=|Bbb N$| is an abbreviation for, or an equivalent to, the statement that there exists a bijection $f:Bbb Nto Bbb Q.$ And that's all there is to it.
$endgroup$
– DanielWainfleet
Dec 9 '18 at 20:19
$begingroup$
You may enjoy the small book Stories About Sets, by Vilenkin.
$endgroup$
– DanielWainfleet
Dec 9 '18 at 20:22
add a comment |
$begingroup$
For an explicit bijection, see -math.stackexchange.com/questions/7643/…
$endgroup$
– Thomas Shelby
Dec 9 '18 at 17:15
1
$begingroup$
Thanks Thomas! This is wonderful to see!
$endgroup$
– user624612
Dec 9 '18 at 17:20
$begingroup$
What is the definition of an infinite sequence ${x_n}_{nin Bbb N} $? It's a function $ f$ with domain $Bbb N,$ except we write $x_n$ for $f(n)$..... And $|Bbb Q|=|Bbb N$| is an abbreviation for, or an equivalent to, the statement that there exists a bijection $f:Bbb Nto Bbb Q.$ And that's all there is to it.
$endgroup$
– DanielWainfleet
Dec 9 '18 at 20:19
$begingroup$
You may enjoy the small book Stories About Sets, by Vilenkin.
$endgroup$
– DanielWainfleet
Dec 9 '18 at 20:22
$begingroup$
For an explicit bijection, see -math.stackexchange.com/questions/7643/…
$endgroup$
– Thomas Shelby
Dec 9 '18 at 17:15
$begingroup$
For an explicit bijection, see -math.stackexchange.com/questions/7643/…
$endgroup$
– Thomas Shelby
Dec 9 '18 at 17:15
1
1
$begingroup$
Thanks Thomas! This is wonderful to see!
$endgroup$
– user624612
Dec 9 '18 at 17:20
$begingroup$
Thanks Thomas! This is wonderful to see!
$endgroup$
– user624612
Dec 9 '18 at 17:20
$begingroup$
What is the definition of an infinite sequence ${x_n}_{nin Bbb N} $? It's a function $ f$ with domain $Bbb N,$ except we write $x_n$ for $f(n)$..... And $|Bbb Q|=|Bbb N$| is an abbreviation for, or an equivalent to, the statement that there exists a bijection $f:Bbb Nto Bbb Q.$ And that's all there is to it.
$endgroup$
– DanielWainfleet
Dec 9 '18 at 20:19
$begingroup$
What is the definition of an infinite sequence ${x_n}_{nin Bbb N} $? It's a function $ f$ with domain $Bbb N,$ except we write $x_n$ for $f(n)$..... And $|Bbb Q|=|Bbb N$| is an abbreviation for, or an equivalent to, the statement that there exists a bijection $f:Bbb Nto Bbb Q.$ And that's all there is to it.
$endgroup$
– DanielWainfleet
Dec 9 '18 at 20:19
$begingroup$
You may enjoy the small book Stories About Sets, by Vilenkin.
$endgroup$
– DanielWainfleet
Dec 9 '18 at 20:22
$begingroup$
You may enjoy the small book Stories About Sets, by Vilenkin.
$endgroup$
– DanielWainfleet
Dec 9 '18 at 20:22
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
It is actually quit easy once you know that $|mathbb{Q}|=|mathbb{N}|$ as this implies that there exists a bijection $f:mathbb{N}rightarrow mathbb{Q}$. Now simply let $x_n = f(n)$.
$endgroup$
$begingroup$
Thank you! This makes sense! I didn't know if much more was needed other than defining the bijective mapping, but it seems that this is about it.
$endgroup$
– user624612
Dec 9 '18 at 17:23
add a comment |
$begingroup$
The answer to this question is going to depend upon what you have available as definitions. Where I come from, a sequence of elements from a set $S$ is just a function $f:mathbb{N}rightarrow S$; if that is the case for you, since you already know there is a bijection from $mathbb{N}$ to $mathbb{Q}$ you are done!
If you wanted to explicitly write down such a sequence, then yes, you will probably want to start with a surjection from $mathbb{N}$ to $mathbb{Z}times mathbb{Z}$, and then a surjection from $mathbb{Z}times mathbb{Z}$ to $mathbb{Q}$. The composition of these functions will be a sequence that hits every rational number.
How to build such surjections? You could define $f:mathbb{N}rightarrow mathbb{Z}times mathbb{Z}$ in pieces, say by sending numbers of the form $2^i3^j$ to $(i,j)$, numbers of the form $5^i7^j$ to $(-i,-j)$, numbers of the form $11^i13^j$ to $(i,-j)$, and numbers of the form $17^i19^j$ to $(-i,j)$, with everything else sent to $(0,0)$. You could define $g:mathbb{Z}times mathbb{Z} rightarrow mathbb{Q}$ by sending $(0,q)$ and $(p,0)$ to $0$, and all other $(p,q)$ to $p/q$.
$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
});
}
});
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%2f3032608%2fhelp-proving-there-is-a-sequence-of-rational-numbers%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$
It is actually quit easy once you know that $|mathbb{Q}|=|mathbb{N}|$ as this implies that there exists a bijection $f:mathbb{N}rightarrow mathbb{Q}$. Now simply let $x_n = f(n)$.
$endgroup$
$begingroup$
Thank you! This makes sense! I didn't know if much more was needed other than defining the bijective mapping, but it seems that this is about it.
$endgroup$
– user624612
Dec 9 '18 at 17:23
add a comment |
$begingroup$
It is actually quit easy once you know that $|mathbb{Q}|=|mathbb{N}|$ as this implies that there exists a bijection $f:mathbb{N}rightarrow mathbb{Q}$. Now simply let $x_n = f(n)$.
$endgroup$
$begingroup$
Thank you! This makes sense! I didn't know if much more was needed other than defining the bijective mapping, but it seems that this is about it.
$endgroup$
– user624612
Dec 9 '18 at 17:23
add a comment |
$begingroup$
It is actually quit easy once you know that $|mathbb{Q}|=|mathbb{N}|$ as this implies that there exists a bijection $f:mathbb{N}rightarrow mathbb{Q}$. Now simply let $x_n = f(n)$.
$endgroup$
It is actually quit easy once you know that $|mathbb{Q}|=|mathbb{N}|$ as this implies that there exists a bijection $f:mathbb{N}rightarrow mathbb{Q}$. Now simply let $x_n = f(n)$.
answered Dec 9 '18 at 17:11
YankoYanko
7,0081629
7,0081629
$begingroup$
Thank you! This makes sense! I didn't know if much more was needed other than defining the bijective mapping, but it seems that this is about it.
$endgroup$
– user624612
Dec 9 '18 at 17:23
add a comment |
$begingroup$
Thank you! This makes sense! I didn't know if much more was needed other than defining the bijective mapping, but it seems that this is about it.
$endgroup$
– user624612
Dec 9 '18 at 17:23
$begingroup$
Thank you! This makes sense! I didn't know if much more was needed other than defining the bijective mapping, but it seems that this is about it.
$endgroup$
– user624612
Dec 9 '18 at 17:23
$begingroup$
Thank you! This makes sense! I didn't know if much more was needed other than defining the bijective mapping, but it seems that this is about it.
$endgroup$
– user624612
Dec 9 '18 at 17:23
add a comment |
$begingroup$
The answer to this question is going to depend upon what you have available as definitions. Where I come from, a sequence of elements from a set $S$ is just a function $f:mathbb{N}rightarrow S$; if that is the case for you, since you already know there is a bijection from $mathbb{N}$ to $mathbb{Q}$ you are done!
If you wanted to explicitly write down such a sequence, then yes, you will probably want to start with a surjection from $mathbb{N}$ to $mathbb{Z}times mathbb{Z}$, and then a surjection from $mathbb{Z}times mathbb{Z}$ to $mathbb{Q}$. The composition of these functions will be a sequence that hits every rational number.
How to build such surjections? You could define $f:mathbb{N}rightarrow mathbb{Z}times mathbb{Z}$ in pieces, say by sending numbers of the form $2^i3^j$ to $(i,j)$, numbers of the form $5^i7^j$ to $(-i,-j)$, numbers of the form $11^i13^j$ to $(i,-j)$, and numbers of the form $17^i19^j$ to $(-i,j)$, with everything else sent to $(0,0)$. You could define $g:mathbb{Z}times mathbb{Z} rightarrow mathbb{Q}$ by sending $(0,q)$ and $(p,0)$ to $0$, and all other $(p,q)$ to $p/q$.
$endgroup$
add a comment |
$begingroup$
The answer to this question is going to depend upon what you have available as definitions. Where I come from, a sequence of elements from a set $S$ is just a function $f:mathbb{N}rightarrow S$; if that is the case for you, since you already know there is a bijection from $mathbb{N}$ to $mathbb{Q}$ you are done!
If you wanted to explicitly write down such a sequence, then yes, you will probably want to start with a surjection from $mathbb{N}$ to $mathbb{Z}times mathbb{Z}$, and then a surjection from $mathbb{Z}times mathbb{Z}$ to $mathbb{Q}$. The composition of these functions will be a sequence that hits every rational number.
How to build such surjections? You could define $f:mathbb{N}rightarrow mathbb{Z}times mathbb{Z}$ in pieces, say by sending numbers of the form $2^i3^j$ to $(i,j)$, numbers of the form $5^i7^j$ to $(-i,-j)$, numbers of the form $11^i13^j$ to $(i,-j)$, and numbers of the form $17^i19^j$ to $(-i,j)$, with everything else sent to $(0,0)$. You could define $g:mathbb{Z}times mathbb{Z} rightarrow mathbb{Q}$ by sending $(0,q)$ and $(p,0)$ to $0$, and all other $(p,q)$ to $p/q$.
$endgroup$
add a comment |
$begingroup$
The answer to this question is going to depend upon what you have available as definitions. Where I come from, a sequence of elements from a set $S$ is just a function $f:mathbb{N}rightarrow S$; if that is the case for you, since you already know there is a bijection from $mathbb{N}$ to $mathbb{Q}$ you are done!
If you wanted to explicitly write down such a sequence, then yes, you will probably want to start with a surjection from $mathbb{N}$ to $mathbb{Z}times mathbb{Z}$, and then a surjection from $mathbb{Z}times mathbb{Z}$ to $mathbb{Q}$. The composition of these functions will be a sequence that hits every rational number.
How to build such surjections? You could define $f:mathbb{N}rightarrow mathbb{Z}times mathbb{Z}$ in pieces, say by sending numbers of the form $2^i3^j$ to $(i,j)$, numbers of the form $5^i7^j$ to $(-i,-j)$, numbers of the form $11^i13^j$ to $(i,-j)$, and numbers of the form $17^i19^j$ to $(-i,j)$, with everything else sent to $(0,0)$. You could define $g:mathbb{Z}times mathbb{Z} rightarrow mathbb{Q}$ by sending $(0,q)$ and $(p,0)$ to $0$, and all other $(p,q)$ to $p/q$.
$endgroup$
The answer to this question is going to depend upon what you have available as definitions. Where I come from, a sequence of elements from a set $S$ is just a function $f:mathbb{N}rightarrow S$; if that is the case for you, since you already know there is a bijection from $mathbb{N}$ to $mathbb{Q}$ you are done!
If you wanted to explicitly write down such a sequence, then yes, you will probably want to start with a surjection from $mathbb{N}$ to $mathbb{Z}times mathbb{Z}$, and then a surjection from $mathbb{Z}times mathbb{Z}$ to $mathbb{Q}$. The composition of these functions will be a sequence that hits every rational number.
How to build such surjections? You could define $f:mathbb{N}rightarrow mathbb{Z}times mathbb{Z}$ in pieces, say by sending numbers of the form $2^i3^j$ to $(i,j)$, numbers of the form $5^i7^j$ to $(-i,-j)$, numbers of the form $11^i13^j$ to $(i,-j)$, and numbers of the form $17^i19^j$ to $(-i,j)$, with everything else sent to $(0,0)$. You could define $g:mathbb{Z}times mathbb{Z} rightarrow mathbb{Q}$ by sending $(0,q)$ and $(p,0)$ to $0$, and all other $(p,q)$ to $p/q$.
edited Dec 9 '18 at 17:19
answered Dec 9 '18 at 17:12
GenericMathematicianGenericMathematician
863
863
add a comment |
add a comment |
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%2f3032608%2fhelp-proving-there-is-a-sequence-of-rational-numbers%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
$begingroup$
For an explicit bijection, see -math.stackexchange.com/questions/7643/…
$endgroup$
– Thomas Shelby
Dec 9 '18 at 17:15
1
$begingroup$
Thanks Thomas! This is wonderful to see!
$endgroup$
– user624612
Dec 9 '18 at 17:20
$begingroup$
What is the definition of an infinite sequence ${x_n}_{nin Bbb N} $? It's a function $ f$ with domain $Bbb N,$ except we write $x_n$ for $f(n)$..... And $|Bbb Q|=|Bbb N$| is an abbreviation for, or an equivalent to, the statement that there exists a bijection $f:Bbb Nto Bbb Q.$ And that's all there is to it.
$endgroup$
– DanielWainfleet
Dec 9 '18 at 20:19
$begingroup$
You may enjoy the small book Stories About Sets, by Vilenkin.
$endgroup$
– DanielWainfleet
Dec 9 '18 at 20:22