0
$\begingroup$

If there exists a bijection between a collection $C$ and a proper class $PC$, is $C$ necessarily a proper class as well? I've read and have been told by math professors that the answer is yes, but could someone motivate that answer?

My understanding of why a collection is a proper class rather than a set is because were the collection to be a set, some contradiction would result. But the contradictions that result are specific to whatever kind of collection is under consideration. E.g., the contradiction that would result were the collection of all cardinals to be a set is different from contradiction that would result were the collections involved in Russell's paradox sets, etc.

So, without knowing the specific contradiction that would result if the collection $C$ (for which there is a bijection with a proper class) were a set, how do we automatically know that $C$ is a proper class and not a set?

$\endgroup$
4
$\begingroup$

If $C$ is a set, then its image by any class function is also a set (Axiom of Replacement). Since $PC$ is the image of $C$ by a class function (the hypothesized bijection) and $PC$ is not a set, we can conclude that $C$ is not a set either.

$\endgroup$
2
$\begingroup$

The answer by eyeballfrog perfectly explains - at least, assuming a set-and-class theory in which replacement holds for sets (so, any set-and-class theory extending ZF, for example) - why the answer to your question is yes. Let me say a bit about what I think is the underlying confusion.

You write:

My understanding of why a collection is a proper class rather than a set is because were the collection to be a set, some contradiction would result. But the contradictions that result are specific to whatever kind of collection is under consideration.

This is a very reasonable takeaway from the usual "story" about proper classes: that Russell's paradox demonstrates the need for a set/class distinction by producing a meaningful dilemma. More generally, this suggests that "set until proven otherwise" be an important principle.

However, this is incorrect, and what's going on is that we're overloading a purely mathematical topic with philosophical bias. The set/class distinction is treated just like any other mathematical issue. We have some axioms to handle the topic, and anything we can prove from those axioms - regardless of the underlying "reason" behind the proof - is valid in our context.


Confession: above I said that eyeballfrog's answer requires a set-and-class theory rather than just a set theory (like ZF). This isn't really true, since we can talk about classes in set theory to a certain extent, but this involves sometimes subtle circumlocutions, which I think are best avoided at first. So for now, just assume that we're working in a background theory which is strong enough to make sense of all the statements we're making without any difficulty. A good candidate for such a theory is NBG.

$\endgroup$
0
$\begingroup$

It is conceptually simpler if you work in a class theory such as NBG or MK, in which classes are actually objects. However, if you want to see how the issue looks like in ZFC, you have to always remember that a class is nothing more than a $1$-parameter sentence over ZFC. For example, the Russell class $R$ would be defined by $R(x) \equiv x \notin x$. And an arbitrary collection is nothing more than a class. Similarly, a bijection between classes $C$ and $D$ is nothing more than a $2$-parameter sentence $F$ over ZFC such that ZFC proves "$\forall x \in C\ \exists! y \in D\ ( F(x,y) ) \land \forall y \in D\ \exists! x \in C\ ( F(x,y) )$". Note that what I just wrote can be expanded to a sentence over ZFC. In other words, classes are definable properties over ZFC, and bijections between classes are definable functions that are provably bijective. Finally, a proper class is a class $C$ such that ZFC proves "$\neg \exists S\ \forall x\ ( C(x) ⇔ x \in S )$". For instance, $R$ is a proper class since ZFC proves "$\neg \exists S\ \forall x\ ( x \notin x ⇔ x \in S )$".


With this in mind it is easy to see that the claim for ZFC is essentially a claim in the meta-system:

For any classes $C,D$ and bijection $F$ from $C$ to $D$, if $C$ is a proper class then $D$ also is.

Proof sketch: Work inside ZFC under the assumption that $\exists S\ \forall x\ ( D(x) ⇔ x \in S )$:

  Let $S$ be such that $\forall x\ ( D(x) ⇔ x \in S )$.

  By replacement and bijectivity of $F$, let $U$ be such that $\forall y \in S\ \forall x \in C\ ( F(x,y) ⇔ x \in U )$.

  Then by bijectivity of $F$ again, we have $\forall x \in C\ ( x \in U )$.

  Thus by specification $\exists T\ \forall x\ ( C(x) ⇔ x \in T )$.

Therefore ZFC proves that $\neg \exists T\ \forall x\ ( C(x) ⇔ x \in T ) ⇒ \neg \exists S\ \forall x\ ( D(x) ⇔ x \in S )$, and the claim follows.


This should also address the issue of how we "automatically know the claim" despite the contradiction being 'specific' to the proper class. Namely, the claim is a meta-theorem that essentially gives us a constructive way to convert any proof that $C$ is a proper class into a proof that $D$ is a proper class, given any proof of a bijection between $C$ and $D$. Yes, the proof generated will vary according to the proofs provided, but as shown above this conversion works uniformly.

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