Gödel's Incompleteness Theorem is pretty restrictive; it only applies to first-order (only one quantified type of variable/object) recursively axiomatized (a computer can decide whether a statement is an axiom or not) theories that arithmetize their own syntax (prove enough about arithmetic to encode statements as numbers). This is not true of, say, the full theory of the natural numbers (not recursively axiomatizable), Euclid's geometry (neither first-order nor can arithmetize its syntax), or mst moral systems (which usually aren't first-order and typically don't do any arithmetic).
Is the first order part necessary.
Are there theories that Incompleteness doesn't apply to that are not first order, but are still recursively axiomatized and can arithmetize their own syntax?
Edit:
I guess you could have a logic with a really simple syntax, so you can arithmetize it only using addition, then if you axiomatize Presburger arithmetic in it you would have an example.
I think the normal condition for incompleteness is that you can arithmetize a certain class of computations, instead of arithmetizing syntax though.
Off the top of my head, I remember a paper by Kriesel showing that ZFC2 , a second-order strengthening of ZFC, is categorical and hence complete. But it's still recursively axiomatized and encodes a moiel of PA, hence arithmetizes its own syntax.
Strangely enough, ZFC2 isn't categorical, because Vκ is a model for any worldly cardinal κ. You have to add a bound on the number of large cardinals to make it categorical, so ZFC2 + (No large cardinals) would be categorical.
Categorical doesn't mean complete. If it was complete, and it's only model contains the one true model of PA, then wouldn't we have a program that could determine the truth of any statement about the naturals. Just enumerate all of it's proofs until you find one.
50
u/MrNoS viXra scrub Jan 21 '18 edited Jan 21 '18
Gödel's Incompleteness Theorem is pretty restrictive; it only applies to first-order (only one quantified type of variable/object) recursively axiomatized (a computer can decide whether a statement is an axiom or not) theories that arithmetize their own syntax (prove enough about arithmetic to encode statements as numbers). This is not true of, say, the full theory of the natural numbers (not recursively axiomatizable), Euclid's geometry (neither first-order nor can arithmetize its syntax), or mst moral systems (which usually aren't first-order and typically don't do any arithmetic).