Prove a result by assuming it's true and showing no contradiction

Question

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 $a\in G$ , $a*i=a$

$G3$: For each element $a\in 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?

Answer 1

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.

Answer 2

(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 a\in 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 $a\in 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^{-1}a = 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.])