Prove that union of countable sets is countable
$begingroup$
Could anyone explain to me the part in red? I can't see how the existence of the set T is used in the proof, and how theorem 2.8 is applied.
Here are the relevant definitions and theorem.
real-analysis proof-explanation
asked Dec 12 '18 at 18:55
Josh NgJosh Ng
977
$endgroup$
add a comment |
$begingroup$
Could anyone explain to me the part in red? I can't see how the existence of the set T is used in the proof, and how theorem 2.8 is applied.
Here are the relevant definitions and theorem.
real-analysis proof-explanation
asked Dec 12 '18 at 18:55
Josh NgJosh Ng
977
$endgroup$
$begingroup$
Suppose the sequence of elements is $1,2,2,3,4,4,4,6,,,,,,,$, then to each element we assign a label, i.e. the first element is $1$, the second is $2$, the third is also $2$ and so on. But when you make up the set $S$, you won't be repeating elements. So $S$ will have number 1, number 2, number 4, number 5, number 8... and so on. So the set $T={1,2,4,5,8, ldots} subset Bbb{N}$ is in one-one correspondence with $S$.
$endgroup$
– Anurag A
Dec 12 '18 at 19:05
add a comment |
$begingroup$
Could anyone explain to me the part in red? I can't see how the existence of the set T is used in the proof, and how theorem 2.8 is applied.
Here are the relevant definitions and theorem.
real-analysis proof-explanation
asked Dec 12 '18 at 18:55
Josh NgJosh Ng
977
$endgroup$
Could anyone explain to me the part in red? I can't see how the existence of the set T is used in the proof, and how theorem 2.8 is applied.
Here are the relevant definitions and theorem.
real-analysis proof-explanation
real-analysis proof-explanation
asked Dec 12 '18 at 18:55
Josh NgJosh Ng
977
asked Dec 12 '18 at 18:55
Josh NgJosh Ng
977
asked Dec 12 '18 at 18:55
Josh NgJosh Ng
977
asked Dec 12 '18 at 18:55
Josh NgJosh Ng
977
asked Dec 12 '18 at 18:55
Josh NgJosh Ng
977
977
$begingroup$
Suppose the sequence of elements is $1,2,2,3,4,4,4,6,,,,,,,$, then to each element we assign a label, i.e. the first element is $1$, the second is $2$, the third is also $2$ and so on. But when you make up the set $S$, you won't be repeating elements. So $S$ will have number 1, number 2, number 4, number 5, number 8... and so on. So the set $T={1,2,4,5,8, ldots} subset Bbb{N}$ is in one-one correspondence with $S$.
$endgroup$
– Anurag A
Dec 12 '18 at 19:05
add a comment |
$begingroup$
Suppose the sequence of elements is $1,2,2,3,4,4,4,6,,,,,,,$, then to each element we assign a label, i.e. the first element is $1$, the second is $2$, the third is also $2$ and so on. But when you make up the set $S$, you won't be repeating elements. So $S$ will have number 1, number 2, number 4, number 5, number 8... and so on. So the set $T={1,2,4,5,8, ldots} subset Bbb{N}$ is in one-one correspondence with $S$.
$endgroup$
– Anurag A
Dec 12 '18 at 19:05
$begingroup$
Suppose the sequence of elements is $1,2,2,3,4,4,4,6,,,,,,,$, then to each element we assign a label, i.e. the first element is $1$, the second is $2$, the third is also $2$ and so on. But when you make up the set $S$, you won't be repeating elements. So $S$ will have number 1, number 2, number 4, number 5, number 8... and so on. So the set $T={1,2,4,5,8, ldots} subset Bbb{N}$ is in one-one correspondence with $S$.
$endgroup$
– Anurag A
Dec 12 '18 at 19:05
$begingroup$
Suppose the sequence of elements is $1,2,2,3,4,4,4,6,,,,,,,$, then to each element we assign a label, i.e. the first element is $1$, the second is $2$, the third is also $2$ and so on. But when you make up the set $S$, you won't be repeating elements. So $S$ will have number 1, number 2, number 4, number 5, number 8... and so on. So the set $T={1,2,4,5,8, ldots} subset Bbb{N}$ is in one-one correspondence with $S$.
$endgroup$
– Anurag A
Dec 12 '18 at 19:05
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Following the arrows you get a surjective function $f:mathbb Ntobigcup_{n=1}^infty E_n$, but there might be repetitions, so it is not injective. Well then you just discard the duplicates and get a bijective function
$f:Tsubseteqmathbb Ntobigcup_{n=1}^infty E_n$.
answered Dec 12 '18 at 19:04
FedericoFederico
5,034514
$endgroup$
add a comment |
$begingroup$
The sequence is a function from $mathbb{N} rightarrow$ S, where $i mapsto x_i$.. This function is surjective by construction. Since there may be double counting, there is a subset T $subset mathbb{N}$ such that T $sim$ S.
answered Dec 12 '18 at 19:10
Joel PereiraJoel Pereira
75719
$endgroup$
add a comment |
$begingroup$
What you have in (17) is a function $g:mathbb Ntimesmathbb Nto S$. Namely, $g(k,j)=x_{k,j}$. You have that $g$ is surjective, but it may not be injective if there are elements repeated among the $E_n$.
Because $g$ is surjective, for each $sin S$ there exists $(x_1,y_1)inmathbb Ntimesmathbb N$ with $g(s_1,t_1)=s$. These pairs may not be unique if $g$ is not injective, but we may choose a single one for each $s$. Say $g(x_s,y_s)=s$. Now let
$$
T={(x_s,y_s): sin S}.
$$
Then $Ssim T$ and $Tsubset mathbb Ntimesmathbb N$. So $T$ is countable and $S$ is countable.
answered Dec 12 '18 at 19:06
Martin ArgeramiMartin Argerami
126k1182181
$endgroup$
$begingroup$
I was not talking about your answer, but rather the way it's phrased in the book, which might not be very clear for someone who is new to this.
$endgroup$
– Martin Argerami
Dec 12 '18 at 19:15
$begingroup$
Yes I agree that it is not sufficiently rigorous for something which should be quite pedagogical
$endgroup$
– Federico
Dec 12 '18 at 19:23
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%2f3037085%2fprove-that-union-of-countable-sets-is-countable%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Following the arrows you get a surjective function $f:mathbb Ntobigcup_{n=1}^infty E_n$, but there might be repetitions, so it is not injective. Well then you just discard the duplicates and get a bijective function
$f:Tsubseteqmathbb Ntobigcup_{n=1}^infty E_n$.
answered Dec 12 '18 at 19:04
FedericoFederico
5,034514
$endgroup$
add a comment |
$begingroup$
Following the arrows you get a surjective function $f:mathbb Ntobigcup_{n=1}^infty E_n$, but there might be repetitions, so it is not injective. Well then you just discard the duplicates and get a bijective function
$f:Tsubseteqmathbb Ntobigcup_{n=1}^infty E_n$.
answered Dec 12 '18 at 19:04
FedericoFederico
5,034514
$endgroup$
add a comment |
$begingroup$
Following the arrows you get a surjective function $f:mathbb Ntobigcup_{n=1}^infty E_n$, but there might be repetitions, so it is not injective. Well then you just discard the duplicates and get a bijective function
$f:Tsubseteqmathbb Ntobigcup_{n=1}^infty E_n$.
answered Dec 12 '18 at 19:04
FedericoFederico
5,034514
$endgroup$
Following the arrows you get a surjective function $f:mathbb Ntobigcup_{n=1}^infty E_n$, but there might be repetitions, so it is not injective. Well then you just discard the duplicates and get a bijective function
$f:Tsubseteqmathbb Ntobigcup_{n=1}^infty E_n$.
answered Dec 12 '18 at 19:04
FedericoFederico
5,034514
answered Dec 12 '18 at 19:04
FedericoFederico
5,034514
answered Dec 12 '18 at 19:04
FedericoFederico
5,034514
answered Dec 12 '18 at 19:04
FedericoFederico
5,034514
5,034514
add a comment |
add a comment |
$begingroup$
The sequence is a function from $mathbb{N} rightarrow$ S, where $i mapsto x_i$.. This function is surjective by construction. Since there may be double counting, there is a subset T $subset mathbb{N}$ such that T $sim$ S.
answered Dec 12 '18 at 19:10
Joel PereiraJoel Pereira
75719
$endgroup$
add a comment |
$begingroup$
The sequence is a function from $mathbb{N} rightarrow$ S, where $i mapsto x_i$.. This function is surjective by construction. Since there may be double counting, there is a subset T $subset mathbb{N}$ such that T $sim$ S.
answered Dec 12 '18 at 19:10
Joel PereiraJoel Pereira
75719
$endgroup$
add a comment |
$begingroup$
The sequence is a function from $mathbb{N} rightarrow$ S, where $i mapsto x_i$.. This function is surjective by construction. Since there may be double counting, there is a subset T $subset mathbb{N}$ such that T $sim$ S.
answered Dec 12 '18 at 19:10
Joel PereiraJoel Pereira
75719
$endgroup$
The sequence is a function from $mathbb{N} rightarrow$ S, where $i mapsto x_i$.. This function is surjective by construction. Since there may be double counting, there is a subset T $subset mathbb{N}$ such that T $sim$ S.
answered Dec 12 '18 at 19:10
Joel PereiraJoel Pereira
75719
answered Dec 12 '18 at 19:10
Joel PereiraJoel Pereira
75719
answered Dec 12 '18 at 19:10
Joel PereiraJoel Pereira
75719
answered Dec 12 '18 at 19:10
Joel PereiraJoel Pereira
75719
75719
add a comment |
add a comment |
$begingroup$
What you have in (17) is a function $g:mathbb Ntimesmathbb Nto S$. Namely, $g(k,j)=x_{k,j}$. You have that $g$ is surjective, but it may not be injective if there are elements repeated among the $E_n$.
Because $g$ is surjective, for each $sin S$ there exists $(x_1,y_1)inmathbb Ntimesmathbb N$ with $g(s_1,t_1)=s$. These pairs may not be unique if $g$ is not injective, but we may choose a single one for each $s$. Say $g(x_s,y_s)=s$. Now let
$$
T={(x_s,y_s): sin S}.
$$
Then $Ssim T$ and $Tsubset mathbb Ntimesmathbb N$. So $T$ is countable and $S$ is countable.
answered Dec 12 '18 at 19:06
Martin ArgeramiMartin Argerami
126k1182181
$endgroup$
$begingroup$
I was not talking about your answer, but rather the way it's phrased in the book, which might not be very clear for someone who is new to this.
$endgroup$
– Martin Argerami
Dec 12 '18 at 19:15
$begingroup$
Yes I agree that it is not sufficiently rigorous for something which should be quite pedagogical
$endgroup$
– Federico
Dec 12 '18 at 19:23
add a comment |
$begingroup$
What you have in (17) is a function $g:mathbb Ntimesmathbb Nto S$. Namely, $g(k,j)=x_{k,j}$. You have that $g$ is surjective, but it may not be injective if there are elements repeated among the $E_n$.
Because $g$ is surjective, for each $sin S$ there exists $(x_1,y_1)inmathbb Ntimesmathbb N$ with $g(s_1,t_1)=s$. These pairs may not be unique if $g$ is not injective, but we may choose a single one for each $s$. Say $g(x_s,y_s)=s$. Now let
$$
T={(x_s,y_s): sin S}.
$$
Then $Ssim T$ and $Tsubset mathbb Ntimesmathbb N$. So $T$ is countable and $S$ is countable.
answered Dec 12 '18 at 19:06
Martin ArgeramiMartin Argerami
126k1182181
$endgroup$
$begingroup$
I was not talking about your answer, but rather the way it's phrased in the book, which might not be very clear for someone who is new to this.
$endgroup$
– Martin Argerami
Dec 12 '18 at 19:15
$begingroup$
Yes I agree that it is not sufficiently rigorous for something which should be quite pedagogical
$endgroup$
– Federico
Dec 12 '18 at 19:23
add a comment |
$begingroup$
What you have in (17) is a function $g:mathbb Ntimesmathbb Nto S$. Namely, $g(k,j)=x_{k,j}$. You have that $g$ is surjective, but it may not be injective if there are elements repeated among the $E_n$.
Because $g$ is surjective, for each $sin S$ there exists $(x_1,y_1)inmathbb Ntimesmathbb N$ with $g(s_1,t_1)=s$. These pairs may not be unique if $g$ is not injective, but we may choose a single one for each $s$. Say $g(x_s,y_s)=s$. Now let
$$
T={(x_s,y_s): sin S}.
$$
Then $Ssim T$ and $Tsubset mathbb Ntimesmathbb N$. So $T$ is countable and $S$ is countable.
answered Dec 12 '18 at 19:06
Martin ArgeramiMartin Argerami
126k1182181
$endgroup$
What you have in (17) is a function $g:mathbb Ntimesmathbb Nto S$. Namely, $g(k,j)=x_{k,j}$. You have that $g$ is surjective, but it may not be injective if there are elements repeated among the $E_n$.
Because $g$ is surjective, for each $sin S$ there exists $(x_1,y_1)inmathbb Ntimesmathbb N$ with $g(s_1,t_1)=s$. These pairs may not be unique if $g$ is not injective, but we may choose a single one for each $s$. Say $g(x_s,y_s)=s$. Now let
$$
T={(x_s,y_s): sin S}.
$$
Then $Ssim T$ and $Tsubset mathbb Ntimesmathbb N$. So $T$ is countable and $S$ is countable.
answered Dec 12 '18 at 19:06
Martin ArgeramiMartin Argerami
126k1182181
edited Dec 12 '18 at 19:14
answered Dec 12 '18 at 19:06
Martin ArgeramiMartin Argerami
126k1182181
answered Dec 12 '18 at 19:06
Martin ArgeramiMartin Argerami
126k1182181
answered Dec 12 '18 at 19:06
Martin ArgeramiMartin Argerami
126k1182181
126k1182181
$begingroup$
I was not talking about your answer, but rather the way it's phrased in the book, which might not be very clear for someone who is new to this.
$endgroup$
– Martin Argerami
Dec 12 '18 at 19:15
$begingroup$
Yes I agree that it is not sufficiently rigorous for something which should be quite pedagogical
$endgroup$
– Federico
Dec 12 '18 at 19:23
add a comment |
$begingroup$
I was not talking about your answer, but rather the way it's phrased in the book, which might not be very clear for someone who is new to this.
$endgroup$
– Martin Argerami
Dec 12 '18 at 19:15
$begingroup$
Yes I agree that it is not sufficiently rigorous for something which should be quite pedagogical
$endgroup$
– Federico
Dec 12 '18 at 19:23
$begingroup$
I was not talking about your answer, but rather the way it's phrased in the book, which might not be very clear for someone who is new to this.
$endgroup$
– Martin Argerami
Dec 12 '18 at 19:15
$begingroup$
I was not talking about your answer, but rather the way it's phrased in the book, which might not be very clear for someone who is new to this.
$endgroup$
– Martin Argerami
Dec 12 '18 at 19:15
$begingroup$
Yes I agree that it is not sufficiently rigorous for something which should be quite pedagogical
$endgroup$
– Federico
Dec 12 '18 at 19:23
$begingroup$
Yes I agree that it is not sufficiently rigorous for something which should be quite pedagogical
$endgroup$
– Federico
Dec 12 '18 at 19:23
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%2f3037085%2fprove-that-union-of-countable-sets-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
$begingroup$
Suppose the sequence of elements is $1,2,2,3,4,4,4,6,,,,,,,$, then to each element we assign a label, i.e. the first element is $1$, the second is $2$, the third is also $2$ and so on. But when you make up the set $S$, you won't be repeating elements. So $S$ will have number 1, number 2, number 4, number 5, number 8... and so on. So the set $T={1,2,4,5,8, ldots} subset Bbb{N}$ is in one-one correspondence with $S$.
$endgroup$
– Anurag A
Dec 12 '18 at 19:05