4
$\begingroup$

Suppose for the sake of argument that we look at ZFC with the axiom of infinity removed.

http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#First_incompleteness_theorem

http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#Second_incompleteness_theorem

We would then be in a position where the hypotheses of Gödel's theorems are not satisfied, correct? Basically, I want to remove, for the sake of argument, a minimal amount of axioms of ZFC so that ZFC minus some axiom(s) leads to a theory that does not include arithmetical truths and is not capable of expressing elementary arithmetic.

Is it possible that ZFC- (my shorthand for ZFC with some axiom(s) removed) is consistent and complete?

$\endgroup$
2
  • $\begingroup$ Let me say that the answer to your question is a trivial "No". It is trivial because if a system is non-complete and you take a weaker system (like for example one obtained deleting axioms of the initial system) then the weaker system is also non-complete. Another issue is what happens when one replaces an axiom with alternative ones (like replacing "Infinity Axiom" with "The negation of Infinity Axiom"). This is in general non trivial, and this is what other peopople has addressed in the answers to your question. $\endgroup$ – boumol May 27 '13 at 6:42
  • $\begingroup$ It doesn't seem that anyone addressed the "consistent" part of my question. If you remove axioms so that ZFC minus axioms is no longer capable of expressing arithmetic, wouldn't incompleteness no longer apply ?? Is there a connection between the consistency of a weak form of ZFC which is ZFC minus enough axioms to make it no longer capable of satisfying the hypotheses of incompleteness and axiom independence? $\endgroup$ – atat May 23 '15 at 15:08
7
$\begingroup$

ZF minus the axiom of infinity plus a new axiom negating the axiom of infinity is bi-interpretable with Peano Arithmetic. And the two equivalent theories are both subject to Gödelian incompleteness.

For the equivalence claim, see Richard Kaye and Tin Lok Wong's paper On interpretations of arithmetic and set theory (which incidentally explores some of the complications alluded to in the answer by @zyx).

$\endgroup$
5
$\begingroup$

In addition to Peter Smith's very correct answer, it should be noted that one can also remove the axioms of choice and regularity without any substantial change.

The reason is that we can still define the relevant finite ordinals and their arithmetics needed for the incompleteness theorems (and because arithmetical truths are absolute between inner models with the same ordinals, so they are true in $L$ which is a model of $\sf ZFC$).

Note also that if $T\subseteq\sf ZFC$ is consistent and complete then $\sf ZFC$ is complete as well (it extends a complete theory), but we know it isn't complete, so no smaller theory is complete -- regardless to the provability of the incompleteness theorems.

$\endgroup$
1
$\begingroup$

The standard answer is slightly incomplete. The true state of things is beautifully explained in Emil Jerabek's comments at https://mathoverflow.net/questions/63887/non-standard-models-of-finite-set-theory/ . Just to record it in one place, and to bring out a surprising point from that MO thread:

  1. It is well known that, in a suitable sense, the ZF theory of non-infinite sets is equivalent to PA.

  2. Less well known, but familiar to experts, is that there is a subtle point about how to define ZF minus infinity for the equivalence to PA to hold.

  3. But the story does not end there, and is not only about this PA/ZF- equivalence! As revealed in the comments by Blass and Jerabek, the ZF axiom of foundation is oversimplified. In more general situations, one wants not foundation but $\in$ induction. In full ZF one can do without it, but this is not an indication of how to axiomatize the same idea in more finitistic or constructive forms of set theory, including variants of ZF.

$\endgroup$
1
  • $\begingroup$ "The standard answer" is (1), in case that was not evident. The surprise for me in reading the MathOverflow comments was that (2) is not a hypercorrection of a basically correct equivalence; the comment by Blass and its answer suggests that the traditional presentation of ZFC is not the last word on the subject. $\endgroup$ – zyx May 26 '13 at 20:47
0
$\begingroup$

There are two "atomic" sets that exist because an axiom says it does. One axiom for the empty set and one axiom for infinite sets. The other few axioms input a set, or multiple sets, and predicates, and output a set that will exist under specific circumstances. So we have two "seeds" and more than half a dozen inference-rule-like axioms. A thing, then, is a set if it is either an atomic set, namely Ø or a set equipollent to the set of natural numbers, or the result of applying finitely many other axioms to get "new" sets. If a property of sets is true of the atomic sets (i.e., the sets in the set theory for which there is an unqualified existential statement like "there is a set with the property that some formalism of 'is empty'.") and closed under the more than half dozen other axioms, then it is true of all sets.

At any rate, I think everyone might have been mistaken about how many axioms I am willing to drop (i.e., not adding its negation to the list, simply removing it from the list of axioms) in order to try to break incompleteness.

I blame myself for my lack of articulative quality in my original question. I am looking for the precise moment in a formal system when incompleteness is broken. If a FS can "model" a variant of ZFC or a variant of ZF, it can "model" PA. PA is what Godel used to prove incompleteness.

How about if we just had the empty set axiom (not even its more general brother the comprehension axiom) and the pair set axiom? Could that system model PA? Well I guess it would because we would still have something infinite going on, roughly speaking, and when that happens incompleteness creeps near.

$\endgroup$
5
  • 1
    $\begingroup$ As the last part of Asaf's answer points out, removing axioms can never make an incomplete theory become complete. This does not depend on Gödel's argument, but is simply a consequence of what "incomplete" means. $\endgroup$ – hmakholm left over Monica Aug 1 '17 at 11:51
  • $\begingroup$ Four years of absolutely zero interaction with the other answers, and then you post an answer instead of editing the question. That's odd. $\endgroup$ – Asaf Karagila Aug 1 '17 at 11:55
  • $\begingroup$ Perhaps what you really want to ask is how many axioms we need to remove from ZFC such that the resulting (still incomplete) theory can be extended with new axioms to make a complete (but still consistent) third theory? $\endgroup$ – hmakholm left over Monica Aug 1 '17 at 12:00
  • $\begingroup$ @HenningMakholm What about the other direction: by adding noncontradictory axioms, is it possible to get to a complete theory without automatically being inconsistent? $\endgroup$ – atat Aug 1 '17 at 12:19
  • $\begingroup$ @atat: For theories in general, yes. But if Gödel's theorem applies to the original theory: not unless you add infinitely many axioms that cannot be recognized algorithmically, $\endgroup$ – hmakholm left over Monica Aug 1 '17 at 13:29

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.