Is there a proof that performing an operation on both sides of an equation preserves equality

abstract-algebraaxiomsgroup-theoryproof-writing

so I was learning some abstract algebra and group theory, when they went over the proof of the cancellation law

$$
ab = ac\implies a^{-1}(ab) = a^{-1}(ac)\implies (a^{-1}a)b = (a^{-1}a)c\implies eb=ec \implies b=c
$$

But the first step in which you add the additional term seems jarring to me, especially since I felt we were proving ever trivial thing from the ground up. Obviously I'm familiar with middle school pre-algebra, so I know that it is true that if we perform an operation on both sides it preserves equality, but I didn't know how we know this is the case always. Is it an axiom or is it proven?

Here is my attempt at a proof, let me know if I am going in the correct direction.

Assume via axiom that $x=x$ and if $a=b$ and $b=c$ then $a=c$, and prove that $a=b\implies ka=kb$

We know that $a=b$, we define $x\mid x=a \implies a=x$. Since $a=b$ and $a=x$, then $b=x$ which we can rewrite as $x=x$. Now we perform the operation on both sides $kx=kx$, which is true via our axiom. Then we re-substitute $x=a$ and $x=b$ to get $ka=kb$. Q.E.D

That was my original idea but I don't know if that's watertight. Thank you!

Best Answer

In first-order logic, we have the formal substitution principle:

Let $\phi$ be a propositional formula with a free variable $v$, and let $\Gamma$ be a context. Also, let $x, y$ be two terms representing values. Then: \begin{align*} \Gamma & \vdash x = y \\ \Gamma & \vdash \phi[v := x] \\ \hline \Gamma & \vdash \phi[v := y]. \end{align*}

Informally, what this says is: if you can prove in some context that $x=y$, and you can also prove some statement is true for $x$, then you can conclude the same statement is true for $y$. (The notation $\phi[v := x]$ just means the result of substituting $x$ in for $v$ in the proposition formula $\phi$.)

Now, if we are working in a group, let us apply this to the formula $\phi := (a^{-1} (ab) = a^{-1} v)$. Then in the context of the proof, we are assuming $ab = ac$. Also, $\phi[v := ab]$ results in the proposition $a^{-1}(ab) = a^{-1}(ab)$, which is true by the first-order axiom (or in some formulations, the formal proof rule) of reflexivity of equality: $t = t$ for any term $t$. Therefore, the substitution principle allows us to conclude that $\phi[v := ac]$ is true, which results in $a^{-1} (ab) = a^{-1} (ac)$.

To give another application which is implicitly used in the proof, let us see how to use the substitution principle to prove the transitivity of equality: if we have $x=y$ and $y=z$ then $x=z$. For this proof, we will use $\phi := (x = v)$. Then we are assuming $y=z$. We also have that $\phi[v := y]$ is true since it reduces to the assumption $x = y$. Therefore, we can conclude $\phi[v := z]$ which is just $x = z$.

Related Question