Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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? –  Joel David Hamkins Jan 18 '12 at 2:47
    
Absoluteness I had in mind is between transitive models. –  Anton Jan 18 '12 at 2:53
    
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. –  Joel David Hamkins Jan 18 '12 at 3:12
    
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. –  Anton Jan 18 '12 at 3:20
    
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. –  Joel David Hamkins Jan 18 '12 at 3:38

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer
    
I recall that transitive collapse exists for well-founded structures. I suppose that this is extended in Boffa's work? –  Asaf Karagila Jan 18 '12 at 17:36
    
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.) –  Emil Jeřábek Jan 18 '12 at 18:26

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.

share|improve this answer
    
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? –  Anton Jan 18 '12 at 2:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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