0
$\begingroup$

This posting is a continuation to an earlier one titled "Can Foundation be captured in $\mathcal L_{\omega_1, \omega}$ ?"

It appears that capturing foundation is problematic at every $\mathcal L_{\alpha, \omega}$ and even at $\mathcal L_{ \infty, \omega}$. [see this and comments below it]

However, can there be particular cases where this fails? I mean where we can capture Foundation for some particular $\mathcal L_{\omega_1, \omega}$ theory.

I'm specifically referring to the theory $\sf ZF + Def$. This theory has all of its models being exactly the pointwise definable models of $\sf ZF$.[Hamkins]

So, it proves $\sf V=HOD$, and accordingly there is a finitary formula $\phi$ in two free variables that defines a binary relation $\leqslant$ that well orders the universe. Now can we use this feature to capture Foundation?

$\textbf{Define: } x \in^{\leqslant} y \iff x \in y \land \forall m \in y \, ( x \leqslant m )$

That is, $x$ is the element of $y$ of the least order according to $\leqslant$.

Now, we define:

$ \textbf{Define: } y \in^\leqslant_K x \iff y \in^\leqslant x \cap K $

Where, as usual: $ x \cap K =\{y \mid y \in x \land y \in K\}$

$\textbf{Foundation: } \forall K \forall x:\\ \neg [ \bigwedge_{n \in \omega} (\exists v_0,..,\exists v_n: \bigwedge_{i \in n} (v_{i+1} \in^\leqslant_K v_i) \land v_0 \in^\leqslant_K x)] $

Now, the idea is that if there exists a nonempty set $K$ such that every element of $K$ has an element of it that is an element of $K$, then there would exist $x \in K$ that violates Foundation.

Would that succeed in capturing Foundation, thereby rendering all models of the resulting theory well founded?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Lemma. A model of ZF satisfies the “Foundation” axiom if and only if it is an $\omega$-model, i.e., iff it satisfies the simpler $\mathcal L_{\omega_1,\omega}$-sentence $\forall x\in\omega\,\bigvee_{n\in\omega}x=n$.

Proof:

Right-to-left: Working inside the model, given $x$ and $K$, define by recursion a partial function $f\colon\omega\to K$ such that $f(0)=x$ and if $f(n)$ is defined and intersects $K$, then $f(n+1)$ is the $\le$-least element of $f(n)\cap K$. If $f$ is total, then $\{f(n):n\in\omega\}$ contradicts the usual axiom of foundation of ZF. Thus, let $n\in\omega$ be minimal such that $f(n)$ is undefined. Assuming $n$ is standard, we have $\neg\exists v_0,\dots,v_n \cdots$ as in the axiom of “Foundation”.

Left-to-right: Define by recursion a function $f\colon\omega\to V$ such that $f(0)=0$ (say) and $f(n+1)=\{f(n)\}$. Let $K=\{f(n):n\in\omega\}$, and $x=f(n)$ for a fixed nonstandard $n\in\omega$. Then “Foundation” fails for $K$ and $x$.

Corollary. The following are equivalent (provably in ZF):

  1. Your theory is consistent.

  2. ZF (or ZFC) has an $\omega$-model.

  3. The closure of ZF (or ZFC) under the $\omega$-rule is consistent.

Proof: The equivalence of 2 and 3 holds for arbitrary countable FO theories by a well-known consequence of the omitting types theorem. Clearly, 1 implies 2 by the Lemma. On the other hand, if $M$ is an $\omega$-model of ZF, then $L^M$ is an $\omega$-model of ZF + V=L, and the set of parameter-free definable elements of $L^M$ is its elementary submodel, thus an $\omega$-model of ZF + Def.

Corollary: If the theory is consistent, then it has a non-well-founded model.

Proof: Assume the theory has a model. If it is not well founded, we are done, thus we may assume there exists a well-founded model of ZF. It follows that there exists a least ordinal $\alpha$ such that $L_\alpha$ is a model of ZF. Now, $L_\alpha$ satisfies “the closure of ZF under the $\omega$-rule is consistent”, as the closure as computed in $L_\alpha$ is included in the true closure. Thus, there exists $M\in L_\alpha$ such that $L_\alpha$ satisfies “$M$ is a point-wise definable $\omega$-model of ZF”. Since $L_\alpha$ is itself a transitive model of ZF, $M$ really is a point-wise definable $\omega$-model of ZF, i.e., a model of your theory. But since $M\in L_\alpha$, $M$ cannot be well founded by the minimality of $\alpha$.

$\endgroup$
2
  • $\begingroup$ Great! So, this form of foundation is in a sense stronger than the usual form written in $\mathcal L_{\omega,\omega}$. $\endgroup$ Jun 14, 2023 at 5:56
  • $\begingroup$ Your left-to-right argument shows that formalizing the axiom without $K$ would also work. $\endgroup$ Jun 14, 2023 at 19:06

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.