Undecidability (was reasoning)

David <dfrankiswork@netscape.net> dfrankiswork at netscape.net
Sun Feb 9 14:15:15 UTC 2003


ER asked about Godel's theorem:
 
> Does this mean that one can answer any question in mathematics 
simply 
> by dreaming up new axioms? I'm assuming the axioms (=posh word for 
> assumption?) are "non-trivial", i.e. they don't simply echo that 
> which you wish to prove.

First, a disclaimer: this is a branch of mathematics which I never 
covered properly at college, so I'm going by what I've read in 
popularisations written for the mathematically aware general public.

However, I believe the answer is 'no'.  You first have to be sure 
that your question is one of the undecidable ones.  Even then I'm 
not sure that you can just add whatever answer you choose to get a 
new axiom.

Axioms are broadly speaking assumptions.  They are the unproved 
logical statements you make from which you construct your theory.

As an example of why you can't just dream up any axioms you like, 
take the proposition (Goldbach's Conjecture) Grey Wolf mentioned: 
that every even number (other than 2) is the sum of two primes.  
That may well be undecidable within the logical framework.  But if 
so, we can prove quite easily that it is, in fact, true.

For suppose we add the axiom that it is false.  Then we are 
asserting that there is *some* even number which is *not* the sum of 
two primes.  You can then identify this number, simply by taking 
each even number in turn and seeing if it can be expressed as the 
sum of two primes (the actual search might take a long time if the 
number is enormously large!); you have then shown that you can find 
a counterexample to Goldbach's Conjecture *within the existing 
framework of logic* which defines the integers (positive and 
negative whole numbers).  Which means that adding the axiom that the 
GC is false means that the GC can't be undecidable.  Thus we have 
proved, by contradiction, that if GC is undecidable it is true.

So we are only left with three possibilities:

GC is undecideable, and therefore true (which means that you can 
only prove it true by 'stepping outside the system';
GC is true, and can be proven so 'within the system' (IMO the likely 
case, though I can't say I follow breaking mathematical news avidly);
GC is false, and eventually someone finds a falsifying example.

I am not sure which, and how many, mathematical questions (whether 
well-known or not) have been shown to be undecidable.  IIRC, the 
Continuum Hypothesis (which states that there are no transfinite 
cardinals between aleph-null (roughly speaking the 'size of infinity 
corresponding to the natural numbers') and C (roughly speaking 
the 'size of infinity corresponding to all numbers including 
irrationals like the squrea root of 2 and trancendentals like pi')) 
is one.

BTW, there was a debate a few weeks ago between Haggridd and John 
Walton about Reductio ad Absurdam arguments.  I am delighted that 
the meandering course of discussion here has actually allowed me to 
put a genuine, bona fide, copper bottomed RAD argument on the list: 
the proof by contradiction above.

David





More information about the HPFGU-OTChatter archive