0
$\begingroup$

I am terribly confused what really "Incomplete" mean in terms of the Godel's theorem.

  1. Does it mean there are some theorems that are definable in First order theory of natural numbers and true but not deducible? (Then doesn't it go against first order completeness?)
  2. Does it mean there are some deducible sets that are not decidable? (They why is it even called as incompleteness)
  3. Does it mean there are theorems of natural numbers which is not definable in first order logic? (But thats obvious since all subsets of natural numbers are uncountably many)

I am not able to follow the proof without getting an understanding of what its trying to prove.

$\endgroup$
4
  • $\begingroup$ theorems instead of theory? $\endgroup$ – Thumbnail Nov 16 '14 at 15:59
  • $\begingroup$ yes. edited it sorry $\endgroup$ – vinothkr Nov 16 '14 at 16:01
  • $\begingroup$ The first one : see here $\endgroup$ – Mauro ALLEGRANZA Nov 16 '14 at 16:24
  • $\begingroup$ See also here $\endgroup$ – Mauro ALLEGRANZA Nov 16 '14 at 16:48
2
$\begingroup$

Regarding the issue :

completeness vs incompleteness

we have to understandt that the two notions are strictly connected (not only by the fact that Gödel was the author of both.

We have to take in account that Gödel's Completeness Theorem for First-Order Logic states :

if a sentence is true in all the models of the axioms (i.e. it is a logical consequence of the axioms) then it is also formally deducible (with FOL axioms and rules) by the axioms.

Gödel's Incompleteness Theorem is relative to formal system $F$ containing "a certain amount" of arithmetic (for example : Robinson Arithmetic, that is weaker than Peano's) and says that :

we can find a sentence $G_F$ expressible in that system, such that neither $G_F$ nor $\lnot G_F$ are deducible from the axioms.

This does not contradict the Completeness Theorem : being underivable from the axioms of $F$, the aforesaid sentences are not logical consequences of the axioms; this implies that they are not true in all models of the system $F$.

The proof of Gödel's Theorem shows us that the Gödel's sentence $G_F$ is true in the standard model; thus, it must be false in some non-standard model.

The arithmetical sentence originally constructed by Gödel in his proof is quite "un-natural", but starting form a result of Paris & Harrington (1977) has been possible, to find "natural" statements expressible in the language of arithmetic that are true but not provable in Peano Arithmetic.

$\endgroup$
3
  • 1
    $\begingroup$ Tell me if i got it right? There are some theorems which are true in Arithmetic as we speak of. But we cannot establish a theory which captures just the arithmetic we speak of to prove them. $\endgroup$ – vinothkr Nov 16 '14 at 16:53
  • 2
    $\begingroup$ @vinothkr - exactly ... but we have to be careful: they are not provable in a theory $F$, so they are not theorems of $F$. But they can be provable in a theory $F^+$: the fact is that we can "repeat" the construction of G Incomp Th also for $F^+$ and find a new G-sentence unprovable in it ... and so on. If we restrict our attention to $F$, "its" G-sentence $G_F$ does not "violate" G Compl Th because, being unprovable in $F$, it is not a log cons of $F$, i.e. it is not true in all models of $F$. But "reading" G-sentencce, we (human mathematicians) can find it true. $\endgroup$ – Mauro ALLEGRANZA Nov 16 '14 at 17:09
  • $\begingroup$ Thanks a lot. I got it i guess $\endgroup$ – vinothkr Nov 16 '14 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.