# What does the completeness of a system mean for the provability of certain statments?

Through the 16th to 19th centuries mathematicians tried to prove the Euclids parallel postulate from Euclid's other four postulates. In the beginning of the 19th century the mathematics community found that the fifth postulate is logically independent of the other four, and thus could be replaced another postulate, giving rise to non-euclidean geometry.

In the 20th century Tarski provided an axiomatic formulation of the euclidean geometry that is complete.

This leads me to a few questions. If Euclid's fifth postulate was unprovable from the other four, wouldn't that make (euclidean geometry - parallel postulate) incomplete? After all, there is an undecidable proposition. That would seemingly make the entirety of Euclidean geometry incomplete.

Taking this further, couldn't you remove an axiom from any axiomatic system, and assuming that axiom is not redundant, then you have a truth that is no longer provable? (otherwise you wouldn't need it as an axiom in the first place.)

I think I am mistaken about the nature of Gödel's theorems, completeness, decidability, or all of them. I was hoping someone could set me straight.

-
The traditional Euclidean axiomatization, with the Fifth Postulate, was not an axiomatization in the modern sense. And it was quite incomplete. The notion of betweenness was used informally, and many (most?) of the theorems were not really proved. For example, at the very beginning an equilateral triangle is constructed, the usual circles construction. But nowhere is it proved that the circles meet. Hilbert (second order) and Tarski (first order) gave the first correct axiomatizations. –  André Nicolas Jul 11 '12 at 4:37

I suspect the worry behind your question is this: What's so great about Gödel's Theorem, since incompleteness is pervasive? (Take your favourite axiomatic system, drop a non-redundant axiom, and there you have it -- incompleteness!)

The point to grasp about Gödel's result is that it is an incompletability theorem. Roughly, a consistent effectively axiomatized formal theory which aims to cover (at least) the arithmetic of addition and multiplication for natural numbers will not only be incomplete, but is in a good sense incompletable, so long as we want the theory to remain consistent and effectively axiomatized (meaning that we can mechanically recognize an axiom when we see it!).

This is made pretty clear in the Wikipedia entry, or in the first chapter of my Gödel book which you can download from http://www.logicmatters.net (go to the Gödel pages there).

-
The first-order theory of the "true" natural numbers, i.e. the set of all first-order sentences true when interpreted in the standard natural numbers, is complete by construction. There are some important hypotheses in Gödel's theorems! –  Zhen Lin Jul 11 '12 at 8:39
Yes: and Gödel's theorem therefore shows that the set of all first-order sentences in the language of basic arithmetic which are true when interpreted in the standard natural numbers is not effectively axoimatizable. –  Peter Smith Feb 13 '14 at 8:50

Yes, Euclid minus 5th is incomplete. No, entirety of Euclid is not complete - 5th completes it.

Situation differs from Godel in that Godel showed that certain systems (e.g., first-order arithmetic) can't be completed by adding any finite number of axioms (other than by making the system inconsistent by adding a contradiction).

-