Technical Reasoning/Examples of Mathematical Proofs

The following is two examples of mathematical proofs. The reader should learn, by looking at these, some of the common features of proofs.

• Proofs may have premises, which need no justification.

• Additionally it must reference certain basic propositions, which are "always true" and need no justification. These are axioms.

• Additionally it uses inference rules. These are formal rules that allow one to use an already accepted proposition to then justify the truth of another proposition.

• Finally, every proof has a conclusion. It is usually the theorem, stated above the proof.

---

These proofs are written for an intended reader who knows algebra and geometry, but not too much more. Therefore, I have kept the language simple, at the cost of giving truly rigorous and formal proofs.

This is intended to make the proofs understandable for a novice.

Toward the end of the next section, though, the reader will no longer be a novice. When we get there, we will revisit these theorems, and give them more professional proofs.

A Geometric Proof

The first system of logic in recorded human history, was that of Euclid's book, Elements. In this book, Euclid began from a collection of definitions, and fundamental propositions which we call "axioms". The axioms themselves do not have proofs, but every proposition which is not an axiom has a proof which ultimately derives from the axioms.

But we cannot just move from one proposition to another at random or without reason. There must be principles about how we may infer one proposition from another, and these are called "inference rules".

For example, let's look at the following argument given by Euclid at the beginning of his book. I've chosen this example because it is relatively short, and therefore a good place for a start.

Theorem: From a Segment, an Equilateral Triangle Let A and B be any two distinct points, and let ${\overline {AB}}$ denote the line segment between them. Then there is an equilateral triangle with one side equal to ${\overline {AB}}$. Proof Form the circle centered at A running through the point B. Call this circle R. Form the circle centered at B running through the point A. Call this circle S. Form a point of intersection of the two circles, call it C. Form the triangle $\Delta ABC$. Both ${\overline {AB}}$ and ${\overline {AC}}$ are radii of the same circle (R) and therefore have the same length. Both ${\overline {BA}}$ and ${\overline {BC}}$ are radii of the same circle (S) and therefore have the same length. Therefore all sides of $\Delta ABC$ have the same length, and so it is an equilateral triangle. $\Box$

Note that we traditionally mark the end of a proof with the $\Box$ symbol, affectionately called the "Halmos" in honor of the mathematician of that name.

Every argument has premises, uses some inference rules, and draws some conclusion.

Premises

In this example, there is only one premise.

• A and B are two distinct points.

Inference Rules

In this example, we used some inference rules. Note that the proof above used some of these inference rules implicitly, and they did not show up explicitly in the proof. But in a sense, these are the rules we must have been using all along.

• For any two distinct points there is a circle centered at one point and running through the other.
• Suppose two circles have radii $r_{1},r_{2}$ and the distance between their centers is d. If $r_{1}+r_{2}>d$, then the circles intersect.
• For any positive number r, we always have that $2r>r$.
• Any two radii of a circle have the same length.
• If x and y are two equal numbers, and y and z are also equal numbers, then $x=z$. (This is called the "transitivity of equality".)

If it seems a little "unfair" to say what the inference rules "must have been" after having used them, that's because in some way, it is!

In fact this is one of the reasons why we are studying logic: So that we can very rigorously lay out all of the rules in advance, so that we don't make up the rules as we go.

The Irrationality of Root-2

Let's now turn to an example which is meant to demonstrate a few things.

First of all, we will look at an example which regards only numbers, not geometry.

Second, this proof will demonstrate the use of a particular "technique" called "proof by contradiction".

The way that we will use proof by contradiction here, is to start by assuming that ${\sqrt {2}}$ is a rational number. From this, we will make several steps of logical and mathematical inference.

After several steps we will infer a contradiction! That is to say, we will infer a result which contradicts some other statement which we also inferred.

Because contradictions are impossible, then we must reject the assumption which caused the contradiction. That is to say, we must reject the assumption "${\sqrt {2}}$ is rational".

And this will be how we prove that ${\sqrt {2}}$ is irrational.

Rational Numbers

First let's review what rational numbers are. The integers are the numbers 0, 1, 2, and so on, but then also -1, -2, and so on toward negative infinite as well.

That is to say, the integers is the following set

$\{\dots ,-2,-1,0,1,2,\dots \}$

We often use the symbol ${\mathbb {Z}}$ to denote the integers. Therefore we may write that the integers are

${\mathbb {Z}}=\{\dots ,-2,-1,0,1,2,\dots \}$

The rational numbers are all numbers which may be formed as a ratio of two integers. That is to say, ${\frac {p}{q}}$ is a rational number, if p and q are both integers and q is not zero. So 1/2 is a rational number, -13/2 is a rational number, 0 is a rational number because it's the same as 0/1.

We cannot so easily enumerate the rational numbers the way that we did the integers. Instead we must use set-builder notation. With this, we may write the set of rational numbers as

$\left\{{\frac {p}{q}}:p,q\in {\mathbb {Z}}{\text{ and }}q\neq 0\right\}$

We use the symbol ${\mathbb {Q}}$ to denote the rational numbers, and therefore

${\mathbb {Q}}=\left\{{\frac {p}{q}}:p,q\in {\mathbb {Z}}{\text{ and }}q\neq 0\right\}$

It's easy to say which numbers are rational, because you can just put an integer over an integer. It's harder to say which numbers are not rational, because you have to prove that no possible integer over integer is equal to a given number. In fact it is quite hard to prove that $\pi$ is not rational, and the first proof was found only more than a thousand years after the idea of a rational number was first defined.

But it is significantly easier to prove that ${\sqrt {2}}$ is not rational, which we will do here.

Note that, by definition, ${\sqrt {2}}$ just means "the positive number which, when squared, is equal to 2". Therefore ${\sqrt {2}}$ just is the unique number which satisfies $x^{2}=2$, and it is this which we will prove is not rational.

Theorem

The following proof of the theorem contains a subproof. If any sentence is not immediately justified by an axiom or inference rule, then it requires a subproof.

Theorem: ${\sqrt {2}}$ is not rational. ${\sqrt {2}}\not \in {\mathbb {Q}}$. Proof Suppose, for contradiction, that ${\sqrt {2}}$ is rational. Then, by definition, there are integers $p,q\in {\mathbb {Z}}$, such that ${\frac {p}{q}}={\sqrt {2}}$ and with $q\neq 0$. We may assume that $p,q$ share no common factors. Subproof Suppose $p,q$ share any common factor, like $d$. Then by definition of d being a factor, there exist integers k and l such that $p=dk$ and $q=d\ell$. Then ${\sqrt {2}}={\frac {p}{q}}={\frac {dk}{d\ell }}={\frac {k}{\ell }}$. This shows that we could have represented ${\sqrt {2}}$ with just the integers k and l, which do not share the factor d. Since we could repeat this argument for any other factors, then it is always possible to eliminate common factors. Therefore ${\sqrt {2}}$ has some representation as a ratio of two integers which share no common factor. By algebra, since ${\frac {p}{q}}={\sqrt {2}}$ then therefore ${\frac {p^{2}}{q^{2}}}=2$. Then, again by algebra, $p^{2}=2q^{2}$ Since $p^{2}$ therefore has a factor of 2, then p must have a factor of 2, since all of the factors of $p^{2}$ must come from one of the two copies of p. Therefore $p^{2}$ actually has two factors of 2, one from each copy of p. Therefore, there must exist an integer $k\in {\mathbb {Z} }$ such that $p^{2}=2\cdot 2k$, by definition of having two factors of 2. Therefore, using all of the above, $4k=2q^{2}$ and so $2k=q^{2}$ But then $q^{2}$ has a factor of two and therefore q has a factor of 2. But this is a contradiction: p and q both have a factor of 2, but also they do not share any common factor. $\Box$

Premises

The above proof contained no premises!

Inference Rules

It used several inference rules, too many to be worth enumerating. But not that, from every proposition in the proof to the next proposition, an inference rule must exist which "permits" it.

Conclusion

Note that the conclusion of the proof is the statement of the theorem: that ${\sqrt {2}}$ is not rational.

The proof ends its last line on the contradiction. But the contradiction is not the conclusion. It is implied that the proof by contradiction is complete, because we have reached the contradiction -- and therefore the theorem has been proved.

So really, the conclusion of the argument is the theorem.

Triangle Angle Sum Proof

Let's see the proof that the interior angles of a triangle sum to 180°.

Note that $\angle A$ denotes "the angle at A". This refers to the rays that form the angle and therefore is not a number.

We call the "measure" of the angle, the number that is associated with it, and denote this with $m\angle A$.

Theorem: Triangle Angle Sum If $\Delta ABC$ is any triangle with vertices A, B, C, then the sum of the interior angles is 180°. $m\angle A+m\angle B+m\angle C=180^{\circ }$ Proof Choose any side of the triangle, arbitrarily. We will take it to be the side ${\overline {AB}}$, which is the side containing vertices A and B. Now draw the line parallel to ${\overleftrightarrow {AB}}$ which passes through C. Now label the angles $\angle 1,\angle 2,\angle 3$ which are formed by the line and $\angle C$. Since the angles $\angle 1,\angle 2,\angle 3$ form one side of a line then $m\angle 1+m\angle 2+m\angle 3=180^{\circ }$. On the other hand, trivially, $\angle C=\angle 2$ and therefore $m\angle C=m\angle 2$. By the "Alternate Interior Angles Theorem", $\angle A\cong \angle 1$ and $\angle B\cong \angle 3$. Therefore, by definition of congruence, $m\angle A=m\angle 1$ and $m\angle B=m\angle 3$. Therefore, by substitution of equals, $m\angle 1+m\angle 2+m\angle 3=m\angle A+m\angle 2+m\angle 3$ From the earlier equation, this is also equal to 180°. Therefore $m\angle A+m\angle B+m\angle C=180^{\circ }$ □

Interrogation

This proof is beautiful! It is simple, natural, intuitive.

However, we should interrogate it. By that I mean that we should ask "How do we know this is true?" for each step.

The first move is to choose a side arbitrarily. This is really no step of logic, so much as merely drawing the reader's attention to one side.

The second move is to draw the line parallel to the chosen side (or line through that side), which passes through the remaining vertex, C. How do we know that this parallel line exists?

We have a choice to make here.

We could say that there is some reason why we know that this line exists. But then we would need to interrogate that reason, which may itself have reasons, and so on.

On the other hand, we could simply declare that the existence of such a line is a "fundamental" fact which needs no reason. That is to say, we could declare it to be an axiom. Should we?

It certainly seems obvious that this parallel line through C exists. Is that justification enough to call the principle an axiom?

Mathematicians historically resisted calling this an axiom, just from some itching suspicion that it doesn't sound fundamental "enough". It seems like the kind of complicated thing which should be derived from other more fundamental principles.

The Other Axioms

Here are the other geometric axioms accepted by Euclid and those after him. These were each regarded as completely uncontroversial and appropriate to choose as axioms.

1. Through any two points, there is a unique line segment from one to the other.
2. Any line segment may be extended infinitely in either direction.
3. Given any two points, call them A and B, there is a unique circle centered at A and passing through B.
4. Any two right angles are congruent.
   

The Parallel Postulate Suppose there are two lines l and m, with point A on l but not m, and point B on m but not l. Suppose that ${\overline {AB}}$ forms angles $\angle A$ and $\angle B$ with lines l and m respectively, on one side of ${\overline {AB}}$. If their sum is less than 180°, $m\angle A+m\angle B<180^{\circ }$ then lines l and m must meet on this side.

Notice how much simpler and more intuitive the other axioms are, when compared with the parallel postulate. It is understandable that the ancient Greek geometers would have sought a simpler axiom which could be used to prove this one.