7
$\begingroup$

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.

$\endgroup$

1 Answer 1

11
$\begingroup$

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.

$\endgroup$
9
  • $\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$ Nov 4, 2018 at 19:54
  • $\begingroup$ @ZuhairAl-Johar Integers. $\endgroup$ Nov 4, 2018 at 20:05
  • 3
    $\begingroup$ @DouglasUlrich That's a proper class in this model. $\endgroup$ Nov 5, 2018 at 13:47
  • 1
    $\begingroup$ @ZuhairAl-Johar Iterated power set. $\endgroup$ Nov 5, 2018 at 20:42
  • 2
    $\begingroup$ @ZuhairAl-Johar That's right. $\endgroup$ Nov 5, 2018 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.