A Conversation for Logical Completeness

Not sure this bit is right...

Post 1

HenryS

"Gödel showed that this paradox could be expressed rigorously and used it to show that there are some problems which simply cannot be proved to be true or false. In fact, they are already known to be true (since if they were false a counter-example would exist which would act as proof for their falsity), but this knowledge is useless since it isn't shown logically."

Well, I'll know more when I've taken the course on Gödel incompleteness theorems this term, but I don't think it is true that there are problems that cannot be proved true or false. Well, its a bit more complex. Given some consistent formal system with enough complexity to do arithmetic at least, you can find statements that are undecidable (cannot be proved either true or false) *within that system*. Since theyre undecidable, you can add 'that statement is true' as a further axiom to get a *new* consistent formal system, which will have other, different, undecidable statements.

The statement in question essentially says 'this statement cannot be proved to be true within this system', so it *is* true, and it *is* shown logically (we prove that it is undecidable, so what the statement claims is true). Its just shown by metamathematical considerations. It is however true that *within the formal system* it is impossible to prove that the statement is true.

Well thats about as far as my knowledge on this goes at the moment - once I've taken the course, I should be able to make a more coherent comment.


Not sure this bit is right...

Post 2

Decaf Silicon

Adding axioms is just what mathematics strains to avoid. Math as a whole should be as self-supporting as possible, truth-wise. The fewer rules we dreg up without proofs, the more solid our foundation. Never mind that our foundation includes a=a and ab=ba, among other unprovables.

Hasta luego.


Not sure this bit is right...

Post 3

Steve Jessop

That's not quite the whole story, though. Mathematicians don't actually mind making up rules which are assumed to be true (we call them axioms). All maths, really, is about making up a set of axioms and then working out what we can conclude about the systems (if any) which satisfy those axioms. The result ab=ba quoted above is an example of one of the axioms of number theory, but there are systems (called non-Abelian) for which this is not only not an axiom, but it isn't even true.

Also, there are a lot of systems which have undecidable statements. This wasn't anything new when Goedel proved his results, and mathematicians were used to the idea that you could take an undecidable statement and either add it as an axiom, or add its opposite as an axiom, and get two different systems for the price of one. Effectively, you can decide arbitrarily between them.

One of Goedel's outstanding new results was to show that every system which includes the whole numbers must either be inconsistent, or have undecidable statements. This is what came as a shock, because most mathematicians didn't think it would be necessary (or even possible) to make arbitrary decisions over statements about something so simple as whole numbers.


Key: Complain about this post

Not sure this bit is right...

Write an Entry

"The Hitchhiker's Guide to the Galaxy is a wholly remarkable book. It has been compiled and recompiled many times and under many different editorships. It contains contributions from countless numbers of travellers and researchers."

Write an entry
Read more