Union of two finite sets is finite [closed]
$begingroup$
§7.3 #1
Let $A$ and $B$ be a pair of disjoint finite sets. Use induction to prove that if $A approx m$ and $B approx n$, then $Acup B approx m+n$.
Conclude that the union of two finite sets is finite.
This problem is from Pinter's A Book of Set Theory.
please help
elementary-set-theory
edited Dec 17 '18 at 6:08
Bungo
13.7k22148
asked Dec 17 '18 at 6:07
math909math909
31
$endgroup$
closed as off-topic by Ben, user21820, Leila, GNUSupporter 8964民主女神 地下教會, Adrian Keister Dec 17 '18 at 15:08
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Ben, user21820, Leila, GNUSupporter 8964民主女神 地下教會, Adrian Keister
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
§7.3 #1
Let $A$ and $B$ be a pair of disjoint finite sets. Use induction to prove that if $A approx m$ and $B approx n$, then $Acup B approx m+n$.
Conclude that the union of two finite sets is finite.
This problem is from Pinter's A Book of Set Theory.
please help
elementary-set-theory
edited Dec 17 '18 at 6:08
Bungo
13.7k22148
asked Dec 17 '18 at 6:07
math909math909
31
$endgroup$
closed as off-topic by Ben, user21820, Leila, GNUSupporter 8964民主女神 地下教會, Adrian Keister Dec 17 '18 at 15:08
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Ben, user21820, Leila, GNUSupporter 8964民主女神 地下教會, Adrian Keister
If this question can be reworded to fit the rules in the help center, please edit the question.
1
$begingroup$
Map the elements of $Acup B$ as: ${1,2,cdots ,m}$ to the elements of $A$ and the ${m+1,m+2,cdots ,m+n}$ to the elements of $B$.
$endgroup$
– Yadati Kiran
Dec 17 '18 at 6:37
add a comment |
$begingroup$
§7.3 #1
Let $A$ and $B$ be a pair of disjoint finite sets. Use induction to prove that if $A approx m$ and $B approx n$, then $Acup B approx m+n$.
Conclude that the union of two finite sets is finite.
This problem is from Pinter's A Book of Set Theory.
please help
elementary-set-theory
edited Dec 17 '18 at 6:08
Bungo
13.7k22148
asked Dec 17 '18 at 6:07
math909math909
31
$endgroup$
§7.3 #1
Let $A$ and $B$ be a pair of disjoint finite sets. Use induction to prove that if $A approx m$ and $B approx n$, then $Acup B approx m+n$.
Conclude that the union of two finite sets is finite.
This problem is from Pinter's A Book of Set Theory.
please help
elementary-set-theory
elementary-set-theory
edited Dec 17 '18 at 6:08
Bungo
13.7k22148
asked Dec 17 '18 at 6:07
math909math909
31
edited Dec 17 '18 at 6:08
Bungo
13.7k22148
asked Dec 17 '18 at 6:07
math909math909
31
edited Dec 17 '18 at 6:08
Bungo
13.7k22148
edited Dec 17 '18 at 6:08
Bungo
13.7k22148
edited Dec 17 '18 at 6:08
Bungo
13.7k22148
13.7k22148
asked Dec 17 '18 at 6:07
math909math909
31
asked Dec 17 '18 at 6:07
math909math909
31
asked Dec 17 '18 at 6:07
math909math909
31
31
closed as off-topic by Ben, user21820, Leila, GNUSupporter 8964民主女神 地下教會, Adrian Keister Dec 17 '18 at 15:08
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Ben, user21820, Leila, GNUSupporter 8964民主女神 地下教會, Adrian Keister
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by Ben, user21820, Leila, GNUSupporter 8964民主女神 地下教會, Adrian Keister Dec 17 '18 at 15:08
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Ben, user21820, Leila, GNUSupporter 8964民主女神 地下教會, Adrian Keister
If this question can be reworded to fit the rules in the help center, please edit the question.
1
$begingroup$
Map the elements of $Acup B$ as: ${1,2,cdots ,m}$ to the elements of $A$ and the ${m+1,m+2,cdots ,m+n}$ to the elements of $B$.
$endgroup$
– Yadati Kiran
Dec 17 '18 at 6:37
add a comment |
1
$begingroup$
Map the elements of $Acup B$ as: ${1,2,cdots ,m}$ to the elements of $A$ and the ${m+1,m+2,cdots ,m+n}$ to the elements of $B$.
$endgroup$
– Yadati Kiran
Dec 17 '18 at 6:37
1
1
$begingroup$
Map the elements of $Acup B$ as: ${1,2,cdots ,m}$ to the elements of $A$ and the ${m+1,m+2,cdots ,m+n}$ to the elements of $B$.
$endgroup$
– Yadati Kiran
Dec 17 '18 at 6:37
$begingroup$
Map the elements of $Acup B$ as: ${1,2,cdots ,m}$ to the elements of $A$ and the ${m+1,m+2,cdots ,m+n}$ to the elements of $B$.
$endgroup$
– Yadati Kiran
Dec 17 '18 at 6:37
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
If either $A$ or $B$ is empty, answer is clear. So let $A$ and $B$ be non empty, that is $m, n geq 1$. We will fix $m$ and use induction on $n$. We have map from $A$ to $
lbrace 1,2,3 ldots m rbrace $.
Base case $n=1$: $B$ has 1 element disjoint from $A$, map this element to $m+1$, and thus we get a map from $Acup B$ to $
lbrace 1,2,3 ldots m+1 rbrace $.
Assume the statement is true for any set (disjoint with $A$) with $n$ elements, now we need to prove for $n+1$. Split $B$ into two sets one with $n$ elements and other with 1 element. I will leave the conclusion for you.
answered Dec 17 '18 at 8:07
1.4142121.414212
507
$endgroup$
1
$begingroup$
If the answer for the empty set is clear, that is a good reason to use that as base case, instead of treating it as special case and starting with the base case $1$. Unless the logic used in the induction step fails for $0to1$, of course, but that's not the case here.
$endgroup$
– celtschk
Dec 17 '18 at 8:43
$begingroup$
Yes. That is correct. The mind always start with $n=1$. But it is good that you mentioned "unless the logic used in the induction step fails for $0 rightarrow 1$".
$endgroup$
– 1.414212
Dec 17 '18 at 8:59
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
If either $A$ or $B$ is empty, answer is clear. So let $A$ and $B$ be non empty, that is $m, n geq 1$. We will fix $m$ and use induction on $n$. We have map from $A$ to $
lbrace 1,2,3 ldots m rbrace $.
Base case $n=1$: $B$ has 1 element disjoint from $A$, map this element to $m+1$, and thus we get a map from $Acup B$ to $
lbrace 1,2,3 ldots m+1 rbrace $.
Assume the statement is true for any set (disjoint with $A$) with $n$ elements, now we need to prove for $n+1$. Split $B$ into two sets one with $n$ elements and other with 1 element. I will leave the conclusion for you.
answered Dec 17 '18 at 8:07
1.4142121.414212
507
$endgroup$
1
$begingroup$
If the answer for the empty set is clear, that is a good reason to use that as base case, instead of treating it as special case and starting with the base case $1$. Unless the logic used in the induction step fails for $0to1$, of course, but that's not the case here.
$endgroup$
– celtschk
Dec 17 '18 at 8:43
$begingroup$
Yes. That is correct. The mind always start with $n=1$. But it is good that you mentioned "unless the logic used in the induction step fails for $0 rightarrow 1$".
$endgroup$
– 1.414212
Dec 17 '18 at 8:59
add a comment |
$begingroup$
If either $A$ or $B$ is empty, answer is clear. So let $A$ and $B$ be non empty, that is $m, n geq 1$. We will fix $m$ and use induction on $n$. We have map from $A$ to $
lbrace 1,2,3 ldots m rbrace $.
Base case $n=1$: $B$ has 1 element disjoint from $A$, map this element to $m+1$, and thus we get a map from $Acup B$ to $
lbrace 1,2,3 ldots m+1 rbrace $.
Assume the statement is true for any set (disjoint with $A$) with $n$ elements, now we need to prove for $n+1$. Split $B$ into two sets one with $n$ elements and other with 1 element. I will leave the conclusion for you.
answered Dec 17 '18 at 8:07
1.4142121.414212
507
$endgroup$
1
$begingroup$
If the answer for the empty set is clear, that is a good reason to use that as base case, instead of treating it as special case and starting with the base case $1$. Unless the logic used in the induction step fails for $0to1$, of course, but that's not the case here.
$endgroup$
– celtschk
Dec 17 '18 at 8:43
$begingroup$
Yes. That is correct. The mind always start with $n=1$. But it is good that you mentioned "unless the logic used in the induction step fails for $0 rightarrow 1$".
$endgroup$
– 1.414212
Dec 17 '18 at 8:59
add a comment |
$begingroup$
If either $A$ or $B$ is empty, answer is clear. So let $A$ and $B$ be non empty, that is $m, n geq 1$. We will fix $m$ and use induction on $n$. We have map from $A$ to $
lbrace 1,2,3 ldots m rbrace $.
Base case $n=1$: $B$ has 1 element disjoint from $A$, map this element to $m+1$, and thus we get a map from $Acup B$ to $
lbrace 1,2,3 ldots m+1 rbrace $.
Assume the statement is true for any set (disjoint with $A$) with $n$ elements, now we need to prove for $n+1$. Split $B$ into two sets one with $n$ elements and other with 1 element. I will leave the conclusion for you.
answered Dec 17 '18 at 8:07
1.4142121.414212
507
$endgroup$
If either $A$ or $B$ is empty, answer is clear. So let $A$ and $B$ be non empty, that is $m, n geq 1$. We will fix $m$ and use induction on $n$. We have map from $A$ to $
lbrace 1,2,3 ldots m rbrace $.
Base case $n=1$: $B$ has 1 element disjoint from $A$, map this element to $m+1$, and thus we get a map from $Acup B$ to $
lbrace 1,2,3 ldots m+1 rbrace $.
Assume the statement is true for any set (disjoint with $A$) with $n$ elements, now we need to prove for $n+1$. Split $B$ into two sets one with $n$ elements and other with 1 element. I will leave the conclusion for you.
answered Dec 17 '18 at 8:07
1.4142121.414212
507
answered Dec 17 '18 at 8:07
1.4142121.414212
507
answered Dec 17 '18 at 8:07
1.4142121.414212
507
answered Dec 17 '18 at 8:07
1.4142121.414212
507
507
1
$begingroup$
If the answer for the empty set is clear, that is a good reason to use that as base case, instead of treating it as special case and starting with the base case $1$. Unless the logic used in the induction step fails for $0to1$, of course, but that's not the case here.
$endgroup$
– celtschk
Dec 17 '18 at 8:43
$begingroup$
Yes. That is correct. The mind always start with $n=1$. But it is good that you mentioned "unless the logic used in the induction step fails for $0 rightarrow 1$".
$endgroup$
– 1.414212
Dec 17 '18 at 8:59
add a comment |
1
$begingroup$
If the answer for the empty set is clear, that is a good reason to use that as base case, instead of treating it as special case and starting with the base case $1$. Unless the logic used in the induction step fails for $0to1$, of course, but that's not the case here.
$endgroup$
– celtschk
Dec 17 '18 at 8:43
$begingroup$
Yes. That is correct. The mind always start with $n=1$. But it is good that you mentioned "unless the logic used in the induction step fails for $0 rightarrow 1$".
$endgroup$
– 1.414212
Dec 17 '18 at 8:59
1
1
$begingroup$
If the answer for the empty set is clear, that is a good reason to use that as base case, instead of treating it as special case and starting with the base case $1$. Unless the logic used in the induction step fails for $0to1$, of course, but that's not the case here.
$endgroup$
– celtschk
Dec 17 '18 at 8:43
$begingroup$
If the answer for the empty set is clear, that is a good reason to use that as base case, instead of treating it as special case and starting with the base case $1$. Unless the logic used in the induction step fails for $0to1$, of course, but that's not the case here.
$endgroup$
– celtschk
Dec 17 '18 at 8:43
$begingroup$
Yes. That is correct. The mind always start with $n=1$. But it is good that you mentioned "unless the logic used in the induction step fails for $0 rightarrow 1$".
$endgroup$
– 1.414212
Dec 17 '18 at 8:59
$begingroup$
Yes. That is correct. The mind always start with $n=1$. But it is good that you mentioned "unless the logic used in the induction step fails for $0 rightarrow 1$".
$endgroup$
– 1.414212
Dec 17 '18 at 8:59
add a comment |
1
$begingroup$
Map the elements of $Acup B$ as: ${1,2,cdots ,m}$ to the elements of $A$ and the ${m+1,m+2,cdots ,m+n}$ to the elements of $B$.
$endgroup$
– Yadati Kiran
Dec 17 '18 at 6:37