26
$\begingroup$

Some proper classes are "too big" to be a set in the sense that they have a subclass that can be put in bijection with $\alpha$ for every cardinal $\alpha$. It is implied in this post that every proper class is "too big" to be a set in this sense, however I have been unable to prove it. It's true if every two proper classes are in bijection, but it's consistent with ZFC for there to be a pair of non-bijective classes.

So, is the following true in ZFC:

For all proper classes, $C$, and $\alpha\in\mathbf{Card}$, $\exists S\subset C$ such that $|S|=\alpha$?

If not, is there something reasonable similar that preserves the intuition about classes that are "too big to be sets"?

$\endgroup$
14
$\begingroup$

$\newcommand{\Ord}{\operatorname{\mathbf{Ord}}}$Yes, this is true. First, let us prove this if $C$ is a subclass of the ordinals. By transfinite recursion, we can define a function $f:C\to \Ord$ such that for each $c\in C$, $f(c)$ is the least ordinal greater than $f(d)$ for all $d\in C$ such that $d<c$. The image of $f$ is a (not necessarily proper) initial segment of $\Ord$: that is, it is either an ordinal or it is all of $\Ord$. Since $f$ is injective (it is strictly order-preserving), if the image of $f$ were an ordinal then $C$ would be a set by Replacement (using the inverse of $f$). Thus the image of $f$ is all of $\Ord$. But now it is trivial to find a subset of $C$ of cardinality $\alpha$: just take $f^{-1}(\alpha)$ (which is a set by Replacement).

Now let $C$ be an arbitrary proper class. Let $D\subseteq \Ord$ be the class of all ranks of elements of $C$. If $D$ is bounded, then it is contained in some ordinal $\alpha$, which means $C$ is contained in $V_{\alpha}$ and hence is a set. So $D$ must be unbounded, and is thus a proper class. By the previous paragraph, for any cardinal $\alpha$, there exists $S\subset D$ of cardinality $\alpha$. Now use Choice to pick a single element of $C$ of rank $s$ for each $s\in S$. The set of all these elements is then a subset of $C$ of cardinality $\alpha$.

(To be clear, this is a proof you can give for any particular class $C$ defined by some formula in the language of set theory. Of course, ZFC cannot quantify over classes, and so cannot even state this "for all $C$..." at once.)

$\endgroup$
  • 2
    $\begingroup$ This makes perfect sense to me and is a much better answer than mine. $\endgroup$ – Steven Stadnicki Jan 23 '17 at 5:56
14
$\begingroup$

Here is an alternative proof to that of Eric.

Since $C$ is a proper class, there is no $\alpha$ such that $C\subseteq V_\alpha$. Consider the class $\{C\cap V_\alpha\mid\alpha\in\mathrm{Ord}\}$, if there is an upper bound on cardinality to this class, some $\kappa$, then there cannot be more than $\kappa^+$ different sets in that class, which would make $C$ a set.

Therefore there are arbitrarily large $C\cap V_\alpha$'s, and therefore there is one larger than your given cardinal.


Interestingly, without choice, it is consistent that there is a proper class which does not have any countably infinite subsets. Although it is true in that every proper class can be mapped onto the class of ordinals.

$\endgroup$
  • 1
    $\begingroup$ That note at the end is very interesting! $\endgroup$ – Stella Biderman Jan 23 '17 at 6:09
  • 2
    $\begingroup$ Yes. I agree! Although there are caveats to it when working in ZF, but we can formalize it in an NBG-like setting to be accurate as stated. $\endgroup$ – Asaf Karagila Jan 23 '17 at 6:10
8
$\begingroup$

No, for one trivial but important reason: ZFC has no idea of the notion of class so you can't speak of classes at all within ZFC.

Perhaps you want something like NBG, but it's actually an axiom of NBG that things that aren't 'set-sized' are 'universe-sized': the Limitation of Size axiom says that for any class $C$, a set $x$ such that $x=C$ exists iff there is not a bijection between $C$ and $V$. See https://en.wikipedia.org/wiki/Axiom_of_limitation_of_size for more details.

Alternately, as noted by Eric Wofsey below, we can attempt to formalize the question in ZFC as follows:

For every formula $\phi(x)$ in one free variable, $(\not\exists S: x\in S\leftrightarrow \phi(x)) \implies (\forall \alpha\in CARD\ \exists T s.t. |\{t: t\in T\wedge \phi(t)\}|=\alpha)$.

I don't see an immediate proof of this in ZFC, but it's certainly plausible; note that if the RHS of the implication is false (that is, if there are cardinals not in the 'domain' of $\phi$), then the cardinals that are in the domain of $\phi$ are closed downwards, so there must be some cardinal $\beta$ such that $\{\gamma: \exists T s.t. |\{t:t\in T\wedge\phi(t)\}|=\gamma\} = \{\gamma: \gamma\lt \beta\}$ - that is, the cardinals in the domain of $\phi$ are exactly the cardinals less than $\beta$.

$\endgroup$
  • 6
    $\begingroup$ But you can prove a metatheorem saying that for any class (i.e., formula with one free variable), ZFC proves that the statement is true for that class. Or you can enlarge the language by adjoining a new unary relation symbol that defines your class. $\endgroup$ – Eric Wofsey Jan 23 '17 at 5:17
  • $\begingroup$ @EricWofsey Very true, though given that we talk about an $S\subset C$ there's a lot of delicacy in the specific formula, especially in indicating that $C$ isn't 'set-sized'. $\endgroup$ – Steven Stadnicki Jan 23 '17 at 5:23
  • 3
    $\begingroup$ There really isn't anything delicate about it. We can quantify over subsets of $C$ with no difficulty: they are just sets all of whose elements satisfy the formula defining $C$. $\endgroup$ – Eric Wofsey Jan 23 '17 at 5:26

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.