When is a set infinite
Prove a set A is infinite if and only if it has a subset B ⊂ A such that B $neq$ A and
|B| = |A|.
For the direction where we have B as a subset of A and have |B| = |A| and need to prove A is infinite,
I want to say that this should work-
Say A is finite. Then B is finite, by way of being a proper subset of A. Therefore, cardinalities of A and B cannot be the same since there exists no bijection between them. This is a contradiction to our hypothesis that they are indeed the same. Hence, A must be infinite.
For the direction where we show if A is infinite, then there must exist B (a proper subset) such that cardinalities of A and B are same, I said this:
If there exists a proper subset B such that cardinalities of A and B are not same, then there exists no bijection between A and B. This is true for finite sets. Now how do I move to say that this must mean infinite sets do not have this property?
NOTE: I'm taking an introductory level class in proof writing and there has been no mention of the axiom of choice.
elementary-set-theory
edited Dec 13 '18 at 5:31
Andrés E. Caicedo
64.8k8158246
asked Dec 11 '18 at 21:35
childishsadbino
1148
add a comment |
Prove a set A is infinite if and only if it has a subset B ⊂ A such that B $neq$ A and
|B| = |A|.
For the direction where we have B as a subset of A and have |B| = |A| and need to prove A is infinite,
I want to say that this should work-
Say A is finite. Then B is finite, by way of being a proper subset of A. Therefore, cardinalities of A and B cannot be the same since there exists no bijection between them. This is a contradiction to our hypothesis that they are indeed the same. Hence, A must be infinite.
For the direction where we show if A is infinite, then there must exist B (a proper subset) such that cardinalities of A and B are same, I said this:
If there exists a proper subset B such that cardinalities of A and B are not same, then there exists no bijection between A and B. This is true for finite sets. Now how do I move to say that this must mean infinite sets do not have this property?
NOTE: I'm taking an introductory level class in proof writing and there has been no mention of the axiom of choice.
elementary-set-theory
edited Dec 13 '18 at 5:31
Andrés E. Caicedo
64.8k8158246
asked Dec 11 '18 at 21:35
childishsadbino
1148
1
Bear in mind an infinite set has both same-sized and smaller proper subsets, so you can't force a contradiction just from a proper subset being smaller.
– J.G.
Dec 11 '18 at 21:40
1
Just because choice wasn't mentioned doesn't mean it's being used or that it is necessary. Of course, you are also assuming that your definition of "infinite" is known to everyone. Seeing how you made that "NOTE" at the end, it might be wise to include your definition of "finite" and "infinite" at the end.
– Asaf Karagila♦
Dec 12 '18 at 0:04
You see I was aware of not having defined what I meant by finite or infinite, but that is precisely my issue. Infinite sets were just introduced as "not finite" in class. In other words, when we don't have a finite number of elements in the set, we called that an infinite set, so I am not entirely sure which definition of set uses which assumptions/axioms.
– childishsadbino
Dec 12 '18 at 0:12
add a comment |
Prove a set A is infinite if and only if it has a subset B ⊂ A such that B $neq$ A and
|B| = |A|.
For the direction where we have B as a subset of A and have |B| = |A| and need to prove A is infinite,
I want to say that this should work-
Say A is finite. Then B is finite, by way of being a proper subset of A. Therefore, cardinalities of A and B cannot be the same since there exists no bijection between them. This is a contradiction to our hypothesis that they are indeed the same. Hence, A must be infinite.
For the direction where we show if A is infinite, then there must exist B (a proper subset) such that cardinalities of A and B are same, I said this:
If there exists a proper subset B such that cardinalities of A and B are not same, then there exists no bijection between A and B. This is true for finite sets. Now how do I move to say that this must mean infinite sets do not have this property?
NOTE: I'm taking an introductory level class in proof writing and there has been no mention of the axiom of choice.
elementary-set-theory
edited Dec 13 '18 at 5:31
Andrés E. Caicedo
64.8k8158246
asked Dec 11 '18 at 21:35
childishsadbino
1148
Prove a set A is infinite if and only if it has a subset B ⊂ A such that B $neq$ A and
|B| = |A|.
For the direction where we have B as a subset of A and have |B| = |A| and need to prove A is infinite,
I want to say that this should work-
Say A is finite. Then B is finite, by way of being a proper subset of A. Therefore, cardinalities of A and B cannot be the same since there exists no bijection between them. This is a contradiction to our hypothesis that they are indeed the same. Hence, A must be infinite.
For the direction where we show if A is infinite, then there must exist B (a proper subset) such that cardinalities of A and B are same, I said this:
If there exists a proper subset B such that cardinalities of A and B are not same, then there exists no bijection between A and B. This is true for finite sets. Now how do I move to say that this must mean infinite sets do not have this property?
NOTE: I'm taking an introductory level class in proof writing and there has been no mention of the axiom of choice.
elementary-set-theory
elementary-set-theory
edited Dec 13 '18 at 5:31
Andrés E. Caicedo
64.8k8158246
asked Dec 11 '18 at 21:35
childishsadbino
1148
edited Dec 13 '18 at 5:31
Andrés E. Caicedo
64.8k8158246
asked Dec 11 '18 at 21:35
childishsadbino
1148
edited Dec 13 '18 at 5:31
Andrés E. Caicedo
64.8k8158246
edited Dec 13 '18 at 5:31
Andrés E. Caicedo
64.8k8158246
edited Dec 13 '18 at 5:31
Andrés E. Caicedo
64.8k8158246
64.8k8158246
asked Dec 11 '18 at 21:35
childishsadbino
1148
asked Dec 11 '18 at 21:35
childishsadbino
1148
asked Dec 11 '18 at 21:35
childishsadbino
1148
1148
1
Bear in mind an infinite set has both same-sized and smaller proper subsets, so you can't force a contradiction just from a proper subset being smaller.
– J.G.
Dec 11 '18 at 21:40
1
Just because choice wasn't mentioned doesn't mean it's being used or that it is necessary. Of course, you are also assuming that your definition of "infinite" is known to everyone. Seeing how you made that "NOTE" at the end, it might be wise to include your definition of "finite" and "infinite" at the end.
– Asaf Karagila♦
Dec 12 '18 at 0:04
You see I was aware of not having defined what I meant by finite or infinite, but that is precisely my issue. Infinite sets were just introduced as "not finite" in class. In other words, when we don't have a finite number of elements in the set, we called that an infinite set, so I am not entirely sure which definition of set uses which assumptions/axioms.
– childishsadbino
Dec 12 '18 at 0:12
add a comment |
1
Bear in mind an infinite set has both same-sized and smaller proper subsets, so you can't force a contradiction just from a proper subset being smaller.
– J.G.
Dec 11 '18 at 21:40
1
Just because choice wasn't mentioned doesn't mean it's being used or that it is necessary. Of course, you are also assuming that your definition of "infinite" is known to everyone. Seeing how you made that "NOTE" at the end, it might be wise to include your definition of "finite" and "infinite" at the end.
– Asaf Karagila♦
Dec 12 '18 at 0:04
You see I was aware of not having defined what I meant by finite or infinite, but that is precisely my issue. Infinite sets were just introduced as "not finite" in class. In other words, when we don't have a finite number of elements in the set, we called that an infinite set, so I am not entirely sure which definition of set uses which assumptions/axioms.
– childishsadbino
Dec 12 '18 at 0:12
1
1
Bear in mind an infinite set has both same-sized and smaller proper subsets, so you can't force a contradiction just from a proper subset being smaller.
– J.G.
Dec 11 '18 at 21:40
Bear in mind an infinite set has both same-sized and smaller proper subsets, so you can't force a contradiction just from a proper subset being smaller.
– J.G.
Dec 11 '18 at 21:40
1
1
Just because choice wasn't mentioned doesn't mean it's being used or that it is necessary. Of course, you are also assuming that your definition of "infinite" is known to everyone. Seeing how you made that "NOTE" at the end, it might be wise to include your definition of "finite" and "infinite" at the end.
– Asaf Karagila♦
Dec 12 '18 at 0:04
Just because choice wasn't mentioned doesn't mean it's being used or that it is necessary. Of course, you are also assuming that your definition of "infinite" is known to everyone. Seeing how you made that "NOTE" at the end, it might be wise to include your definition of "finite" and "infinite" at the end.
– Asaf Karagila♦
Dec 12 '18 at 0:04
You see I was aware of not having defined what I meant by finite or infinite, but that is precisely my issue. Infinite sets were just introduced as "not finite" in class. In other words, when we don't have a finite number of elements in the set, we called that an infinite set, so I am not entirely sure which definition of set uses which assumptions/axioms.
– childishsadbino
Dec 12 '18 at 0:12
You see I was aware of not having defined what I meant by finite or infinite, but that is precisely my issue. Infinite sets were just introduced as "not finite" in class. In other words, when we don't have a finite number of elements in the set, we called that an infinite set, so I am not entirely sure which definition of set uses which assumptions/axioms.
– childishsadbino
Dec 12 '18 at 0:12
add a comment |
2 Answers
2
active
oldest
votes
The usual proof uses the fact that $A$ has a proper subset that is countable. Call it $C$ and label its elements $c_1,c_2dots$.
Then we can construct a bijection $A rightarrow Asetminus {c_1}$. The function is defined by $f(x)=x$ if $x$ is not in $C$ and $f(c_n)=c_{n+1}$
Now in order to show the countable subset exists just build it with induction.
answered Dec 11 '18 at 21:48
Jorge Fernández
75.1k1190191
add a comment |
Thanks for warning us not to use the axiom of choice, since that makes for such an easy proof of a countably infinite subset (which is the crux of the problem) one could be forgiven for not knowing a choice-free strategy to prove the same.
If $A$ is infinite $Bbb N$ can either be injected or surjected to $A$, respectively implying $A$ has an infinite subset or $A$ is countable. In the latter case $A$ is countably infinite and can be bijected with $Bbb N$, so either way $A$ has a subset we can biject with $Bbb N$, say ${f(n)|ninBbb N}$.
Finally, $B:=Abackslash{f(0)}$ bijects with $A$; in the $Bto A$ direction send $f(n)$ to $f(n-1)$, or any other element of $B$ to itself.
answered Dec 11 '18 at 21:48
J.G.
23.2k22137
3
Isn't the OP's statement "Every infinite set is Dedekind-infinite", which requires some form of choice?
– eyeballfrog
Dec 11 '18 at 21:55
@eyeballfrog: That depends on the choice of definition of infinite...
– Asaf Karagila♦
Dec 12 '18 at 0:05
After having read the definition of a Dedekind-infinite set, I believe that is what I mean to use as the definition of infinite.
– childishsadbino
Dec 12 '18 at 0:18
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%2f3035862%2fwhen-is-a-set-infinite%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
The usual proof uses the fact that $A$ has a proper subset that is countable. Call it $C$ and label its elements $c_1,c_2dots$.
Then we can construct a bijection $A rightarrow Asetminus {c_1}$. The function is defined by $f(x)=x$ if $x$ is not in $C$ and $f(c_n)=c_{n+1}$
Now in order to show the countable subset exists just build it with induction.
answered Dec 11 '18 at 21:48
Jorge Fernández
75.1k1190191
add a comment |
The usual proof uses the fact that $A$ has a proper subset that is countable. Call it $C$ and label its elements $c_1,c_2dots$.
Then we can construct a bijection $A rightarrow Asetminus {c_1}$. The function is defined by $f(x)=x$ if $x$ is not in $C$ and $f(c_n)=c_{n+1}$
Now in order to show the countable subset exists just build it with induction.
answered Dec 11 '18 at 21:48
Jorge Fernández
75.1k1190191
add a comment |
The usual proof uses the fact that $A$ has a proper subset that is countable. Call it $C$ and label its elements $c_1,c_2dots$.
Then we can construct a bijection $A rightarrow Asetminus {c_1}$. The function is defined by $f(x)=x$ if $x$ is not in $C$ and $f(c_n)=c_{n+1}$
Now in order to show the countable subset exists just build it with induction.
answered Dec 11 '18 at 21:48
Jorge Fernández
75.1k1190191
The usual proof uses the fact that $A$ has a proper subset that is countable. Call it $C$ and label its elements $c_1,c_2dots$.
Then we can construct a bijection $A rightarrow Asetminus {c_1}$. The function is defined by $f(x)=x$ if $x$ is not in $C$ and $f(c_n)=c_{n+1}$
Now in order to show the countable subset exists just build it with induction.
answered Dec 11 '18 at 21:48
Jorge Fernández
75.1k1190191
answered Dec 11 '18 at 21:48
Jorge Fernández
75.1k1190191
answered Dec 11 '18 at 21:48
Jorge Fernández
75.1k1190191
answered Dec 11 '18 at 21:48
Jorge Fernández
75.1k1190191
75.1k1190191
add a comment |
add a comment |
Thanks for warning us not to use the axiom of choice, since that makes for such an easy proof of a countably infinite subset (which is the crux of the problem) one could be forgiven for not knowing a choice-free strategy to prove the same.
If $A$ is infinite $Bbb N$ can either be injected or surjected to $A$, respectively implying $A$ has an infinite subset or $A$ is countable. In the latter case $A$ is countably infinite and can be bijected with $Bbb N$, so either way $A$ has a subset we can biject with $Bbb N$, say ${f(n)|ninBbb N}$.
Finally, $B:=Abackslash{f(0)}$ bijects with $A$; in the $Bto A$ direction send $f(n)$ to $f(n-1)$, or any other element of $B$ to itself.
answered Dec 11 '18 at 21:48
J.G.
23.2k22137
3
Isn't the OP's statement "Every infinite set is Dedekind-infinite", which requires some form of choice?
– eyeballfrog
Dec 11 '18 at 21:55
@eyeballfrog: That depends on the choice of definition of infinite...
– Asaf Karagila♦
Dec 12 '18 at 0:05
After having read the definition of a Dedekind-infinite set, I believe that is what I mean to use as the definition of infinite.
– childishsadbino
Dec 12 '18 at 0:18
add a comment |
Thanks for warning us not to use the axiom of choice, since that makes for such an easy proof of a countably infinite subset (which is the crux of the problem) one could be forgiven for not knowing a choice-free strategy to prove the same.
If $A$ is infinite $Bbb N$ can either be injected or surjected to $A$, respectively implying $A$ has an infinite subset or $A$ is countable. In the latter case $A$ is countably infinite and can be bijected with $Bbb N$, so either way $A$ has a subset we can biject with $Bbb N$, say ${f(n)|ninBbb N}$.
Finally, $B:=Abackslash{f(0)}$ bijects with $A$; in the $Bto A$ direction send $f(n)$ to $f(n-1)$, or any other element of $B$ to itself.
answered Dec 11 '18 at 21:48
J.G.
23.2k22137
3
Isn't the OP's statement "Every infinite set is Dedekind-infinite", which requires some form of choice?
– eyeballfrog
Dec 11 '18 at 21:55
@eyeballfrog: That depends on the choice of definition of infinite...
– Asaf Karagila♦
Dec 12 '18 at 0:05
After having read the definition of a Dedekind-infinite set, I believe that is what I mean to use as the definition of infinite.
– childishsadbino
Dec 12 '18 at 0:18
add a comment |
Thanks for warning us not to use the axiom of choice, since that makes for such an easy proof of a countably infinite subset (which is the crux of the problem) one could be forgiven for not knowing a choice-free strategy to prove the same.
If $A$ is infinite $Bbb N$ can either be injected or surjected to $A$, respectively implying $A$ has an infinite subset or $A$ is countable. In the latter case $A$ is countably infinite and can be bijected with $Bbb N$, so either way $A$ has a subset we can biject with $Bbb N$, say ${f(n)|ninBbb N}$.
Finally, $B:=Abackslash{f(0)}$ bijects with $A$; in the $Bto A$ direction send $f(n)$ to $f(n-1)$, or any other element of $B$ to itself.
answered Dec 11 '18 at 21:48
J.G.
23.2k22137
Thanks for warning us not to use the axiom of choice, since that makes for such an easy proof of a countably infinite subset (which is the crux of the problem) one could be forgiven for not knowing a choice-free strategy to prove the same.
If $A$ is infinite $Bbb N$ can either be injected or surjected to $A$, respectively implying $A$ has an infinite subset or $A$ is countable. In the latter case $A$ is countably infinite and can be bijected with $Bbb N$, so either way $A$ has a subset we can biject with $Bbb N$, say ${f(n)|ninBbb N}$.
Finally, $B:=Abackslash{f(0)}$ bijects with $A$; in the $Bto A$ direction send $f(n)$ to $f(n-1)$, or any other element of $B$ to itself.
answered Dec 11 '18 at 21:48
J.G.
23.2k22137
answered Dec 11 '18 at 21:48
J.G.
23.2k22137
answered Dec 11 '18 at 21:48
J.G.
23.2k22137
answered Dec 11 '18 at 21:48
J.G.
23.2k22137
23.2k22137
3
Isn't the OP's statement "Every infinite set is Dedekind-infinite", which requires some form of choice?
– eyeballfrog
Dec 11 '18 at 21:55
@eyeballfrog: That depends on the choice of definition of infinite...
– Asaf Karagila♦
Dec 12 '18 at 0:05
After having read the definition of a Dedekind-infinite set, I believe that is what I mean to use as the definition of infinite.
– childishsadbino
Dec 12 '18 at 0:18
add a comment |
3
Isn't the OP's statement "Every infinite set is Dedekind-infinite", which requires some form of choice?
– eyeballfrog
Dec 11 '18 at 21:55
@eyeballfrog: That depends on the choice of definition of infinite...
– Asaf Karagila♦
Dec 12 '18 at 0:05
After having read the definition of a Dedekind-infinite set, I believe that is what I mean to use as the definition of infinite.
– childishsadbino
Dec 12 '18 at 0:18
3
3
Isn't the OP's statement "Every infinite set is Dedekind-infinite", which requires some form of choice?
– eyeballfrog
Dec 11 '18 at 21:55
Isn't the OP's statement "Every infinite set is Dedekind-infinite", which requires some form of choice?
– eyeballfrog
Dec 11 '18 at 21:55
@eyeballfrog: That depends on the choice of definition of infinite...
– Asaf Karagila♦
Dec 12 '18 at 0:05
@eyeballfrog: That depends on the choice of definition of infinite...
– Asaf Karagila♦
Dec 12 '18 at 0:05
After having read the definition of a Dedekind-infinite set, I believe that is what I mean to use as the definition of infinite.
– childishsadbino
Dec 12 '18 at 0:18
After having read the definition of a Dedekind-infinite set, I believe that is what I mean to use as the definition of infinite.
– childishsadbino
Dec 12 '18 at 0:18
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3035862%2fwhen-is-a-set-infinite%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
1
Bear in mind an infinite set has both same-sized and smaller proper subsets, so you can't force a contradiction just from a proper subset being smaller.
– J.G.
Dec 11 '18 at 21:40
1
Just because choice wasn't mentioned doesn't mean it's being used or that it is necessary. Of course, you are also assuming that your definition of "infinite" is known to everyone. Seeing how you made that "NOTE" at the end, it might be wise to include your definition of "finite" and "infinite" at the end.
– Asaf Karagila♦
Dec 12 '18 at 0:04
You see I was aware of not having defined what I meant by finite or infinite, but that is precisely my issue. Infinite sets were just introduced as "not finite" in class. In other words, when we don't have a finite number of elements in the set, we called that an infinite set, so I am not entirely sure which definition of set uses which assumptions/axioms.
– childishsadbino
Dec 12 '18 at 0:12