Relating induction proof to Cantor's Theorem
up vote
-1
down vote
favorite
How would a proof by induction to show that $n < 2^n$ for all $n in ℤ$ be related to showing Cantor's Theorem for finite sets?
I have the proof completed however I don't quite see the relation between the two. I understand that Cantor's Theorem states that the power set of any given set will have a greater cardinality than that of the given set.
All explanations are much appreciated thank you.
discrete-mathematics
edited Dec 5 at 13:24
Math Girl
626318
asked Dec 5 at 13:18
Zdravstvuyte94
355
add a comment |
up vote
-1
down vote
favorite
How would a proof by induction to show that $n < 2^n$ for all $n in ℤ$ be related to showing Cantor's Theorem for finite sets?
I have the proof completed however I don't quite see the relation between the two. I understand that Cantor's Theorem states that the power set of any given set will have a greater cardinality than that of the given set.
All explanations are much appreciated thank you.
discrete-mathematics
edited Dec 5 at 13:24
Math Girl
626318
asked Dec 5 at 13:18
Zdravstvuyte94
355
1
It's a combinatorial fact the for a set of $n$ elements, its power set has $2^n$ elements.
– freakish
Dec 5 at 13:27
Appreciate it! I really was not using my head for this haha.
– Zdravstvuyte94
Dec 5 at 13:37
add a comment |
up vote
-1
down vote
favorite
up vote
-1
down vote
favorite
How would a proof by induction to show that $n < 2^n$ for all $n in ℤ$ be related to showing Cantor's Theorem for finite sets?
I have the proof completed however I don't quite see the relation between the two. I understand that Cantor's Theorem states that the power set of any given set will have a greater cardinality than that of the given set.
All explanations are much appreciated thank you.
discrete-mathematics
edited Dec 5 at 13:24
Math Girl
626318
asked Dec 5 at 13:18
Zdravstvuyte94
355
How would a proof by induction to show that $n < 2^n$ for all $n in ℤ$ be related to showing Cantor's Theorem for finite sets?
I have the proof completed however I don't quite see the relation between the two. I understand that Cantor's Theorem states that the power set of any given set will have a greater cardinality than that of the given set.
All explanations are much appreciated thank you.
discrete-mathematics
discrete-mathematics
edited Dec 5 at 13:24
Math Girl
626318
asked Dec 5 at 13:18
Zdravstvuyte94
355
edited Dec 5 at 13:24
Math Girl
626318
asked Dec 5 at 13:18
Zdravstvuyte94
355
edited Dec 5 at 13:24
Math Girl
626318
edited Dec 5 at 13:24
Math Girl
626318
edited Dec 5 at 13:24
Math Girl
626318
626318
asked Dec 5 at 13:18
Zdravstvuyte94
355
asked Dec 5 at 13:18
Zdravstvuyte94
355
asked Dec 5 at 13:18
Zdravstvuyte94
355
355
1
It's a combinatorial fact the for a set of $n$ elements, its power set has $2^n$ elements.
– freakish
Dec 5 at 13:27
Appreciate it! I really was not using my head for this haha.
– Zdravstvuyte94
Dec 5 at 13:37
add a comment |
1
It's a combinatorial fact the for a set of $n$ elements, its power set has $2^n$ elements.
– freakish
Dec 5 at 13:27
Appreciate it! I really was not using my head for this haha.
– Zdravstvuyte94
Dec 5 at 13:37
1
1
It's a combinatorial fact the for a set of $n$ elements, its power set has $2^n$ elements.
– freakish
Dec 5 at 13:27
It's a combinatorial fact the for a set of $n$ elements, its power set has $2^n$ elements.
– freakish
Dec 5 at 13:27
Appreciate it! I really was not using my head for this haha.
– Zdravstvuyte94
Dec 5 at 13:37
Appreciate it! I really was not using my head for this haha.
– Zdravstvuyte94
Dec 5 at 13:37
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
If a finite set $S$ has cardinality $n,$ what is the cardinality of the power set of $S$?
answered Dec 5 at 13:25
David K
52.2k340115
Oh, shoot I can't believe I didn't realize this, I must have been thinking of something else. Thank you so much!
– Zdravstvuyte94
Dec 5 at 13:37
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',
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%2f3027055%2frelating-induction-proof-to-cantors-theorem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
If a finite set $S$ has cardinality $n,$ what is the cardinality of the power set of $S$?
answered Dec 5 at 13:25
David K
52.2k340115
Oh, shoot I can't believe I didn't realize this, I must have been thinking of something else. Thank you so much!
– Zdravstvuyte94
Dec 5 at 13:37
add a comment |
up vote
1
down vote
accepted
If a finite set $S$ has cardinality $n,$ what is the cardinality of the power set of $S$?
answered Dec 5 at 13:25
David K
52.2k340115
Oh, shoot I can't believe I didn't realize this, I must have been thinking of something else. Thank you so much!
– Zdravstvuyte94
Dec 5 at 13:37
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
If a finite set $S$ has cardinality $n,$ what is the cardinality of the power set of $S$?
answered Dec 5 at 13:25
David K
52.2k340115
If a finite set $S$ has cardinality $n,$ what is the cardinality of the power set of $S$?
answered Dec 5 at 13:25
David K
52.2k340115
answered Dec 5 at 13:25
David K
52.2k340115
answered Dec 5 at 13:25
David K
52.2k340115
answered Dec 5 at 13:25
David K
52.2k340115
52.2k340115
Oh, shoot I can't believe I didn't realize this, I must have been thinking of something else. Thank you so much!
– Zdravstvuyte94
Dec 5 at 13:37
add a comment |
Oh, shoot I can't believe I didn't realize this, I must have been thinking of something else. Thank you so much!
– Zdravstvuyte94
Dec 5 at 13:37
Oh, shoot I can't believe I didn't realize this, I must have been thinking of something else. Thank you so much!
– Zdravstvuyte94
Dec 5 at 13:37
Oh, shoot I can't believe I didn't realize this, I must have been thinking of something else. Thank you so much!
– Zdravstvuyte94
Dec 5 at 13:37
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%2f3027055%2frelating-induction-proof-to-cantors-theorem%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
It's a combinatorial fact the for a set of $n$ elements, its power set has $2^n$ elements.
– freakish
Dec 5 at 13:27
Appreciate it! I really was not using my head for this haha.
– Zdravstvuyte94
Dec 5 at 13:37