Proof by Contradiction to Prove Theorem that is not True
$begingroup$
Based on the following incorrect Theorem, why is this proof by contradiction not valid?
Theorem
If $x+y=10$
Then $xneq 3 text{ and } yneq 8$
Proof
Assume:
$x+y=10$
$x=3$ or $y=8$
Let $x=3$ and $y=8$
Since $x+y=3+8=11neq 10$ we have a contradiction based on the assumptions.
Based on this haven't we just proven the above theorem which we know to be incorrect. The steps I have been taught for proving something using proof by contradiction is to assume $Pland lnot Q$ which I believe that I have done correctly. Then you simply want to derive something that is not true, which I also feel that I have done ($x+yneq 10$).
So, my question is, where have I gone wrong/what is it that I am not understanding correctly?
discrete-mathematics
asked Dec 16 '18 at 0:06
Jac FrallJac Frall
174
$endgroup$
add a comment |
$begingroup$
Based on the following incorrect Theorem, why is this proof by contradiction not valid?
Theorem
If $x+y=10$
Then $xneq 3 text{ and } yneq 8$
Proof
Assume:
$x+y=10$
$x=3$ or $y=8$
Let $x=3$ and $y=8$
Since $x+y=3+8=11neq 10$ we have a contradiction based on the assumptions.
Based on this haven't we just proven the above theorem which we know to be incorrect. The steps I have been taught for proving something using proof by contradiction is to assume $Pland lnot Q$ which I believe that I have done correctly. Then you simply want to derive something that is not true, which I also feel that I have done ($x+yneq 10$).
So, my question is, where have I gone wrong/what is it that I am not understanding correctly?
discrete-mathematics
asked Dec 16 '18 at 0:06
Jac FrallJac Frall
174
$endgroup$
add a comment |
$begingroup$
Based on the following incorrect Theorem, why is this proof by contradiction not valid?
Theorem
If $x+y=10$
Then $xneq 3 text{ and } yneq 8$
Proof
Assume:
$x+y=10$
$x=3$ or $y=8$
Let $x=3$ and $y=8$
Since $x+y=3+8=11neq 10$ we have a contradiction based on the assumptions.
Based on this haven't we just proven the above theorem which we know to be incorrect. The steps I have been taught for proving something using proof by contradiction is to assume $Pland lnot Q$ which I believe that I have done correctly. Then you simply want to derive something that is not true, which I also feel that I have done ($x+yneq 10$).
So, my question is, where have I gone wrong/what is it that I am not understanding correctly?
discrete-mathematics
asked Dec 16 '18 at 0:06
Jac FrallJac Frall
174
$endgroup$
Based on the following incorrect Theorem, why is this proof by contradiction not valid?
Theorem
If $x+y=10$
Then $xneq 3 text{ and } yneq 8$
Proof
Assume:
$x+y=10$
$x=3$ or $y=8$
Let $x=3$ and $y=8$
Since $x+y=3+8=11neq 10$ we have a contradiction based on the assumptions.
Based on this haven't we just proven the above theorem which we know to be incorrect. The steps I have been taught for proving something using proof by contradiction is to assume $Pland lnot Q$ which I believe that I have done correctly. Then you simply want to derive something that is not true, which I also feel that I have done ($x+yneq 10$).
So, my question is, where have I gone wrong/what is it that I am not understanding correctly?
discrete-mathematics
discrete-mathematics
asked Dec 16 '18 at 0:06
Jac FrallJac Frall
174
asked Dec 16 '18 at 0:06
Jac FrallJac Frall
174
asked Dec 16 '18 at 0:06
Jac FrallJac Frall
174
asked Dec 16 '18 at 0:06
Jac FrallJac Frall
174
asked Dec 16 '18 at 0:06
Jac FrallJac Frall
174
174
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Yes, you have set up things correctly: Assume $x+y=10$, and then, to start the proof by Contradiction, you (correctly) assumed that it is not true that $x neq 3$ and $y neq 8$. And the latter means that $x=3$ or $y=8$. But from that, you cannot infer that $x=3$ and $y=8$, which is what you need in order to get to $x+y=11$ and thus to your contradiction.
answered Dec 16 '18 at 0:13
Bram28Bram28
63.1k44793
$endgroup$
$begingroup$
I cannot see why that is the case. It seems to me that the truth value for $x=3lor y=8$ would be true when both $x=3$ and $ y=8$?
$endgroup$
– Jac Frall
Dec 16 '18 at 0:19
$begingroup$
@JacFrall True, from $x=3 land y=8$ you can indeed infer $x=3 lor y=8$. But in order for your proof to work, you need to go the other way around: Your Proof by Contradiction goes like this: $neg (x neq 3 land y neq 8) Rightarrow (x =3 lor y=8) Rightarrow x = 3 land y=8 Rightarrow x+y=11$.
$endgroup$
– Bram28
Dec 16 '18 at 0:24
$begingroup$
Look at your proof. You assume $x=3$ or $y=8$ ... and yet on the very next line you say 'Let $x=3$ and $y=8$' ... wait! Where does that come from? Certainly not from your assumption, because from $x=3$ or $y=8$ you cannot infer $x=3$ and $y=8$. And so is this a new assumption? A second assumption? But then when that second assumption runs into a contradiction, all you u have shown is that it cannot be trrue that $x=3$ and $y=8$ ... the first assumption does not get discharged, and hence you have not shown that it cannot be true that $x=3$ or $y=8$
$endgroup$
– Bram28
Dec 16 '18 at 0:33
$begingroup$
Yes that makes much more sense now. Thank you for helping me see that it is a stronger statement and thus you cannot assume more than the initial $Pland lnot Q$
$endgroup$
– Jac Frall
Dec 16 '18 at 0:44
$begingroup$
@JacFrall Cool, glad I could help! :)
$endgroup$
– Bram28
Dec 16 '18 at 0:45
add a comment |
$begingroup$
this theorem is wrong
$P: bigg[x+y=10implies (xne 3land yne 8)bigg]iff bigg[(x=3 lor y=8)implies x+yne 10bigg]$
Suppose $x=3$, you take $y:=7$ so $x+y=10$ contradiction so your theorem is wrong
by contradiction :
$lnot P :quad x+y=10 land (x= 3lor y= 8)$
$x+y=10$ and $x=3$ we take $y:=7$, so the proposition $lnot P$ is right.
I remind you $P:(simplies t)iff (lnot slor t)$ so $lnot P :sland lnot t$
To avoid any confusion you have to add quantifier so the proposition becomes
$ P :forall (x,y)in mathbb{N}^2,bigg[x+y=10implies (xne 3land yne 8)bigg]$
So the negative is :
$lnot P : exists (x,y)in mathbb{N}^2,quad (x+y=10) land (x= 3lor y= 8)$
We only need to find one 2-tuple that satisfies the proposition, so $(x,y)=(3,7)$ fits. We conclude $lnot P$ is right thus $P$ is wrong
answered Dec 16 '18 at 0:39
StuStu
1,1881414
$endgroup$
$begingroup$
Yes, I understand that the Theorem is not True. This is why I was confused. I was showing that some obviously false theorem was true using proof by contradiction, asking for clarification.
$endgroup$
– Jac Frall
Dec 16 '18 at 0:41
$begingroup$
I added a proof by contradiction
$endgroup$
– Stu
Dec 16 '18 at 0:49
$begingroup$
I see. What confused me was I thought you could let $x=3 $ and $y=8$ in the proof by contradiction since this seems to satisfy the $x=3 lor y=8$ part of $lnot P$.
$endgroup$
– Jac Frall
Dec 16 '18 at 0:54
$begingroup$
what do you mean?
$endgroup$
– Stu
Dec 16 '18 at 1:43
$begingroup$
$forall cdots P$ and $existscdots lnot P$
$endgroup$
– Stu
Dec 16 '18 at 1:47
|
show 3 more comments
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%2f3042086%2fproof-by-contradiction-to-prove-theorem-that-is-not-true%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Yes, you have set up things correctly: Assume $x+y=10$, and then, to start the proof by Contradiction, you (correctly) assumed that it is not true that $x neq 3$ and $y neq 8$. And the latter means that $x=3$ or $y=8$. But from that, you cannot infer that $x=3$ and $y=8$, which is what you need in order to get to $x+y=11$ and thus to your contradiction.
answered Dec 16 '18 at 0:13
Bram28Bram28
63.1k44793
$endgroup$
$begingroup$
I cannot see why that is the case. It seems to me that the truth value for $x=3lor y=8$ would be true when both $x=3$ and $ y=8$?
$endgroup$
– Jac Frall
Dec 16 '18 at 0:19
$begingroup$
@JacFrall True, from $x=3 land y=8$ you can indeed infer $x=3 lor y=8$. But in order for your proof to work, you need to go the other way around: Your Proof by Contradiction goes like this: $neg (x neq 3 land y neq 8) Rightarrow (x =3 lor y=8) Rightarrow x = 3 land y=8 Rightarrow x+y=11$.
$endgroup$
– Bram28
Dec 16 '18 at 0:24
$begingroup$
Look at your proof. You assume $x=3$ or $y=8$ ... and yet on the very next line you say 'Let $x=3$ and $y=8$' ... wait! Where does that come from? Certainly not from your assumption, because from $x=3$ or $y=8$ you cannot infer $x=3$ and $y=8$. And so is this a new assumption? A second assumption? But then when that second assumption runs into a contradiction, all you u have shown is that it cannot be trrue that $x=3$ and $y=8$ ... the first assumption does not get discharged, and hence you have not shown that it cannot be true that $x=3$ or $y=8$
$endgroup$
– Bram28
Dec 16 '18 at 0:33
$begingroup$
Yes that makes much more sense now. Thank you for helping me see that it is a stronger statement and thus you cannot assume more than the initial $Pland lnot Q$
$endgroup$
– Jac Frall
Dec 16 '18 at 0:44
$begingroup$
@JacFrall Cool, glad I could help! :)
$endgroup$
– Bram28
Dec 16 '18 at 0:45
add a comment |
$begingroup$
Yes, you have set up things correctly: Assume $x+y=10$, and then, to start the proof by Contradiction, you (correctly) assumed that it is not true that $x neq 3$ and $y neq 8$. And the latter means that $x=3$ or $y=8$. But from that, you cannot infer that $x=3$ and $y=8$, which is what you need in order to get to $x+y=11$ and thus to your contradiction.
answered Dec 16 '18 at 0:13
Bram28Bram28
63.1k44793
$endgroup$
$begingroup$
I cannot see why that is the case. It seems to me that the truth value for $x=3lor y=8$ would be true when both $x=3$ and $ y=8$?
$endgroup$
– Jac Frall
Dec 16 '18 at 0:19
$begingroup$
@JacFrall True, from $x=3 land y=8$ you can indeed infer $x=3 lor y=8$. But in order for your proof to work, you need to go the other way around: Your Proof by Contradiction goes like this: $neg (x neq 3 land y neq 8) Rightarrow (x =3 lor y=8) Rightarrow x = 3 land y=8 Rightarrow x+y=11$.
$endgroup$
– Bram28
Dec 16 '18 at 0:24
$begingroup$
Look at your proof. You assume $x=3$ or $y=8$ ... and yet on the very next line you say 'Let $x=3$ and $y=8$' ... wait! Where does that come from? Certainly not from your assumption, because from $x=3$ or $y=8$ you cannot infer $x=3$ and $y=8$. And so is this a new assumption? A second assumption? But then when that second assumption runs into a contradiction, all you u have shown is that it cannot be trrue that $x=3$ and $y=8$ ... the first assumption does not get discharged, and hence you have not shown that it cannot be true that $x=3$ or $y=8$
$endgroup$
– Bram28
Dec 16 '18 at 0:33
$begingroup$
Yes that makes much more sense now. Thank you for helping me see that it is a stronger statement and thus you cannot assume more than the initial $Pland lnot Q$
$endgroup$
– Jac Frall
Dec 16 '18 at 0:44
$begingroup$
@JacFrall Cool, glad I could help! :)
$endgroup$
– Bram28
Dec 16 '18 at 0:45
add a comment |
$begingroup$
Yes, you have set up things correctly: Assume $x+y=10$, and then, to start the proof by Contradiction, you (correctly) assumed that it is not true that $x neq 3$ and $y neq 8$. And the latter means that $x=3$ or $y=8$. But from that, you cannot infer that $x=3$ and $y=8$, which is what you need in order to get to $x+y=11$ and thus to your contradiction.
answered Dec 16 '18 at 0:13
Bram28Bram28
63.1k44793
$endgroup$
Yes, you have set up things correctly: Assume $x+y=10$, and then, to start the proof by Contradiction, you (correctly) assumed that it is not true that $x neq 3$ and $y neq 8$. And the latter means that $x=3$ or $y=8$. But from that, you cannot infer that $x=3$ and $y=8$, which is what you need in order to get to $x+y=11$ and thus to your contradiction.
answered Dec 16 '18 at 0:13
Bram28Bram28
63.1k44793
edited Dec 16 '18 at 0:29
answered Dec 16 '18 at 0:13
Bram28Bram28
63.1k44793
answered Dec 16 '18 at 0:13
Bram28Bram28
63.1k44793
answered Dec 16 '18 at 0:13
Bram28Bram28
63.1k44793
63.1k44793
$begingroup$
I cannot see why that is the case. It seems to me that the truth value for $x=3lor y=8$ would be true when both $x=3$ and $ y=8$?
$endgroup$
– Jac Frall
Dec 16 '18 at 0:19
$begingroup$
@JacFrall True, from $x=3 land y=8$ you can indeed infer $x=3 lor y=8$. But in order for your proof to work, you need to go the other way around: Your Proof by Contradiction goes like this: $neg (x neq 3 land y neq 8) Rightarrow (x =3 lor y=8) Rightarrow x = 3 land y=8 Rightarrow x+y=11$.
$endgroup$
– Bram28
Dec 16 '18 at 0:24
$begingroup$
Look at your proof. You assume $x=3$ or $y=8$ ... and yet on the very next line you say 'Let $x=3$ and $y=8$' ... wait! Where does that come from? Certainly not from your assumption, because from $x=3$ or $y=8$ you cannot infer $x=3$ and $y=8$. And so is this a new assumption? A second assumption? But then when that second assumption runs into a contradiction, all you u have shown is that it cannot be trrue that $x=3$ and $y=8$ ... the first assumption does not get discharged, and hence you have not shown that it cannot be true that $x=3$ or $y=8$
$endgroup$
– Bram28
Dec 16 '18 at 0:33
$begingroup$
Yes that makes much more sense now. Thank you for helping me see that it is a stronger statement and thus you cannot assume more than the initial $Pland lnot Q$
$endgroup$
– Jac Frall
Dec 16 '18 at 0:44
$begingroup$
@JacFrall Cool, glad I could help! :)
$endgroup$
– Bram28
Dec 16 '18 at 0:45
add a comment |
$begingroup$
I cannot see why that is the case. It seems to me that the truth value for $x=3lor y=8$ would be true when both $x=3$ and $ y=8$?
$endgroup$
– Jac Frall
Dec 16 '18 at 0:19
$begingroup$
@JacFrall True, from $x=3 land y=8$ you can indeed infer $x=3 lor y=8$. But in order for your proof to work, you need to go the other way around: Your Proof by Contradiction goes like this: $neg (x neq 3 land y neq 8) Rightarrow (x =3 lor y=8) Rightarrow x = 3 land y=8 Rightarrow x+y=11$.
$endgroup$
– Bram28
Dec 16 '18 at 0:24
$begingroup$
Look at your proof. You assume $x=3$ or $y=8$ ... and yet on the very next line you say 'Let $x=3$ and $y=8$' ... wait! Where does that come from? Certainly not from your assumption, because from $x=3$ or $y=8$ you cannot infer $x=3$ and $y=8$. And so is this a new assumption? A second assumption? But then when that second assumption runs into a contradiction, all you u have shown is that it cannot be trrue that $x=3$ and $y=8$ ... the first assumption does not get discharged, and hence you have not shown that it cannot be true that $x=3$ or $y=8$
$endgroup$
– Bram28
Dec 16 '18 at 0:33
$begingroup$
Yes that makes much more sense now. Thank you for helping me see that it is a stronger statement and thus you cannot assume more than the initial $Pland lnot Q$
$endgroup$
– Jac Frall
Dec 16 '18 at 0:44
$begingroup$
@JacFrall Cool, glad I could help! :)
$endgroup$
– Bram28
Dec 16 '18 at 0:45
$begingroup$
I cannot see why that is the case. It seems to me that the truth value for $x=3lor y=8$ would be true when both $x=3$ and $ y=8$?
$endgroup$
– Jac Frall
Dec 16 '18 at 0:19
$begingroup$
I cannot see why that is the case. It seems to me that the truth value for $x=3lor y=8$ would be true when both $x=3$ and $ y=8$?
$endgroup$
– Jac Frall
Dec 16 '18 at 0:19
$begingroup$
@JacFrall True, from $x=3 land y=8$ you can indeed infer $x=3 lor y=8$. But in order for your proof to work, you need to go the other way around: Your Proof by Contradiction goes like this: $neg (x neq 3 land y neq 8) Rightarrow (x =3 lor y=8) Rightarrow x = 3 land y=8 Rightarrow x+y=11$.
$endgroup$
– Bram28
Dec 16 '18 at 0:24
$begingroup$
@JacFrall True, from $x=3 land y=8$ you can indeed infer $x=3 lor y=8$. But in order for your proof to work, you need to go the other way around: Your Proof by Contradiction goes like this: $neg (x neq 3 land y neq 8) Rightarrow (x =3 lor y=8) Rightarrow x = 3 land y=8 Rightarrow x+y=11$.
$endgroup$
– Bram28
Dec 16 '18 at 0:24
$begingroup$
Look at your proof. You assume $x=3$ or $y=8$ ... and yet on the very next line you say 'Let $x=3$ and $y=8$' ... wait! Where does that come from? Certainly not from your assumption, because from $x=3$ or $y=8$ you cannot infer $x=3$ and $y=8$. And so is this a new assumption? A second assumption? But then when that second assumption runs into a contradiction, all you u have shown is that it cannot be trrue that $x=3$ and $y=8$ ... the first assumption does not get discharged, and hence you have not shown that it cannot be true that $x=3$ or $y=8$
$endgroup$
– Bram28
Dec 16 '18 at 0:33
$begingroup$
Look at your proof. You assume $x=3$ or $y=8$ ... and yet on the very next line you say 'Let $x=3$ and $y=8$' ... wait! Where does that come from? Certainly not from your assumption, because from $x=3$ or $y=8$ you cannot infer $x=3$ and $y=8$. And so is this a new assumption? A second assumption? But then when that second assumption runs into a contradiction, all you u have shown is that it cannot be trrue that $x=3$ and $y=8$ ... the first assumption does not get discharged, and hence you have not shown that it cannot be true that $x=3$ or $y=8$
$endgroup$
– Bram28
Dec 16 '18 at 0:33
$begingroup$
Yes that makes much more sense now. Thank you for helping me see that it is a stronger statement and thus you cannot assume more than the initial $Pland lnot Q$
$endgroup$
– Jac Frall
Dec 16 '18 at 0:44
$begingroup$
Yes that makes much more sense now. Thank you for helping me see that it is a stronger statement and thus you cannot assume more than the initial $Pland lnot Q$
$endgroup$
– Jac Frall
Dec 16 '18 at 0:44
$begingroup$
@JacFrall Cool, glad I could help! :)
$endgroup$
– Bram28
Dec 16 '18 at 0:45
$begingroup$
@JacFrall Cool, glad I could help! :)
$endgroup$
– Bram28
Dec 16 '18 at 0:45
add a comment |
$begingroup$
this theorem is wrong
$P: bigg[x+y=10implies (xne 3land yne 8)bigg]iff bigg[(x=3 lor y=8)implies x+yne 10bigg]$
Suppose $x=3$, you take $y:=7$ so $x+y=10$ contradiction so your theorem is wrong
by contradiction :
$lnot P :quad x+y=10 land (x= 3lor y= 8)$
$x+y=10$ and $x=3$ we take $y:=7$, so the proposition $lnot P$ is right.
I remind you $P:(simplies t)iff (lnot slor t)$ so $lnot P :sland lnot t$
To avoid any confusion you have to add quantifier so the proposition becomes
$ P :forall (x,y)in mathbb{N}^2,bigg[x+y=10implies (xne 3land yne 8)bigg]$
So the negative is :
$lnot P : exists (x,y)in mathbb{N}^2,quad (x+y=10) land (x= 3lor y= 8)$
We only need to find one 2-tuple that satisfies the proposition, so $(x,y)=(3,7)$ fits. We conclude $lnot P$ is right thus $P$ is wrong
answered Dec 16 '18 at 0:39
StuStu
1,1881414
$endgroup$
$begingroup$
Yes, I understand that the Theorem is not True. This is why I was confused. I was showing that some obviously false theorem was true using proof by contradiction, asking for clarification.
$endgroup$
– Jac Frall
Dec 16 '18 at 0:41
$begingroup$
I added a proof by contradiction
$endgroup$
– Stu
Dec 16 '18 at 0:49
$begingroup$
I see. What confused me was I thought you could let $x=3 $ and $y=8$ in the proof by contradiction since this seems to satisfy the $x=3 lor y=8$ part of $lnot P$.
$endgroup$
– Jac Frall
Dec 16 '18 at 0:54
$begingroup$
what do you mean?
$endgroup$
– Stu
Dec 16 '18 at 1:43
$begingroup$
$forall cdots P$ and $existscdots lnot P$
$endgroup$
– Stu
Dec 16 '18 at 1:47
|
show 3 more comments
$begingroup$
this theorem is wrong
$P: bigg[x+y=10implies (xne 3land yne 8)bigg]iff bigg[(x=3 lor y=8)implies x+yne 10bigg]$
Suppose $x=3$, you take $y:=7$ so $x+y=10$ contradiction so your theorem is wrong
by contradiction :
$lnot P :quad x+y=10 land (x= 3lor y= 8)$
$x+y=10$ and $x=3$ we take $y:=7$, so the proposition $lnot P$ is right.
I remind you $P:(simplies t)iff (lnot slor t)$ so $lnot P :sland lnot t$
To avoid any confusion you have to add quantifier so the proposition becomes
$ P :forall (x,y)in mathbb{N}^2,bigg[x+y=10implies (xne 3land yne 8)bigg]$
So the negative is :
$lnot P : exists (x,y)in mathbb{N}^2,quad (x+y=10) land (x= 3lor y= 8)$
We only need to find one 2-tuple that satisfies the proposition, so $(x,y)=(3,7)$ fits. We conclude $lnot P$ is right thus $P$ is wrong
answered Dec 16 '18 at 0:39
StuStu
1,1881414
$endgroup$
$begingroup$
Yes, I understand that the Theorem is not True. This is why I was confused. I was showing that some obviously false theorem was true using proof by contradiction, asking for clarification.
$endgroup$
– Jac Frall
Dec 16 '18 at 0:41
$begingroup$
I added a proof by contradiction
$endgroup$
– Stu
Dec 16 '18 at 0:49
$begingroup$
I see. What confused me was I thought you could let $x=3 $ and $y=8$ in the proof by contradiction since this seems to satisfy the $x=3 lor y=8$ part of $lnot P$.
$endgroup$
– Jac Frall
Dec 16 '18 at 0:54
$begingroup$
what do you mean?
$endgroup$
– Stu
Dec 16 '18 at 1:43
$begingroup$
$forall cdots P$ and $existscdots lnot P$
$endgroup$
– Stu
Dec 16 '18 at 1:47
|
show 3 more comments
$begingroup$
this theorem is wrong
$P: bigg[x+y=10implies (xne 3land yne 8)bigg]iff bigg[(x=3 lor y=8)implies x+yne 10bigg]$
Suppose $x=3$, you take $y:=7$ so $x+y=10$ contradiction so your theorem is wrong
by contradiction :
$lnot P :quad x+y=10 land (x= 3lor y= 8)$
$x+y=10$ and $x=3$ we take $y:=7$, so the proposition $lnot P$ is right.
I remind you $P:(simplies t)iff (lnot slor t)$ so $lnot P :sland lnot t$
To avoid any confusion you have to add quantifier so the proposition becomes
$ P :forall (x,y)in mathbb{N}^2,bigg[x+y=10implies (xne 3land yne 8)bigg]$
So the negative is :
$lnot P : exists (x,y)in mathbb{N}^2,quad (x+y=10) land (x= 3lor y= 8)$
We only need to find one 2-tuple that satisfies the proposition, so $(x,y)=(3,7)$ fits. We conclude $lnot P$ is right thus $P$ is wrong
answered Dec 16 '18 at 0:39
StuStu
1,1881414
$endgroup$
this theorem is wrong
$P: bigg[x+y=10implies (xne 3land yne 8)bigg]iff bigg[(x=3 lor y=8)implies x+yne 10bigg]$
Suppose $x=3$, you take $y:=7$ so $x+y=10$ contradiction so your theorem is wrong
by contradiction :
$lnot P :quad x+y=10 land (x= 3lor y= 8)$
$x+y=10$ and $x=3$ we take $y:=7$, so the proposition $lnot P$ is right.
I remind you $P:(simplies t)iff (lnot slor t)$ so $lnot P :sland lnot t$
To avoid any confusion you have to add quantifier so the proposition becomes
$ P :forall (x,y)in mathbb{N}^2,bigg[x+y=10implies (xne 3land yne 8)bigg]$
So the negative is :
$lnot P : exists (x,y)in mathbb{N}^2,quad (x+y=10) land (x= 3lor y= 8)$
We only need to find one 2-tuple that satisfies the proposition, so $(x,y)=(3,7)$ fits. We conclude $lnot P$ is right thus $P$ is wrong
answered Dec 16 '18 at 0:39
StuStu
1,1881414
edited Dec 16 '18 at 8:33
answered Dec 16 '18 at 0:39
StuStu
1,1881414
answered Dec 16 '18 at 0:39
StuStu
1,1881414
answered Dec 16 '18 at 0:39
StuStu
1,1881414
1,1881414
$begingroup$
Yes, I understand that the Theorem is not True. This is why I was confused. I was showing that some obviously false theorem was true using proof by contradiction, asking for clarification.
$endgroup$
– Jac Frall
Dec 16 '18 at 0:41
$begingroup$
I added a proof by contradiction
$endgroup$
– Stu
Dec 16 '18 at 0:49
$begingroup$
I see. What confused me was I thought you could let $x=3 $ and $y=8$ in the proof by contradiction since this seems to satisfy the $x=3 lor y=8$ part of $lnot P$.
$endgroup$
– Jac Frall
Dec 16 '18 at 0:54
$begingroup$
what do you mean?
$endgroup$
– Stu
Dec 16 '18 at 1:43
$begingroup$
$forall cdots P$ and $existscdots lnot P$
$endgroup$
– Stu
Dec 16 '18 at 1:47
|
show 3 more comments
$begingroup$
Yes, I understand that the Theorem is not True. This is why I was confused. I was showing that some obviously false theorem was true using proof by contradiction, asking for clarification.
$endgroup$
– Jac Frall
Dec 16 '18 at 0:41
$begingroup$
I added a proof by contradiction
$endgroup$
– Stu
Dec 16 '18 at 0:49
$begingroup$
I see. What confused me was I thought you could let $x=3 $ and $y=8$ in the proof by contradiction since this seems to satisfy the $x=3 lor y=8$ part of $lnot P$.
$endgroup$
– Jac Frall
Dec 16 '18 at 0:54
$begingroup$
what do you mean?
$endgroup$
– Stu
Dec 16 '18 at 1:43
$begingroup$
$forall cdots P$ and $existscdots lnot P$
$endgroup$
– Stu
Dec 16 '18 at 1:47
$begingroup$
Yes, I understand that the Theorem is not True. This is why I was confused. I was showing that some obviously false theorem was true using proof by contradiction, asking for clarification.
$endgroup$
– Jac Frall
Dec 16 '18 at 0:41
$begingroup$
Yes, I understand that the Theorem is not True. This is why I was confused. I was showing that some obviously false theorem was true using proof by contradiction, asking for clarification.
$endgroup$
– Jac Frall
Dec 16 '18 at 0:41
$begingroup$
I added a proof by contradiction
$endgroup$
– Stu
Dec 16 '18 at 0:49
$begingroup$
I added a proof by contradiction
$endgroup$
– Stu
Dec 16 '18 at 0:49
$begingroup$
I see. What confused me was I thought you could let $x=3 $ and $y=8$ in the proof by contradiction since this seems to satisfy the $x=3 lor y=8$ part of $lnot P$.
$endgroup$
– Jac Frall
Dec 16 '18 at 0:54
$begingroup$
I see. What confused me was I thought you could let $x=3 $ and $y=8$ in the proof by contradiction since this seems to satisfy the $x=3 lor y=8$ part of $lnot P$.
$endgroup$
– Jac Frall
Dec 16 '18 at 0:54
$begingroup$
what do you mean?
$endgroup$
– Stu
Dec 16 '18 at 1:43
$begingroup$
what do you mean?
$endgroup$
– Stu
Dec 16 '18 at 1:43
$begingroup$
$forall cdots P$ and $existscdots lnot P$
$endgroup$
– Stu
Dec 16 '18 at 1:47
$begingroup$
$forall cdots P$ and $existscdots lnot P$
$endgroup$
– Stu
Dec 16 '18 at 1:47
|
show 3 more comments
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%2f3042086%2fproof-by-contradiction-to-prove-theorem-that-is-not-true%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
