Real Analysis Review Day 4: Cardinality (Part I)

If X and Y are nonempty sets, then

card(X)\le card(Y), card(X)=card(Y), card(X)\ge card(Y)

mean \exists f: X\to Y which is injective, bijective, or surjective, respectively. We also define

card(X)<card(Y), card(Y)<card(X)

to mean that \exists an injection but no bijection, or a surjection but no bijection, from X to Y. These relationships can be extended to the empty set by declaring that

card(\emptyset)<card(X) and card(X)>card(\emptyset) for all X\not=\emptyset.

Proposition. card(X)\le card(Y) iff card(Y)\le card(X).

Proof. \Rightarrow: If f: X\to Y is injective, pick an arbitrary x_0\in X and define g: Y\to X by g(y)=f^{-1}(y) if y\in f(X), g(y)=x_0 otherwise. Then g is surjective.

\Leftarrow: If g: Y\to X is surjective, the sets g^{-1}(\{x\})(x\in X) are nonempty and disjoint, so any f\in\prod_{x\in X} g^{-1}(\{x\}) is an injection from X to Y. \Box

Proposition. For any sets X and Y, either card(X)\le card(Y) or card(Y)\le card(X).

Proof. Consider the set \mathcal J of all injections from subsets of X to Y. The members of J can be regarded as subsets of X\times Y, so \mathcal J is partially ordered by inclusion. Applying Zorn’s Lemma, then \mathcal J has a maximal element f, with domain A and range B. If x_0\in X\setminus A and y_0\in Y\setminus B, then f can be extended to an injection from A\cup\{x_0\} to B\cup\{y_0\} by setting f(x_0)=y_0, contradicting maximality. Hence either A=X, in which case card(X)\le card(Y), or B=Y, in which case f^{-1} is an injection from Y to X and card(Y)\le card(X). \Box

Proposition. The Schroder-Bernstein Theorem. If card(X)\le card(Y) and card(Y)\le card(X), then card(X)=card(Y).

Proof. Let f: X\to Y and g: Y\to X be injections. Consider a point x\in X: If x\in g(Y), we form g^{-1}(x)\in Y;  if g^{-1}(x)\in f(X), we form f^{-1}(g^{-1}(x)); and so forth. Either this process can be continued indefinitely, or it terminates with an element of X\setminus g(Y) (perhaps x itself), or it terminates with an element of Y\setminus f(X). In these three cases we say that x is in X_\infty, X_X, or X_Y; thus X is the disjoint union of X_\infty, X_X, and X_Y. In the same way, Y is the disjoint union of three sets Y_\infty, Y_X, and Y_Y. Clearly f maps X_\infty onto Y_\infty and X_X, whereas g maps Y_Y onto X_Y. Therefore, if we define h: X\to Y by h(x)=f(x) if x\in X_\infty\cup X_X and h(x)=g^{-1}(x) if x\in X_Y, then h is bijective. \Box

Proposition. For any set X, card(X)<card(\mathcal P(X)).

Proof. On the one hand, the map f(x)=\{x\} is an injection from X to \mathcal P(X). On the other, if g: X\to\mathcal P(X), let Y=\{x\in X: x\notin g(x)\}. Then Y\notin g(X), for if Y=g(x_0) for some x_0\in X, any attempt to answer the question “Is x_0\in Y?” quickly leads to contradiction. Therefore g cannot be surjective. \Box

“Friendship with one’s self is all important, because without it one cannot be friends with anyone else in the world.” ~ Eleanor Roosevelt

To be continued tomorrow 🙂


1] Gerald B. Folland, Real Analysis: Modern Techniques and Their Applications, 2ed, page 6-7.

[2] Purpose Fairy’s 21-Day Happiness Challenge,

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: