Undecidability (was reasoning)

Tim Regan <timregan@microsoft.com> timregan at microsoft.com
Tue Feb 11 20:05:43 UTC 2003


Hi All,

--- "ER" wrote:
> can one introduce a new, self-evident, axiom to ZF that allows CH 
to be decidable? 

My understanding of Gödel's Theorem is that your job would never be 
finished. For any new theorem, you could extend the axioms to make 
the theorem provable (the easy way is to add the theorem as an axiom 
itself, but there may be ways that meet your "self-evident" criteria 
too). But lurking around the corner is another theorem that you 
cannot prove so you add axioms to fix that. But lurking around the 
corner is another theorem that you cannot prove so you add axioms to 
fix that. But lurking around the corner is another theorem that you 
cannot prove so you add axioms to fix that. If I were Lemony Snicket 
I'd keep this going for at least a page, but I'm not. Gödel proved 
that you must either go on forever adding axioms or add one that 
contradicts an existing axiom rendering the system inconsistent.

Back to the Continuum Hypothesis. I think there are a whole bunch of 
axioms that one can add, that each turn out to be equivalent to the 
hypothesis itself, and thus render it provable. None of them are 
self-evident in the same sense that Zermelo-Fraenkel set theory 
axioms are. But "self-evident" is a subjective term.

Self-evident axioms have a hard time through history. Think of 
Euclid's axiom that parallel lines never meet and Lobachevsky's 
sphere work (where parallel lines do meet!); or the law of excluded 
middle (something is true or it is not true) and constructivist 
mathematics (which proved 'useful' to theoretical computer 
scientists since the constructivist's notion of proof coincides with 
the execution of a program).

Though it's out of print now I really liked Wiliiam S. 
Hatcher's "The Logical Foundations of Mathematics" (Pergammon 1982; 
ISBN 0-08-025800-X). He has a great Chapter on Frege's system. 
Hatcher got me so lulled by the clarity of the system that I found 
the flaw (Russel's paradox) a shock when it is unveiled at the end 
of the chapter - even though I was already familiar with the paradox 
and its implication to Frege.

It is odd how Gödel's Theorem hasn't had the impact you'd expect in 
mathematics, outside the study of logic and foundations. I did a 
maths degree as an undergrad (ages ago, '84 - '87), and while we 
covered the theorem in logic, it was not mentioned in any other part 
of the mathematics course. Recently though, we had a talk at work 
from a Berkeley Computer Science professor, Martin Davis, which he 
described as follows:
"Although Kurt Gödel was on TIME magazine's list of the twenty 
greatest "scientists and thinkers" of the twentieth century, the 
work of the overwhelming majority of mathematicians has been quite 
unaffected by his work.  I will discuss Godel's own vision of the 
implications of his incompleteness theorem for the future of 
mathematics, and will talk about what has actually been accomplished 
in that direction."
It was a good talk (though sadly lots of it was over my head).

With all this OT chatter of mathematics, it would be great to know 
what Hermione actually learns in Arithmancy. But sadly, I my think 
finding out is about as likely as my getting a Hogwart's letter :-(

Cheers,

Dumbledad.






More information about the HPFGU-OTChatter archive