Operate in ZFC. Can we find a function-class $\phi$ whose domain is the class of ordinals such that the following properties hold?

  • If $x \in \phi(\alpha)$, then either $x \in \mathbb{N}$ or there exists some ordinal $\beta < \alpha$ with $\phi(\beta) = x$;
  • If $\phi(\alpha) \subseteq \phi(\beta)$, then $\alpha = \beta$.

The first of these conditions equivalently states that the image of $\phi$ is a transitive set, except that the natural numbers are treated as urelements, and with the constraint that $\phi(\beta) \in \phi(\alpha) \implies \beta \in \alpha$.

The second condition means that $\phi$ is injective and its image is an antichain under inclusion.

We can construct such a function-class if we assume additional axioms, such as the existence of no inaccessible cardinals. In particular, the following construction will work:

  • $\phi(0) := \{ 1 \}$
  • $\phi(\alpha + 1) := \{ 2, \phi(\alpha) \}$ for every $\alpha$
  • $\phi(\omega) := \{ 3 \}$
  • $\phi(\beta) := \{ 4, \phi(\textrm{cf}(\beta))\} \cup \{ \phi(\gamma) : \gamma \in C_{\beta} \}$ (where $C_{\beta}$ is a cofinal subset of $\beta$ with order-type $\textrm{cf}(\beta)$ such that no element of $C_{\beta}$ is less than or equal to $\textrm{cf}(\beta)$), for singular limit ordinals $\beta$
  • $\phi(\omega_{\alpha+1}) := \{ 5, \phi(\alpha) \}$ for every $\alpha$

The first of these rules deals with the zero ordinal, and the second deals with successor ordinals. The third of these handles the special case $\omega$. The fourth handles limit ordinals which are not regular ordinals. The fifth handles initial ordinals of successor cardinals. This construction, however, does not define an image if there are inaccessible cardinals (whose initial ordinals do not fit the form for either the fourth or fifth rules).

Proof: We can verify transitivity since every element of $\phi(\alpha)$ is, by definition, either a natural number or a $\phi(\beta)$ for some earlier $\beta$. Verifying the antichain property is more complicated, but it boils down to the following:

  • Clearly $\phi(\alpha) \subseteq \phi(\beta)$ means that their unique urelements must agree, which means $\alpha$ and $\beta$ were processed by the same rule (out of the five provided).
  • The first and third rules each only process one ordinal, and the second and fifth are clearly injective as well.
  • For the fourth rule, we can recover $\textrm{cf}(\alpha)$ and $C_{\alpha}$ from $\phi(\alpha)$ by removing the urelement, inverting $\phi$, and separating the preimage into its first element and the remaining elements. If $\phi(\alpha) \subseteq \phi(\beta)$, it thus follows that $C_{\alpha} \subseteq C_{\beta}$, and that they have the same order-type (which is a regular ordinal), which implies they have the same limit, so $\alpha = \beta$.

This works when there are no inaccessible cardinals, and one can introduce further rules to provide a construction which works under the weaker hypothesis that there are no hyper-inaccessible cardinals. Is there a construction which does not depend on additional axioms beyond ZFC?

  • 2
    $\begingroup$ I suspect this has something to do with Vopenka's Principle. Maybe you can show that VP implies there is no such function $\phi$? $\endgroup$ – Will Brian Oct 16 '15 at 16:16
  • $\begingroup$ Thanks, that actually works (by reducing it to the equivalent statement 'For every proper class of simple directed graphs, there are two members of the class with a homomorphism between them.'). $\endgroup$ – Adam P. Goucher Oct 17 '15 at 14:20

Adam has shown that Vopěnka's principle implies that there is no such $\phi$ as in the question. Let me prove this conclusion under a weaker hypothesis, a large cardinal assumption weaker than VP. Specifically, I claim that if there is a stationary proper class of Woodin cardinals, then there is no such $\phi$ as in the question.

The assumption that there is a stationary proper class of Woodin cardinals is strictly weaker in consistency strength than a supercompact cardinal, which is strictly less than an extendible cardinal, which is strictly less than Vopěnka's principle (assuming consistency).

Let's begin. Suppose that the Woodin cardinals form a stationary proper class, and suppose that $\phi:\text{Ord}\to V$ is a function with the stated properties. Since there is a closed unbounded set of $\delta$ with $\phi''\delta\subset V_\delta$, there must be such a $\delta$ that is a Woodin cardinal. Consider $\phi\upharpoonright\delta:\delta\to V_\delta$. Since $\delta$ is Woodin, there is $\kappa<\delta$ such that there is an elementary embedding $j:V\to M$ with critical point $\kappa$ and for which $j(\phi)$ and $\phi$ agree up to and including $\kappa$. In particular, $\phi(\kappa)=j(\phi)(\kappa)$.

Consider now the elements of $\phi(\kappa)$. If we have a natural number $n\in\phi(\kappa)$, then by elementarity, we have $n=j(n)\in j(\phi(\kappa))=j(\phi)(j(\kappa))$. And if there is $x\in \phi(\kappa)$ that is not a natural number, then $x=\phi(\beta)$ for some $\beta<\kappa$. By our assumption on $j$, we know $j(\phi)(\beta)=\phi(\beta)=x$. Since $\phi(\beta)\in\phi(\kappa)$, it follows by elementarity that $j(\phi)(j(\beta))=j(\phi)(\beta)\in j(\phi)(j(\kappa))$, which means $x\in j(\phi)(j(\kappa))$. Thus, we've shown $\phi(\kappa)\subset j(\phi)(j(\kappa))$. But since $j(\phi)(\kappa)=\phi(\kappa)$, this means $j(\phi)(\kappa)\subset j(\phi)(j(\kappa))$. So $j(\phi)$ sometimes has inclusion comparable elements, and by elementarity there must be $\alpha<\kappa$ with $\phi(\alpha)\subset\phi(\kappa)$, contradicting one of the properties of $\phi$. QED


If there is a subtle cardinal then such $\phi$ doesn't exist.

An subtle cardinal is a cardinal $\kappa$ such that for every sequence of sets $\langle S_\alpha \mid \alpha < \kappa\rangle$ such that $S_\alpha \subseteq \alpha$ and a club $C\subseteq \kappa$ there are $\alpha < \beta$ in $C$ such that $S_\beta\cap \alpha = S_\alpha$.

In our case, let us fix some bijection $f$ between $On \times \{0\} \cup \omega \times \{1\}$ and $On$ such that $f(n, 1) < \omega$ for all $n < \omega$ and $f(\beta, 0) = \beta$ for all $\beta \geq \omega$. Define: $$S_\alpha = \{f(\beta, 0) \mid \phi(\beta)\in\phi(\alpha)\}\cup \{f(n, 1) \mid n \in \phi(\alpha)\cap\omega\}$$

Note that $S_\alpha \subseteq \alpha$ for all $\alpha\geq \omega$. Clearly, $S_\alpha \subseteq S_\beta$ implies $\phi(\alpha) \subseteq \phi(\beta)$. Assume that $\kappa$ is subtle. Then there are $\omega\leq \alpha < \beta$ such that $S_\alpha = S_\beta\cap \alpha$ and in particular, $S_\alpha \subseteq S_\beta$.

Remark: subtle cardinals are consistent with $V=L$ (assuming that they are consistent with ZFC) and if $0^\#$ exists then every Silver indiscernible is subtle.

  • 4
    $\begingroup$ Quite a decrease in consistency strength! $\endgroup$ – Asaf Karagila Oct 20 '15 at 10:59
  • 2
    $\begingroup$ Haven't you used only that $\kappa$ is subtle, rather than ineffable? $\endgroup$ – Joel David Hamkins Oct 20 '15 at 11:24
  • 2
    $\begingroup$ @JoelDavidHamkins Yes, you're right. I think that if we drop the "for all club C" in the definition of subtle cardinal it would be the exact large cardinal that we need since we probably can define $\phi$ from a counterexample for this "almost-subtlety". $\endgroup$ – Yair Hayut Oct 20 '15 at 12:06

Assuming Vopenka's principle (a large cardinal axiom), we can show there is no such $\phi$. In particular, a corollary of Vopenka's principle is that every proper class of directed graphs contains some pair $G, H$ such that $G$ is isomorphic to a subgraph of $H$. However, this contradicts the existence of such a $\phi$, since we could define $G_{\alpha}$ as follows:

  • Take a directed $3$-cycle and attach the basepoint of $H(\phi(\alpha))$ to one of its vertices.

where for any set $S$, we define a pointed graph $H(S)$ inductively:

  • If $S = n \in \mathbb{N}$, then $H(S)$ is a directed $(n+4)$-cycle with an arbitrarily chosen basepoint;
  • Otherwise, $H(S)$ consists of a basepoint vertex of indegree $0$ and outdegree $|S|$ connected to the basepoint of a copy of $H(x)$ for each $x \in S$.

Then $G(\alpha)$ is isomorphic to a subgraph of $G(\beta)$ (for some $\alpha < \beta$) by Vopenka's principle. Choose the minimal such pair (i.e. minimal $\beta$, then minimal $\alpha < \beta$ with this property). This implies $H(\phi(\alpha))$ is isomorphic to a subgraph of $H(\phi(\beta))$ which preserves the basepoint (since there is only one directed $3$-cycle in each graph). Hence there is an injection $f$ from $\phi(\alpha)$ to $\phi(\beta)$ such that ($\forall x \in \phi(\alpha)$) $H(x)$ is isomorphic to a subgraph of $H(f(x))$. But by assumption of minimality, this means $x = H(x)$ for all $x$, so $\phi(\alpha) \subseteq \phi(\beta)$. Contradiction.

Thanks to Will Brian for the suggestion of using Vopenka's principle.


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.