Different models of ZF disagree on equality of explicit recursively enumerable sets

Question

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).

Answer 1

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.

Answer 2

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.