Assuming that ZF is consistent, are there two recursively enumerable sets defined by explicit enumerators that are the same in one model of ZF+Con(ZF) but different in another model of ZF+Con(ZF)? If so, can such sets each have finitely many elements? I don't know how exactly to define "explicit", but I mean that I want two programs written down in a Turing-complete language and two models of ZF+Con(ZF) that disagree on their equality. I am willing to relax the explicitness slightly in the sense that if you can prove the existence of such a pair of programs it is also fine, but I am much more interested to see explicit examples. Please forgive my unfamiliarity with this subject and my edits in attempting to correctly express what I am trying to ask. I am trying to understand how different the models of ZF can be with respect to recursively enumerable sets, under the assumption of Con(ZF).

  • 1
    $\begingroup$ What about the empty set as compared to the set of proofs of inconsistencies of ZF? You can recursively enumerate the latter, but you will not be able to prove in ZF that it is empty. Is this an example of what you are looking for? $\endgroup$ – Hanno Oct 26 '14 at 9:32
  • $\begingroup$ @Hanno: Hmm it is indeed an example of what I am looking for but it is not really what I'm trying to understand. Sorry I'm going to edit my question to strengthen the requirement beyond just independence of ZF.. $\endgroup$ – user21820 Oct 26 '14 at 9:57
  • $\begingroup$ Now that you have edited the question it is no longer clear to me in which set theory your question is to be formalized. But in $ZF + \text{Con}(ZF + \text{Con}(ZF))$ (in which also $\text{Con}(ZF)$ an hence $\text{Con}(ZF + \neg\text{Con}(ZF))$ [by Goedel] are theorems) you have models both for $ZF + \text{Con}(ZF)$ and for $ZF + \neg\text{Con}(ZF)$, so the example from my previous comment would still work if I didn't confuse things too much. $\endgroup$ – Hanno Oct 26 '14 at 10:41
  • $\begingroup$ @Hanno: Well for the question itself I would assume that ZF is consistent, otherwise the question won't even be meaningful as any model of ZF would prove both the equality and inequality. I honestly don't know how to formalize my inquiry but I hope you get the idea of what I am trying to ask. $\endgroup$ – user21820 Oct 26 '14 at 10:53
  • 2
    $\begingroup$ Yes I think so - I think the point really is that one can choose the r.e. sets in such a way thay their equality is just equivalent to the consistency of ZF, so you end up looking for looking for models of ZF which disagree on the consistency of ZF to get an example for your question. $\endgroup$ – Hanno Oct 26 '14 at 10:58

After comments, I believe the question is:

Can we find two models $M$ and $M'$ of $ZF + \text{Con}(ZF)$ such that there is an r.e. set $W_e$ (where $e$ is a standard natural number) for which $M$ satisfies "$W_e$ is empty" and $M'$ satisfies "$W_e$ is nonempty".

The answer is "yes", using basic facts about Gödel's incompleteness theorem and r.e. sets. First, for any sentence $\phi$ and any effective theory $T$, the set of formal proofs of $\phi$ from $T$ is recursively enumerable (of course, this set of proofs may be empty). For the rest of this answer, our theory $T$ will be $ZF + \text{Con}(ZF)$. We could just as well use $T = ZFC + \text{Con}(ZFC)$, or $T = PA + \text{Con}(PA)$, it makes no difference.

Now the incompleteness theorem says that for any effective, consistent theory $T$ that is sufficiently strong (and ZF is already more than sufficiently strong), $T$ will not prove $\text{Con}(T)$. And if $T$ is consistent and has true axioms (again, $ZF + \text{Con}(ZF)$ has this property) then $T$ cannot prove a false sentence such as $\lnot\text{Con}(T)$. Remember that $\lnot \text{Con}(T)$ says "there is a formal proof of $0=1$ from $T$", and the set of all such formal proofs is again r.e., although it may be empty.

So we let $W_e$ be the set that contains only $0$, if there is a proof of $\lnot\text{Con}(T)$, and which is empty otherwise. Then $W_e$ is a particular r.e. set, AND $e$ is a particular natural number that we could, in principle, work out exactly. One way to see that $W_e$ is r.e. is that it is the image of the r.e. set of formal proofs under the constant map $f(x) = 0$.

Because $T$ does not prove or disprove $\lnot\text{Con}(T)$, there will be models of $T$ that satisfy $\lnot\text{Con}(T)$ and models that do not satisfy that sentence. In the models that do satisfy $\lnot\text{Con}(T)$, we have $W_e = \{0\}$. In the models that do not satisfy $\lnot\text{Con}(T)$, we have $W_e = \emptyset$.

P.S. The aside about "truth" above is not really necessary, although it is the easiest way to see the results needed here. Remember that the first incompleteness theorem says that if $T$ is an effective, consistent theory containing enough arithmetic (but without any assumption the theory is sound or true), then there is a Rosser sentence $R_T$ that is neither provable nor disprovable in $T$. So there are models of $T$ in which $R_T$ is true, and models in which $R_T$ is false.

Now $R_T$ has a particular syntactical form: it says that a specific computable set of natural numbers is empty. So if we let $X$ be this computable set of natural numbers, and let $W$ be the image of $X$ under the constant map $f(e) = 0$, then $W$ is r.e., and models of $R_T$ will satisfy "$W = \emptyset"$, and models of $\lnot R_T$ will satisfy "$W = \{0\}$". Here we can let $T$ be $ZFC + \text{Con}(ZFC)$, or any other sufficiently strong, consistent, effective theory.

For a general introduction to the incompleteness theorems I suggest Gödel without tears by Peter Smith.

| cite | improve this answer | |
  • $\begingroup$ Okay I think I get your answer except that you seem to have assumed Con(T). Is that somehow implied by T = ZF + Con(ZF)? $\endgroup$ – user21820 Oct 26 '14 at 14:10
  • $\begingroup$ Neither Con(T) nor its negation is implied by T. That's why T has models satisfying Con(T) and models that do not satisfy Con(T). This holds for every effective, consistent theory T that is sufficiently strong. $\endgroup$ – Carl Mummert Oct 26 '14 at 14:12
  • $\begingroup$ I think user21820's question alluded to the background theory, which should include $\text{Con}(T)$. So e.g. one might take $ZF + \text{Con}(T) = ZF + \text{Con}(ZF + \text{Con}(ZF))$. $\endgroup$ – Hanno Oct 26 '14 at 14:48
  • $\begingroup$ @CarlMummert: I'm sorry for my ignorance, but do you have a reference at hand for the proof that a consistent, effective theory $T$ does not only not prove $\text{Con}(T)$, but also not $\neg\text{Con}(T)$? I didn't know that, which is why I suggested to use $ZF + \text{Con}(ZF + \text{Con}(ZF))$ in the comments, even though there I only looked for models of $T = ZF$, and not $T = ZF + \text{Con}(ZF)$. $\endgroup$ – Hanno Oct 26 '14 at 14:50
  • 1
    $\begingroup$ @user21820: I have edited the question. There are two ways to resolve this issue: (1) note that ZF + Con(ZF) is a true, consistent theory, so it can't prove that it is inconsistent; (2) Use an r.e. set obtained from the Rosser sentence instead, so that we don't have to worry about whether the theory T is true or sound. $\endgroup$ – Carl Mummert Oct 26 '14 at 15:38

Just a remark on a possible point of confusion which arised in the comments: If we impose $\text{Con}(ZF)$ as an axiom of our ambient set theory, we assume the statement itself, but not its provability; provability however is what is needed for statements to be inherited to all models of a theory. Hence, working within $ZF + \text{Con}(ZF)$ does not imply that we cannot construct models of $ZF$ violating $\text{Con}(ZF)$.

Put another way: One might argue that, assuming $\text{Con}(ZF)$, the r.e. sets we are considering are both empty, so we can compare them and see they are equal, so how might this suddenly become impossible in certain models? Again, the point is that what we can internalize to models of $ZF$ are specific formulas of set theory, and formulas equivalent in the ambient theory (like $\emptyset=\emptyset$ and $\emptyset=\{n\ |\ \neg\text{Con}(ZF)\}$ above) need not be equivalent in any model.

| cite | improve this answer | |
  • $\begingroup$ This is exactly the point: we are defining an r.e. set by a formula within ZFC, and that formula will have a different meaning in different models. In particular the formula for Con(T) quantifies over the natural numbers, and because different models of ZF can have very different "natural numbers" inside them, these models can disagree about whether that formula is true or not. $\endgroup$ – Carl Mummert Oct 26 '14 at 15:13
  • $\begingroup$ Thanks for your help in elucidating exactly what I was trying to ask! I'll have to think carefully about all these to see if they answer my real questions. =) $\endgroup$ – user21820 Oct 26 '14 at 15:42

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.