Mixing
![A linearly independent subset of a vector space [on hold]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
Explanation of proof by contradiction
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
There's one part of an explanation of proof by contradiction that I don't understand at the moment.
Here's the explanation:
"Let's say we desire to prove the truth of a statement,M.
A proof by contradiction will proceed by initially assuming that M is false i.e assuming M'(where M' is the negation of the statement M).
We would try to deduce from this a statement N that is clearly false.
Now having deduced a statement N from M', we have shown that M'=> N.
Hence also N'=>M
Now as we know N is false, N' is true and thus M is also true.
Therefore we've proven M."
My question refers to the bold and underlined part of the explanation:
Why is it that N'=>M ?
proof-explanation
asked Jul 16 at 21:10
stochasticmrfox
216
add a comment |Â
up vote
1
down vote
favorite
There's one part of an explanation of proof by contradiction that I don't understand at the moment.
Here's the explanation:
"Let's say we desire to prove the truth of a statement,M.
A proof by contradiction will proceed by initially assuming that M is false i.e assuming M'(where M' is the negation of the statement M).
We would try to deduce from this a statement N that is clearly false.
Now having deduced a statement N from M', we have shown that M'=> N.
Hence also N'=>M
Now as we know N is false, N' is true and thus M is also true.
Therefore we've proven M."
My question refers to the bold and underlined part of the explanation:
Why is it that N'=>M ?
proof-explanation
asked Jul 16 at 21:10
stochasticmrfox
216
1
Do you know that if $p implies q$ then $q' implies p'$ ?
– Adayah
Jul 16 at 21:12
2
It is the contrapositive of $M'Rightarrow N $, and is equivalent to it.
– Bernard
Jul 16 at 21:13
1
What's your definition of "truth" at this point? Probably truth tables. Construct the truth tables for both $M'to N$ and $N'to M$.
– Git Gud
Jul 16 at 21:13
Ah I see. I do know the general idea of a contrapositive(i.e if P=>Q then Q'=>P') but didn't know how to extend it to M' => N being equivalent to N'=>M. Thank you
– stochasticmrfox
Jul 16 at 21:26
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
There's one part of an explanation of proof by contradiction that I don't understand at the moment.
Here's the explanation:
"Let's say we desire to prove the truth of a statement,M.
A proof by contradiction will proceed by initially assuming that M is false i.e assuming M'(where M' is the negation of the statement M).
We would try to deduce from this a statement N that is clearly false.
Now having deduced a statement N from M', we have shown that M'=> N.
Hence also N'=>M
Now as we know N is false, N' is true and thus M is also true.
Therefore we've proven M."
My question refers to the bold and underlined part of the explanation:
Why is it that N'=>M ?
proof-explanation
asked Jul 16 at 21:10
stochasticmrfox
216
There's one part of an explanation of proof by contradiction that I don't understand at the moment.
Here's the explanation:
"Let's say we desire to prove the truth of a statement,M.
A proof by contradiction will proceed by initially assuming that M is false i.e assuming M'(where M' is the negation of the statement M).
We would try to deduce from this a statement N that is clearly false.
Now having deduced a statement N from M', we have shown that M'=> N.
Hence also N'=>M
Now as we know N is false, N' is true and thus M is also true.
Therefore we've proven M."
My question refers to the bold and underlined part of the explanation:
Why is it that N'=>M ?
proof-explanation
asked Jul 16 at 21:10
stochasticmrfox
216
asked Jul 16 at 21:10
stochasticmrfox
216
asked Jul 16 at 21:10
stochasticmrfox
216
asked Jul 16 at 21:10
stochasticmrfox
216
216
1
Do you know that if $p implies q$ then $q' implies p'$ ?
– Adayah
Jul 16 at 21:12
2
It is the contrapositive of $M'Rightarrow N $, and is equivalent to it.
– Bernard
Jul 16 at 21:13
1
What's your definition of "truth" at this point? Probably truth tables. Construct the truth tables for both $M'to N$ and $N'to M$.
– Git Gud
Jul 16 at 21:13
Ah I see. I do know the general idea of a contrapositive(i.e if P=>Q then Q'=>P') but didn't know how to extend it to M' => N being equivalent to N'=>M. Thank you
– stochasticmrfox
Jul 16 at 21:26
add a comment |Â
1
Do you know that if $p implies q$ then $q' implies p'$ ?
– Adayah
Jul 16 at 21:12
2
It is the contrapositive of $M'Rightarrow N $, and is equivalent to it.
– Bernard
Jul 16 at 21:13
1
What's your definition of "truth" at this point? Probably truth tables. Construct the truth tables for both $M'to N$ and $N'to M$.
– Git Gud
Jul 16 at 21:13
Ah I see. I do know the general idea of a contrapositive(i.e if P=>Q then Q'=>P') but didn't know how to extend it to M' => N being equivalent to N'=>M. Thank you
– stochasticmrfox
Jul 16 at 21:26
1
1
Do you know that if $p implies q$ then $q' implies p'$ ?
– Adayah
Jul 16 at 21:12
Do you know that if $p implies q$ then $q' implies p'$ ?
– Adayah
Jul 16 at 21:12
2
2
It is the contrapositive of $M'Rightarrow N $, and is equivalent to it.
– Bernard
Jul 16 at 21:13
It is the contrapositive of $M'Rightarrow N $, and is equivalent to it.
– Bernard
Jul 16 at 21:13
1
1
What's your definition of "truth" at this point? Probably truth tables. Construct the truth tables for both $M'to N$ and $N'to M$.
– Git Gud
Jul 16 at 21:13
What's your definition of "truth" at this point? Probably truth tables. Construct the truth tables for both $M'to N$ and $N'to M$.
– Git Gud
Jul 16 at 21:13
Ah I see. I do know the general idea of a contrapositive(i.e if P=>Q then Q'=>P') but didn't know how to extend it to M' => N being equivalent to N'=>M. Thank you
– stochasticmrfox
Jul 16 at 21:26
Ah I see. I do know the general idea of a contrapositive(i.e if P=>Q then Q'=>P') but didn't know how to extend it to M' => N being equivalent to N'=>M. Thank you
– stochasticmrfox
Jul 16 at 21:26
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
True statements can only lead to true statements. If you had a true statement and could also derive a false statement, the concept of statements being either true or false falls apart.
Therefore this concept of proving something by contradiction works so well, if you already know (but not proven yet!) that something is true: First you assume your statement $M$ is false and then derive an impossible state $N$ from this new assumption $M'$.
Thus: $M'$ can't be true, (if it were, then $N$ would be true!). The only conclusion then is, that $N'$ must be true and therefore also $M$ must be true.
As pointed out by the others: You should look up truth tables and how negation and implication interact with another.
answered Jul 16 at 21:24
Imago
1,2101819
add a comment |Â
up vote
0
down vote
We know that $Pimplies Q$ is equivalent to
$$P' lor Q $$
or
$$(Q')' lor P'$$
which is equivalent to
$$Q' implies P'$$
answered Jul 16 at 21:22
Salahamam_ Fatima
33.6k21229
What does the symbol in between P' and Q mean?
– stochasticmrfox
Jul 16 at 21:37
@stochasticmrfox It means logical or. P' or Q.
– Salahamam_ Fatima
Jul 16 at 21:46
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
True statements can only lead to true statements. If you had a true statement and could also derive a false statement, the concept of statements being either true or false falls apart.
Therefore this concept of proving something by contradiction works so well, if you already know (but not proven yet!) that something is true: First you assume your statement $M$ is false and then derive an impossible state $N$ from this new assumption $M'$.
Thus: $M'$ can't be true, (if it were, then $N$ would be true!). The only conclusion then is, that $N'$ must be true and therefore also $M$ must be true.
As pointed out by the others: You should look up truth tables and how negation and implication interact with another.
answered Jul 16 at 21:24
Imago
1,2101819
add a comment |Â
up vote
1
down vote
True statements can only lead to true statements. If you had a true statement and could also derive a false statement, the concept of statements being either true or false falls apart.
Therefore this concept of proving something by contradiction works so well, if you already know (but not proven yet!) that something is true: First you assume your statement $M$ is false and then derive an impossible state $N$ from this new assumption $M'$.
Thus: $M'$ can't be true, (if it were, then $N$ would be true!). The only conclusion then is, that $N'$ must be true and therefore also $M$ must be true.
As pointed out by the others: You should look up truth tables and how negation and implication interact with another.
answered Jul 16 at 21:24
Imago
1,2101819
add a comment |Â
up vote
1
down vote
up vote
1
down vote
True statements can only lead to true statements. If you had a true statement and could also derive a false statement, the concept of statements being either true or false falls apart.
Therefore this concept of proving something by contradiction works so well, if you already know (but not proven yet!) that something is true: First you assume your statement $M$ is false and then derive an impossible state $N$ from this new assumption $M'$.
Thus: $M'$ can't be true, (if it were, then $N$ would be true!). The only conclusion then is, that $N'$ must be true and therefore also $M$ must be true.
As pointed out by the others: You should look up truth tables and how negation and implication interact with another.
answered Jul 16 at 21:24
Imago
1,2101819
True statements can only lead to true statements. If you had a true statement and could also derive a false statement, the concept of statements being either true or false falls apart.
Therefore this concept of proving something by contradiction works so well, if you already know (but not proven yet!) that something is true: First you assume your statement $M$ is false and then derive an impossible state $N$ from this new assumption $M'$.
Thus: $M'$ can't be true, (if it were, then $N$ would be true!). The only conclusion then is, that $N'$ must be true and therefore also $M$ must be true.
As pointed out by the others: You should look up truth tables and how negation and implication interact with another.
answered Jul 16 at 21:24
Imago
1,2101819
answered Jul 16 at 21:24
Imago
1,2101819
answered Jul 16 at 21:24
Imago
1,2101819
answered Jul 16 at 21:24
Imago
1,2101819
1,2101819
add a comment |Â
add a comment |Â
up vote
0
down vote
We know that $Pimplies Q$ is equivalent to
$$P' lor Q $$
or
$$(Q')' lor P'$$
which is equivalent to
$$Q' implies P'$$
answered Jul 16 at 21:22
Salahamam_ Fatima
33.6k21229
What does the symbol in between P' and Q mean?
– stochasticmrfox
Jul 16 at 21:37
@stochasticmrfox It means logical or. P' or Q.
– Salahamam_ Fatima
Jul 16 at 21:46
add a comment |Â
up vote
0
down vote
We know that $Pimplies Q$ is equivalent to
$$P' lor Q $$
or
$$(Q')' lor P'$$
which is equivalent to
$$Q' implies P'$$
answered Jul 16 at 21:22
Salahamam_ Fatima
33.6k21229
What does the symbol in between P' and Q mean?
– stochasticmrfox
Jul 16 at 21:37
@stochasticmrfox It means logical or. P' or Q.
– Salahamam_ Fatima
Jul 16 at 21:46
add a comment |Â
up vote
0
down vote
up vote
0
down vote
We know that $Pimplies Q$ is equivalent to
$$P' lor Q $$
or
$$(Q')' lor P'$$
which is equivalent to
$$Q' implies P'$$
answered Jul 16 at 21:22
Salahamam_ Fatima
33.6k21229
We know that $Pimplies Q$ is equivalent to
$$P' lor Q $$
or
$$(Q')' lor P'$$
which is equivalent to
$$Q' implies P'$$
answered Jul 16 at 21:22
Salahamam_ Fatima
33.6k21229
answered Jul 16 at 21:22
Salahamam_ Fatima
33.6k21229
answered Jul 16 at 21:22
Salahamam_ Fatima
33.6k21229
answered Jul 16 at 21:22
Salahamam_ Fatima
33.6k21229
33.6k21229
What does the symbol in between P' and Q mean?
– stochasticmrfox
Jul 16 at 21:37
@stochasticmrfox It means logical or. P' or Q.
– Salahamam_ Fatima
Jul 16 at 21:46
add a comment |Â
What does the symbol in between P' and Q mean?
– stochasticmrfox
Jul 16 at 21:37
@stochasticmrfox It means logical or. P' or Q.
– Salahamam_ Fatima
Jul 16 at 21:46
What does the symbol in between P' and Q mean?
– stochasticmrfox
Jul 16 at 21:37
What does the symbol in between P' and Q mean?
– stochasticmrfox
Jul 16 at 21:37
@stochasticmrfox It means logical or. P' or Q.
– Salahamam_ Fatima
Jul 16 at 21:46
@stochasticmrfox It means logical or. P' or Q.
– Salahamam_ Fatima
Jul 16 at 21:46
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%2f2853862%2fexplanation-of-proof-by-contradiction%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
1
Do you know that if $p implies q$ then $q' implies p'$ ?
– Adayah
Jul 16 at 21:12
2
It is the contrapositive of $M'Rightarrow N $, and is equivalent to it.
– Bernard
Jul 16 at 21:13
1
What's your definition of "truth" at this point? Probably truth tables. Construct the truth tables for both $M'to N$ and $N'to M$.
– Git Gud
Jul 16 at 21:13
Ah I see. I do know the general idea of a contrapositive(i.e if P=>Q then Q'=>P') but didn't know how to extend it to M' => N being equivalent to N'=>M. Thank you
– stochasticmrfox
Jul 16 at 21:26