## Monday, January 31, 2011

### Types of Proofs

When you're first taking a course in math proofs, you learn about things like direct proof, proof by contradiction, proof by induction, and so on. Now that I have more experience, these are the types of proofs that I've experienced:

Proof by Algebra
These are the types of proofs most often encountered in a math class that isn't very proof-oriented, like statistics or (sometimes) linear algebra. The problem will say something like
A Palanquin Duo is a pair of numbers, x and y, such that x+ y = a for some real number a. Then the product xy is called a Palanquin Product. Show that the minimum Palanquin Product for a given a occurs when x = y = a/2.
[Yes, I made this up completely.] You see this and you go "shit, that's a bunch of weird crap" but when you go to do it, it just requires some algebra (or calculus, or whatever - basically some calculations/math that are sort of obvious in context). Often these are pretty easy because it's sort of obvious what the next step is, and you just have to have faith that if you keep going, the proof will work out.

Proof by Definition
These proofs usually ask you to verify that something specified in the proof is, in fact, an Thing, where the Thing is something that is defined in the course. For example,
Let A1 and A2 be two topologies on a space, X. Show that A1 intersect A2 is also a topology on X.
When you first, in your math career, encounter this type of proof, you often think something like, "My gosh, why would that be true?" But if you look at the definition of a topology (or whatever), you can easily verify that all of the conditions are easily met using the assumptions that you're given.

Proof by Construction
I may not be using the word "construction" here as it is usually used in math. But sometimes you are asked to show that something exists and the easiest way is to actually show how it can be made. For example,
Show that every Lebesque-measurable function may be approximated by a step function such that [blah blah conditions].
I see these in analysis, mostly, where you end up doing a lot of stuff with epsilons and deltas and building up a giant edifice step by step. These types of proofs can be very hard.

Proof by Induction
The canonical induction proofs are when you want to prove something for every natural number, for instance,
For \$n>1\$, show that \$2 + 2^n + 2^3 + ... + 2^n = 2^(n+1) - 2\$
To do this, you prove that the statement is true for n=1 and then that, if it is true for some n, it is true for n+1. But there are much more complicated and interesting types of induction proofs out there as well. Induction is fun - when you can get it to work, it often feels like cheating.

Proof by a Trick You'd Never Have Thought Of
I assume this is self-explanatory. Usually the professor will show these proofs in class rather than expecting you to do them as homework. There is a reason some theorems are named after the mathematician who first proved or formulated them!