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!

  • 8
    One way of looking at it is to observe that multiplication in a group is a function. If $G$ is a group, and $a$ is a fixed element, then $f:x\mapsto ax$ is a function $f$ from $G$ to itself. Because a function only has a single value at all the elements of the domain, we have the implication: $x=y\implies f(x)=f(y)$. This applies to all functions. Injective or not (injectivity gives you the converse implication also). – Jyrki Lahtonen Aug 14 at 18:43
  • Here's the answer I gave to a similar and much related question : math.stackexchange.com/questions/2808744/… – Max Aug 15 at 13:05
up vote 15 down vote accepted

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$.

  • 1
    No disrespect meant to the answer, but this explanation is always offered, and I never understand how it helps. The key of the problem seems to be just that the group operation is a function when one side is fixed. When people bring up "the substitution principle" I am always reminded of students who defined some $f$ and then concluded that $a=b\implies f(a)=f(b)$ by the substitution principle, when in fact their $f$ wasn't a function at all. In other words, I guess they didn't recognize their $f$ didn't satisfy the description given above. Very easy to misunderstand, comparatively. – rschwieb Aug 14 at 20:23
  • 2
    @rschwieb Your comment along the lines of "it's because group multiplication is assumed to be a function" would make a great separate answer. – Daniel Schepler Aug 14 at 21:06
  • Reluctant to, since the last sentence of the other solution and Jyrki's comment already say as much :/ – rschwieb Aug 15 at 2:31
  • @rschwieb I'm quite sure the error in those proofs can be pointed out without referring to the concept of a function. – JiK Aug 15 at 10:01
  • 1
    @JiK Given that "function" is a prerequisite for defining a group, I don't see the merit in skirting what functions are. If the answer to a question already follows by definition, that should be mentioned foremost. – rschwieb Aug 15 at 13:11

We usually take it as an axiom of the relation of equality. In particular, we assume that on a set $E$ there is a relation $=$ which satisfies the following properties for $a,b,c\in E:$

(1) $a=a$ for all $a\in E$ (egoism), (2) If $a=b,$ then $b=a$ (reciprocity), (3) If $a=b$ and $b=c,$ then $a=c$ (continuity), (4) For any function $f$ defined on $E,$ we have that if $a=b,$ then $f(a)=f(b)$ (conservation).

  • 3
    I suppose that reflexivity, symmetry, transitivity are more commonly used for the first three properties – Hagen von Eitzen Aug 14 at 18:19
  • @HagenvonEitzen Yes, that is correct. – Allawonder Aug 14 at 18:46
  • 3
    +1 for the last line alone. Sorry that I missed it in my first reading, when typing my comment under the question – Jyrki Lahtonen Aug 14 at 18:48
  • @Allawonder Where do 1-3 even come into play? As far as I can see it simply follows from 4) since multiplication on the left by an element is by definition a function. – rschwieb Aug 14 at 20:17
  • 1
    @Allawonder OK: thanks for the clarifying comment :) – rschwieb Aug 15 at 13:20

If the sign "$=$" was some relation that we had just defined on strings like "$ab$", then it would be necessary to establish what you ask for. That is not the case, however. The sign "$=$" denotes equality and juxtaposition of letters denotes multiplication, which is a function. And for every function $f$ you have that $x=y$ implies $f(x)=f(y)$. (Or more similar to the situation here: $x=y$ implies $g(z, x)=g(z, y)$.)

Your proof seems fine, but a bit more complicated than necessary.

We start with x = x by the reflexive property of equality. Then we substitute each x with ka yielding ka = ka, since the reflexive property of equality holds for all x, and closure holds for any operation by definition.

Then, since a = b, we can choose to only replace the rightmost "a" with "b" and that yields,

ka = kb.

Since we've assumed an arbitrary binary operation here (not a group) which we suppressed writing, for any binary operation F, we have that if a = b, then F(k, a) = F(k, b).

The result has many corollaries, all assuming that x = y, such as F(a, k) = F(b, k), and for a unary operation U, U(x) = U(y), and for any trinary operation T, T(k, a, j) = T(k, b, j). The most general of which seems as follows:

Theoerm: Suppose that x = y, and that a$_1$, ..., a$_n$ is a complete list L of variables and constants in a formula with an operation F. Suppose for some a$_k$ in L, a$_k$ = x. (Note k could equal 1, or k could equal n). Then

F(a$_1$, ..., a$_k$, ..., a$_n$) = F(a$_1$, ..., y, ..., a$_n$).

Proof: I'll leave this as an exercise. See above for a hint.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.