The existence of the Mostowski collapses for a non-set-like well-founded relation from which there is a homomorphism to $Ord$

Question

Given classes $H$, $R$, can we find a class $G$ such that the following statement is provable in ZFC?

If $R\subseteq V\times V$ and $H$ is a function from $V$ into $Ord$ such that for all sets $x,y$, $y\ R\ x$ implies that $H(y)<H(x)$, then $G$ is a function from $V$ into $V$ such that for all sets $x$, $G(x)=\{G(y)\ |\ y\ R\ x\}$.

Note that the relation $R$ in the above statement must be well-founded, but need not to be set-like.

---

The intent of this question is to investigate the relationship between the following three properties of a class relation $R$:

(1) There is a function $H$ from $V$ into $Ord$ such that for all sets $x,y$, $y\ R\ x$ implies that $H(y)<H(x)$, i.e., there is a homomorphism from $[V,R]$ into $[Ord,\in]$.

(2) There is a function $F$ from $V$ into $Ord$ such that for all sets $x$, $F(x)=\mathrm{sup}^{+}\{F(y)\ |\ y\ R\ x\}$, i.e., there is a rank function for $R$.

(3) There is a function $G$ from $V$ into $V$ such that for all sets $x$, $G(x)=\{G(y)\ |\ y\ R\ x\}$, i.e., there is a Mostowski function for $R$.

It is easily seen that (3) $\Rightarrow$ (2) $\Rightarrow$ (1), and Schweber's answer below shows that (1) $\Rightarrow$ (2). The question now is whether we can prove that (1) $\Rightarrow$ (3).

Answer 1

For $x, a$ sets, let the Mostowski rank of $x$ at set $a$, $MR_a(x)$, be the rank of $x$ in the Mostowski collapse applied to $R\cap a^2$. Let the Mostowski spectrum of a set $x$, $MS(x)$, be the set of possible values of the Mostwoski rank of $x$, as $a$ varies over all sets. On the face of it, $MS(x)$ is a class, rather than a set. However, by induction on $H(x)$, $MS(x)$ is bounded; specifically, for each ordinal $\alpha$ there is some ordinal $b(\alpha)$ such that $H(x)\le \alpha$ implies $MS(x)\subseteq \beta$. For example, if $\alpha=0$, then $b(\alpha)=1$, since every $x$ with $H(x)=0$ can only ever be collapsed to $0$. (Indeed, regardless of $R$ we'll always have $b(\alpha)\le\alpha+1$, but we don't need that here.)

In fact, $MS(x)$ has a maximum! Why? Well, for every $\alpha\in MS(x)$, let $S_\alpha$ be a set containing $x$, such that $MR_{S_\alpha}(x)=\alpha$. Now consider the set $T=\bigcup_{\alpha\in MS(\alpha)} S_\alpha$. Mostowski rank is monotonic: $a\subseteq b$ implies $MR_a(x)\le MR_b(x)$. So $MR_T(x)\ge \alpha$ for every $\alpha\in MS(\alpha)$. But also $MR_T(x)\in MS(x)$, by definition. So it is the maximum of this set.

Now consider the map $\mu(x)=\max(MS(x))$.

Answer 2

After 4 days, I solved my own question. The answer is negative, that is, we can not prove in ZFC the existence of the required $G$ for all classes $H$, $R$. In what follows, we construct special classes $H$ and $R$ such that if there is a required $G$ then we can prove in ZFC the consistency of itself.

Consider in ZFC a language of set theory $\mathscr{L}_{\dot{\in}}$ whose predicates are $\dot{\in},\dot{=}$, whose connectives and quantifiers are $\neg,\wedge,\forall$ and whose variables are $v_0,v_1,\dots$. Consider the class $$A=\{(\varphi,f)\ |\ \varphi\ \mbox{is a formula of}\ \mathscr{L}_{\dot{\in}}\ \mbox{and}\ f\ \mbox{is a function from}\ \omega\ \mbox{to}\ V\}.$$ Pick two arbitrary sets $a,b\not\in A$. We first define the function $H$ from $V$ into $\omega$ as follows.

(1) $H(a)=0$ and $H(b)=1$

(2) for all $(\varphi,f)\in A$, $H(\varphi,f)=n+2$, where $n$ is the number of connectives and quantifiers in $\varphi$

(3) for all sets $x\in V-A\cup\{a,b\}$, $H(x)=0$.

Then we define the relation $R\subseteq V\times V$ as follows.

(i) for all $x\not\in A$, $\ y\ R\ x$ if and only if $x=b$ and $y=a$.

(ii) for all $(\varphi,f)\in A$ such that $\varphi$ is an atomic formula $v_i\dot{\in}v_j$ (resp. $v_i\dot{=}v_j$ ) and such that $f(i)\in f(j)$ (resp. $f(i)=f(j)$ ), $\ y\ R\ (\varphi,f)$ if and only if $y=a$.

(iii) for all $(\varphi,f)\in A$ such that $\varphi$ is an atomic formula $v_i\dot{\in}v_j$ (resp. $v_i\dot{=}v_j$ ) and such that $f(i)\not\in f(j)$ (resp. $f(i)\neq f(j)$ ), $\ y\ R\ (\varphi,f)$ if and only if $y=a$ or $y=b$.

(iv) for all $(\varphi,f)\in A$ such that $\varphi$ is $\neg\psi$ for some $\psi$, $\ y\ R\ (\varphi,f)$ if and only if $y=a$ or $y=(\psi,f)$.

(v) for all $(\varphi,f)\in A$ such that $\varphi$ is $\psi\wedge\chi$ for some $\psi,\chi$, $\ y\ R\ (\varphi,f)$ if and only if $y=(\psi,f)$ or $y=(\chi,f)$.

(vi) for all $(\varphi,f)\in A$ such that $\varphi$ is $\forall v_i\psi$ for some $v_i,\psi$, $\ y\ R\ (\varphi,f)$ if and only if $y=(\psi,g)$ for some function $g$ from $\omega$ to $V$ such that $g(j)=f(j)$ for all $j\neq i$.

It can be easily verified that for all sets $x,y$, $\ y\ R\ x$ implies that $H(y)<H(x)$.

Now, we assume towards a contradiction that there is a class $G$ from $V$ into $V$ such that for all sets $x$, $G(x)=\{G(y)\ |\ y\ R\ x\}$. Then, by the definition of $R$, we have:

(I) $G(a)=0$ and $G(b)=\{0\}$.

(II) for all $(\varphi,f)\in A$ such that $\varphi$ is an atomic formula $v_i\dot{\in}v_j$ (resp. $v_i\dot{=}v_j$ ) and such that $f(i)\in f(j)$ (resp. $f(i)=f(j)$ ), $\ G(\varphi,f)=\{0\}$.

(III) for all $(\varphi,f)\in A$ such that $\varphi$ is an atomic formula $v_i\dot{\in}v_j$ (resp. $v_i\dot{=}v_j$ ) and such that $f(i)\not\in f(j)$ (resp. $f(i)\neq f(j)$ ), $\ G(\varphi,f)=\{0,\{0\}\}$.

(IV) for all $(\varphi,f)\in A$ such that $\varphi$ is $\neg\psi$ for some $\psi$, $\ G(\varphi,f)=\{0,G(\psi,f)\}$.

(V) for all $(\varphi,f)\in A$ such that $\varphi$ is $\psi\wedge\chi$ for some $\psi,\chi$, $\ G(\varphi,f)=\{G(\psi,f),G(\chi,f)\}$.

(VI) for all $(\varphi,f)\in A$ such that $\varphi$ is $\forall v_i\psi$ for some $v_i,\psi$, $\ G(\varphi,f)=\{G(\psi,g)\ |\ \mbox{$g$ is a function from $\omega$ to $V$ such that $g(j)=f(j)$ for all $j\neq i$}\}$.

It is easily seen that for all $(\varphi,f)\in A$, $G(\varphi,f)\neq 0$. By induction on $n$ we can prove that for all sets $x$, if $H(x)=n$ then $G(x)\in V_{n+1}$. Hence, $G$ is a function from $V$ into $V_\omega$. We define a member of $V_\omega$ as a "good" member by recursion via $\in$ on $V_\omega$ as follows.

For all $x\in V_\omega$, $x$ is good if and only if either $0\not\in x$ and all members of $x$ are good, or $0\in x$ and all members of $x-\{0\}$ are not good.

For example, $0$ is good since $0\not\in0$ and all members of $0$ are good; $\{0\}$ is also good since $0\in\{0\}$ and all members of $\{0\}-\{0\}$ are not good; $\{0,\{0\}\}$ is not good since $0\in\{0,\{0\}\}$ but $\{0\}\in\{0,\{0\}\}-\{0\}$ is good.

For all $(\varphi,f)\in A$, we define $$f\models\varphi\ \mbox{if and only if}\ G(\varphi,f)\ \mbox{is good.}$$

By (I)-(VI) and the definition of "goodness", we have:

(1) for all $(\varphi,f)\in A$ such that $\varphi$ is an atomic formula $v_i\dot{\in}v_j$ (resp. $v_i\dot{=}v_j$ ), $\ f\models\varphi$ if and only if $f(i)\in f(j)$ (resp. $f(i)=f(j)$ ).

(2) for all $(\varphi,f)\in A$ such that $\varphi$ is $\neg\psi$ for some $\psi$, $\ f\models\varphi$ if and only if not $f\models\psi$.

(3) for all $(\varphi,f)\in A$ such that $\varphi$ is $\psi\wedge\chi$ for some $\psi,\chi$, $\ f\models\varphi$ if and only if $f\models\psi$ and $f\models\chi$.

(4) for all $(\varphi,f)\in A$ such that $\varphi$ is $\forall v_i\psi$ for some $v_i,\psi$, $\ f\models\varphi$ if and only if $g\models\psi$ for all functions $g$ from $\omega$ to $V$ such that $g(j)=f(j)$ for all $j\neq i$.

However, the existence of such a satisfaction relation can not be proved in ZFC, and we obtain the desired contradiction.