Proof Positive

   If you have a good imagination, picture the following:  An eight-by-eight board (a chess or checker board will do) and a set of dominos.  If not, perhaps you can lay your hands on the real things to augment your imagination.  Now, lay (or imagine laying) one domino on two adjacent squares of the board.  Since the board has 64 squares it should take 32 dominoes to do the job.

   The fact that this is possible is obvious.  Anyone should get it right on the first try.  Now, try to lay out the dominoes such that the lower left and upper right corner squares are left uncovered.  This covers two fewer squares, so it should take one less domino.  Try it.  If you succeed, you will have proved that it’s possible.  If you fail, can you prove that it’s impossible?

   There are at least two ways to complete the proof that this task is impossible.  One way is to program a computer to check every possible arrangement of dominos.  This is the “brute force” method of proof.  The other way is more elegant.  It consists of noticing one of the features of a chess board:  The fact that adjacent squares are of opposite colors, and that squares of the same color are always diagonal.  Combine this with the fact that a domino must always cover adjacent squares and never diagonals and you have a proof.  Notice that the opposite diagonal squares are the same color.  Notice that each domino must always cover two squares of opposite colors.  You simply can’t cover two differently colored squares with each domino and have two squares of the same color left over, if the board has the same number of squares of each color.

   What does this illustrate in a larger sense?  For one thing, it illustrates the varied nature of proofs.  Statements may affirm something.  Statements may be provably true or false, they may be suspected to be true or false, or their status may simply be unknown.  A person’s “belief structure” is the set of statements that person would accept as true.  Most people accept statements as true that they can’t themselves prove to be true, but they believe that others can.  Many people accept statements as true that they know can’t be proven, or they accept inadequate proofs, or they are simply not concerned with the criteria for proof (or the truth, which to them may not even be the same thing).

   A proof of existence consists of demonstrating a single example of something.  On the other hand, you can’t ever prove that something (like God) does not exist.  Some statements assert a relationship or predict an outcome.  These are more tricky than statements about existence.  These statements may involve single instances, categories with any number of instances, or even sets with an infinite number of instances.  A proof of truth has to consider every instance.  A proof that a statement is false only has to find a single counter-example.  Sometimes an assumption is made that you can prove a statement is false by proving that its opposite is true.  Likewise, you can prove a statement is true by proving its opposite is false.  But these methods of proof are subject to the weakness of the assumption that there is no middle ground between the true and the false.  This type of proof implies that everything is provably true or false, and that itself, is an assertion that has been proven false.  It is Goedel’s Incompleteness Theorem.  It states, in essence, that statements in any adequate language cannot always be proven either true or false.  There are always three possibilities, not just two:  A statement is provably true, a statement is provably false, or a statement is not known to be either.  In this latter category there are, again, three types of statements:  Those that will later be proven true, those that will later be proven false, and those that remain, either suspected to be true or false, or proven to be undecidable.

   An interesting conjecture is the statement that every even number is the sum of two primes.  A prime number, remember, is a number not evenly divisible by any number other than itself and one.  Since every prime number must be odd, and two odd numbers always add up to an even number, it appears that the conjecture could be true.  However, this conjecture has so far defied proof.  It appears that each even number, and there are an infinite number of even numbers, is a separate problem.  No one has yet found an even number that was not the sum of two primes.  But, there appears not to be a pattern or algorithm that tells us how to get the two primes that will add up to any given even number.  Without such a procedure, we are left with an infinite number of separate problems, and an infinite number of problems cannot be solved.  Thus, if a procedure for this does not exist, we are left with a simple statement that is probably true, but can never be proved.

   Statements that are undecidable fall into at least three categories:  Those which generalize about an infinite set of things, those which are self-referential, and those involving things about which we have insufficient evidence.  I like the statement “The Barber of Seville shaves every man who does not shave himself.”  The question is, who shaves the Barber?  Since the first statement ought to answer that question, but contradicts itself when doing so, it makes the truth of the statement undecidable in a sense.  My own answer to the paradox is that the Barber of Seville is obviously a woman, but that’s a cheap solution, and the general point remains.  The statement in the preceding paragraph, “every even number is the sum of two primes,” is an example of a generalization about an infinite set of things.  And, statements that lack sufficient proof are why we have courtrooms, juries, judges, and lawyers.

   Spend some time Numinating about proofs (if you were unconvinced by “What are the Odds?” you might try constructing your own proofs one way or the other, and test them against my assertions, but be careful that you don’t create a slightly altered version, rather than an exact equivalent of what I asserted, or we will be in dispute over apples and oranges).  Next time we’ll kick it up a notch, and Numinate once again about Truth itself.