Mixing
Is it always necessary to prove the 'iff' in both directions?
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
I have an exercise in my course, which asks to prove $A cup B = B iff A subseteq B$.
My proof is: Let $A nsubseteq B$, that is, $exists a in A : a notin B$. Then from the definition follows $a in A cup B = B$, in contradiction to the initial assertion. $square$
Usually I see that it's much more rigorous to prove $implies$, then $impliedby$, but I'm not sure, if that's only an option or a strict rule — and specifically if my proof does the job in both directions or there are some gaps that I don't recognize. My script suggests a really long 10+ lines proof using the 'both directions style', but I myself don't really see this necessity at least here.
This being said, is it always a must to prove the 'iff' in both directions?
elementary-set-theory proof-writing
asked Jul 30 at 19:02
Jørgen Solheim
203
 |Â
show 3 more comments
up vote
2
down vote
favorite
I have an exercise in my course, which asks to prove $A cup B = B iff A subseteq B$.
My proof is: Let $A nsubseteq B$, that is, $exists a in A : a notin B$. Then from the definition follows $a in A cup B = B$, in contradiction to the initial assertion. $square$
Usually I see that it's much more rigorous to prove $implies$, then $impliedby$, but I'm not sure, if that's only an option or a strict rule — and specifically if my proof does the job in both directions or there are some gaps that I don't recognize. My script suggests a really long 10+ lines proof using the 'both directions style', but I myself don't really see this necessity at least here.
This being said, is it always a must to prove the 'iff' in both directions?
elementary-set-theory proof-writing
asked Jul 30 at 19:02
Jørgen Solheim
203
5
You may prove an iff statement by proving each direction individually or in a single step by only using implications which are themselves also biconditional. Your proof however is not formed using biconditional statements and so only succeeds in proving the forward implication. The reverse implication has yet to be proven.
– JMoravitz
Jul 30 at 19:05
@JMoravitz I think your comment answers what was intended better than the existing answer, so it might be worth posting it (or similar) as an answer.
– Mark S.
Jul 30 at 19:07
Thanks! So what does exactly fail to show the reverse direction here? I've been thinking of the "then", of course, but this surely can't be only because of the word usage, can it?
– Jørgen Solheim
Jul 30 at 19:08
I'm not sure what what I see here succeeds in proving either direction. As far as I can see it assumes $Anotsubseteq B$ and somehow arrives at a contradiction. If the "somehow" checks out, that would prove $Asubseteq B$ in general, but it doesn't seem to connect it to the other side of the biimplication.
– Henning Makholm
Jul 30 at 19:12
2
@HenningMakholm is succeeds in proving $Acup B=Bimplies Asubseteq B$ via contradition by showing that if $Anotsubseteq B$ while at the same time as tacitly assuming $Acup B=B$ it follows that there is some $ain Asetminus B$ which is simultaneously in and not in $B$.
– JMoravitz
Jul 30 at 19:14
 |Â
show 3 more comments
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I have an exercise in my course, which asks to prove $A cup B = B iff A subseteq B$.
My proof is: Let $A nsubseteq B$, that is, $exists a in A : a notin B$. Then from the definition follows $a in A cup B = B$, in contradiction to the initial assertion. $square$
Usually I see that it's much more rigorous to prove $implies$, then $impliedby$, but I'm not sure, if that's only an option or a strict rule — and specifically if my proof does the job in both directions or there are some gaps that I don't recognize. My script suggests a really long 10+ lines proof using the 'both directions style', but I myself don't really see this necessity at least here.
This being said, is it always a must to prove the 'iff' in both directions?
elementary-set-theory proof-writing
asked Jul 30 at 19:02
Jørgen Solheim
203
I have an exercise in my course, which asks to prove $A cup B = B iff A subseteq B$.
My proof is: Let $A nsubseteq B$, that is, $exists a in A : a notin B$. Then from the definition follows $a in A cup B = B$, in contradiction to the initial assertion. $square$
Usually I see that it's much more rigorous to prove $implies$, then $impliedby$, but I'm not sure, if that's only an option or a strict rule — and specifically if my proof does the job in both directions or there are some gaps that I don't recognize. My script suggests a really long 10+ lines proof using the 'both directions style', but I myself don't really see this necessity at least here.
This being said, is it always a must to prove the 'iff' in both directions?
elementary-set-theory proof-writing
asked Jul 30 at 19:02
Jørgen Solheim
203
asked Jul 30 at 19:02
Jørgen Solheim
203
asked Jul 30 at 19:02
Jørgen Solheim
203
asked Jul 30 at 19:02
Jørgen Solheim
203
203
5
You may prove an iff statement by proving each direction individually or in a single step by only using implications which are themselves also biconditional. Your proof however is not formed using biconditional statements and so only succeeds in proving the forward implication. The reverse implication has yet to be proven.
– JMoravitz
Jul 30 at 19:05
@JMoravitz I think your comment answers what was intended better than the existing answer, so it might be worth posting it (or similar) as an answer.
– Mark S.
Jul 30 at 19:07
Thanks! So what does exactly fail to show the reverse direction here? I've been thinking of the "then", of course, but this surely can't be only because of the word usage, can it?
– Jørgen Solheim
Jul 30 at 19:08
I'm not sure what what I see here succeeds in proving either direction. As far as I can see it assumes $Anotsubseteq B$ and somehow arrives at a contradiction. If the "somehow" checks out, that would prove $Asubseteq B$ in general, but it doesn't seem to connect it to the other side of the biimplication.
– Henning Makholm
Jul 30 at 19:12
2
@HenningMakholm is succeeds in proving $Acup B=Bimplies Asubseteq B$ via contradition by showing that if $Anotsubseteq B$ while at the same time as tacitly assuming $Acup B=B$ it follows that there is some $ain Asetminus B$ which is simultaneously in and not in $B$.
– JMoravitz
Jul 30 at 19:14
 |Â
show 3 more comments
5
You may prove an iff statement by proving each direction individually or in a single step by only using implications which are themselves also biconditional. Your proof however is not formed using biconditional statements and so only succeeds in proving the forward implication. The reverse implication has yet to be proven.
– JMoravitz
Jul 30 at 19:05
@JMoravitz I think your comment answers what was intended better than the existing answer, so it might be worth posting it (or similar) as an answer.
– Mark S.
Jul 30 at 19:07
Thanks! So what does exactly fail to show the reverse direction here? I've been thinking of the "then", of course, but this surely can't be only because of the word usage, can it?
– Jørgen Solheim
Jul 30 at 19:08
I'm not sure what what I see here succeeds in proving either direction. As far as I can see it assumes $Anotsubseteq B$ and somehow arrives at a contradiction. If the "somehow" checks out, that would prove $Asubseteq B$ in general, but it doesn't seem to connect it to the other side of the biimplication.
– Henning Makholm
Jul 30 at 19:12
2
@HenningMakholm is succeeds in proving $Acup B=Bimplies Asubseteq B$ via contradition by showing that if $Anotsubseteq B$ while at the same time as tacitly assuming $Acup B=B$ it follows that there is some $ain Asetminus B$ which is simultaneously in and not in $B$.
– JMoravitz
Jul 30 at 19:14
5
5
You may prove an iff statement by proving each direction individually or in a single step by only using implications which are themselves also biconditional. Your proof however is not formed using biconditional statements and so only succeeds in proving the forward implication. The reverse implication has yet to be proven.
– JMoravitz
Jul 30 at 19:05
You may prove an iff statement by proving each direction individually or in a single step by only using implications which are themselves also biconditional. Your proof however is not formed using biconditional statements and so only succeeds in proving the forward implication. The reverse implication has yet to be proven.
– JMoravitz
Jul 30 at 19:05
@JMoravitz I think your comment answers what was intended better than the existing answer, so it might be worth posting it (or similar) as an answer.
– Mark S.
Jul 30 at 19:07
@JMoravitz I think your comment answers what was intended better than the existing answer, so it might be worth posting it (or similar) as an answer.
– Mark S.
Jul 30 at 19:07
Thanks! So what does exactly fail to show the reverse direction here? I've been thinking of the "then", of course, but this surely can't be only because of the word usage, can it?
– Jørgen Solheim
Jul 30 at 19:08
Thanks! So what does exactly fail to show the reverse direction here? I've been thinking of the "then", of course, but this surely can't be only because of the word usage, can it?
– Jørgen Solheim
Jul 30 at 19:08
I'm not sure what what I see here succeeds in proving either direction. As far as I can see it assumes $Anotsubseteq B$ and somehow arrives at a contradiction. If the "somehow" checks out, that would prove $Asubseteq B$ in general, but it doesn't seem to connect it to the other side of the biimplication.
– Henning Makholm
Jul 30 at 19:12
I'm not sure what what I see here succeeds in proving either direction. As far as I can see it assumes $Anotsubseteq B$ and somehow arrives at a contradiction. If the "somehow" checks out, that would prove $Asubseteq B$ in general, but it doesn't seem to connect it to the other side of the biimplication.
– Henning Makholm
Jul 30 at 19:12
2
2
@HenningMakholm is succeeds in proving $Acup B=Bimplies Asubseteq B$ via contradition by showing that if $Anotsubseteq B$ while at the same time as tacitly assuming $Acup B=B$ it follows that there is some $ain Asetminus B$ which is simultaneously in and not in $B$.
– JMoravitz
Jul 30 at 19:14
@HenningMakholm is succeeds in proving $Acup B=Bimplies Asubseteq B$ via contradition by showing that if $Anotsubseteq B$ while at the same time as tacitly assuming $Acup B=B$ it follows that there is some $ain Asetminus B$ which is simultaneously in and not in $B$.
– JMoravitz
Jul 30 at 19:14
 |Â
show 3 more comments
3 Answers
3
active
oldest
votes
up vote
3
down vote
accepted
It appears that you're trying (without making it completely clear) to prove $Acup B=B Leftrightarrow Asubseteq B$ by showing that $Acup B=B$ together with $Anotsubseteq B$ leads to a contradiction.
If you think that is a complete proof, how about this one, by the same principle:
Claim: For any integer $n>2$, $$ ntext is prime iff ntext is odd $$
Proof: Assume that $n$ is prime and that $n$ is not odd. Then $n$ is even, so $n=2k$ for some $k$. But then $2$ divides $n$, which is a contradiction with $n$ being prime, since $n>2$. $Box$
This seems to follow exactly the same logic as your proof -- namely, considering $PLeftrightarrow Q$ to be proved because I have shown that $neg Q$ and $P$ together lead to a contradiction.
But there are odd numbers that are not prime -- such as $9$ -- so the claim is not actually true.
answered Jul 30 at 19:23
Henning Makholm
225k16290516
1
This is a nice example.
– Mark Bennet
Jul 30 at 19:26
add a comment |Â
up vote
3
down vote
"iff" means it is true both ways. If you only prove one way, you haven't shown "iff".
You are supposing the right hand side false, and show that if this is so the left-hand side must be false also, giving a contradiction. So if the left-hand side is true, the right-hand side can't be false, so must be true. You have shown the forward implication.
But now you have also to show the reverse implication. Note that with sets, to prove equality you also have to prove two things - so to show $Acup B=B$ observe that if $ain B$ then $ain Acup B$ by definition of union, whence $Bsubseteq Acup B$
Suppose $Asubseteq B$ and $ain A$ then $ain B$ by the definition of a subset. And if $ain B$ then $ain B$. Now if $ain Acup B$ then in either case $ain A$ or $ain B$ then $ain B$. So $Acup Bsubseteq B$.
Since each side of the proposed equality is contained in the other, they are indeed equal.
I wrote this out in detail because of the hidden two-way implication concealed within $=$.
answered Jul 30 at 19:05
Mark Bennet
76.3k773170
add a comment |Â
up vote
0
down vote
Left to right. A $subseteq$ A $cup$ B = B.
Right to left. A squeeze proof.
B $subseteq$ A $cup$ B $subseteq$ B $cup$ B = B.
Yes, iff, if and only if, means prove both directions.
answered Jul 31 at 3:24
William Elliot
5,0722414
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
It appears that you're trying (without making it completely clear) to prove $Acup B=B Leftrightarrow Asubseteq B$ by showing that $Acup B=B$ together with $Anotsubseteq B$ leads to a contradiction.
If you think that is a complete proof, how about this one, by the same principle:
Claim: For any integer $n>2$, $$ ntext is prime iff ntext is odd $$
Proof: Assume that $n$ is prime and that $n$ is not odd. Then $n$ is even, so $n=2k$ for some $k$. But then $2$ divides $n$, which is a contradiction with $n$ being prime, since $n>2$. $Box$
This seems to follow exactly the same logic as your proof -- namely, considering $PLeftrightarrow Q$ to be proved because I have shown that $neg Q$ and $P$ together lead to a contradiction.
But there are odd numbers that are not prime -- such as $9$ -- so the claim is not actually true.
answered Jul 30 at 19:23
Henning Makholm
225k16290516
1
This is a nice example.
– Mark Bennet
Jul 30 at 19:26
add a comment |Â
up vote
3
down vote
accepted
It appears that you're trying (without making it completely clear) to prove $Acup B=B Leftrightarrow Asubseteq B$ by showing that $Acup B=B$ together with $Anotsubseteq B$ leads to a contradiction.
If you think that is a complete proof, how about this one, by the same principle:
Claim: For any integer $n>2$, $$ ntext is prime iff ntext is odd $$
Proof: Assume that $n$ is prime and that $n$ is not odd. Then $n$ is even, so $n=2k$ for some $k$. But then $2$ divides $n$, which is a contradiction with $n$ being prime, since $n>2$. $Box$
This seems to follow exactly the same logic as your proof -- namely, considering $PLeftrightarrow Q$ to be proved because I have shown that $neg Q$ and $P$ together lead to a contradiction.
But there are odd numbers that are not prime -- such as $9$ -- so the claim is not actually true.
answered Jul 30 at 19:23
Henning Makholm
225k16290516
1
This is a nice example.
– Mark Bennet
Jul 30 at 19:26
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
It appears that you're trying (without making it completely clear) to prove $Acup B=B Leftrightarrow Asubseteq B$ by showing that $Acup B=B$ together with $Anotsubseteq B$ leads to a contradiction.
If you think that is a complete proof, how about this one, by the same principle:
Claim: For any integer $n>2$, $$ ntext is prime iff ntext is odd $$
Proof: Assume that $n$ is prime and that $n$ is not odd. Then $n$ is even, so $n=2k$ for some $k$. But then $2$ divides $n$, which is a contradiction with $n$ being prime, since $n>2$. $Box$
This seems to follow exactly the same logic as your proof -- namely, considering $PLeftrightarrow Q$ to be proved because I have shown that $neg Q$ and $P$ together lead to a contradiction.
But there are odd numbers that are not prime -- such as $9$ -- so the claim is not actually true.
answered Jul 30 at 19:23
Henning Makholm
225k16290516
It appears that you're trying (without making it completely clear) to prove $Acup B=B Leftrightarrow Asubseteq B$ by showing that $Acup B=B$ together with $Anotsubseteq B$ leads to a contradiction.
If you think that is a complete proof, how about this one, by the same principle:
Claim: For any integer $n>2$, $$ ntext is prime iff ntext is odd $$
Proof: Assume that $n$ is prime and that $n$ is not odd. Then $n$ is even, so $n=2k$ for some $k$. But then $2$ divides $n$, which is a contradiction with $n$ being prime, since $n>2$. $Box$
This seems to follow exactly the same logic as your proof -- namely, considering $PLeftrightarrow Q$ to be proved because I have shown that $neg Q$ and $P$ together lead to a contradiction.
But there are odd numbers that are not prime -- such as $9$ -- so the claim is not actually true.
answered Jul 30 at 19:23
Henning Makholm
225k16290516
answered Jul 30 at 19:23
Henning Makholm
225k16290516
answered Jul 30 at 19:23
Henning Makholm
225k16290516
answered Jul 30 at 19:23
Henning Makholm
225k16290516
225k16290516
1
This is a nice example.
– Mark Bennet
Jul 30 at 19:26
add a comment |Â
1
This is a nice example.
– Mark Bennet
Jul 30 at 19:26
1
1
This is a nice example.
– Mark Bennet
Jul 30 at 19:26
This is a nice example.
– Mark Bennet
Jul 30 at 19:26
add a comment |Â
up vote
3
down vote
"iff" means it is true both ways. If you only prove one way, you haven't shown "iff".
You are supposing the right hand side false, and show that if this is so the left-hand side must be false also, giving a contradiction. So if the left-hand side is true, the right-hand side can't be false, so must be true. You have shown the forward implication.
But now you have also to show the reverse implication. Note that with sets, to prove equality you also have to prove two things - so to show $Acup B=B$ observe that if $ain B$ then $ain Acup B$ by definition of union, whence $Bsubseteq Acup B$
Suppose $Asubseteq B$ and $ain A$ then $ain B$ by the definition of a subset. And if $ain B$ then $ain B$. Now if $ain Acup B$ then in either case $ain A$ or $ain B$ then $ain B$. So $Acup Bsubseteq B$.
Since each side of the proposed equality is contained in the other, they are indeed equal.
I wrote this out in detail because of the hidden two-way implication concealed within $=$.
answered Jul 30 at 19:05
Mark Bennet
76.3k773170
add a comment |Â
up vote
3
down vote
"iff" means it is true both ways. If you only prove one way, you haven't shown "iff".
You are supposing the right hand side false, and show that if this is so the left-hand side must be false also, giving a contradiction. So if the left-hand side is true, the right-hand side can't be false, so must be true. You have shown the forward implication.
But now you have also to show the reverse implication. Note that with sets, to prove equality you also have to prove two things - so to show $Acup B=B$ observe that if $ain B$ then $ain Acup B$ by definition of union, whence $Bsubseteq Acup B$
Suppose $Asubseteq B$ and $ain A$ then $ain B$ by the definition of a subset. And if $ain B$ then $ain B$. Now if $ain Acup B$ then in either case $ain A$ or $ain B$ then $ain B$. So $Acup Bsubseteq B$.
Since each side of the proposed equality is contained in the other, they are indeed equal.
I wrote this out in detail because of the hidden two-way implication concealed within $=$.
answered Jul 30 at 19:05
Mark Bennet
76.3k773170
add a comment |Â
up vote
3
down vote
up vote
3
down vote
"iff" means it is true both ways. If you only prove one way, you haven't shown "iff".
You are supposing the right hand side false, and show that if this is so the left-hand side must be false also, giving a contradiction. So if the left-hand side is true, the right-hand side can't be false, so must be true. You have shown the forward implication.
But now you have also to show the reverse implication. Note that with sets, to prove equality you also have to prove two things - so to show $Acup B=B$ observe that if $ain B$ then $ain Acup B$ by definition of union, whence $Bsubseteq Acup B$
Suppose $Asubseteq B$ and $ain A$ then $ain B$ by the definition of a subset. And if $ain B$ then $ain B$. Now if $ain Acup B$ then in either case $ain A$ or $ain B$ then $ain B$. So $Acup Bsubseteq B$.
Since each side of the proposed equality is contained in the other, they are indeed equal.
I wrote this out in detail because of the hidden two-way implication concealed within $=$.
answered Jul 30 at 19:05
Mark Bennet
76.3k773170
"iff" means it is true both ways. If you only prove one way, you haven't shown "iff".
You are supposing the right hand side false, and show that if this is so the left-hand side must be false also, giving a contradiction. So if the left-hand side is true, the right-hand side can't be false, so must be true. You have shown the forward implication.
But now you have also to show the reverse implication. Note that with sets, to prove equality you also have to prove two things - so to show $Acup B=B$ observe that if $ain B$ then $ain Acup B$ by definition of union, whence $Bsubseteq Acup B$
Suppose $Asubseteq B$ and $ain A$ then $ain B$ by the definition of a subset. And if $ain B$ then $ain B$. Now if $ain Acup B$ then in either case $ain A$ or $ain B$ then $ain B$. So $Acup Bsubseteq B$.
Since each side of the proposed equality is contained in the other, they are indeed equal.
I wrote this out in detail because of the hidden two-way implication concealed within $=$.
answered Jul 30 at 19:05
Mark Bennet
76.3k773170
edited Jul 30 at 19:25
answered Jul 30 at 19:05
Mark Bennet
76.3k773170
answered Jul 30 at 19:05
Mark Bennet
76.3k773170
answered Jul 30 at 19:05
Mark Bennet
76.3k773170
76.3k773170
add a comment |Â
add a comment |Â
up vote
0
down vote
Left to right. A $subseteq$ A $cup$ B = B.
Right to left. A squeeze proof.
B $subseteq$ A $cup$ B $subseteq$ B $cup$ B = B.
Yes, iff, if and only if, means prove both directions.
answered Jul 31 at 3:24
William Elliot
5,0722414
add a comment |Â
up vote
0
down vote
Left to right. A $subseteq$ A $cup$ B = B.
Right to left. A squeeze proof.
B $subseteq$ A $cup$ B $subseteq$ B $cup$ B = B.
Yes, iff, if and only if, means prove both directions.
answered Jul 31 at 3:24
William Elliot
5,0722414
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Left to right. A $subseteq$ A $cup$ B = B.
Right to left. A squeeze proof.
B $subseteq$ A $cup$ B $subseteq$ B $cup$ B = B.
Yes, iff, if and only if, means prove both directions.
answered Jul 31 at 3:24
William Elliot
5,0722414
Left to right. A $subseteq$ A $cup$ B = B.
Right to left. A squeeze proof.
B $subseteq$ A $cup$ B $subseteq$ B $cup$ B = B.
Yes, iff, if and only if, means prove both directions.
answered Jul 31 at 3:24
William Elliot
5,0722414
answered Jul 31 at 3:24
William Elliot
5,0722414
answered Jul 31 at 3:24
William Elliot
5,0722414
answered Jul 31 at 3:24
William Elliot
5,0722414
5,0722414
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2867320%2fis-it-always-necessary-to-prove-the-iff-in-both-directions%23new-answer', 'question_page');
);
Post as a guest
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
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
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
5
You may prove an iff statement by proving each direction individually or in a single step by only using implications which are themselves also biconditional. Your proof however is not formed using biconditional statements and so only succeeds in proving the forward implication. The reverse implication has yet to be proven.
– JMoravitz
Jul 30 at 19:05
@JMoravitz I think your comment answers what was intended better than the existing answer, so it might be worth posting it (or similar) as an answer.
– Mark S.
Jul 30 at 19:07
Thanks! So what does exactly fail to show the reverse direction here? I've been thinking of the "then", of course, but this surely can't be only because of the word usage, can it?
– Jørgen Solheim
Jul 30 at 19:08
I'm not sure what what I see here succeeds in proving either direction. As far as I can see it assumes $Anotsubseteq B$ and somehow arrives at a contradiction. If the "somehow" checks out, that would prove $Asubseteq B$ in general, but it doesn't seem to connect it to the other side of the biimplication.
– Henning Makholm
Jul 30 at 19:12
2
@HenningMakholm is succeeds in proving $Acup B=Bimplies Asubseteq B$ via contradition by showing that if $Anotsubseteq B$ while at the same time as tacitly assuming $Acup B=B$ it follows that there is some $ain Asetminus B$ which is simultaneously in and not in $B$.
– JMoravitz
Jul 30 at 19:14