5
$\begingroup$

I have a question about 'class versions' of almost disjoint sets. To even state what I'm after, I need to go beyond what one can state in theories like NBG or MK. I'm wondering about the status of the following:

There is a class C of proper classes of sets with the following two properties

(1) C is almost disjoint in the sense that every two different members of C intersect in a set,

and yet

(2) The size of C is larger than the size of the class V of sets in the sense that there is no injection of C into V.

I don't have a preferred theory in mind in which to discuss these, I'm interested in hearing about what the possible approaches could be.

It is clear that (1) + (2) is consistent from an inaccessible, but my question is whether these are provable in any natural system. Even more, I'd be interested in whether there are models where there is a class of classes C where (1) + (2) fails.

The reason that I'm interested in these is that they are connected to results on functors on the category of classes that I'm thinking about.

Once the matter of almost disjoint classes is cleared up, I might be back with a follow up on the question that motivates this.

$\endgroup$
1
  • 3
    $\begingroup$ Morally, I think, once you allow classes to be elements of larger collections, they're just sets again. $\endgroup$
    – Asaf Karagila
    Commented Jan 16, 2015 at 0:01

2 Answers 2

7
$\begingroup$

There is an easy way to construct a bijection between the collection of all classes and a certain collection of almost-disjoint classes: send each class $X$ to the class $\{X \cap V_\alpha : \alpha \in \mathrm{Ord}\}.$ Theories with collections of classes should support this construction with relative ease since this argument makes no essential use of collections of classes. So the question becomes whether the collection of classes is larger than $V$. This is true, provided some relatively basic combinatorics.

By the usual diagonal argument, no map from $V$ into the collection of classes can be onto: given such a map $F$, consider the class $R = \{x \in V : x \notin F(x)\}$. This requires comprehension with higher-order parameters, so this could potentially fail in a very weak theory with collections of classes.

Since the second fact talks about surjections rather than injections, we also need the fact that if there is an injection from the collection of all classes into $V$ then there is a surjection from $V$ onto the collection of all classes. This is trivial, given such an injection, map each set to its preimage if there is one, or to $\varnothing$ (say) if there is none.

Without further knowledge about your theory of collections of classes, there is no way to know whether these three pieces work. However, I suspect whatever you have in mind satisfies all three pieces.

$\endgroup$
7
$\begingroup$

Here is a way to formalize the almost-disjointness phenomenon in GBC. You don't need an inaccessible cardinal.

Theorem. In any model of GBC, there is definable transformation of classes $X\mapsto X^*$, such that if $X\neq Y$, then $X^*$ and $Y^*$ are almost disjoint, and there is no definable map from sets $a\mapsto X_a$ such that every $X^*$ is some $X_a$.

(What I mean by a transformation of classes is that there is a formula $\phi(X,Y)$ with only first-order quantifiers and class variables $X$ and $Y$ such that GBC proves that every class $X$ has one and only one class $Y=X^*$ for which $\phi(X,X^*)$ holds.)

Proof. Let $X^*=\left\{X\cap V_\alpha \mid\alpha\in\text{Ord}\right\}$. If $X\neq Y$, then $X\cap V_\alpha\neq Y\cap V_\alpha$ for all sufficiently large ordinals $\alpha$, and so $X^*\cap Y^*$ is a set. Thus, they are almost disjoint.

But I claim that there is no definable map $a\mapsto X_a$ that is surjective onto the classes $X^*$. For any map $a\mapsto X_a$, let $A=\{\ a\ \mid a\notin X_a\ \}$, and it is easy to see that $A\neq X_a$ for any $a$. Since $X=\bigcup X^*$ for any $X$, it follows that $A^*\neq X_a^*$ for any set $a$. QED

In particular, there can be no "injection" of the classes $X^*$ into the sets, since by inverting that we would get such a forbidden surjection $a\mapsto X_a^*$.

$\endgroup$
5
  • $\begingroup$ I feel like it's been a while since we last posted almost simultaneous and essentially identical answers... Cheers! $\endgroup$ Commented Jan 15, 2015 at 23:51
  • $\begingroup$ Yes, cheers! The more the merrier... $\endgroup$ Commented Jan 16, 2015 at 0:02
  • $\begingroup$ Thanks, you two, that's great! The source of this question is a result due independently to two groups. It says: every functor F on the category of classes is set based in an appropriate sense. Both papers got the result on class functors by analogy to the case of functors of sets of bounded cardinality (where there is no foundational issue). Both used almost disjoint families. One worked assuming Grothendieck universes, giving up a single category of classes. The other used NBG but didn't have your argument. Thanks again. $\endgroup$
    – Larry Moss
    Commented Jan 16, 2015 at 14:37
  • $\begingroup$ In the second part of Joel's theorem, "definable map" is implicitly understood to mean "first order definable, possibly with class parameters". Note that there are models of GBC in which there are $\Sigma^1_1$-definable bijections between the collections of classes and the collection of sets. For models of Kelley-Morse, of course, this could not happen. $\endgroup$
    – Ali Enayat
    Commented Jan 16, 2015 at 17:13
  • $\begingroup$ Yes, that is right. Another way to think about it is that the level of definability should be the same as our background theory allows us to use in forming classes, so that from the definition of the map $a\mapsto X_a$, we can form the class $A$ as in the proof. In GBC, the argument is that there is no surjective first-order definable map (possibly with class parameters), but in KM, the same argument shows there can be no second-order definable map. $\endgroup$ Commented Jan 16, 2015 at 17:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .