April 25, 2024
To derive A = Z write down A. Below that write a true statement and the substitutions to apply to get the next statement = B. The equality is established when the last statement is = Z.
To get from A to B use a true statement and substitutions. True statements are axioms of the the mathematical theory you are working in. Substitutions are systematically replacing one thing by another.
Every mathematical theory has its own set of axioms. Axioms are just pretend true; different theories can have have contradictory axioms. For example, non-Euclidean geometries do not satisfy Euclid’s Fifth Postulate.
The real numbers are a Dedekind complete ordered field that you are familiar with from high school algebra, even though you might not be able to write down all of its axioms off the top of your head.
One of the axioms is the identity law for multiplication a = 1a.
This can be used to show what you might think to be the unremarkable fact that x + x = 2x. Start with
\underline{x} + \underline{x}
\qquad\{\overline{a} = \underline{1a}\mid a\leftarrow x\}
=\overline{1x} + \overline{1x}.
Underbar and overbar match what is being substituted with the result of the substitution. In this case we substituted the same expression two times. Substitution is a mechanical operation that even a dumb computer could do, but it is also a useful technique that can help you with more complicated derivations.
Another axiom is the distibutive law ac + bc = (a + b)c.
=\underline{1}\underline{\underline{\underline{{x}}}} + \underline{\underline{1}}\underline{\underline{\underline{x}}}.
\qquad\{\overline{a}\overline{\overline{\overline{c}}} + \overline{\overline{b}}\overline{\overline{\overline{c}}} = (\underline{a} + \underline{\underline{b}})\underline{\underline{\underline{c}}}\mid a\leftarrow 1, b\leftarrow 1, c\leftarrow x\}
= (\overline{1} + \overline{\overline{1}})\overline{\overline{\overline{x}}}
\qquad\{\overline{1 + 1} = \underline{2}\}
=\overline{2}x
This might seem to be a long-winded way of showing x + x = 2x but it illustrates the general technique of showing A = Z. No mathematician uses this clumsy over/underbar notation when deriving equations, but they are thinking that in their head.
Let’s derive the less unremarkable fact (x + y)^2 = x^2 + 2xy + y^2 using this technique. You may have learned the FOIL method for this – First, Outer, Inner, Last so (x + y)^2 = (x + y)(x + y) = xx + xy + yx + yy = x^2 + 2xy + y^2. Mathematics uses axioms and substituion for rigorous derivations instead of cute mnemonics.
Derivation. Start by writing A
\underline{(x + y)}^2
then write the axiom and substitutions
\qquad\{\overline{a}^2 = \underline{aa}\mid a\leftarrow(x + y)\}
Issac Newton’s preferred way of writing a^2 was aa. \underline{(x + y)} corresponds to \overline{a} and \underline{aa} corresponds to
= \overline{(x + y)(x + y)}
after substituting a by (x + y). Next we apply the distributive law
= \underline{(x + y)}(\underline{\underline{x}} + \underline{\underline{\underline{y}}})
\qquad\{\overline{a}(\overline{\overline{b}} + \overline{\overline{\overline{c}}}) = \underline{a}\underline{\underline{b}} + \underline{a}\underline{\underline{\underline{c}}}\mid a\leftarrow(x+y), b\leftarrow x, c\leftarrow y\}
= \overline{(x + y)}\overline{\overline{x}} + \overline{(x + y)}\overline{\overline{\overline{y}}}
Applying the distributive law again twice
= \underline{(x + y)x} + \underline{\underline{(x + y)y}}
\qquad\{(a + b)c = ac + bc\}
= \overline{xx + yx} + \overline{\overline{xy + yy}}
where you can provide the subsitutions in your head now. The commutitive law for multiplication yields
= xx + xy + xy + yy
Using the lemma a + a = 2a from above xy + xy = 2xy so
= x^2 + 2xy + y^2
This shows (x + y)^2 = x^2 + 2xy + y^2.
To be pedantic we should write
= \underline{xx} + \underline{\underline{xy + xy}} + \underline{yy}
\qquad\{\overline{aa} = \underline{a}^2, \overline{\overline{b + b}} = \underline{2b}\mid a\leftarrow x, a\leftarrow y, b \leftarrow xy\}.
= \overline{x}^2 + \overline{2xy} + \overline{y}^2
As your math skills improve you won’t need such low level derivations. If you get into trouble skipping steps you can always fall back to this to be confident what you write is mathematically true.
Here is a more interesting example from probability theory where X is a random variable and E[X] is its expected value. Behind the scenes X is a function and expectation is an integral.
Derive E[(X - E[X])^2] = E[X^2] - E[X]^2.
E[\underline{(X - E[X])^2}]
\qquad\{\overline{(a - b)^2} = \underline{a^2 - 2ab + b^2} \mid a\leftarrow X, b\leftarrow E[X]\}
= \underline{E[\overline{X^2 - 2XE[X] + E[X]^2}]}
\qquad\{\overline{E[A - B + C]} = \underline{E[A]} - \underline{\underline{E[B]}} + \underline{\underline{\underline{E[C]}}}\mid A\leftarrow X^2, B\leftarrow 2XE[X], C\leftarrow E[X]^2\}
= \overline{E[X^2]} - \overline{\overline{\underline{E[2XE[X]]}}} + \overline{\overline{\overline{\underline{\underline{E[E[X]^2]]}}}}}
\qquad\{\overline{E[cA]} = \underline{cE[A]}, \overline{\overline{E[b]}} = \underline{\underline{b}}\mid c\leftarrow 2E[X], A\leftarrow X, b\leftarrow E[X]^2\} (using XE[X] = E[X]X)
= E[X^2] - \overline{2\underline{E[X]E[X]}} + \overline{\overline{E[X]^2]}}
\qquad\{\overline{aa} = \underline{a^2}\} (exponent)
= E[X^2] - 2\overline{E[X]^2} + E[X]^2
\qquad\{ac + bc = (a + b)c\} (distributive)
= E[X^2] + (-2 + 1)E[X]^2
= E[X^2] - E[X]^2.
This establishes E[(X - E[X])^2] = E[X^2] - E[X]^2.
To prove ‘if A then Z’ or, equivalently, ‘A\Rightarrow B’ write down A. Below that write a true statement and the substitutions to apply to get the next statement B. If the statements P and P\Rightarrow Q occur in the derivation then the statement Q can be written (modus ponens). The proof is done when the last statement is Z – QED (quod erat demonstrandum).
Theorem. If x + x = x then x = 0.
Proof: Start by writing down A.
x + x = x
\qquad\{a = b \Rightarrow a + c = b + c\mid a\leftarrow x + x, b\leftarrow x, c\leftarrow(-x)\}
x + x = x\Rightarrow x + x + (-x) = x + (-x)
\qquad\{\text{modus ponens}\}
x + \underline{x + (-x)} = \underline{x + (-x)}
\qquad\{\overline{a + (-a)} = \underline{0}\mid a\leftarrow x\} (inverse)
\underline{x + \overline{0}} = \overline{0}
\qquad\{\overline{a + 0} = \underline{a}\mid a\leftarrow x\} (identity)
\overline{x} = 0
This shows x + x = x implies x = 0.
It is good form to explicitly state when a proof has been completed. This proof has been completed. QED.