Mixing
Show that if $S$ is a finite set with n elements, then $S$ has $2^n$ subsets by using mathematical induction
$begingroup$
I don't understand this exercise of mathematical induction. I also have the answer but I still don't get it. The exercise says the following:
Use mathematical induction to show that if $S$
is a finite set with n elements, then $S$ has $2^{n}$ subsets.
And the answer is:
BASIS STEP: $P(0)$ is true, since a set with zero elements, the empty set, has exactly
$2^0 = 1$ subsets, since it has one subset, namely, itself.
INDUCTIVE STEP: Assume that $P(k)$ is true, that is, that every set with $k$ elements has $2^k$ subsets. It must be shown that under this assumption $P(k + 1)$, which is the statement that every set with $k + 1$ elements has $2^{k+1}$ subsets, must also be true.
To show this, let $T$
be a set with $k + 1$ elements. Then, it is possible to write $T = S ∪ {a}$ where $a$ is one of the elements of $T$ and $S = T - {a}$. The subsets of $T$ can be obtained in the following way. For each subset $X$ of $S$ there are exactly two subsets of $T$, namely, $X$ and $X ∪ {a}$. These constitute all the subsets of $T$ and are all distinct. Since there are $2^k$ subsets of $S$, there are $2 · 2^k$ = $2^{k+1}$ subsets of $T$.
I understand everything up to 'which is the statement that every set with k+1 elements has $2^{k+1}$ subsets, must also be true'. I know that we start by evaluating the first element P(0) to see if it's true and we try to show that P(k) is true to then show that P(k+1). But I don't get the part in which T is the union of S and {a} and so on.
Does anyone understand this? Thank you.
induction
asked Nov 22 '17 at 17:22
ArnauArnau
1009
$endgroup$
add a comment |
$begingroup$
I don't understand this exercise of mathematical induction. I also have the answer but I still don't get it. The exercise says the following:
Use mathematical induction to show that if $S$
is a finite set with n elements, then $S$ has $2^{n}$ subsets.
And the answer is:
BASIS STEP: $P(0)$ is true, since a set with zero elements, the empty set, has exactly
$2^0 = 1$ subsets, since it has one subset, namely, itself.
INDUCTIVE STEP: Assume that $P(k)$ is true, that is, that every set with $k$ elements has $2^k$ subsets. It must be shown that under this assumption $P(k + 1)$, which is the statement that every set with $k + 1$ elements has $2^{k+1}$ subsets, must also be true.
To show this, let $T$
be a set with $k + 1$ elements. Then, it is possible to write $T = S ∪ {a}$ where $a$ is one of the elements of $T$ and $S = T - {a}$. The subsets of $T$ can be obtained in the following way. For each subset $X$ of $S$ there are exactly two subsets of $T$, namely, $X$ and $X ∪ {a}$. These constitute all the subsets of $T$ and are all distinct. Since there are $2^k$ subsets of $S$, there are $2 · 2^k$ = $2^{k+1}$ subsets of $T$.
I understand everything up to 'which is the statement that every set with k+1 elements has $2^{k+1}$ subsets, must also be true'. I know that we start by evaluating the first element P(0) to see if it's true and we try to show that P(k) is true to then show that P(k+1). But I don't get the part in which T is the union of S and {a} and so on.
Does anyone understand this? Thank you.
induction
asked Nov 22 '17 at 17:22
ArnauArnau
1009
$endgroup$
$begingroup$
@quasi Yes, thank you very much.
$endgroup$
– Arnau
Nov 22 '17 at 17:34
$begingroup$
About the part $T = S cup {a}$, that's just saying that if $T$ has $k+1$ elements, then for any element $a in T$, the set $T$ is a union of a $k$ element set $S$ and ${a}$.
$endgroup$
– quasi
Nov 22 '17 at 17:36
add a comment |
$begingroup$
I don't understand this exercise of mathematical induction. I also have the answer but I still don't get it. The exercise says the following:
Use mathematical induction to show that if $S$
is a finite set with n elements, then $S$ has $2^{n}$ subsets.
And the answer is:
BASIS STEP: $P(0)$ is true, since a set with zero elements, the empty set, has exactly
$2^0 = 1$ subsets, since it has one subset, namely, itself.
INDUCTIVE STEP: Assume that $P(k)$ is true, that is, that every set with $k$ elements has $2^k$ subsets. It must be shown that under this assumption $P(k + 1)$, which is the statement that every set with $k + 1$ elements has $2^{k+1}$ subsets, must also be true.
To show this, let $T$
be a set with $k + 1$ elements. Then, it is possible to write $T = S ∪ {a}$ where $a$ is one of the elements of $T$ and $S = T - {a}$. The subsets of $T$ can be obtained in the following way. For each subset $X$ of $S$ there are exactly two subsets of $T$, namely, $X$ and $X ∪ {a}$. These constitute all the subsets of $T$ and are all distinct. Since there are $2^k$ subsets of $S$, there are $2 · 2^k$ = $2^{k+1}$ subsets of $T$.
I understand everything up to 'which is the statement that every set with k+1 elements has $2^{k+1}$ subsets, must also be true'. I know that we start by evaluating the first element P(0) to see if it's true and we try to show that P(k) is true to then show that P(k+1). But I don't get the part in which T is the union of S and {a} and so on.
Does anyone understand this? Thank you.
induction
asked Nov 22 '17 at 17:22
ArnauArnau
1009
$endgroup$
I don't understand this exercise of mathematical induction. I also have the answer but I still don't get it. The exercise says the following:
Use mathematical induction to show that if $S$
is a finite set with n elements, then $S$ has $2^{n}$ subsets.
And the answer is:
BASIS STEP: $P(0)$ is true, since a set with zero elements, the empty set, has exactly
$2^0 = 1$ subsets, since it has one subset, namely, itself.
INDUCTIVE STEP: Assume that $P(k)$ is true, that is, that every set with $k$ elements has $2^k$ subsets. It must be shown that under this assumption $P(k + 1)$, which is the statement that every set with $k + 1$ elements has $2^{k+1}$ subsets, must also be true.
To show this, let $T$
be a set with $k + 1$ elements. Then, it is possible to write $T = S ∪ {a}$ where $a$ is one of the elements of $T$ and $S = T - {a}$. The subsets of $T$ can be obtained in the following way. For each subset $X$ of $S$ there are exactly two subsets of $T$, namely, $X$ and $X ∪ {a}$. These constitute all the subsets of $T$ and are all distinct. Since there are $2^k$ subsets of $S$, there are $2 · 2^k$ = $2^{k+1}$ subsets of $T$.
I understand everything up to 'which is the statement that every set with k+1 elements has $2^{k+1}$ subsets, must also be true'. I know that we start by evaluating the first element P(0) to see if it's true and we try to show that P(k) is true to then show that P(k+1). But I don't get the part in which T is the union of S and {a} and so on.
Does anyone understand this? Thank you.
induction
induction
asked Nov 22 '17 at 17:22
ArnauArnau
1009
asked Nov 22 '17 at 17:22
ArnauArnau
1009
edited Nov 22 '17 at 18:04
Arnau
asked Nov 22 '17 at 17:22
ArnauArnau
1009
asked Nov 22 '17 at 17:22
ArnauArnau
1009
asked Nov 22 '17 at 17:22
ArnauArnau
1009
1009
$begingroup$
@quasi Yes, thank you very much.
$endgroup$
– Arnau
Nov 22 '17 at 17:34
$begingroup$
About the part $T = S cup {a}$, that's just saying that if $T$ has $k+1$ elements, then for any element $a in T$, the set $T$ is a union of a $k$ element set $S$ and ${a}$.
$endgroup$
– quasi
Nov 22 '17 at 17:36
add a comment |
$begingroup$
@quasi Yes, thank you very much.
$endgroup$
– Arnau
Nov 22 '17 at 17:34
$begingroup$
About the part $T = S cup {a}$, that's just saying that if $T$ has $k+1$ elements, then for any element $a in T$, the set $T$ is a union of a $k$ element set $S$ and ${a}$.
$endgroup$
– quasi
Nov 22 '17 at 17:36
$begingroup$
@quasi Yes, thank you very much.
$endgroup$
– Arnau
Nov 22 '17 at 17:34
$begingroup$
@quasi Yes, thank you very much.
$endgroup$
– Arnau
Nov 22 '17 at 17:34
$begingroup$
About the part $T = S cup {a}$, that's just saying that if $T$ has $k+1$ elements, then for any element $a in T$, the set $T$ is a union of a $k$ element set $S$ and ${a}$.
$endgroup$
– quasi
Nov 22 '17 at 17:36
$begingroup$
About the part $T = S cup {a}$, that's just saying that if $T$ has $k+1$ elements, then for any element $a in T$, the set $T$ is a union of a $k$ element set $S$ and ${a}$.
$endgroup$
– quasi
Nov 22 '17 at 17:36
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Let $A={Ysubset T }$ and $B=Ccup D$ where $C={Xcup {a}:Xsubset S}$ and $ D= {Xsubset S}$
$A=B$, and $C$ and $D$ are disjoint and contain the same number of elements, which is $2^k$ by induction.
answered Nov 22 '17 at 17:51
Amos QuitoAmos Quito
1163
$endgroup$
add a comment |
$begingroup$
An example might help . . .
Suppose $k = 3$.
Let $T$ be a set of $4$ elements, say $T = {a,b,c,d}$.
Then $T = S cup {a}$, where $S = {b,c,d}$ is a set of $3$ elements.
Suppose we've already shown that any set with $3$ elements has $2^3 = 8$ subsets. Thus, we know that $S$ has $8$ subsets.
Each subset of $S$ is also a subset of $T$, so $T$ has those $8$ subsets to begin with.
But for each of the $8$ subsets of $S$, there is a new subset of $T$ obtained by including the element $a$ as an additional element. That yields $8$ more subsets.
Thus, $T$ has $2^3 + 2^3 = 2cdot 2^3 = 2^4$ subsets.
answered Nov 22 '17 at 17:49
quasiquasi
36k22663
$endgroup$
add a comment |
$begingroup$
Well that is because, you will use the inductive hypotesis.
So, if you want to prove $P(k+1)$, then the set must have $k+1$ elements.
They named that set $T$
So if you take $k$ elements of $T$ and build the subset $S$ with those $k$ elements, then $T = S cup $ { $a$ } where $a$ is the element that was not among the chosen $k$
answered Jan 8 at 21:17
ZAFZAF
4357
$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%2f2532663%2fshow-that-if-s-is-a-finite-set-with-n-elements-then-s-has-2n-subsets-by%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$
Let $A={Ysubset T }$ and $B=Ccup D$ where $C={Xcup {a}:Xsubset S}$ and $ D= {Xsubset S}$
$A=B$, and $C$ and $D$ are disjoint and contain the same number of elements, which is $2^k$ by induction.
answered Nov 22 '17 at 17:51
Amos QuitoAmos Quito
1163
$endgroup$
add a comment |
$begingroup$
Let $A={Ysubset T }$ and $B=Ccup D$ where $C={Xcup {a}:Xsubset S}$ and $ D= {Xsubset S}$
$A=B$, and $C$ and $D$ are disjoint and contain the same number of elements, which is $2^k$ by induction.
answered Nov 22 '17 at 17:51
Amos QuitoAmos Quito
1163
$endgroup$
add a comment |
$begingroup$
Let $A={Ysubset T }$ and $B=Ccup D$ where $C={Xcup {a}:Xsubset S}$ and $ D= {Xsubset S}$
$A=B$, and $C$ and $D$ are disjoint and contain the same number of elements, which is $2^k$ by induction.
answered Nov 22 '17 at 17:51
Amos QuitoAmos Quito
1163
$endgroup$
Let $A={Ysubset T }$ and $B=Ccup D$ where $C={Xcup {a}:Xsubset S}$ and $ D= {Xsubset S}$
$A=B$, and $C$ and $D$ are disjoint and contain the same number of elements, which is $2^k$ by induction.
answered Nov 22 '17 at 17:51
Amos QuitoAmos Quito
1163
answered Nov 22 '17 at 17:51
Amos QuitoAmos Quito
1163
answered Nov 22 '17 at 17:51
Amos QuitoAmos Quito
1163
answered Nov 22 '17 at 17:51
Amos QuitoAmos Quito
1163
1163
add a comment |
add a comment |
$begingroup$
An example might help . . .
Suppose $k = 3$.
Let $T$ be a set of $4$ elements, say $T = {a,b,c,d}$.
Then $T = S cup {a}$, where $S = {b,c,d}$ is a set of $3$ elements.
Suppose we've already shown that any set with $3$ elements has $2^3 = 8$ subsets. Thus, we know that $S$ has $8$ subsets.
Each subset of $S$ is also a subset of $T$, so $T$ has those $8$ subsets to begin with.
But for each of the $8$ subsets of $S$, there is a new subset of $T$ obtained by including the element $a$ as an additional element. That yields $8$ more subsets.
Thus, $T$ has $2^3 + 2^3 = 2cdot 2^3 = 2^4$ subsets.
answered Nov 22 '17 at 17:49
quasiquasi
36k22663
$endgroup$
add a comment |
$begingroup$
An example might help . . .
Suppose $k = 3$.
Let $T$ be a set of $4$ elements, say $T = {a,b,c,d}$.
Then $T = S cup {a}$, where $S = {b,c,d}$ is a set of $3$ elements.
Suppose we've already shown that any set with $3$ elements has $2^3 = 8$ subsets. Thus, we know that $S$ has $8$ subsets.
Each subset of $S$ is also a subset of $T$, so $T$ has those $8$ subsets to begin with.
But for each of the $8$ subsets of $S$, there is a new subset of $T$ obtained by including the element $a$ as an additional element. That yields $8$ more subsets.
Thus, $T$ has $2^3 + 2^3 = 2cdot 2^3 = 2^4$ subsets.
answered Nov 22 '17 at 17:49
quasiquasi
36k22663
$endgroup$
add a comment |
$begingroup$
An example might help . . .
Suppose $k = 3$.
Let $T$ be a set of $4$ elements, say $T = {a,b,c,d}$.
Then $T = S cup {a}$, where $S = {b,c,d}$ is a set of $3$ elements.
Suppose we've already shown that any set with $3$ elements has $2^3 = 8$ subsets. Thus, we know that $S$ has $8$ subsets.
Each subset of $S$ is also a subset of $T$, so $T$ has those $8$ subsets to begin with.
But for each of the $8$ subsets of $S$, there is a new subset of $T$ obtained by including the element $a$ as an additional element. That yields $8$ more subsets.
Thus, $T$ has $2^3 + 2^3 = 2cdot 2^3 = 2^4$ subsets.
answered Nov 22 '17 at 17:49
quasiquasi
36k22663
$endgroup$
An example might help . . .
Suppose $k = 3$.
Let $T$ be a set of $4$ elements, say $T = {a,b,c,d}$.
Then $T = S cup {a}$, where $S = {b,c,d}$ is a set of $3$ elements.
Suppose we've already shown that any set with $3$ elements has $2^3 = 8$ subsets. Thus, we know that $S$ has $8$ subsets.
Each subset of $S$ is also a subset of $T$, so $T$ has those $8$ subsets to begin with.
But for each of the $8$ subsets of $S$, there is a new subset of $T$ obtained by including the element $a$ as an additional element. That yields $8$ more subsets.
Thus, $T$ has $2^3 + 2^3 = 2cdot 2^3 = 2^4$ subsets.
answered Nov 22 '17 at 17:49
quasiquasi
36k22663
edited Nov 22 '17 at 18:10
answered Nov 22 '17 at 17:49
quasiquasi
36k22663
answered Nov 22 '17 at 17:49
quasiquasi
36k22663
answered Nov 22 '17 at 17:49
quasiquasi
36k22663
36k22663
add a comment |
add a comment |
$begingroup$
Well that is because, you will use the inductive hypotesis.
So, if you want to prove $P(k+1)$, then the set must have $k+1$ elements.
They named that set $T$
So if you take $k$ elements of $T$ and build the subset $S$ with those $k$ elements, then $T = S cup $ { $a$ } where $a$ is the element that was not among the chosen $k$
answered Jan 8 at 21:17
ZAFZAF
4357
$endgroup$
add a comment |
$begingroup$
Well that is because, you will use the inductive hypotesis.
So, if you want to prove $P(k+1)$, then the set must have $k+1$ elements.
They named that set $T$
So if you take $k$ elements of $T$ and build the subset $S$ with those $k$ elements, then $T = S cup $ { $a$ } where $a$ is the element that was not among the chosen $k$
answered Jan 8 at 21:17
ZAFZAF
4357
$endgroup$
add a comment |
$begingroup$
Well that is because, you will use the inductive hypotesis.
So, if you want to prove $P(k+1)$, then the set must have $k+1$ elements.
They named that set $T$
So if you take $k$ elements of $T$ and build the subset $S$ with those $k$ elements, then $T = S cup $ { $a$ } where $a$ is the element that was not among the chosen $k$
answered Jan 8 at 21:17
ZAFZAF
4357
$endgroup$
Well that is because, you will use the inductive hypotesis.
So, if you want to prove $P(k+1)$, then the set must have $k+1$ elements.
They named that set $T$
So if you take $k$ elements of $T$ and build the subset $S$ with those $k$ elements, then $T = S cup $ { $a$ } where $a$ is the element that was not among the chosen $k$
answered Jan 8 at 21:17
ZAFZAF
4357
answered Jan 8 at 21:17
ZAFZAF
4357
answered Jan 8 at 21:17
ZAFZAF
4357
answered Jan 8 at 21:17
ZAFZAF
4357
4357
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%2f2532663%2fshow-that-if-s-is-a-finite-set-with-n-elements-then-s-has-2n-subsets-by%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$
@quasi Yes, thank you very much.
$endgroup$
– Arnau
Nov 22 '17 at 17:34
$begingroup$
About the part $T = S cup {a}$, that's just saying that if $T$ has $k+1$ elements, then for any element $a in T$, the set $T$ is a union of a $k$ element set $S$ and ${a}$.
$endgroup$
– quasi
Nov 22 '17 at 17:36