Perhaps the biggest difference between mathematics at school and at university is a change in style into reasoning in more abstract and rigorous ways. As a student of pure mathematics you will for instance spend a great deal of your first year real analysis course untangling definitions and proving facts you may have taken granted for years – in a sense re-learning everything from scratch in a more formal setting.
I myself got to spend my first lecture in real analysis seeing proofs of statements like
from the axioms of the real number system, and a few lectures later proving effectively that a continuous function taking positive and negative values must pass through the
x-axis (Intermediate Value Theorem).
I recall that the main difficulty faced in the very beginning by some people (including myself) came down to lack of training in constructing and appreciating formal arguments, the mechanics of it. Although some universities have introductory courses to pure mathematics not all do, and they are usually very short (mine was one week).
Therefore I wanted to write a few lines about what most schools and some universities may not explicitly cover, namely the common high level methods for proving mathematical statements.
I will also remark before continuing that this is not a discussion about proofs in the formal sense of proof theory (a branch of mathematical logic). This is mainly a discussion about proofs in everyday mathematical practice.
Here methods will be outlined to keep in mind when facing mathematical statements of a certain form.
An implication consists of a Hypothesis and a Conclusion written , meaning “If then “.
An example of an implication is:
The truth table of the implication statement is defined as follows:
Method 1.1 (Trivial Proof):
From the truth table you can see that if you are able to show that the conclusion is true then is always true regardless of the truth value of the hypothesis .
Consider the following statement: “If I live in London then I live in the universe”.
Since the conclusion is always true it does not matter where I live, the implication is still true.
Note that the notion of a trivial proof usually means something different from the above.
If a mathematician refers to a proof as trivial they usually mean that it is “obvious”/”easy to prove” (in relation to the assumed knowledge of the audience).
Though you should beware of people who do this too much, it is really not a substitute for a proof if it means you can’t reconstruct it.
Method 1.2 (Vacuous Proof):
From the truth table you can also see that if you are able to show that the hypothesis is false then is always true regardless of the truth value of the conclusion .
This has the somewhat surprising meaning that a false statement can imply anything!
Consider the following statement “If pigs fly then you are president of USA”.
Pigs don’t fly so the hypothesis is false and so the implication is true.
But clearly you are not president of USA (unless you are Obama reading this in which case you should stop procrastinating and get back to work!) so how does this make sense?
The rationale behind the table is that an implication is defined to be true until proven false.
Who knows what happens if pigs do fly, maybe you will then be president?
We cannot know until there is a flying pig and therefore since we can’t say that the implication is false we must say it is true.
(DISCLAIMER: please don’t try throwing pigs out the window hoping they will fly, I am not responsible).
Method 1.3 (Direct Proof):
This is perhaps the most familiar method.
To show that the implication is true you assume is true and deduce (by some logical process) that is true.
Here is how you can prove using the direct method:
Then using the hypothesis.
Therefore and so .
Hence the implication is proved.
Existence statements require you to show the existence of some mathematical object in a set satisfying a certain statement . Often such existence statements are combined with implications to say that under certain hypotheses we can assert the existence of an object satisfying a given statement.
A mathematical object can be anything from a number, matrix or graph to circles, spheres and manifolds in geometry to groups, rings and modules in algebra.
There are essentially two categories of existence proofs, constructive and non-constructive.
I will also mention a third which really belongs to one of the two above but is worth mentioning separately.
Method 2.1 (Constructive Proof):
The constructive method is based upon building a mathematical object directly by means of supplying an algorithm or procedure for the construction of the object.
Such proofs can give a wealth of insight and are therefore often preferred over all other methods.
However constructive proofs are not always easy to find.
Safe to say being destructive (or rather non-constructive) is many times easier than being constructive – true in life, true in mathematics.
– Prove that there exist a real root to .
so and hence we can exhibit as a real root.
Here I have proven that has a real root by explicitly finding one through trivial factorization, so the proof may be considered constructive.
A somewhat less trivial example is given by the Euclidean Algorithm. Not only does it show the highest common factor of two integers exist, it also tells you how to find them.
Method 2.2 (Non-Constructive Proof):
A non-constructive proof usually means showing that something cannot not exist, and therefore must exist.
This argument crucially relies on a philosophical principle dating back to Aristotle called “Law of the excluded middle” which is the third of the three classical Laws of Thought.
The law says that everything which has a truth value is either True or False, there is no middle ground.
Therefore if we can show that something cannot not exist (by means of contradiction) then the only alternative is that it must exist by the law of the excluded middle.
The law basically implies we are allowed to eliminate double negations.
Both proof by contraposition and proof by contradiction (see above) depend on this law for their validity.
One school of philosophy known as ‘Constructivism’ rejects the law of the excluded middle and therefore rejects this method altogether and all proofs that follow from it (imagine how devastating for mathematics!).
Nevertheless this law is generally accepted by most people throughout mathematics.
The disadvantage with this method is that it doesn’t usually give much insight into how to find the object, it just tells you it must exist. However on the plus-side it is often easier to argue by (and sometimes the only possible argument).
A proof can also be non-constructive if it refers back to a theorem which guarantees existence but in turn gives no constructive answer.
– Prove that there exist a real root to .
I mentioned the Intermediate Value Theorem earlier which implies that a continuous real-valued function taking positive and negative values must cross the x-axis at least once.
Now being a polynomial is a continuous real-valued function (why?).
Moreover and .
Hence has a real root by the Intermediate Value Theorem.
In fact a very similar argument can be applied to show that any odd-degree polynomial always has at least one real root (how?).
This proof is non-constructive because I have not given a method for finding the real root, just referred to a theorem which tells us it has to exist somewhere (in fact somewhere between -2 and 2).
– Prove that some digit in the decimal expansion of has to appear infinitely often.
We know is irrational so its decimal expansion is never ending.
Suppose there didn’t exist a digit occuring infinitely often.
Then each of the digits appears finitely many times, say at most times each.
But then there can be at most decimals in the decimal expansion of which is a contradiction to its irrationality.
Hence there exist a digit in the decimal expansion of appearing infinitely often, but we don’t know which.
Method 2.3 (Probabilistic Proof):
The Probabilistic Method proceeds by showing that an object with given properties must exist with positive probability. It can then be claimed with certainty that the object has to exist since there is at least one object in the sample space pushing the probability above zero.
The method is non-constructive.
A full example is probably slightly out of scope for this post but perhaps among the simpler examples is a proof of a lower bound on Ramsey Numbers of the form due to Paul Erdos.
You can read about it here.
Method 4.1 (Combinatorial Proof):
A combinatorial proof revolves around proving some identity by means of finding an explicit bijection or counting the same thing in two ways.
Combinatorial arguments are usually extremely more elegant and illuminating than their (usually) inductive counterpart.
Here is an example of a combinatorial proof:
– Prove that
On the right hand side we have the cardinality of the power set (i.e the set of all subsets) of objects.
On the left hand side we are summing over the number of all subsets of size for
These two are equal and hence the identity follows.
Now try proving this by induction!
More examples can be found in a previous article I wrote on the Orbit-Stabilizer Theorem and the Burnside Lemma.
Method 4.2 (Uniqueness Proof):
Statements which have the word “unique” in them require uniqueness proofs.
Uniqueness can mean different things in different contexts.
In number theory you may be talking about the only number, or the only number modulo n satisfying a given proposition.
In algebra you may be talking about the only algebraic object up to isomorphism (algebraic equality).
In topology you may be talking about the only topological space up to homeomorphism (topological equality).
In general one could prove uniqueness with respect to any class or invariant.
Proofs of uniqueness often goes hand in hand with proofs of existence.
The skeleton for uniqueness proofs are almost always the same.
One assumes non-uniqueness and then shows that the supposedly non-unique objects satisfying the given proposition must in fact be equal.
Here is a trivial (yet demonstrative) example of this procedure:
– Prove that has a unique solution
Suppose there are two numbers satisfying the above equation.
Then and .
Hence the solution is unique if it exists (this needs to be proved as well, but we can easily see it is 2)
There are of course a myriad of other techniques and proof patterns specific to more narrow mathematical domains, but most of the methods you have seen above are used throughout mathematics.
It may also be worth mentioning how to disprove a mathematical statement.
To disprove a mathematical statement it is enough to produce exactly one counter example.
For instance if you are to disprove that is true for all you should not show that is false for all . It is enough to exhibit one such that is false.
It is also important that you prove that your counter example is valid by proving that it satisfies all hypotheses AND does not satisfy the conclusion.
For example here is a false statement:
– “All real numbers are rational”
We can disprove this by exhibiting one number which we prove is real and cannot be rational.
Provided exists we proved in Method 3.5 that cannot be rational.
A proof that exists as a real number can be found here.
These facts together disproves the statement.
How do you know if a statement is true or false?
There is no general answer, if there were mathematics wouldn’t be particularly interesting.
What about heuristically?
If you are proving exercises in class you may as well trust the problem setter unless they explicitly ask you to determine the true or falsehood of a statement.
In general having found a question that makes sense (which can be hard in itself) I would personally recommend going by your intuition (…whatever that really means). If you think it might be false you may want to start looking for a counter example immediately. If you have no clue then you should start proving the statement. While doing so you might stumble over something which breaks the statement and that can help you construct a counter example by exploiting what makes it fall apart. Otherwise you either succeed in proving the statement or you get stuck somewhere and what to do then is a topic for another discussion.
Finally, if you are interested in reading about some humorous false proof techniques see here. I am sure anyone who have sat in a math class could identify with at least some of these.
Here are some exercises you may wish to try:
Exercise 2 (Binomial Identity – Intermediate):
Prove the binomial identity via induction.
Can you find a combinatorial proof?