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).



The existence of the Mostowski collapses for a non-set-like well-founded relation from which there is a homomorphism to $Ord$
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.


