8
$\begingroup$

Let $(\mathcal{M},E)$ be an internally non-well-founded model of set theory i.e of $ZFC^{\neg f}=ZFC\setminus \mathrm{foundation}+\neg \mathrm{foundation}$, then $\mathcal{M}$ includes an infinite decreasing $E$-sequence. I am interested to know about the degree of illness of internally non-well-founded models in the literature. For example we see there are many models of $ZF$ satisfying various versions of $AC$ that are really distinct. My question is:

$*$) What is the difference between internally non-well-founded models, in the sense of axiom of foundation? I mean how the existence of different decreasing sequences in different models effect their universes. Does an especial sequence capture some interesting properties in that model, in which not satisfying necessarily by all internally non-well-founded models?

I am also interested to find the answer of the following question.

$\bigstar$) Is any of the following statements true?

$(\rm{I})~~~~$ Working in $V$, for any infinite ordinal $\beta$, there exists a model $(\mathcal{M},E)$ of $ZFC^{\neg f}$ with $Ord(\mathcal{M})=\beta$ such that $\mathcal{M}$ contains a decreasing $E$-sequence of length $\beta$.

$(\rm{II})~~~$ Working in $V$, for any infinite ordinal $\beta$, there exists a model $(\mathcal{M},E)$ of $ZFC^{\neg f}$ with $Ord({\mathcal{M}})=\beta$ such that for any $\alpha<\beta$, $\mathcal{M}$ has a decreasing $E$-sequence of length $\alpha$.

clearly $\rm{I}\longrightarrow\rm{II}$.

Edit: I have been thought that the concept of an ill-foundeded model and aninternally ill-foundeded model are the same, but Prof. Enayat and William informed me about the difference, in the following comments. The question $(\bigstar)$ answered by Prof. Enayat stems from the question $*$. I thought maybe $\bigstar$ shows me some different pictures about non-well-founded models.

$\endgroup$
10
  • 3
    $\begingroup$ A remark about terminology: Sometimes the term ill-founded model of set theory means a model of ZFC which is ill founded from point of view of the real universe. These have many connections to admissibility. $\endgroup$
    – William
    Jan 1, 2016 at 10:28
  • $\begingroup$ You should clarify these questions further. The first is vague. In the latter two, is $\beta$ an ordinal from the real universe? What does the ordinal of M mean here? $\endgroup$
    – William
    Jan 1, 2016 at 10:32
  • 6
    $\begingroup$ Your definition of ill-founded for a model of set theory is incorrect, since an ill-founded model of set theory is usually defined to be a model $(M,E)$ such that $E$ is not well-founded from an external point of view. In particular, by compactness, $ZF$has lots of ill-founded models, even though $ZF$ includes the foundation axiom. $\endgroup$
    – Ali Enayat
    Jan 1, 2016 at 11:02
  • 3
    $\begingroup$ So I suggest modifying the first paragraph of your question, since it is confusing the internal notion of well-foundedness with the external one. Also, in light of your formulation of questions (I) and (II), it is not clear to me what is the point of your question (*). $\endgroup$
    – Ali Enayat
    Jan 1, 2016 at 11:10
  • 1
    $\begingroup$ Your first paragraph is still problematic, since as I mentioned in my earlier comment, there are many non-well-founded models of $ZFC$. I suggest the terminology internally non-well-founded, or internally ill-founded as a way of referring to models of $ZFC^{\neg f}$. I also suggest deleting the sentence about compactness, since compactness is of no use in building models of $ZFC^{\neg f}$ , compactness can only be used to build models that are non-well-founded from an external point of view. $\endgroup$
    – Ali Enayat
    Jan 1, 2016 at 14:34

1 Answer 1

12
$\begingroup$

(I) is true (and therefore so is (II)), assuming that $ZF$ has a well-founded model $M_\beta$ of ordinal height $\beta$. I will outline a construction that is meant to be carried out in within a model of $ZF$. It will produce the desired ill-founded model satisfying (II) when implemented within $M_\beta$.

Given an extensional digraph $G=(X,E)$, with $X$ as the vertex set and $E$ as the edge set, define the deficiency set $D(G)$ of $G$ to be the collection of subsets $S$ of $X$ that are not "coded" in $G$, i.e., there is no element $a$ in $X$ such that $S$ = {$x \in X : xEa$}.

In the above paragraph "digraph" stands for directed graph, and "extensional" means that if $a$ and $b$ are distinct vertices of $X$, then there is some $c\in X$ such that $cEa \leftrightarrow cEb$ does not hold. Also, $G$ is allowed to be a class.

We now can define by recursion a digraph $G_\alpha = (X_\alpha, E_\alpha)$ for each ordinal $\alpha$ as follows:

$G_0 = G$;

$G_{\alpha+1} = (X_{\alpha+1}, E_{\alpha+1})$, where $X_{\alpha+1} = X_{\alpha} \cup D(G_{\alpha})$, and $E_{\alpha+1} = E_{\alpha}$ together with edges of the form $(x,X)$, where $x\in X_{\alpha}$, $X \in D(G_{\alpha})$, and $x\in X$.

For limit $\alpha$, $G_\alpha$ is the union of $G_\beta$ for $\beta<\alpha$.

The model/digraph $M$ we are interested in is the union of all the $G_\alpha$s, as $\alpha$ ranges over the ordinals, and $G$ is isomorphic to the linearly ordered set obtained by reversing the ordering on the class of ordinals. Here the vertex set $X$ of $G$ should be chosen so that no vertex is a set of vertices, or a set of set of vertices, etc. (to see how this can be arranged, see footnote 15 on page 10 of the paper whose link appears at the end of this answer).

Intuitively speaking, the model $M$ can be thought of as the set-theoretic completion of $G$, so it should be dubbed the von Neumann completion of $G$. With the above choice of $G$, this is a class model of ZF without foundation whose class of ordinals is isomorphic to the "real class of ordinals" and which includes a decreasing chain of sets of length $Ord$.

N.B. Models of $ZF$ in which the foundation axiom fails are often constructed using the so-called Bernays-Rieger permutation method (not to be confused with the Fraenkel-Mostowski permutation method of constructing models of $ZF$ in which the axiom of choice fails). The model constructed above is based on a different idea, explored in detail for models of finite set theory in the following paper (This sort of model was also used in this answer of mine).

A. Enayat, J. Schmerl, and A. Visser, Omega Models of Finite Set Theory in Set theory, Arithmetic, and Foundations of Mathematics: Theorems, Philosophies (edited by J. Kennedy and R. Kossak), Cambridge University Press, 2011.

A preprint can be found here.

$\endgroup$
1
  • 1
    $\begingroup$ When I took the axiomatic set theory course with Matti Rubin, a large portion was dedicated to proving the consistency of the axiom of foundation and its negation. We studied these permutation models and showed that you can actually obtain a proper class of atoms. It was very nice. $\endgroup$
    – Asaf Karagila
    Jan 1, 2016 at 15:15

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.