7
$\begingroup$

Let $\text{ZF}^-$ be the set theory without powerset, choice, and foundation. Consider the following notions:

  • Wellfounded sets $$WF(c) \Leftrightarrow (\forall x \subseteq TC(c)) \left[x \neq \emptyset \rightarrow (\exists y \in x) (\forall t \in x) [t \notin y]\right]$$
  • Ordinals $$ON(c) \Leftrightarrow WF(c) \wedge \text{Transitive}(c) \wedge (\forall x,y \in c)[x = y \vee x \in y \vee y \in x]$$
  • $\omega$ $$x = \omega \Leftrightarrow ON(x) \wedge (\forall y \in x)[y = \emptyset \vee (\exists z)[y = z \cup \{z\}]] $$

Are those $\Delta_1$ notions? Are those notions absolute between transitive models of $\text{ZF}^-$? More precisely, is there a model $V$ of $\text{ZF}^-$ with transitive classes $N,M \models \text{ZF}^-$ s.t. those notions are not absolute between $N$ and $M$? Does the situation change if we add powerset or choice to our theory?

Those notions are absolute once we have foundation, moreover they are definable by a $\Delta_0$ formula. I was wondering if they are still absolute without assuming foundation, but that requires more work to show; or if they cease being absolute at all. If so, is there an easy way to construct a counterexample?

$\endgroup$
5
  • $\begingroup$ And could you also clarify the sense of absoluteness you have in mind? This notion is used with various inequivalent senses in set theory. Of course, even in ZFC none of these notions is fully absolute, in the sense of having all models of ZFC agree on whether a set is an ordinal, but the notions are absolute between transitive models of ZFC. Do you mean $\Delta_1$ definable? $\endgroup$ Jan 18, 2012 at 2:47
  • $\begingroup$ Absoluteness I had in mind is between transitive models. $\endgroup$
    – Anton
    Jan 18, 2012 at 2:53
  • $\begingroup$ I find that ambiguous, since it isn't clear if you are considering transitive models of your weak theory with ZFC in the ambient background, or if you also want only your weak theory in the background, and then consider transitive models of your weak theory. Of course, if you have foundation in the background theory, then any transitive model of your weak theory will automatically satisfy foundation. $\endgroup$ Jan 18, 2012 at 3:12
  • $\begingroup$ Well I am just following the usual proof that CON(ZF - Foundation) implies CON(ZFC). That is usually done in two steps, first proving that CON(ZF - Foundation) implies CON(ZF) by the construction of V; and then proving CON(ZF) implies CON(ZFC) by constructing L. The reason requiring foundation is usually explained as a technical convenience, that helps when absoluteness is developed. What I was wondering is whether you actually need foundation in order to have ordinals absolute, or whether it just lets us write shorter proofs. $\endgroup$
    – Anton
    Jan 18, 2012 at 3:20
  • $\begingroup$ OK, so it seems you want to assume only your weak theory in the background. But I edited my answer with another ambiguity about what your theory is, since even ZFC-powerset is ambiguous, since replacement and collection no longer give rise to the same theory when powerset is not present, and the various versions of choice also are not equivalent without power set. $\endgroup$ Jan 18, 2012 at 3:38

2 Answers 2

11
$\begingroup$

None of these three notions is absolute, even if you retain powerset and the axiom of choice.

In Boffa’s set theory (which contains ZFC without foundation, and is conservative over ZFC with respect to the well-founded kernel), every extensional set-like binary relation is isomorphic to a transitive class with $\in$. In particular, you can take the ultrapower of the universe over a nonprincipal ultrafilter on a countable set, and let $M$ be its transitive collapse. Then there are nonstandard integers in $M$, i.e., $\omega^M\ne\omega$.

References for Boffa’s axiom:

  1. Maurice Boffa, Forcing et négation de l’axiome de Fondement, Académie Royale de Belgique, Mémoires, Classe des Sciences, Collection $8^o$, II. Série 40, No. 7 (1972).

  2. David Ballard and Karel Hrbáček, Standard Foundations for Nonstandard Analysis, Journal of Symbolic Logic 57 (1992), No. 2, 741–748.

$\endgroup$
6
  • $\begingroup$ I recall that transitive collapse exists for well-founded structures. I suppose that this is extended in Boffa's work? $\endgroup$
    – Asaf Karagila
    Jan 18, 2012 at 17:36
  • $\begingroup$ Right, well-founded extensional structures have transitive collapse already in ZF w/o foundation, whereas Boffa’s axiom ensures we can drop the assumption of well-foundedness from this result. (That this is implied by the axiom is quite easy to see, the real work is to show that the axiom is consistent, though that’s not terribly difficult either.) $\endgroup$ Jan 18, 2012 at 18:26
  • $\begingroup$ The accessible references I have for Boffa's axiom (reference 2 and Aczel's monograph) formulate it seemingly less generally, for set (rather than merely set-like) extensional relations. Is there an evident reduction? $\endgroup$ Oct 28, 2015 at 2:26
  • $\begingroup$ In fact, I do not even see how the class version is to be stated: how to assert the existence of a proper class other than via a unique specification, but transitive collapse is no longer unique, is it? $\endgroup$ Oct 28, 2015 at 13:56
  • $\begingroup$ Boffa's set theory includes global choice, and the transitive collapse you obtain will be definable from the original class and the global choice function. I'm pretty sure the statement is included somewhere in 2, but I am out of the office ATM so I can't tell you exactly. The proof is completely straightforward; you just write the class relation as an ordinal-indexed increasing union of sets that are transitive subrelations, and successively apply Boffa's axiom. $\endgroup$ Oct 28, 2015 at 14:32
9
$\begingroup$

Without the foundation axiom, you have to specify what you mean by an ordinal, precisely because the various definitions are no longer equivalent:

  • An ordinal is a transitive set well-ordered by $\in$.
  • An ordinal is a hereditarily transitive set.
  • An ordinal is a transitive set linearly ordered by $\in$.

For example, in a model of Aczel's AFA, there is a set $a$ which is equal to $\{a\}$, and such a set is hereditarily transitive, but it is not well-ordered by $\in$, since it has no $\in$-least member, and it is not a strict linear order, since it is reflexive. One may similarly construct sets in AFA that are transitive and linearly ordered by $\in$, but not well-ordered.

Similarly, the various equivalent formulations of well-foundedness become inequivalent without the axiom of choice. For example, the equivalence of the following two notions of well-foundedness is itself equivalent to the principle of dependent choice, a weak form of the axiom of choice:

  • There is no infinite descending sequence
  • Every subset has a minimal element.

Thus, without any AC, the notion of well-foundedness depends on how you express it.

Another ambiguity here is that the meaning of ZFC-powerset is ambiguous without elaboration, as Victoria Gitman, Thomas Johnstone and I proved in our paper What is the theory ZFC-powerset?. Also, the familiar equivalent formulations of the axiom of choice (such as WOP or choice functions, etc.) are no longer equivalent when power set is absent.

So it isn't clear exactly what your weak theory is.

$\endgroup$
1
  • $\begingroup$ This is a valid remark, I should have been more precise. Well-foundedness I had in mind is the one where every subset has a minimal element. Then I'm only interested in well-founded sets for the definition of the ordinals. With that restriction all those three definitions should be equivalent, right? $\endgroup$
    – Anton
    Jan 18, 2012 at 2:30

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.