Prove a result by assuming it's true and showing no contradictionMinimal Set of group axiomsQns on Propositional Logic - Inference Rules + Logical EquivalencePropositional Logic with rules of inference problem.Is the following a correct logical proof?Tertium non datur and Inductive Subset of a Well Ordered SetModus Tollens ProofLogic Beginner Question to InferencesDifference between “ proof by reductio ad absurdum” and “proof by contradiction”?How are statements laid out in deductive proof?How to prove $lnot(pto q)vdash p landlnot q$Is the following series of equivalences a proof that the “modus tollens” law is a tautology. ( Reducing all tautologies to only one?)
Is there a way to create a report for the failed entries while calling REST API
During the Space Shuttle Columbia Disaster of 2003, Why Did The Flight Director Say, "Lock the doors."?
Dereferencing a pointer in a for loop initializer creates a seg fault
How do we avoid CI-driven development...?
Physics of Guitar frets and sound
How to say "fit" in Latin?
Why should public servants be apolitical?
What are good ways to improve as a writer other than writing courses?
Does this Foo machine halt?
Double blind peer review when paper cites author's GitHub repo for code
sed delete all the words before a match
Infeasibility in mathematical optimization models
Word or idiom defining something barely functional
When "he's gone" means "he's dead", is it a contraction of "he is" or "he has"?
As a 16 year old, how can I keep my money safe from my mother?
What is the idiomatic way of saying “he is ticklish under armpits”?
How to help new students accept function notation
Blocking people from taking pictures of me with smartphone
How to mark beverage cans in a cooler for a blind person?
In a topological space if there exists a loop that cannot be contracted to a point does there exist a simple loop that cannot be contracted also?
Atari ST DRAM timing puzzle
Why should we care about syntactic proofs if we can show semantically that statements are true?
Looking for a new job because of relocation - is it okay to tell the real reason?
Is this cheap "air conditioner" able to cool a room?
Prove a result by assuming it's true and showing no contradiction
Minimal Set of group axiomsQns on Propositional Logic - Inference Rules + Logical EquivalencePropositional Logic with rules of inference problem.Is the following a correct logical proof?Tertium non datur and Inductive Subset of a Well Ordered SetModus Tollens ProofLogic Beginner Question to InferencesDifference between “ proof by reductio ad absurdum” and “proof by contradiction”?How are statements laid out in deductive proof?How to prove $lnot(pto q)vdash p landlnot q$Is the following series of equivalences a proof that the “modus tollens” law is a tautology. ( Reducing all tautologies to only one?)
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$begingroup$
Preface: I'm not too experienced in propositional logic, just the basics, and I'm familiar with common proof methods (modus ponens, modus tollens, reductio ad absurdum, etc) but not so familiar to be comfortable here.
I have been trying to explain why a certain proof is not satisfactory (for my notes). It goes like this (an example):
Consider a group $G$ with identity $i$ obeying the typical group axioms (associativity, existence of identity, existence of inverse). Specifically:
$G1$: If $a,b,c in G$, then $(a*b)*c=a*(b*c)$
$G2$: There exists an element $i in G$, such that for all $ain G$ , $a*i=a$
$G3$: For each element $ain G$ there exists an element $a^-1 in G$ such that $a*a^-1=i$
We wish to prove that, for the identity is defined by the postulate $a*i=a$, then we can show $i*a=a$. The 'proof' follows like this:
$$ i*a=a $$
$$ a*(i*a)=a*a $$
$$ (a*i)*a=a*a $$
$$ a*a = a*a $$
$$ (a*a)*a^-1 = (a*a)*a^-1 $$
$$ a*(a*a^-1) = a*(a*a^-1) $$
$$ a*i=a*i $$
$$ a=a $$
This last result is of course true. We've shown that $i*a=a$ does not lead to a contradiction, but this is not in and of itself a proof. We've also shown that under the same sequence of operations, both sides of $i*a=a$ are equivalent. This seems good, but it feels wrong. The proper proof, in my mind, would start with $a=a$ and derive $i*a=a$, but because we can do this by writing the above proof and working backwards, the above proof seems sound...
I thought that I could find a counterexample, because obviously if we started with something like $i*a=a*a$ then we might not be able to get to something like $a=a$. The trick, I guess, is that all of the steps in the above proof are reversible, but I don't know if that's necessarily true. So what can be said? Is there a good counterexample?
logic fake-proofs
asked Jul 29 at 16:45
Sam GallagherSam Gallagher
1776 bronze badges
$endgroup$
|
show 12 more comments
$begingroup$
Preface: I'm not too experienced in propositional logic, just the basics, and I'm familiar with common proof methods (modus ponens, modus tollens, reductio ad absurdum, etc) but not so familiar to be comfortable here.
I have been trying to explain why a certain proof is not satisfactory (for my notes). It goes like this (an example):
Consider a group $G$ with identity $i$ obeying the typical group axioms (associativity, existence of identity, existence of inverse). Specifically:
$G1$: If $a,b,c in G$, then $(a*b)*c=a*(b*c)$
$G2$: There exists an element $i in G$, such that for all $ain G$ , $a*i=a$
$G3$: For each element $ain G$ there exists an element $a^-1 in G$ such that $a*a^-1=i$
We wish to prove that, for the identity is defined by the postulate $a*i=a$, then we can show $i*a=a$. The 'proof' follows like this:
$$ i*a=a $$
$$ a*(i*a)=a*a $$
$$ (a*i)*a=a*a $$
$$ a*a = a*a $$
$$ (a*a)*a^-1 = (a*a)*a^-1 $$
$$ a*(a*a^-1) = a*(a*a^-1) $$
$$ a*i=a*i $$
$$ a=a $$
This last result is of course true. We've shown that $i*a=a$ does not lead to a contradiction, but this is not in and of itself a proof. We've also shown that under the same sequence of operations, both sides of $i*a=a$ are equivalent. This seems good, but it feels wrong. The proper proof, in my mind, would start with $a=a$ and derive $i*a=a$, but because we can do this by writing the above proof and working backwards, the above proof seems sound...
I thought that I could find a counterexample, because obviously if we started with something like $i*a=a*a$ then we might not be able to get to something like $a=a$. The trick, I guess, is that all of the steps in the above proof are reversible, but I don't know if that's necessarily true. So what can be said? Is there a good counterexample?
logic fake-proofs
asked Jul 29 at 16:45
Sam GallagherSam Gallagher
1776 bronze badges
$endgroup$
4
$begingroup$
This looks like a classical logical fallacy: begging the question. That proof is OK if each step is an "if and only if", but even in that case, I agree with you that the presentation is poor.
$endgroup$
– Giuseppe Negro
Jul 29 at 16:51
1
$begingroup$
Let's look at the reversed proof: how do you go from Step 2 to Step 1? You're using "left-cancellation", correct? But that assumes $ia=a.$
$endgroup$
– Adrian Keister
Jul 29 at 16:54
2
$begingroup$
@AzIf00 If the identity element is commutative, it might be desirable to remove one of the equivalences from the axioms.
$endgroup$
– Sam Gallagher
Jul 29 at 17:02
1
$begingroup$
@Azif00 See e.g. jstor.org/stable/2371204?seq=1#metadata_info_tab_contents
$endgroup$
– Sam Gallagher
Jul 29 at 17:04
1
$begingroup$
The accepted answer to this question addresses your choice of axioms, I think.
$endgroup$
– Kajelad
Jul 29 at 17:45
|
show 12 more comments
$begingroup$
Preface: I'm not too experienced in propositional logic, just the basics, and I'm familiar with common proof methods (modus ponens, modus tollens, reductio ad absurdum, etc) but not so familiar to be comfortable here.
I have been trying to explain why a certain proof is not satisfactory (for my notes). It goes like this (an example):
Consider a group $G$ with identity $i$ obeying the typical group axioms (associativity, existence of identity, existence of inverse). Specifically:
$G1$: If $a,b,c in G$, then $(a*b)*c=a*(b*c)$
$G2$: There exists an element $i in G$, such that for all $ain G$ , $a*i=a$
$G3$: For each element $ain G$ there exists an element $a^-1 in G$ such that $a*a^-1=i$
We wish to prove that, for the identity is defined by the postulate $a*i=a$, then we can show $i*a=a$. The 'proof' follows like this:
$$ i*a=a $$
$$ a*(i*a)=a*a $$
$$ (a*i)*a=a*a $$
$$ a*a = a*a $$
$$ (a*a)*a^-1 = (a*a)*a^-1 $$
$$ a*(a*a^-1) = a*(a*a^-1) $$
$$ a*i=a*i $$
$$ a=a $$
This last result is of course true. We've shown that $i*a=a$ does not lead to a contradiction, but this is not in and of itself a proof. We've also shown that under the same sequence of operations, both sides of $i*a=a$ are equivalent. This seems good, but it feels wrong. The proper proof, in my mind, would start with $a=a$ and derive $i*a=a$, but because we can do this by writing the above proof and working backwards, the above proof seems sound...
I thought that I could find a counterexample, because obviously if we started with something like $i*a=a*a$ then we might not be able to get to something like $a=a$. The trick, I guess, is that all of the steps in the above proof are reversible, but I don't know if that's necessarily true. So what can be said? Is there a good counterexample?
logic fake-proofs
asked Jul 29 at 16:45
Sam GallagherSam Gallagher
1776 bronze badges
$endgroup$
Preface: I'm not too experienced in propositional logic, just the basics, and I'm familiar with common proof methods (modus ponens, modus tollens, reductio ad absurdum, etc) but not so familiar to be comfortable here.
I have been trying to explain why a certain proof is not satisfactory (for my notes). It goes like this (an example):
Consider a group $G$ with identity $i$ obeying the typical group axioms (associativity, existence of identity, existence of inverse). Specifically:
$G1$: If $a,b,c in G$, then $(a*b)*c=a*(b*c)$
$G2$: There exists an element $i in G$, such that for all $ain G$ , $a*i=a$
$G3$: For each element $ain G$ there exists an element $a^-1 in G$ such that $a*a^-1=i$
We wish to prove that, for the identity is defined by the postulate $a*i=a$, then we can show $i*a=a$. The 'proof' follows like this:
$$ i*a=a $$
$$ a*(i*a)=a*a $$
$$ (a*i)*a=a*a $$
$$ a*a = a*a $$
$$ (a*a)*a^-1 = (a*a)*a^-1 $$
$$ a*(a*a^-1) = a*(a*a^-1) $$
$$ a*i=a*i $$
$$ a=a $$
This last result is of course true. We've shown that $i*a=a$ does not lead to a contradiction, but this is not in and of itself a proof. We've also shown that under the same sequence of operations, both sides of $i*a=a$ are equivalent. This seems good, but it feels wrong. The proper proof, in my mind, would start with $a=a$ and derive $i*a=a$, but because we can do this by writing the above proof and working backwards, the above proof seems sound...
I thought that I could find a counterexample, because obviously if we started with something like $i*a=a*a$ then we might not be able to get to something like $a=a$. The trick, I guess, is that all of the steps in the above proof are reversible, but I don't know if that's necessarily true. So what can be said? Is there a good counterexample?
logic fake-proofs
logic fake-proofs
asked Jul 29 at 16:45
Sam GallagherSam Gallagher
1776 bronze badges
asked Jul 29 at 16:45
Sam GallagherSam Gallagher
1776 bronze badges
edited Jul 29 at 17:43
Sam Gallagher
asked Jul 29 at 16:45
Sam GallagherSam Gallagher
1776 bronze badges
asked Jul 29 at 16:45
Sam GallagherSam Gallagher
1776 bronze badges
asked Jul 29 at 16:45
Sam GallagherSam Gallagher
1776 bronze badges
1776 bronze badges
4
$begingroup$
This looks like a classical logical fallacy: begging the question. That proof is OK if each step is an "if and only if", but even in that case, I agree with you that the presentation is poor.
$endgroup$
– Giuseppe Negro
Jul 29 at 16:51
1
$begingroup$
Let's look at the reversed proof: how do you go from Step 2 to Step 1? You're using "left-cancellation", correct? But that assumes $ia=a.$
$endgroup$
– Adrian Keister
Jul 29 at 16:54
2
$begingroup$
@AzIf00 If the identity element is commutative, it might be desirable to remove one of the equivalences from the axioms.
$endgroup$
– Sam Gallagher
Jul 29 at 17:02
1
$begingroup$
@Azif00 See e.g. jstor.org/stable/2371204?seq=1#metadata_info_tab_contents
$endgroup$
– Sam Gallagher
Jul 29 at 17:04
1
$begingroup$
The accepted answer to this question addresses your choice of axioms, I think.
$endgroup$
– Kajelad
Jul 29 at 17:45
|
show 12 more comments
4
$begingroup$
This looks like a classical logical fallacy: begging the question. That proof is OK if each step is an "if and only if", but even in that case, I agree with you that the presentation is poor.
$endgroup$
– Giuseppe Negro
Jul 29 at 16:51
1
$begingroup$
Let's look at the reversed proof: how do you go from Step 2 to Step 1? You're using "left-cancellation", correct? But that assumes $ia=a.$
$endgroup$
– Adrian Keister
Jul 29 at 16:54
2
$begingroup$
@AzIf00 If the identity element is commutative, it might be desirable to remove one of the equivalences from the axioms.
$endgroup$
– Sam Gallagher
Jul 29 at 17:02
1
$begingroup$
@Azif00 See e.g. jstor.org/stable/2371204?seq=1#metadata_info_tab_contents
$endgroup$
– Sam Gallagher
Jul 29 at 17:04
1
$begingroup$
The accepted answer to this question addresses your choice of axioms, I think.
$endgroup$
– Kajelad
Jul 29 at 17:45
4
4
$begingroup$
This looks like a classical logical fallacy: begging the question. That proof is OK if each step is an "if and only if", but even in that case, I agree with you that the presentation is poor.
$endgroup$
– Giuseppe Negro
Jul 29 at 16:51
$begingroup$
This looks like a classical logical fallacy: begging the question. That proof is OK if each step is an "if and only if", but even in that case, I agree with you that the presentation is poor.
$endgroup$
– Giuseppe Negro
Jul 29 at 16:51
1
1
$begingroup$
Let's look at the reversed proof: how do you go from Step 2 to Step 1? You're using "left-cancellation", correct? But that assumes $ia=a.$
$endgroup$
– Adrian Keister
Jul 29 at 16:54
$begingroup$
Let's look at the reversed proof: how do you go from Step 2 to Step 1? You're using "left-cancellation", correct? But that assumes $ia=a.$
$endgroup$
– Adrian Keister
Jul 29 at 16:54
2
2
$begingroup$
@AzIf00 If the identity element is commutative, it might be desirable to remove one of the equivalences from the axioms.
$endgroup$
– Sam Gallagher
Jul 29 at 17:02
$begingroup$
@AzIf00 If the identity element is commutative, it might be desirable to remove one of the equivalences from the axioms.
$endgroup$
– Sam Gallagher
Jul 29 at 17:02
1
1
$begingroup$
@Azif00 See e.g. jstor.org/stable/2371204?seq=1#metadata_info_tab_contents
$endgroup$
– Sam Gallagher
Jul 29 at 17:04
$begingroup$
@Azif00 See e.g. jstor.org/stable/2371204?seq=1#metadata_info_tab_contents
$endgroup$
– Sam Gallagher
Jul 29 at 17:04
1
1
$begingroup$
The accepted answer to this question addresses your choice of axioms, I think.
$endgroup$
– Kajelad
Jul 29 at 17:45
$begingroup$
The accepted answer to this question addresses your choice of axioms, I think.
$endgroup$
– Kajelad
Jul 29 at 17:45
|
show 12 more comments
2 Answers
2
active
oldest
votes
$begingroup$
Your proof reminds me of the many 'proofs' I have seen for induction, where instead of showing that:
$$varphi(0)=[some formula]$$
or
$$varphi(n+1)=[some formula]$$
it is instead assumed, and then through various manipulations one ends up with $0=0$, which is then followed by the remark: "See, it checks out!"
The big danger with this is that if you cannot reverse the process, then it is not a proof at all .... Indeed, showing that $0=0$ shows nothing at all ... of course $0=0$ is true!
Example: Suppose I want to prove that for all $n$:
$Sigma_i=0^n i = 42$
(which is of course false!)
OK, so I say: Well, for the base I need to show that $Sigma_i=0^0 i = 42$
Well, let's see:
$Sigma_i=0^0 i = 42$
$0*Sigma_i=0^0 i = 0*42$
$0=0$
"Aha!! QED!"
...except it's not QED at all ... Sure, you can always derive $0=0$. And, for that matter, you can always derive $a=a$. None of that shows anything at all.
So yes, you are right that you really want to reverse this process to count as a proof of $i * a = a$
OK, but if so, it seems like you could just start with $a * a = a* a$. That is, you'd get:
$$ a*a = a*a $$ (This is OK to start with, since it's always true)
$$ (a*i)*a=a*a $$ (since we're given that $a*i=a$)
$$ a*(i*a)=a*a $$ (because of Association)
$$ i*a=a $$ (Hmmmm ... why does that follow from $ a*(i*a)=a*a $? That is not at all clear!)
One more thing: The tile of your question raises red flags as well: just because some assumption does not lead to a contradiction does not mean that it is true ... or implied by the givens.
Example: I give you that $a=1$. Now, is $b=2$? If you assume $b=2$, no contradiction will follow ... but it is clearly not implied by $a=1$
Also realize that you being unable to derive a contradiction does not mean there is no contradiction.... maybe there is a contradiction, but you just didn't see how to derive it.
And finally, just because you are able to infer $a=a$ does not mean that there is no contradiction. Again, you can always infer $a=a$. .. including from a contradiction ... indeed, anything follows from a contradiction.
answered Jul 29 at 17:52
Bram28Bram28
67.5k4 gold badges48 silver badges94 bronze badges
$endgroup$
add a comment |
$begingroup$
(First some vocabulary. If $a*i = a; forall a in S$ then $i$ is a right identity and if $u*a = a;forall a in S$ then $u$ is a left identity. If $aa^-1 = i$ where $i$ is a right identity then $a^-1$ is a right inverse and if $a^!a = u$ where $u$ is a left inverse.)
First: You are correct that a proof from conclusion to non-contradiction is not valid unless every step is reversible.
In this proof the irreversible step is the very first. $a = ia implies a*a = a*ia$ but $a*a = a*ia not implies a = ia$.
(But the statement $a*a = (a*i)*a = a*(i*a)$ is most certainly correct.)
Second: The axioms of a group INCLUDE that $a*i = i*a = a;forall ain G$. so there is nothing to prove.
There are (among others) two axioms of a group. 1) that there is an identity element that is both a right and left identity. And 2) that for every element $ain G$ there exists an element that if both a left and right inverse of $a$.
If we were to replace axiom 1) with simply that there is a right identity element that may not be a left identity but keep axiom 2) in tact then:
The step in the proof above is reversible. sort of. $i = a^-1a = aa^-1$. so $a*a = a*(ia)implies a^-1*a*a = a^-1*a*(ia)implies a*a^-1*a = i*(i*a)implies a*i = (i*i)*a implies a = i*a$. And we have proven the stronger axiom 1)
Likewise if we were to replace axiom 2) with every element has a right identity but not necessarily a left inverse, but kept axiom 1) in tact we could prove the stronger 2) via
$i = hh^-1$ so $(h^-1)^-1=i(h^-1)^-1 = hh^-1(h^-1)^-1=h*i = h$. So $h^-1 h = h^-1(h^-1)^-1 = i= hh^-1$
But if we replace BOTH 1) and 2) with a weaker right identities exist and every element has a right inverse but say nothing of left inverses or left inverses, we can not prove a left inverse exist.
For a counter example look up a semigroup with a right identity and right inverse but not left indentities.
(Worth noting that a structure can have a right identity but not a left identity or a left identity but not right identity, but if a structure has both a left and right identity they must be same element. [If a structure has a left identity $u$ and right identity $i$ then $u*i = u$ because $i$ is a right identity and $u*i = i$ because $u$ is a left identity.])
answered Jul 29 at 18:47
fleabloodfleablood
78.3k2 gold badges29 silver badges98 bronze badges
$endgroup$
add a comment |
Your Answer
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%2f3307557%2fprove-a-result-by-assuming-its-true-and-showing-no-contradiction%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$
Your proof reminds me of the many 'proofs' I have seen for induction, where instead of showing that:
$$varphi(0)=[some formula]$$
or
$$varphi(n+1)=[some formula]$$
it is instead assumed, and then through various manipulations one ends up with $0=0$, which is then followed by the remark: "See, it checks out!"
The big danger with this is that if you cannot reverse the process, then it is not a proof at all .... Indeed, showing that $0=0$ shows nothing at all ... of course $0=0$ is true!
Example: Suppose I want to prove that for all $n$:
$Sigma_i=0^n i = 42$
(which is of course false!)
OK, so I say: Well, for the base I need to show that $Sigma_i=0^0 i = 42$
Well, let's see:
$Sigma_i=0^0 i = 42$
$0*Sigma_i=0^0 i = 0*42$
$0=0$
"Aha!! QED!"
...except it's not QED at all ... Sure, you can always derive $0=0$. And, for that matter, you can always derive $a=a$. None of that shows anything at all.
So yes, you are right that you really want to reverse this process to count as a proof of $i * a = a$
OK, but if so, it seems like you could just start with $a * a = a* a$. That is, you'd get:
$$ a*a = a*a $$ (This is OK to start with, since it's always true)
$$ (a*i)*a=a*a $$ (since we're given that $a*i=a$)
$$ a*(i*a)=a*a $$ (because of Association)
$$ i*a=a $$ (Hmmmm ... why does that follow from $ a*(i*a)=a*a $? That is not at all clear!)
One more thing: The tile of your question raises red flags as well: just because some assumption does not lead to a contradiction does not mean that it is true ... or implied by the givens.
Example: I give you that $a=1$. Now, is $b=2$? If you assume $b=2$, no contradiction will follow ... but it is clearly not implied by $a=1$
Also realize that you being unable to derive a contradiction does not mean there is no contradiction.... maybe there is a contradiction, but you just didn't see how to derive it.
And finally, just because you are able to infer $a=a$ does not mean that there is no contradiction. Again, you can always infer $a=a$. .. including from a contradiction ... indeed, anything follows from a contradiction.
answered Jul 29 at 17:52
Bram28Bram28
67.5k4 gold badges48 silver badges94 bronze badges
$endgroup$
add a comment |
$begingroup$
Your proof reminds me of the many 'proofs' I have seen for induction, where instead of showing that:
$$varphi(0)=[some formula]$$
or
$$varphi(n+1)=[some formula]$$
it is instead assumed, and then through various manipulations one ends up with $0=0$, which is then followed by the remark: "See, it checks out!"
The big danger with this is that if you cannot reverse the process, then it is not a proof at all .... Indeed, showing that $0=0$ shows nothing at all ... of course $0=0$ is true!
Example: Suppose I want to prove that for all $n$:
$Sigma_i=0^n i = 42$
(which is of course false!)
OK, so I say: Well, for the base I need to show that $Sigma_i=0^0 i = 42$
Well, let's see:
$Sigma_i=0^0 i = 42$
$0*Sigma_i=0^0 i = 0*42$
$0=0$
"Aha!! QED!"
...except it's not QED at all ... Sure, you can always derive $0=0$. And, for that matter, you can always derive $a=a$. None of that shows anything at all.
So yes, you are right that you really want to reverse this process to count as a proof of $i * a = a$
OK, but if so, it seems like you could just start with $a * a = a* a$. That is, you'd get:
$$ a*a = a*a $$ (This is OK to start with, since it's always true)
$$ (a*i)*a=a*a $$ (since we're given that $a*i=a$)
$$ a*(i*a)=a*a $$ (because of Association)
$$ i*a=a $$ (Hmmmm ... why does that follow from $ a*(i*a)=a*a $? That is not at all clear!)
One more thing: The tile of your question raises red flags as well: just because some assumption does not lead to a contradiction does not mean that it is true ... or implied by the givens.
Example: I give you that $a=1$. Now, is $b=2$? If you assume $b=2$, no contradiction will follow ... but it is clearly not implied by $a=1$
Also realize that you being unable to derive a contradiction does not mean there is no contradiction.... maybe there is a contradiction, but you just didn't see how to derive it.
And finally, just because you are able to infer $a=a$ does not mean that there is no contradiction. Again, you can always infer $a=a$. .. including from a contradiction ... indeed, anything follows from a contradiction.
answered Jul 29 at 17:52
Bram28Bram28
67.5k4 gold badges48 silver badges94 bronze badges
$endgroup$
add a comment |
$begingroup$
Your proof reminds me of the many 'proofs' I have seen for induction, where instead of showing that:
$$varphi(0)=[some formula]$$
or
$$varphi(n+1)=[some formula]$$
it is instead assumed, and then through various manipulations one ends up with $0=0$, which is then followed by the remark: "See, it checks out!"
The big danger with this is that if you cannot reverse the process, then it is not a proof at all .... Indeed, showing that $0=0$ shows nothing at all ... of course $0=0$ is true!
Example: Suppose I want to prove that for all $n$:
$Sigma_i=0^n i = 42$
(which is of course false!)
OK, so I say: Well, for the base I need to show that $Sigma_i=0^0 i = 42$
Well, let's see:
$Sigma_i=0^0 i = 42$
$0*Sigma_i=0^0 i = 0*42$
$0=0$
"Aha!! QED!"
...except it's not QED at all ... Sure, you can always derive $0=0$. And, for that matter, you can always derive $a=a$. None of that shows anything at all.
So yes, you are right that you really want to reverse this process to count as a proof of $i * a = a$
OK, but if so, it seems like you could just start with $a * a = a* a$. That is, you'd get:
$$ a*a = a*a $$ (This is OK to start with, since it's always true)
$$ (a*i)*a=a*a $$ (since we're given that $a*i=a$)
$$ a*(i*a)=a*a $$ (because of Association)
$$ i*a=a $$ (Hmmmm ... why does that follow from $ a*(i*a)=a*a $? That is not at all clear!)
One more thing: The tile of your question raises red flags as well: just because some assumption does not lead to a contradiction does not mean that it is true ... or implied by the givens.
Example: I give you that $a=1$. Now, is $b=2$? If you assume $b=2$, no contradiction will follow ... but it is clearly not implied by $a=1$
Also realize that you being unable to derive a contradiction does not mean there is no contradiction.... maybe there is a contradiction, but you just didn't see how to derive it.
And finally, just because you are able to infer $a=a$ does not mean that there is no contradiction. Again, you can always infer $a=a$. .. including from a contradiction ... indeed, anything follows from a contradiction.
answered Jul 29 at 17:52
Bram28Bram28
67.5k4 gold badges48 silver badges94 bronze badges
$endgroup$
Your proof reminds me of the many 'proofs' I have seen for induction, where instead of showing that:
$$varphi(0)=[some formula]$$
or
$$varphi(n+1)=[some formula]$$
it is instead assumed, and then through various manipulations one ends up with $0=0$, which is then followed by the remark: "See, it checks out!"
The big danger with this is that if you cannot reverse the process, then it is not a proof at all .... Indeed, showing that $0=0$ shows nothing at all ... of course $0=0$ is true!
Example: Suppose I want to prove that for all $n$:
$Sigma_i=0^n i = 42$
(which is of course false!)
OK, so I say: Well, for the base I need to show that $Sigma_i=0^0 i = 42$
Well, let's see:
$Sigma_i=0^0 i = 42$
$0*Sigma_i=0^0 i = 0*42$
$0=0$
"Aha!! QED!"
...except it's not QED at all ... Sure, you can always derive $0=0$. And, for that matter, you can always derive $a=a$. None of that shows anything at all.
So yes, you are right that you really want to reverse this process to count as a proof of $i * a = a$
OK, but if so, it seems like you could just start with $a * a = a* a$. That is, you'd get:
$$ a*a = a*a $$ (This is OK to start with, since it's always true)
$$ (a*i)*a=a*a $$ (since we're given that $a*i=a$)
$$ a*(i*a)=a*a $$ (because of Association)
$$ i*a=a $$ (Hmmmm ... why does that follow from $ a*(i*a)=a*a $? That is not at all clear!)
One more thing: The tile of your question raises red flags as well: just because some assumption does not lead to a contradiction does not mean that it is true ... or implied by the givens.
Example: I give you that $a=1$. Now, is $b=2$? If you assume $b=2$, no contradiction will follow ... but it is clearly not implied by $a=1$
Also realize that you being unable to derive a contradiction does not mean there is no contradiction.... maybe there is a contradiction, but you just didn't see how to derive it.
And finally, just because you are able to infer $a=a$ does not mean that there is no contradiction. Again, you can always infer $a=a$. .. including from a contradiction ... indeed, anything follows from a contradiction.
answered Jul 29 at 17:52
Bram28Bram28
67.5k4 gold badges48 silver badges94 bronze badges
edited Jul 30 at 13:53
answered Jul 29 at 17:52
Bram28Bram28
67.5k4 gold badges48 silver badges94 bronze badges
answered Jul 29 at 17:52
Bram28Bram28
67.5k4 gold badges48 silver badges94 bronze badges
answered Jul 29 at 17:52
Bram28Bram28
67.5k4 gold badges48 silver badges94 bronze badges
67.5k4 gold badges48 silver badges94 bronze badges
add a comment |
add a comment |
$begingroup$
(First some vocabulary. If $a*i = a; forall a in S$ then $i$ is a right identity and if $u*a = a;forall a in S$ then $u$ is a left identity. If $aa^-1 = i$ where $i$ is a right identity then $a^-1$ is a right inverse and if $a^!a = u$ where $u$ is a left inverse.)
First: You are correct that a proof from conclusion to non-contradiction is not valid unless every step is reversible.
In this proof the irreversible step is the very first. $a = ia implies a*a = a*ia$ but $a*a = a*ia not implies a = ia$.
(But the statement $a*a = (a*i)*a = a*(i*a)$ is most certainly correct.)
Second: The axioms of a group INCLUDE that $a*i = i*a = a;forall ain G$. so there is nothing to prove.
There are (among others) two axioms of a group. 1) that there is an identity element that is both a right and left identity. And 2) that for every element $ain G$ there exists an element that if both a left and right inverse of $a$.
If we were to replace axiom 1) with simply that there is a right identity element that may not be a left identity but keep axiom 2) in tact then:
The step in the proof above is reversible. sort of. $i = a^-1a = aa^-1$. so $a*a = a*(ia)implies a^-1*a*a = a^-1*a*(ia)implies a*a^-1*a = i*(i*a)implies a*i = (i*i)*a implies a = i*a$. And we have proven the stronger axiom 1)
Likewise if we were to replace axiom 2) with every element has a right identity but not necessarily a left inverse, but kept axiom 1) in tact we could prove the stronger 2) via
$i = hh^-1$ so $(h^-1)^-1=i(h^-1)^-1 = hh^-1(h^-1)^-1=h*i = h$. So $h^-1 h = h^-1(h^-1)^-1 = i= hh^-1$
But if we replace BOTH 1) and 2) with a weaker right identities exist and every element has a right inverse but say nothing of left inverses or left inverses, we can not prove a left inverse exist.
For a counter example look up a semigroup with a right identity and right inverse but not left indentities.
(Worth noting that a structure can have a right identity but not a left identity or a left identity but not right identity, but if a structure has both a left and right identity they must be same element. [If a structure has a left identity $u$ and right identity $i$ then $u*i = u$ because $i$ is a right identity and $u*i = i$ because $u$ is a left identity.])
answered Jul 29 at 18:47
fleabloodfleablood
78.3k2 gold badges29 silver badges98 bronze badges
$endgroup$
add a comment |
$begingroup$
(First some vocabulary. If $a*i = a; forall a in S$ then $i$ is a right identity and if $u*a = a;forall a in S$ then $u$ is a left identity. If $aa^-1 = i$ where $i$ is a right identity then $a^-1$ is a right inverse and if $a^!a = u$ where $u$ is a left inverse.)
First: You are correct that a proof from conclusion to non-contradiction is not valid unless every step is reversible.
In this proof the irreversible step is the very first. $a = ia implies a*a = a*ia$ but $a*a = a*ia not implies a = ia$.
(But the statement $a*a = (a*i)*a = a*(i*a)$ is most certainly correct.)
Second: The axioms of a group INCLUDE that $a*i = i*a = a;forall ain G$. so there is nothing to prove.
There are (among others) two axioms of a group. 1) that there is an identity element that is both a right and left identity. And 2) that for every element $ain G$ there exists an element that if both a left and right inverse of $a$.
If we were to replace axiom 1) with simply that there is a right identity element that may not be a left identity but keep axiom 2) in tact then:
The step in the proof above is reversible. sort of. $i = a^-1a = aa^-1$. so $a*a = a*(ia)implies a^-1*a*a = a^-1*a*(ia)implies a*a^-1*a = i*(i*a)implies a*i = (i*i)*a implies a = i*a$. And we have proven the stronger axiom 1)
Likewise if we were to replace axiom 2) with every element has a right identity but not necessarily a left inverse, but kept axiom 1) in tact we could prove the stronger 2) via
$i = hh^-1$ so $(h^-1)^-1=i(h^-1)^-1 = hh^-1(h^-1)^-1=h*i = h$. So $h^-1 h = h^-1(h^-1)^-1 = i= hh^-1$
But if we replace BOTH 1) and 2) with a weaker right identities exist and every element has a right inverse but say nothing of left inverses or left inverses, we can not prove a left inverse exist.
For a counter example look up a semigroup with a right identity and right inverse but not left indentities.
(Worth noting that a structure can have a right identity but not a left identity or a left identity but not right identity, but if a structure has both a left and right identity they must be same element. [If a structure has a left identity $u$ and right identity $i$ then $u*i = u$ because $i$ is a right identity and $u*i = i$ because $u$ is a left identity.])
answered Jul 29 at 18:47
fleabloodfleablood
78.3k2 gold badges29 silver badges98 bronze badges
$endgroup$
add a comment |
$begingroup$
(First some vocabulary. If $a*i = a; forall a in S$ then $i$ is a right identity and if $u*a = a;forall a in S$ then $u$ is a left identity. If $aa^-1 = i$ where $i$ is a right identity then $a^-1$ is a right inverse and if $a^!a = u$ where $u$ is a left inverse.)
First: You are correct that a proof from conclusion to non-contradiction is not valid unless every step is reversible.
In this proof the irreversible step is the very first. $a = ia implies a*a = a*ia$ but $a*a = a*ia not implies a = ia$.
(But the statement $a*a = (a*i)*a = a*(i*a)$ is most certainly correct.)
Second: The axioms of a group INCLUDE that $a*i = i*a = a;forall ain G$. so there is nothing to prove.
There are (among others) two axioms of a group. 1) that there is an identity element that is both a right and left identity. And 2) that for every element $ain G$ there exists an element that if both a left and right inverse of $a$.
If we were to replace axiom 1) with simply that there is a right identity element that may not be a left identity but keep axiom 2) in tact then:
The step in the proof above is reversible. sort of. $i = a^-1a = aa^-1$. so $a*a = a*(ia)implies a^-1*a*a = a^-1*a*(ia)implies a*a^-1*a = i*(i*a)implies a*i = (i*i)*a implies a = i*a$. And we have proven the stronger axiom 1)
Likewise if we were to replace axiom 2) with every element has a right identity but not necessarily a left inverse, but kept axiom 1) in tact we could prove the stronger 2) via
$i = hh^-1$ so $(h^-1)^-1=i(h^-1)^-1 = hh^-1(h^-1)^-1=h*i = h$. So $h^-1 h = h^-1(h^-1)^-1 = i= hh^-1$
But if we replace BOTH 1) and 2) with a weaker right identities exist and every element has a right inverse but say nothing of left inverses or left inverses, we can not prove a left inverse exist.
For a counter example look up a semigroup with a right identity and right inverse but not left indentities.
(Worth noting that a structure can have a right identity but not a left identity or a left identity but not right identity, but if a structure has both a left and right identity they must be same element. [If a structure has a left identity $u$ and right identity $i$ then $u*i = u$ because $i$ is a right identity and $u*i = i$ because $u$ is a left identity.])
answered Jul 29 at 18:47
fleabloodfleablood
78.3k2 gold badges29 silver badges98 bronze badges
$endgroup$
(First some vocabulary. If $a*i = a; forall a in S$ then $i$ is a right identity and if $u*a = a;forall a in S$ then $u$ is a left identity. If $aa^-1 = i$ where $i$ is a right identity then $a^-1$ is a right inverse and if $a^!a = u$ where $u$ is a left inverse.)
First: You are correct that a proof from conclusion to non-contradiction is not valid unless every step is reversible.
In this proof the irreversible step is the very first. $a = ia implies a*a = a*ia$ but $a*a = a*ia not implies a = ia$.
(But the statement $a*a = (a*i)*a = a*(i*a)$ is most certainly correct.)
Second: The axioms of a group INCLUDE that $a*i = i*a = a;forall ain G$. so there is nothing to prove.
There are (among others) two axioms of a group. 1) that there is an identity element that is both a right and left identity. And 2) that for every element $ain G$ there exists an element that if both a left and right inverse of $a$.
If we were to replace axiom 1) with simply that there is a right identity element that may not be a left identity but keep axiom 2) in tact then:
The step in the proof above is reversible. sort of. $i = a^-1a = aa^-1$. so $a*a = a*(ia)implies a^-1*a*a = a^-1*a*(ia)implies a*a^-1*a = i*(i*a)implies a*i = (i*i)*a implies a = i*a$. And we have proven the stronger axiom 1)
Likewise if we were to replace axiom 2) with every element has a right identity but not necessarily a left inverse, but kept axiom 1) in tact we could prove the stronger 2) via
$i = hh^-1$ so $(h^-1)^-1=i(h^-1)^-1 = hh^-1(h^-1)^-1=h*i = h$. So $h^-1 h = h^-1(h^-1)^-1 = i= hh^-1$
But if we replace BOTH 1) and 2) with a weaker right identities exist and every element has a right inverse but say nothing of left inverses or left inverses, we can not prove a left inverse exist.
For a counter example look up a semigroup with a right identity and right inverse but not left indentities.
(Worth noting that a structure can have a right identity but not a left identity or a left identity but not right identity, but if a structure has both a left and right identity they must be same element. [If a structure has a left identity $u$ and right identity $i$ then $u*i = u$ because $i$ is a right identity and $u*i = i$ because $u$ is a left identity.])
answered Jul 29 at 18:47
fleabloodfleablood
78.3k2 gold badges29 silver badges98 bronze badges
answered Jul 29 at 18:47
fleabloodfleablood
78.3k2 gold badges29 silver badges98 bronze badges
answered Jul 29 at 18:47
fleabloodfleablood
78.3k2 gold badges29 silver badges98 bronze badges
answered Jul 29 at 18:47
fleabloodfleablood
78.3k2 gold badges29 silver badges98 bronze badges
78.3k2 gold badges29 silver badges98 bronze badges
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%2f3307557%2fprove-a-result-by-assuming-its-true-and-showing-no-contradiction%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
4
$begingroup$
This looks like a classical logical fallacy: begging the question. That proof is OK if each step is an "if and only if", but even in that case, I agree with you that the presentation is poor.
$endgroup$
– Giuseppe Negro
Jul 29 at 16:51
1
$begingroup$
Let's look at the reversed proof: how do you go from Step 2 to Step 1? You're using "left-cancellation", correct? But that assumes $ia=a.$
$endgroup$
– Adrian Keister
Jul 29 at 16:54
2
$begingroup$
@AzIf00 If the identity element is commutative, it might be desirable to remove one of the equivalences from the axioms.
$endgroup$
– Sam Gallagher
Jul 29 at 17:02
1
$begingroup$
@Azif00 See e.g. jstor.org/stable/2371204?seq=1#metadata_info_tab_contents
$endgroup$
– Sam Gallagher
Jul 29 at 17:04
1
$begingroup$
The accepted answer to this question addresses your choice of axioms, I think.
$endgroup$
– Kajelad
Jul 29 at 17:45