Tag Archive: cardinality


Real Analysis Review Day 5: Cardinality (Part II)

Filed under: Interdisciplinary, Mathematics — Leave a comment
May 12, 2015

Definition. A set X is called countable (or denumerable) if card(X)\le card(\mathbb N). In particular, all finite sets are countable. If X is countable but not finite, then X is countably infinite.

 

Proposition. a. If X and Y are countable, so is X\times Y.

b. If A is countable and X_\alpha is countable for every \alpha\in A, then \cup_{\alpha\in A}X_\alpha is countable.

c. If X is countably infinite, then card(X)=card(\mathbb N).

Proof. a. If suffices to prove that \mathbb N^2 is countable. Define a bijection from $\mathbb N$ to $\mathbb N^2$ by listing, for n successively equal to 2, 3, 4, …, those elements (j, k)\in\mathbb N^2 such that j+k=n in order of increasing j, thus:

(1, 1), (1, 2), (2, 1), (1, 3), (2, 2), (3, 1), (1, 4), (2, 3), (3, 2), (4, 1), …

b. For each \alpha\in A $\exists$ a surjective f_\alpha: \mathbb N\to X_\alpha, and then the map f: \mathbb N\times A\to\cup_{\alpha\in A}X_\alpha defined by f(n, \alpha)=f_\alpha(n) is surjective.

c. X is an infinite subset of $\mathbb N$. Lef f(1) be the smallest element of X, and define f(n) inductively to be the smallest element of X\setminus\{f(1), ..., f(n-1)\}. Then f is a bijection from \mathbb N to X. \Box

 

Corollary. \mathbb Z and \mathbb Q are countable.

Proof. \mathbb Z is the union of the countable sets \mathbb N, \{-n: n\in\mathbb N\}, and \{0\}, and one can define a surjection f: \mathbb Z^2\to\mathbb Q by f(m, n)=m/n if n\not=0 and f(m, 0)=0. \Box

 

Definition. A set X is said to have the cardinality of the continuum if card(X)=card(\mathbb R). We use letter $latex\mathfrak c$ as an abbreviation for card(\mathbb R):

card(X)=\mathfrak c iff card(X)=card(\mathbb R)

Proposition. card(\mathcal P(\mathbb N))=\mathfrak c.

Proof. If A\subset \mathbb N, define f(A)\in\mathbb R to be \sum_{n\in A}2^{-n} if \mathbb N\setminus A is infinite and 1+\sum_{n\in A}2^{-n} if \mathbb N\setminus A is finite. Then f: \mathcal P(\mathbb N)\to\mathbb R is injective. On the other hand, define g: \mathcal P(\mathbb Z)\to\mathbb R by g(A)=log(\sum_{n\in A}2^{-n}) if A is bounded below and g(A)=0 otherwise. Then g is surjective since every positive real number has a base-2 decimal expansion. Since card(P(\mathbb Z))=card(\mathcal P(\mathbb N)), the result follows from the Schroder-Bernstein Theorem. \Box

 

Corollary. If card(X)\ge\mathfrak c, then X is uncountable.

 

Proposition. a. If card(X)\le\mathfrak c and card(Y)\le\mathfrak c, then card(X\times Y)\le\mathfrak c.

b. If card(A)\le\mathfrak c and card(X_\alpha)\le\mathfrak c for all \alpha\in A, then card(\cup_{\alpha\in A}X_\alpha)\le\mathfrak c.

Proof. It suffices to take X=latex Y=\mathcal P(\mathbb N). Define \phi, \psi: \mathbb N\to\mathbb N by \phi(n)=2n and \psi(n)=2n-1. Then f: \mathcal P(\mathbb N)^2\to\mathcal P(\mathbb N) defined by f(A, B)=\psi(A)\cup\phi(B) is bijective.  $\Box$

 

” Gratitude makes sense of our past, brings peace for today, and creates a vision for tomorrow.” ~ Melody Beattie

 

To be continued tomorrow 🙂

References

[1] Gerald B. Folland, Real Analysis: Modern Techniques and Their Applications, 2ed, page 8-9.

[2] Purpose Fairy’s 21-Day Happiness Challenge, http://www.jrmstart.com/wordpress/wp-content/uploads/2014/10/Free+eBook+-+PurposeFairys+21-Day+Happiness+Challenge.pdf.

Advertisements
Tags: ,
Comment

Real Analysis Review Day 4: Cardinality (Part I)

Filed under: Interdisciplinary, Mathematics — Leave a comment
May 10, 2015

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 🙂

References

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

[2] Purpose Fairy’s 21-Day Happiness Challenge, http://www.jrmstart.com/wordpress/wp-content/uploads/2014/10/Free+eBook+-+PurposeFairys+21-Day+Happiness+Challenge.pdf.

Tags: ,
Comment