14
$\begingroup$

In Bonn, we've been have a discussion on the topic in the title:

Suppose that $A$ and $B$ are classes and that there are injections from $A$ to $B$ and from $B$ to $A$. Does it follow that there is a bijection between $A$ and $B$?

Example: Let $A$ the class of sets of cardinality one and let $B$ be the class of sets of cardinality two. There is an injection

$A\to B$ sending $a$ to $\{a,\varnothing\}$,

$B\to A$ sending b to $\{\{b\}\}$.

Does it follow that there is a bijection between $A$ and $B$?

$\endgroup$
3
  • 2
    $\begingroup$ I'm not sure whether the question makes sense. $\endgroup$ Oct 19, 2009 at 1:12
  • 3
    $\begingroup$ I think it does make sense. A "bijection" between classes A and B should just be a subclass of A x B (i.e. a collection defined by some formula in the language of set theory) which is a one-to-one correspondence; similarly for "class injections." $\endgroup$ Oct 19, 2009 at 2:02
  • $\begingroup$ Yes, it makes sense (see my answer for elaboration). $\endgroup$ Oct 19, 2009 at 2:20

4 Answers 4

8
$\begingroup$

Ignoring set-theoretic technicalities of formulating the question properly, I see no reason that the usual proof of Schroder-Bernstein wouldn't work.

(Set-theoretic technicalities: In the standard language of set theory, you can't quantify over classes, so you can't quite state this. However, you can prove a metatheorem saying that whenever you exhibit two such injections, you can prove there is also a bijection. Alternatively, you could work in set theory with classes, in which the statement can be made properly and you ought to be able to prove it just like ordinary Schroder-Bernstein. Alternatively, it is a trivial corollary of the "global" axiom of choice (which implies, in particular, that all proper classes have the same size), though this is kind of applying a sledgehammer.)

$\endgroup$
4
  • 1
    $\begingroup$ Me either, but is that a proof? $\endgroup$ Oct 19, 2009 at 1:21
  • $\begingroup$ Sure it is. You can use the Schroder-Bernstein argument to explicitly construct a bijection from A to B given your two injections, for example. $\endgroup$ Oct 19, 2009 at 1:41
  • 4
    $\begingroup$ Could you expand your argument? I see that this works fine in MK (Morse-Kelley Set Theory), but I don't immediately see why it works in NBG. The problem is that NBG does not allow the comprehension of classes by quantification over classes, avoiding that seems non-trivial to me. $\endgroup$ Sep 6, 2010 at 19:03
  • 1
    $\begingroup$ I show the details of one way to do it in my answer. $\endgroup$ Sep 6, 2010 at 21:09
26
$\begingroup$

Since the question has arisen whether the standard arguments really do work with classes, let me post this answer giving some fuller details about one comparatively concrete way to do it. Other methods are also possible.

I shall work in the theory of Goedel-Bernays GB set theory (without global choice), a general setting for treating classes, which forms a conservative extension of ZF. This theory includes as a special case the traditional treatment of classes as definable collections in ZF, since every model of ZF, when augmented with its definable classes, forms a model of GB. Thus, the GB context seems the most comprehensive way to answer (and if you prefer ZF, then just imagine that all classes here are definable from parameters).

Suppose that $A$ and $B$ are classes and that we have class functions $F:A\to B$ and $G:B\to A$ which are injective, as in the question. Let $A_0=A-\operatorname{ran}(G)$, which is a class, since it is definable from $A$ and $G$. Let us say that a sequence $\langle x_0,x_1,x_2,\ldots\rangle$ is a back-and-forth-iteration sequence if $x_0\in A$ and $x_{2n+1}=F(x_{2n})$ and $x_{2n+2}=G(x_{2n+1})$ for all natural numbers $n$. Let $A_n$ be the elements $a_{2n}$ that appear at the even coordinates of a back-and-forth iteration sequence with $a_0\in A_0$. This notion is definable from $F$ and $G$, and the point is that we have a uniform presentation of the $A_n$ in a single class $\{(n,a)\mid a\in A_n\}$. Let $A^+=\bigcup_n A_n$, which is a class definable from $F$ and $G$.

Let $H$ be the function $(F\upharpoonright A^+)\cup(G^{-1}\upharpoonright A-A^+)$. I claim that this is the desired bijection between $A$ and $B$. First, it is clearly a class that is definable from $F$ and $G$. Second, it is a function from $A$ to $B$. Note that if $a\in A_n$, then $G(F(a))\in A_{n+1}\subset A^+$, and so $F(a)$ is not $G^{-1}(a')$ for any $a'\in A-A^+$. Thus, the function $H$ is injective. Secondly, if $b\in B$ and $G(b)\in A_n$, then it must be that $n\geq 1$ and so $b=F(a')$ for some $a'\in A_{n-1}\subset A^+$, putting $b\in\operatorname{ran}(H)$. Otherwise, $G(b)\notin A^+$, and so again $b\in\operatorname{ran}(H)$. So $H$ is a bijection. QED

Some of the other proofs can also be formalized for classes, if one simply uses the sequences as I did here for iterating.

$\endgroup$
5
  • $\begingroup$ +1: Thank you for clarifying, Joel! $\endgroup$ Sep 6, 2010 at 21:32
  • 1
    $\begingroup$ Ah ok. For me the point is the definabilty of the sequences. I thought it was difficult since the we cannot control the size of the range, which should be a subset (which set?) of the class $A \cup B$. But instead, we could just say, that $s$ is a set, which is a function with domain $\omega$, and such that for all $n$, $s(2n+1)=F(s(2n))$ and $s(2n+2=G(s(2n+1))$. I know this is trivial, but I didn't see it. ;) $\endgroup$ Sep 6, 2010 at 22:14
  • $\begingroup$ Yes, every $a\in A$ is the start of a unique back-and-forth sequence, by an instance of the Replacement axioms. $\endgroup$ Sep 6, 2010 at 23:13
  • $\begingroup$ This stuff is over my head, but somehow I was under the inpression that all proper classes were the "same size". But in that case there'd be no point in asking about the Cantor-Bernstein theorem. Is "all proper classes are equivalent" something that only holds true is certain brands of set theory? Or is it all wrong? $\endgroup$
    – bof
    Aug 28, 2023 at 11:08
  • 1
    $\begingroup$ @bof Yes, the assertion that all classes are equinumerous is true in some class theories and not others. Note that if the class V of all sets is equiunumerous with the class of ordinals Ord, then the universe is well-ordered, and this implies a strong form of the axiom of choice known as global choice. Meanwhile, it is consistent with ZFC including choice for sets, that V is not the same size as Ord. Indeed, it is consistent that the univese admits no global linear order (see mathoverflow.net/a/110823/1946). $\endgroup$ Aug 28, 2023 at 12:11
5
$\begingroup$

To ask this question, you have to first be clear what you mean by a "class". Do you mean a finite formula in ZFC language with one free variable, P(x)? (Writing P(x) roughly means "x has property P".)

Second, what do you mean by a map from a class P to a class Q? Do you mean a class of ordered pairs?

If "yes" to both of the above, then I think the answer to your question is also "yes", because the Schroeder-Bernstein argument will allow you to explicitly write down a formula F(x,y) from the formulas P( ) and Q( ) that is a "bijection" in the sense that for all x such that P(x) there is a unique y such that Q(y) and F(x,y).

If, however, you mean class in some other sense, like the undefined notion of "class" used in NBG set theory, or something more vague, a different answer will be required.

I recommend reading the wikipedia article on Zermelo-Frenkel Set Theory and browsing related articles until you feel comfortable the precise meanings of the basic terminology :)

$\endgroup$
1
  • 2
    $\begingroup$ In NBG the same answer still works, it just works even better because you can state it as a theorem rather than a metatheorem. The only thing to check is that you never would need to use comprehension with class variables, but you don't--you only use the specific classes in question as parameters. $\endgroup$ Oct 19, 2009 at 2:24
4
$\begingroup$

This is an interesting question. I think there are some issues which the others did not mention yet. But I'm not an expert at all, I might be wrong. Please leave me a comment!

In the following, I work in $ZF$. Thus, a class is just a formula. There are some constructions and relations of sets which directly carry over to classes. For example $A=B$ means that the formulas of $A,B$ are equivalent.

Let's sketch the proof for classes. Let $A,B$ classes, $f : A \to B$, $g : B \to A$ injective maps. Define the classes $A_n \subseteq A, B_n \subseteq B$ recursively by $A_0=A, B_0 = B, A_{n+1} = g[B_n], B_{n+1}=f[A_n]$. Then $h : A \to B$, defined by $f$ on $\cap_n A_n \cup (\cup_n A_{2n} \setminus A_{2n+1})$ and by $g^{-1}$ in the rest, is well-defined and a bijection.

Unions, cuts, images of functions etc. are not the problem. But what about the recursion? What we really need here is a recursion scheme for classes. Actually there is a theorem which might be called the transfinite recursion scheme for classes:

Let $R$ be a well-founded and set-like relation of the class $A$ and $F : A \times V \to V$ a function. Then there is a function $G : A \to V$, such that for all $x \in A$

$G(x)=F(x,G|_{\{y \in A : y R x\}})$.

However, note that the images of $G$ are sets, not proper classes. We can't use that theorem here.

I think we need a meta-theorem stating that the above also holds when $V$ is replaced by the set of formulas and $R=\mathbb{N}$. Also, the meta-world should be able to talk about functions. But this is not plausible at all, since the resulting formula won't have to be finite, right?

For example, try to define a formula $G(n)$ recursively by $G(0)=\phi_0$ (doesn't matter what $\phi_n$ is) and $G(n)=G(n-1) \wedge \phi_n$. Why should there be a formula $\psi(n,x)$ such that $\psi(n,x) \Leftrightarrow \wedge_{i=0}^{n} \phi_i$? I think we need a rather mighty logical calculus for that.

Also note that Francois' great answer here (proving Schröder-Bernstein without the existence of the set $\omega$) also causes problems when you want to write down the formula for the part "...$\exists s : \{0,...,n\} \to A$ ...". Perhaps there is really no bijection between the two classes mentioned above (class of all singletons, and class of all 2-element sets)?

$\endgroup$
8
  • 1
    $\begingroup$ Since you treat classes as formulae, I'm not sure you can always intersect or take a union of infinitely many, as this would translate to an infinitely long formula. So the definition for $h$ is a bit problematic. $\endgroup$
    – Asaf Karagila
    Sep 3, 2010 at 23:07
  • $\begingroup$ Right, this is another issue. $\endgroup$ Sep 3, 2010 at 23:12
  • $\begingroup$ I think that if you look at the class $\omega\times A\times B$, then you can define $A_n$ and $B_n$ as sub-classes for which you have $\langle n, x, b\rangle$ where $x$ is the variable for the formula defining $A_n$. Then you can take intersection or union by writing a formula which says that for all/some $n\in\omega$ the pair $\langle a,b\rangle$ satisfies some property. Then you verify that it is in fact a function and you should be done. $\endgroup$
    – Asaf Karagila
    Sep 4, 2010 at 0:44
  • $\begingroup$ I don't understand. My problem is: We may build by "outer induction" a formula for $A_n$ for every $n$, but there does not seem to be a formula $\psi$ such that $\psi(n,x)$ iff $x \in A_n$. $\endgroup$ Sep 4, 2010 at 2:07
  • $\begingroup$ Hmmm. Yes, I see the problem now. $\endgroup$
    – Asaf Karagila
    Sep 4, 2010 at 8:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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