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
editThe 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.
Note that we traditionally mark the end of a proof with the 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
editIn this example, there is only one premise.
- A and B are two distinct points.
Inference Rules
editIn 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 and the distance between their centers is d. If , then the circles intersect.
- For any positive number r, we always have that .
- 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 . (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
editLet'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 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 " is rational".
And this will be how we prove that is irrational.
Rational Numbers
editFirst 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
We often use the symbol to denote the integers. Therefore we may write that the integers are
The rational numbers are all numbers which may be formed as a ratio of two integers. That is to say, 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
We use the symbol to denote the rational numbers, and therefore
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 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 is not rational, which we will do here.
Note that, by definition, just means "the positive number which, when squared, is equal to 2". Therefore just is the unique number which satisfies , and it is this which we will prove is not rational.
Theorem
editThe 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: is not rational.
.
|
Premises
editThe above proof contained no premises!
Inference Rules
editIt 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
editNote that the conclusion of the proof is the statement of the theorem: that 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
editLet's see the proof that the interior angles of a triangle sum to 180°.
Note that 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 .
Theorem: Triangle Angle Sum
If is any triangle with vertices A, B, C, then the sum of the interior angles is 180°.
|
Interrogation
editThis 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
editHere 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.
- Through any two points, there is a unique line segment from one to the other.
- Any line segment may be extended infinitely in either direction.
- Given any two points, call them A and B, there is a unique circle centered at A and passing through B.
- 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 forms angles and with lines l and m respectively, on one side of . If their sum is less than 180°, 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.