Mixing
The union of a sequence of infinite, countable sets is countable.
$begingroup$
While reading Walter Rudin's Principles of Mathematical Analysis, I ran into the following theorem and proof:
Theorem 2.12. Let $left{E_nright}$, $n=1,2,dots$, be a sequence of countable sets, and put
$$
S=bigcup_{n=1}^infty E_n.
$$
Then $S$ is countable.
Proof. Let every set $E_n$ be arranged in a sequence $left{X_{nk}right}$, $k=1,2,3,dots$, and consider the infinite array
in which the elements of $E_n$ form the $n$th row. The array contains all elements of $S$. As indicated by the arrows, these elements can be arranged in a sequence
$$
x_{11};x_{21},x_{12};x_{31},x_{22},x_{13};x_{41},x_{32},x_{23},x_{14};dotstag{*}
$$
If any two of the sets $E_n$ have elements in common, these will appear more than once in $(*)$. Hence there is a subset $T$ of the set of all positive integers such that $Ssim T$, which shows that $S$ is at most countable. Since $E_1subset S$, and $E_1$ is infinite, $S$ is infinite, and thus countable. $blacksquare$
How does the bolded sentence follow from all previous? In fact, I do not know how the matrix and $(*)$ come into play.
real-analysis
asked Jul 19 '13 at 16:23
ClericCleric
3,20242466
$endgroup$
add a comment |
$begingroup$
While reading Walter Rudin's Principles of Mathematical Analysis, I ran into the following theorem and proof:
Theorem 2.12. Let $left{E_nright}$, $n=1,2,dots$, be a sequence of countable sets, and put
$$
S=bigcup_{n=1}^infty E_n.
$$
Then $S$ is countable.
Proof. Let every set $E_n$ be arranged in a sequence $left{X_{nk}right}$, $k=1,2,3,dots$, and consider the infinite array
in which the elements of $E_n$ form the $n$th row. The array contains all elements of $S$. As indicated by the arrows, these elements can be arranged in a sequence
$$
x_{11};x_{21},x_{12};x_{31},x_{22},x_{13};x_{41},x_{32},x_{23},x_{14};dotstag{*}
$$
If any two of the sets $E_n$ have elements in common, these will appear more than once in $(*)$. Hence there is a subset $T$ of the set of all positive integers such that $Ssim T$, which shows that $S$ is at most countable. Since $E_1subset S$, and $E_1$ is infinite, $S$ is infinite, and thus countable. $blacksquare$
How does the bolded sentence follow from all previous? In fact, I do not know how the matrix and $(*)$ come into play.
real-analysis
asked Jul 19 '13 at 16:23
ClericCleric
3,20242466
$endgroup$
3
$begingroup$
The sequence is an onto map $mathbb Nto S$. By considering a suitable subset $T$ of $mathbb N$ (i.e. removing duplicates) the (restricted) map becomes bijective.
$endgroup$
– Hagen von Eitzen
Jul 19 '13 at 16:27
$begingroup$
@HagenvonEitzen, how did you conclude that $mathbb Nto S$?
$endgroup$
– Cleric
Jul 19 '13 at 17:37
add a comment |
$begingroup$
While reading Walter Rudin's Principles of Mathematical Analysis, I ran into the following theorem and proof:
Theorem 2.12. Let $left{E_nright}$, $n=1,2,dots$, be a sequence of countable sets, and put
$$
S=bigcup_{n=1}^infty E_n.
$$
Then $S$ is countable.
Proof. Let every set $E_n$ be arranged in a sequence $left{X_{nk}right}$, $k=1,2,3,dots$, and consider the infinite array
in which the elements of $E_n$ form the $n$th row. The array contains all elements of $S$. As indicated by the arrows, these elements can be arranged in a sequence
$$
x_{11};x_{21},x_{12};x_{31},x_{22},x_{13};x_{41},x_{32},x_{23},x_{14};dotstag{*}
$$
If any two of the sets $E_n$ have elements in common, these will appear more than once in $(*)$. Hence there is a subset $T$ of the set of all positive integers such that $Ssim T$, which shows that $S$ is at most countable. Since $E_1subset S$, and $E_1$ is infinite, $S$ is infinite, and thus countable. $blacksquare$
How does the bolded sentence follow from all previous? In fact, I do not know how the matrix and $(*)$ come into play.
real-analysis
asked Jul 19 '13 at 16:23
ClericCleric
3,20242466
$endgroup$
While reading Walter Rudin's Principles of Mathematical Analysis, I ran into the following theorem and proof:
Theorem 2.12. Let $left{E_nright}$, $n=1,2,dots$, be a sequence of countable sets, and put
$$
S=bigcup_{n=1}^infty E_n.
$$
Then $S$ is countable.
Proof. Let every set $E_n$ be arranged in a sequence $left{X_{nk}right}$, $k=1,2,3,dots$, and consider the infinite array
in which the elements of $E_n$ form the $n$th row. The array contains all elements of $S$. As indicated by the arrows, these elements can be arranged in a sequence
$$
x_{11};x_{21},x_{12};x_{31},x_{22},x_{13};x_{41},x_{32},x_{23},x_{14};dotstag{*}
$$
If any two of the sets $E_n$ have elements in common, these will appear more than once in $(*)$. Hence there is a subset $T$ of the set of all positive integers such that $Ssim T$, which shows that $S$ is at most countable. Since $E_1subset S$, and $E_1$ is infinite, $S$ is infinite, and thus countable. $blacksquare$
How does the bolded sentence follow from all previous? In fact, I do not know how the matrix and $(*)$ come into play.
real-analysis
real-analysis
asked Jul 19 '13 at 16:23
ClericCleric
3,20242466
asked Jul 19 '13 at 16:23
ClericCleric
3,20242466
asked Jul 19 '13 at 16:23
ClericCleric
3,20242466
asked Jul 19 '13 at 16:23
ClericCleric
3,20242466
asked Jul 19 '13 at 16:23
ClericCleric
3,20242466
3,20242466
3
$begingroup$
The sequence is an onto map $mathbb Nto S$. By considering a suitable subset $T$ of $mathbb N$ (i.e. removing duplicates) the (restricted) map becomes bijective.
$endgroup$
– Hagen von Eitzen
Jul 19 '13 at 16:27
$begingroup$
@HagenvonEitzen, how did you conclude that $mathbb Nto S$?
$endgroup$
– Cleric
Jul 19 '13 at 17:37
add a comment |
3
$begingroup$
The sequence is an onto map $mathbb Nto S$. By considering a suitable subset $T$ of $mathbb N$ (i.e. removing duplicates) the (restricted) map becomes bijective.
$endgroup$
– Hagen von Eitzen
Jul 19 '13 at 16:27
$begingroup$
@HagenvonEitzen, how did you conclude that $mathbb Nto S$?
$endgroup$
– Cleric
Jul 19 '13 at 17:37
3
3
$begingroup$
The sequence is an onto map $mathbb Nto S$. By considering a suitable subset $T$ of $mathbb N$ (i.e. removing duplicates) the (restricted) map becomes bijective.
$endgroup$
– Hagen von Eitzen
Jul 19 '13 at 16:27
$begingroup$
The sequence is an onto map $mathbb Nto S$. By considering a suitable subset $T$ of $mathbb N$ (i.e. removing duplicates) the (restricted) map becomes bijective.
$endgroup$
– Hagen von Eitzen
Jul 19 '13 at 16:27
$begingroup$
@HagenvonEitzen, how did you conclude that $mathbb Nto S$?
$endgroup$
– Cleric
Jul 19 '13 at 17:37
$begingroup$
@HagenvonEitzen, how did you conclude that $mathbb Nto S$?
$endgroup$
– Cleric
Jul 19 '13 at 17:37
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Look at the sequence *
x11;x21,x12;x31,x22,x13;x41,x32,x23,x14;…
Within each ;; add the suffixes.
1+1 =2
2+1 = 1+2 = 3
1+3 = 2+2 = 3+1 = 4
and so on.
So for any positive integer you shall get a countable (finite) number of such combination and in each case you shall get elements of $S$. If you remove duplicate items then you shall get a set $S$. This set will be bijective with the set of natural numbers as for each natural number you shall get only a finite number of elements.
I hope it is clear now. The bold sequence is constructed by taking arrows in the matrix. In the matrix the elements of the set $E_i$ are written in arrow.
answered Jul 19 '13 at 16:45
DuttaDutta
3,78852243
$endgroup$
add a comment |
$begingroup$
Using the Cantor Diagonal process, we can link one distinct natural number to each element of S. So, if all the elements $x_{mn}$ are distinct, we are done, as a 1-1 correspondence has been established.
The topic of the bold sentence appears when two elements of S are same. Then we have lost the 1-1 correspondence.
To further picture it, suppose all the elements of S are distinct. then we consider the function $f:N mapsto S$ (N = set of natural numbers) defined by $f(1) = x_{11}$, $f(2) = x_{21}$, $f(3) = x_{12}$, $f(4) = x_{31}$,... (that is, we used the cantor's diagonal process to assign the elements of S to each natural number). But now, what if $x_{11} = x_{31}$? We know, from Peano Axioms $1 ne 4$. But we are getting $f(1) = f(4)$. So f is not a 1-1 correspondence anymore.
But, we are allowed to delete all the duplicates when we are forming the union set S. So, we erase $x_{31}$ from the list. But are we done? NO! Because we don't map 4 to any elements of S!. By Def 2.3, equivalence requires bijection, and f is no longer surrjective.
To avoid this issue, let us consider a subset T of N. Every element of N is in T except for 4. Then clearly T is at most countable since if T is not finite, it is infinite and thus by theorem 2.8 it is countable, and $T sim S$. So, S is also at most countable.
Here we say at most countable because there might be the case that every element of S is equal to $x_{11}$. Then T = {1} and S is finite.
But S is clearly not finite, as $E_1$ is a subset of S and $E_1$ is infinite. So, S is atmost countable and infinte, that implies S is countable.
answered Jan 1 at 19:01
Avik ChakravartyAvik Chakravarty
12
$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%2f447505%2fthe-union-of-a-sequence-of-infinite-countable-sets-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$
Look at the sequence *
x11;x21,x12;x31,x22,x13;x41,x32,x23,x14;…
Within each ;; add the suffixes.
1+1 =2
2+1 = 1+2 = 3
1+3 = 2+2 = 3+1 = 4
and so on.
So for any positive integer you shall get a countable (finite) number of such combination and in each case you shall get elements of $S$. If you remove duplicate items then you shall get a set $S$. This set will be bijective with the set of natural numbers as for each natural number you shall get only a finite number of elements.
I hope it is clear now. The bold sequence is constructed by taking arrows in the matrix. In the matrix the elements of the set $E_i$ are written in arrow.
answered Jul 19 '13 at 16:45
DuttaDutta
3,78852243
$endgroup$
add a comment |
$begingroup$
Look at the sequence *
x11;x21,x12;x31,x22,x13;x41,x32,x23,x14;…
Within each ;; add the suffixes.
1+1 =2
2+1 = 1+2 = 3
1+3 = 2+2 = 3+1 = 4
and so on.
So for any positive integer you shall get a countable (finite) number of such combination and in each case you shall get elements of $S$. If you remove duplicate items then you shall get a set $S$. This set will be bijective with the set of natural numbers as for each natural number you shall get only a finite number of elements.
I hope it is clear now. The bold sequence is constructed by taking arrows in the matrix. In the matrix the elements of the set $E_i$ are written in arrow.
answered Jul 19 '13 at 16:45
DuttaDutta
3,78852243
$endgroup$
add a comment |
$begingroup$
Look at the sequence *
x11;x21,x12;x31,x22,x13;x41,x32,x23,x14;…
Within each ;; add the suffixes.
1+1 =2
2+1 = 1+2 = 3
1+3 = 2+2 = 3+1 = 4
and so on.
So for any positive integer you shall get a countable (finite) number of such combination and in each case you shall get elements of $S$. If you remove duplicate items then you shall get a set $S$. This set will be bijective with the set of natural numbers as for each natural number you shall get only a finite number of elements.
I hope it is clear now. The bold sequence is constructed by taking arrows in the matrix. In the matrix the elements of the set $E_i$ are written in arrow.
answered Jul 19 '13 at 16:45
DuttaDutta
3,78852243
$endgroup$
Look at the sequence *
x11;x21,x12;x31,x22,x13;x41,x32,x23,x14;…
Within each ;; add the suffixes.
1+1 =2
2+1 = 1+2 = 3
1+3 = 2+2 = 3+1 = 4
and so on.
So for any positive integer you shall get a countable (finite) number of such combination and in each case you shall get elements of $S$. If you remove duplicate items then you shall get a set $S$. This set will be bijective with the set of natural numbers as for each natural number you shall get only a finite number of elements.
I hope it is clear now. The bold sequence is constructed by taking arrows in the matrix. In the matrix the elements of the set $E_i$ are written in arrow.
answered Jul 19 '13 at 16:45
DuttaDutta
3,78852243
answered Jul 19 '13 at 16:45
DuttaDutta
3,78852243
answered Jul 19 '13 at 16:45
DuttaDutta
3,78852243
answered Jul 19 '13 at 16:45
DuttaDutta
3,78852243
3,78852243
add a comment |
add a comment |
$begingroup$
Using the Cantor Diagonal process, we can link one distinct natural number to each element of S. So, if all the elements $x_{mn}$ are distinct, we are done, as a 1-1 correspondence has been established.
The topic of the bold sentence appears when two elements of S are same. Then we have lost the 1-1 correspondence.
To further picture it, suppose all the elements of S are distinct. then we consider the function $f:N mapsto S$ (N = set of natural numbers) defined by $f(1) = x_{11}$, $f(2) = x_{21}$, $f(3) = x_{12}$, $f(4) = x_{31}$,... (that is, we used the cantor's diagonal process to assign the elements of S to each natural number). But now, what if $x_{11} = x_{31}$? We know, from Peano Axioms $1 ne 4$. But we are getting $f(1) = f(4)$. So f is not a 1-1 correspondence anymore.
But, we are allowed to delete all the duplicates when we are forming the union set S. So, we erase $x_{31}$ from the list. But are we done? NO! Because we don't map 4 to any elements of S!. By Def 2.3, equivalence requires bijection, and f is no longer surrjective.
To avoid this issue, let us consider a subset T of N. Every element of N is in T except for 4. Then clearly T is at most countable since if T is not finite, it is infinite and thus by theorem 2.8 it is countable, and $T sim S$. So, S is also at most countable.
Here we say at most countable because there might be the case that every element of S is equal to $x_{11}$. Then T = {1} and S is finite.
But S is clearly not finite, as $E_1$ is a subset of S and $E_1$ is infinite. So, S is atmost countable and infinte, that implies S is countable.
answered Jan 1 at 19:01
Avik ChakravartyAvik Chakravarty
12
$endgroup$
add a comment |
$begingroup$
Using the Cantor Diagonal process, we can link one distinct natural number to each element of S. So, if all the elements $x_{mn}$ are distinct, we are done, as a 1-1 correspondence has been established.
The topic of the bold sentence appears when two elements of S are same. Then we have lost the 1-1 correspondence.
To further picture it, suppose all the elements of S are distinct. then we consider the function $f:N mapsto S$ (N = set of natural numbers) defined by $f(1) = x_{11}$, $f(2) = x_{21}$, $f(3) = x_{12}$, $f(4) = x_{31}$,... (that is, we used the cantor's diagonal process to assign the elements of S to each natural number). But now, what if $x_{11} = x_{31}$? We know, from Peano Axioms $1 ne 4$. But we are getting $f(1) = f(4)$. So f is not a 1-1 correspondence anymore.
But, we are allowed to delete all the duplicates when we are forming the union set S. So, we erase $x_{31}$ from the list. But are we done? NO! Because we don't map 4 to any elements of S!. By Def 2.3, equivalence requires bijection, and f is no longer surrjective.
To avoid this issue, let us consider a subset T of N. Every element of N is in T except for 4. Then clearly T is at most countable since if T is not finite, it is infinite and thus by theorem 2.8 it is countable, and $T sim S$. So, S is also at most countable.
Here we say at most countable because there might be the case that every element of S is equal to $x_{11}$. Then T = {1} and S is finite.
But S is clearly not finite, as $E_1$ is a subset of S and $E_1$ is infinite. So, S is atmost countable and infinte, that implies S is countable.
answered Jan 1 at 19:01
Avik ChakravartyAvik Chakravarty
12
$endgroup$
add a comment |
$begingroup$
Using the Cantor Diagonal process, we can link one distinct natural number to each element of S. So, if all the elements $x_{mn}$ are distinct, we are done, as a 1-1 correspondence has been established.
The topic of the bold sentence appears when two elements of S are same. Then we have lost the 1-1 correspondence.
To further picture it, suppose all the elements of S are distinct. then we consider the function $f:N mapsto S$ (N = set of natural numbers) defined by $f(1) = x_{11}$, $f(2) = x_{21}$, $f(3) = x_{12}$, $f(4) = x_{31}$,... (that is, we used the cantor's diagonal process to assign the elements of S to each natural number). But now, what if $x_{11} = x_{31}$? We know, from Peano Axioms $1 ne 4$. But we are getting $f(1) = f(4)$. So f is not a 1-1 correspondence anymore.
But, we are allowed to delete all the duplicates when we are forming the union set S. So, we erase $x_{31}$ from the list. But are we done? NO! Because we don't map 4 to any elements of S!. By Def 2.3, equivalence requires bijection, and f is no longer surrjective.
To avoid this issue, let us consider a subset T of N. Every element of N is in T except for 4. Then clearly T is at most countable since if T is not finite, it is infinite and thus by theorem 2.8 it is countable, and $T sim S$. So, S is also at most countable.
Here we say at most countable because there might be the case that every element of S is equal to $x_{11}$. Then T = {1} and S is finite.
But S is clearly not finite, as $E_1$ is a subset of S and $E_1$ is infinite. So, S is atmost countable and infinte, that implies S is countable.
answered Jan 1 at 19:01
Avik ChakravartyAvik Chakravarty
12
$endgroup$
Using the Cantor Diagonal process, we can link one distinct natural number to each element of S. So, if all the elements $x_{mn}$ are distinct, we are done, as a 1-1 correspondence has been established.
The topic of the bold sentence appears when two elements of S are same. Then we have lost the 1-1 correspondence.
To further picture it, suppose all the elements of S are distinct. then we consider the function $f:N mapsto S$ (N = set of natural numbers) defined by $f(1) = x_{11}$, $f(2) = x_{21}$, $f(3) = x_{12}$, $f(4) = x_{31}$,... (that is, we used the cantor's diagonal process to assign the elements of S to each natural number). But now, what if $x_{11} = x_{31}$? We know, from Peano Axioms $1 ne 4$. But we are getting $f(1) = f(4)$. So f is not a 1-1 correspondence anymore.
But, we are allowed to delete all the duplicates when we are forming the union set S. So, we erase $x_{31}$ from the list. But are we done? NO! Because we don't map 4 to any elements of S!. By Def 2.3, equivalence requires bijection, and f is no longer surrjective.
To avoid this issue, let us consider a subset T of N. Every element of N is in T except for 4. Then clearly T is at most countable since if T is not finite, it is infinite and thus by theorem 2.8 it is countable, and $T sim S$. So, S is also at most countable.
Here we say at most countable because there might be the case that every element of S is equal to $x_{11}$. Then T = {1} and S is finite.
But S is clearly not finite, as $E_1$ is a subset of S and $E_1$ is infinite. So, S is atmost countable and infinte, that implies S is countable.
answered Jan 1 at 19:01
Avik ChakravartyAvik Chakravarty
12
edited Jan 1 at 19:20
answered Jan 1 at 19:01
Avik ChakravartyAvik Chakravarty
12
answered Jan 1 at 19:01
Avik ChakravartyAvik Chakravarty
12
answered Jan 1 at 19:01
Avik ChakravartyAvik Chakravarty
12
12
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%2f447505%2fthe-union-of-a-sequence-of-infinite-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
3
$begingroup$
The sequence is an onto map $mathbb Nto S$. By considering a suitable subset $T$ of $mathbb N$ (i.e. removing duplicates) the (restricted) map becomes bijective.
$endgroup$
– Hagen von Eitzen
Jul 19 '13 at 16:27
$begingroup$
@HagenvonEitzen, how did you conclude that $mathbb Nto S$?
$endgroup$
– Cleric
Jul 19 '13 at 17:37