Are there models of first order Zermelo set theory (axiomatized by: Extensionaity, Foundation, empty set, pairing, set union, power, Separation, infinity) in which $\in$-induction fail?

I asked this question on Mathematics Stack Exchange here 4 days ago, to receive no answer yet, I thought this question already has a well known answer that is somehow evading me. Seeing that nobody answered thus far, makes me wonder if this is really an elementary issue? The whole issue is whether the proof that Foundation implies $\in$-induction necessitate existence of transitive closures for all sets, and since first order Zermelo doesn't prove the existence of transitive closures for all sets, then this raised this issue in my mind.


The answer is no. Take the standard model of Z and add in a $\mathbb{Z}$-sequence of objects, each of whose only element is the previous one. I.e., define

$M=\bigcup_{n<\omega} \bigcup_{m<\omega}\mathcal{P}^n(V_{\omega} \cup (\{\omega + \omega\}\times[-m, \infty))),$ where we adjust the $\mathcal{P}$ operator to replace each singleton of the form $\{(\omega+\omega,m)\}$ with $(\omega+\omega,m+1).$

We define the relation $E$ on $V_{\omega} \cup (\{\omega + \omega\}\times \mathbb{Z})$ by $E \restriction V_{\omega}=\in \restriction V_{\omega}$ and $E \restriction \mathbb{Z}=\{((\omega+\omega,n),(\omega+\omega,n+1)): n \in \mathbb{Z}\},$ with no relations between "integer objects" and "set objects." Extending $E$ to the iterated power sets is done in the natural way.

It's easy to see $(M,E)$ satisfies Z, and furthermore an object has a (set-sized) transitive closure iff its transitive closure class has no integer objects. In particular, every counterexample to "everything has a transitive closure" contains another counterexample, and such counterexamples exist, contradicting $E$-induction.

  • $\begingroup$ I just want to make sure of the interval $[-m,\infty)$, does it mean the set of all reals $\geq -m$, or does it mean the set of all integers (elements of $\mathbb{Z}$) $\geq -m$ $\endgroup$ – Zuhair Al-Johar Nov 4 '18 at 19:54
  • $\begingroup$ @ZuhairAl-Johar Integers. $\endgroup$ – Elliot Glazer Nov 4 '18 at 20:05
  • 3
    $\begingroup$ @DouglasUlrich That's a proper class in this model. $\endgroup$ – Elliot Glazer Nov 5 '18 at 13:47
  • 1
    $\begingroup$ @ZuhairAl-Johar Iterated power set. $\endgroup$ – Elliot Glazer Nov 5 '18 at 20:42
  • 2
    $\begingroup$ @ZuhairAl-Johar That's right. $\endgroup$ – Elliot Glazer Nov 5 '18 at 21:09

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.