0

I was always taught that if I want to prove that some element, say an additive inverse, is unique, that I suppose there are two inverses and establish that they are equal.

What was left out I think, though, was the specific proof strategy. It seems to me that there are two different ways to think of this:

a) Direct proof: let $b$ and $c$ be arbitrary field elements. Establishing that they are equal, since they are arbitrary, establishes that any such elements with this property are equal.

(Arguably, there is some induction associated with this, but it seems to me that it isn't completely necessary, because we've already extended it to any arbitrary element.)

b) Proof by contradiction: let $b$ and $c$ be arbitrary field elements, and suppose $b \neq c$. Then establish that $b = c$.

The latter proof strategy seems more common to me from what I have seen, but the contradiction aspect seems unnecessary when we could just prove this fact directly.

Am I correct that proofs of uniqueness, generally speaking, are direct applications of the universal introduction rule in logic?

Bernard
  • 175,478
  • What is the introduction rule? – Bernard Feb 07 '20 at 08:42
  • I am perhaps not stating this as rigorously as possible, but essentially: if I prove $P(a)$ for some proposition $P$ and $a$ is arbitrary, then $\forall a, P(a)$ is true. –  Feb 07 '20 at 08:47
  • I think the two methods are not equivalent. The b) version seems stronger too me, as the assumption sometimes gives you the existence of things (thinking of functions we may get an input with distinct outputs), which may be useful when trying to prove the equality. – Jonas Linssen Feb 07 '20 at 09:12

1 Answers1

0

A formal proof of any statement in a mathematical theory is simply an ordered list of statements containing the statement to be proven and such that each statement is either

  • an application of an axiom of the theory, or
  • some statement "$B$" which is preceded in the list by statements "$A$" and "$A \implies B$".

Such proofs would be exceedingly difficult to produce directly for all but the simplest of theorems. Thus we introduce several "proof methods" that allow us to simplify the lists of statements needed to establish a proof. These methods are themselves justified by meta-mathematical arguments that if such a simplified proof exists, then it can always be converted into a full formal proof.

The most obvious method is to allow applications of previously proven theorems to appear as statements in a proof. This is justified because one could simply insert the proof of the other theorem into this proof to get a formal proof.

Methods relevant to your question are:

  • Method of the added hypothesis: You create a new mathematical theory by adding an additional axiom "H" (the "hypothesis") to the axioms of the original theory. If a statement $B$ is proved in this new mathematical theory, then $H\implies B$ can be proven in the original theory by prepending the statements in the proof of $B$ with "$H \implies$".

Any time you see phrases such as "Let ..." or "Suppose ...", this method is being used.

  • Method of the added constant: This is a subvariety of the method of the added hypothesis. The added hypothesis $H(c)$ includes an unquantified variable $c$. Unquantified variables in an axiom are called constants of the theory. For example, in the theory of Real numbers, $\Bbb R$ is a constant. It appears in the axioms of that theory without being quantified (i.e., introduced with a $\forall$ or $\exists$). If some statement $B(c)$ can be proven with the added hypothesis, then $\forall c, H(c) \implies B(c)$ can be proven in the original theory.

This is what you've called the "universal introduction rule".

  • Method of proof-by-contradiction. By a simple trick, you can prove anything from a contradiction in conventional logic. In this method, to prove a statement $A$, you add the hypothesis $\lnot A$, and proceed to prove both $B$ and $\lnot B$, for some statement $B$. From this one deduces $A$ by the trick. In the original theory this proves $\lnot A \implies A$, which can be re-written as $(\lnot\lnot A) \vee A$, which reduces to $A \vee A$, and then to just $A$.

The point of all this (other than to improve your grounding in the theory of proof) is to point out that - under classical logic - any proof by contradiction can be rewritten as a direct proof. Contradiction is not capable of proving something that is unprovable otherwise. And the only thing more fishy about it than a direct proof is whether one wants to accept certain components of classical logic.

We resort to proof by contradiction not to prove something that cannot be proved otherwise, but rather because it makes the proof easier to follow. Take a common proof that $\sqrt 2$ is irrational:

Assume that $\sqrt 2 = \frac pq$, where $p, q$ have no common factors. In particular, at most one of them is divisible by $2$. Then $p^2 = 2q^2$, so $2\mid p^2$ and therefore $2\mid p$ and $2^2 \mid p^2 = 2q^2$. But then $2\mid q^2$ and thus $2 \mid q$, in contradiction to $p$ and $q$ having no common factors.

Try rewriting that proof without using contradiction. The justifications above will tell you how to do it, but the result will be a horrifying mash of implications that are near-impossible to follow.

So it may be possible to prove uniqueness without using contradiction (and quite frankly, I quite commonly see it proven without contradiction), but it is not always as easy.

Paul Sinclair
  • 43,643