4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $F\circ H$ need not to have the desired property, because $H(y)<H(x)$ need not to imply $y\ R\ x$. $\endgroup$ – Guozhen Shen Nov 30 '16 at 4:59
  • $\begingroup$ @Sets Quite right, I misread your desired property; fixed. $\endgroup$ – Noah Schweber Nov 30 '16 at 5:20
  • $\begingroup$ The function $\mu$ you have defined satisfies that $\mu(x)=sup^{+}\{\mu(y)\ |\ y\ R\ x\}$ but not that $\mu(x)=\{\mu(y)\ |\ y\ R\ x\}$. For example, if $x\ R\ y$, $y\ R\ z$ and not $x\ R\ z$, then $\mu(z)$ should be $\{\{0\}\}$, which is not an ordinal. $\endgroup$ – Guozhen Shen Nov 30 '16 at 7:45
  • $\begingroup$ @Sets Quite right, I was sloppy. However, it's easily fixed: in fact, the Mostowski spectrum always has a maximum value, and we may take that. $\endgroup$ – Noah Schweber Dec 1 '16 at 2:56
  • $\begingroup$ The $\mu(x)=\mathrm{max}(MS(x))$ is still an ordinal, but as the example above, the desired $G(x)$ could be a set which is not an ordinal. If we consider the class $MSC(x)$ of all possible values of the Mostwoski collapse of $R\cap a^2$ at $x$ ($MSC(x)$ is a subset of $V_{H(x)+1}$), this set need not to have a maximal member, and we can not choose a right member of $MSC(x)$ to define $G(x)$. $\endgroup$ – Guozhen Shen Dec 1 '16 at 3:29
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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