Proof Techniques (Informal)
We do a lot of proofs in mathematics. So it's relevant to have some general intuition for the informal notions of how we talk about proofs, so that there is intuition that more precise notions can crystallise around.
While there are more developed and formalised systems of proofs capable of proving things more clearly and precisely that are able to be studied in their own right, the goal here is to introduce some basic ideas and intuitions for proofs. These don't tend to be used individually, but mixed and matched and represent a more general notion of things.
Constructive Proofs
These are their own whole rabbit hole on their own, and there are whole branches of math devoted to this. Most notably, type theory.
One simple and intuitive way you might want to try to prove something is to just provide an example of the thing.
Let's say you want to prove that 4 is even. Well a number is even if it is a multiple of 2. So if we provide "2*2=4", then we have a proof that 4 is even.
"Any even number plus 2 is even."
So it takes an even number x. Since we know that x is even, we have an element y such that 2y=x.
2y+2=x+2
2(y+1)=x+2
Therefore, we found our candidate. If x is a number, and it has a proof y that it is even, x+2 has a proof that it is even, namely y+1.
How can you prove that there exists a number such that the sum of its factors equals its squares? By providing a number: 6, and checking the computation.
This kind of proof is called a Constructive Proof. Proof by construction can be surprisingly strong at times. But it has a handful of large weaknesses.
We often call the provided proof in a constructive proof a witness.
For example: Can you proved a witness to the claim that 64 is a perfect square?
Proof by Exhaustion
This is just a proof where you brute force the thing. For example, you can prove that every number less than ten thousand that ends in 0 is a multiple of ten by manually checking each one. That's a waste of time in that specific case but technically possible.
If you have reduced something to a finite list of things, you can just try all of them. Very often people don't manually do proof by exhaustion, but rather have a computer check a bunch of cases. An example of an exhaustion step was how all the base cases were checked for the four-colouring problem.
There isn't much to say on this one.
Proof by Cases
This is kind of the same thing as proof by exhaustion, where you prove it when one thing is true, and again if it was false. I have listed it separately because it's a special case of proof by exhaustion. You can nest these to get more cases, and thus do arbitrary proof by exhaustion. The vibe is sort of different, though.
An example is the proof that n²+n is always even. There are two cases, n is even, and n is odd. If n is even, it is 2m, and thus n²+n=4m²+2m=2(2m²+m)
And if it is not even, then it is 2m+1, and hence
n²+n=4m²+4m+1 + 2m+ 1= 4m²+6m+2=2(2m²+3m+1)
And hence is even.
Proof by Assumption
Let's say you want to prove that whenever A is true, B is also true. In that case you begin by assuming A, and then you can see what else is true.
For example, if a divides k, then a divides bk for every b.
First you assume that a divides k. That means there is some n such that na=k
And then that means that for every b such:
bna=bk
Hence an also divides bk.
Proof by Contrapositive
This is a special case of proof by assumption. Instead of assuming the premise, you assume the end goal is false, and show the premise must be false.
For example, if n² is even, then n is even.
If n is not even then n=2m+1 for some integer m. And thus n²=4m²+4m+1, which is an even number plus one. n²=2(2m²+2m)+1 hence if n is not even, n² is not even.
Therefore, by contrapositive, n² is even means that n is even.
Proof by Contradiction
Proof by contradiction is where you begin by assuming that something is not true, and you show that that doesn't make any sense.
For example, √2 is irrational:
Let's begin by assuming the opposite, that it is rational. In that case
a/b=√2
And thus there is some smallest pair a and b such that
a²/b²=2
Where this is as simplified as you can make it. But the goal is to show it can still be simplified, because it doesn't make sense if either number is odd.
Or:
a²=2b²
This means a² is even.
And an odd number squared is odd, so a² being even implies a is even. Let's call hald of a as n.
Notably, this means a²=(2n)²=4n², hence
4n²=2b²
And thus
2n²=b²
But that means b is even, or equal to some 2m.
But if a/b is made of two even numbers, then n/m is the same as a/b. n/m is thus a more simplified version of a/b. Which contradicts where we said a/b was the most simplified version. Therefore, there is no such rational a/b.
Hence the square root of 2 is irrational.
Inductive Proof
Proof by induction! This is where I come in! (Ordinals are the structure that induction works on.)
This is where you prove something by showing it is true for some smallest case, and then if it is true for all the smaller cases, then it must be true for the next case.
For example, every natural number is either 2m or 2m+1.
Base case: 0
This follows by construction by the witness m=0
Inductive step: n+1
Now we prove it for any n+1.
If you already know it's true for every number less than n+1, then that means you know n is equal to some 2k or some 2k+1.
Proof by case:
Case: n=2k
Then you have the witness m=k, that shows n+1 equals 2m+1.
Case: n=2k+1
n+1=2k+1+1=2k+2
And thus the witness m=k+1 shows that n+1=2m for some m.
Formal Proof
This is doing a formalised proof in a proof system. Most formal proofs need no instances of natural human languages, since they use their own new languages that are easier to check and verify. This is when you start being super careful. You can justify all the techniques I've introduced above in most formal systems.