What does it mean to prove something?

Update: Please read this post after... Or maybe before? People shy away from having an opinion about a proposition because "it isn't proven one way or another". They either haven't seen any proof/disproof or they have a disconnected view of what "proof" means. Sometimes they'll even say things like "You can't prove a negative."

What is proof, though, and what does it mean to prove something? The easiest way to demonstrate is with a syllogism that even an Ancient Greek could grasp let alone a modern toddler. We are going to prove that this object in my hand is green.

Premise: All books are green.
Observation or Given: This rectangular object I have in my hand is a book.
Logical step: modus ponens.
Conclusion: This object is green. (I don't have to look, I just proved it.)

Hopefully two things stood out to you. One is the parenthetical--a proof means you don't have to go out and verify, if you trust the proof. Two is that a proof can be about anything, even something we can observe to be false. Going out and observing a book that's not green does not invalidate the proof given above. What it does do is falsify the premise, which falsifies the conclusion in the context of the proof. In reality, the book I have in my hand may be green or may not be, the proof says nothing about reality; I have to look to find out.

A valid proof is one that follows the rules of deductive logic through a chain of allowed steps. These steps are defined within the rules of logic or as additional premises, or the steps may even come from previous conclusions. An invalid proof is one that made a mistake with one of the rules or violated one of its premises--this is actually a useful proof technique, because if you can show that by following the rules that a particular premise contradicts itself later on, then that premise is faulty.

Not all invalid proofs have false premises or conclusions:

Premise: Bike chains make Pepsi taste bad.
Observation: This bike chain is rusty.
Logical step: modus tollens.

In this case an invalid logical step was taken. Modus tollens has no place here.

The next example after syllogisms I would give would be those evil and stupid math proofs you may have done in your first algebra or geometry class. They expect you to know a list of propositions or postulates or premises and will use those to justify every step.

Common Postulates:
1. Commutative Property of Addition: $a + b = b + a$
2. Commutative Property of Multiplication: $a * b = b * a$
3. Associative Property of Addition: $(a + b) + c = a + (b + c)$
4. Associative Property of Multiplication: $(a*b)*c = a*(b*c)$
5. Additive Property of Equality: If $a = b$, then $a + c = b + c$
6. Multiplicative Property of Equality: If $a = b$, then $a * c = b * c$

Given: $7x + 2 = 2 + 5x - 6$, solve for $x$.
Logical steps: $7x + 2 = 2 - 6 + 5x$ by the commutative property of addition.
$7x + 2 = (2 - 6) + 5x$ by the associative property of addition.
$7x + 2 = -4 + 5x$ combining like terms. (Akin to saying "TRUE or TRUE is just TRUE".)
$2x + 2 = -4$ by the additive property of equality. (In this case, we're adding $c = -5x$.)
$2x = -6$ by the same property, in this case we're adding $-2$ to both sides. (Or subtracting by 2.)
$x = -3$ by the multiplicative property of equality. (In this case we're multiplying by $1/2$.)
Therefore the solution is $x = -3$.

Phew! I did have to research how these proofs went because it's been so long since I had to do one. You literally have to specify every single step. Ew. If you had forgotten, say, the second step of transforming $2-6$ into $(2-6)$ you would have "an invalid proof". At least according to this style of proof, fortunately there are other styles.

The next kind of proof I would show is one by mathematical induction. (Which is not a logically inductive "proof", all math proofs are deductive.)

The next kind of proof I would show is one where you assume your audience isn't retarded and omit some steps or their reasoning. You start proving cooler things and more useful things, you start leveraging calculus intuitions to prove things one couldn't prove before.

Then I'd show them to Euclid's Elements. It's probably the perfect example of a set of classical mathematical proofs that build off each other. Everyone should read even just a section of it just to see Euclid's brilliance. The math itself can be challenging but at least in Book 1 should be feasible for anyone with a high school education...

Finally I would show computer-generated proofs. If time permitted, I would show a proof or two from the field of Combinatorial Game Theory just because it has a neat flavor of proofs about games.

The general idea though is you start from accepted facts, or at least assume certain facts (that you might be able to prove are contradictory to assuming them, or you might just assume them "for the sake of argument" and later say "Well yes if the world was perfect we wouldn't have this bad thing."). You can come back around to logical proofs since those are shorter to demonstrated. For instance, I can prove a negative just fine:

Premise: The fossil record would contain evidence of unicorns if unicorns existed.
Observation: The fossil record does not contain such evidence.
Conclusion: Unicorns do not exist.

You might also be able to use modus tollens if your premise permits it. (Whether common sense permits it is another matter.)

Premise: A Ph.D from MIT implies you're a smart person.
Observation: You're not a smart person.
Conclusion: You do not have a Ph.D from MIT.

As a side note, every time you prove something you necessarily prove its equivalent negation. You can transform any proposition to use negative language or positive language, but one may be harder to understand or less interesting-sounding than the other. For instance, suppose you proved that "there exists at least one woman in the neighborhood". Oh yeah. The equivalent negation of this is "not all people are men in the neighborhood". Aw. Now it's not that interesting.

The problem with negation in general is that we typically work with classes or sets of objects instead of a singular thing, and so there can easily be asymmetry in the sizes of these groups. While the things we call "food" are vast in number, the things we call "not food" are incredibly vaster. And while the things we call "odd numbers" are incredibly vast in number (in this case infinite), the things we call "real numbers" are incredibly vaster (there's a "larger infinity" associated with them than with odd numbers).

Anyway, let's get back to the topic at hand: proof.

As demonstrated, "proof" means something very specific, but it's also not a sacred cow. The real question is "Here's a proof, we know it's valid, how do we know whether its premises or conclusions are actually true?" Proof doesn't determine truth, so lack of it or abundance of it shouldn't necessarily determine your opinions on whether something is true. Now if you agree with a valid proof's premises, you must agree with its conclusions if you wish to remain consistent. If you agree that $1/3$ and $0.33333...$ are exactly, totally, completely the same numbers, and that $3/3$ and $1$ are the same numbers, then you must agree that $0.99999...$ and $1$ are exactly, totally, completely the same numbers. But whether you actually agree that $1/3 = 0.333...$ should be determined by other things you agree with.

This is where inductive logic comes into play, it's where scientific reasoning and evidence come into play. For some reason when it comes to topics that one has an emotional feeling in, one mixes up "proof" and "evidence" and assumes "evidence" is inferior to "proof" when in fact it powers it when it comes to reality. The most basic form of evidence is common sense. Why do we believe the most basic premises that we believe? It seems like the common-sense thing to do. If you didn't know any of the arguments for why the sky is blue, why would you still believe the sky is blue? Because look at it! It's blue! It's not dark green! It'd be stupid to walk around claiming something like that! Use your common sense. (Some people even go so far as to say it's self-evident, but, well, that's another matter, one I don't agree with.)

It turns out that there are three simple desiderata, that is, desirable properties, that we can define in ordinary common-sense sounding language. These three simple desiderata end up deductively deriving Bayesian Probability Theory, you can read how by looking at my posts tagged with "bayes" that start going through Jaynes' Probability Theory book.

This means that there is math governing "common sense". There is math that tells you whether you are justified in believing a particular premise is actually true, and therefore whether you can trust its deductive conclusions or not as also being true. If you care about being right, you can't afford to ignore it.

Every-day life rarely revolves around trading proofs. It revolves around trading evidence and updating beliefs. It's not legally required to give a proof that one man killed another to send the killer to life in prison, it's merely required to give enough legal evidence, which is a specific term and more restrictive than mathematical evidence. You don't require a proof that a movie is worth watching from your friend, you take their word as evidence that you'll think it's worth watching too and go watch it. The state doesn't require proof that you're not going to kill someone every time you go driving (but you will be denied a license or insurance if the evidence suggests you're a reckless driver). People's demand for proof and ignoring of evidence is proportional to how much emotional stake in the outcome they have. It's even funny that often times it's for things of less real-world consequence than those which they're perfectly happy to have a tiny amount of evidence of. (Yes, evidence is quantifiable.)

For an atheist, the God Question looks especially ridiculous, though perhaps that's not fair because if the Christians are right then they will in fact suffer the consequence of burning in Hell for eternity if they stray from their belief. (But while we're on Pascal's Wager, if you go through that sort of reasoning and maintain your belief, just remember there are other religions out there who say the same thing--that if you're a Christian, and not one of their group, you will suffer eternal torment in the afterlife.) Fortunately there's also a mathematically specific starting point in the face of no evidence. No evidence does not entitle you to have whatever prior belief you want. There is a definite starting point from which you begin to count the evidence and the information if there is any.

Next time you see someone bemoaning the lack of proof, ask them how many things they have opinions about for which they also have proofs of. Teach them the nature of evidence if they're willing, but at least let them know that the math exists which determines the right answer for anything. Whether the "right answer" is efficiently computable is another matter, but the fact that we know there is one puts the final nail in the coffin for folks who think that because they're entitled to their opinion, their opinion is entitled to be wrong or that opinions aren't meant to be judged for truth value or that they're entitled to go about this world spouting off whatever opinions they have and suffer no consequences. (This isn't meant to suggest any consequences are justified, minimally just that you can't walk around spouting falsehoods and expecting to never be called out on it.)

If you can't accept you've been proved wrong in a mathematical conversation where one assumes that the minimal set of ZFC set theory axioms are agreed upon, you should distance yourself from mathematical conversations. Similarly, if you can't accept that the evidence, mathematically, is not in your favor, you should distance yourself from any conversations and go into hiding. Yes, sometimes the evidence is not on one side, but that's because evidence is conserved. When it does amass on a particular side, it takes a lot to spread it out again and twice that effort to amass it on a different side.

Posted on 2012-03-08 by Jach

Tags: math, philosophy, stupidity

LaTeX allowed in comments, use $\\...\\$\$ to wrap inline and $$...$$ to wrap blocks.