by tzy9393

Definition: If there exists a 1-1 mapping of {A} onto {B}, we say that {A} and {B} can be put in 1-1 correspondence , or that {A} and {B} have the same cardinal number , or briefly, that {A} and {B} are equivalent, and we write {A\sim B}. This relation clearly has the following three properties:

  1. It is reflexive: {A\sim A}.
  2. It is symmetric: if {A\sim B}, then {B\sim A}.
  3. It is transitive: if {A\sim B} and {B\sim C}, then {A\sim C}.

Definition: For any positive integer {n}, let {J_{n}} be the set whose elements are the integers, {1,2,...,n}; let {J} be the set of all positive integers. For any set {A}, we say:

  1. (a) {A} is finite if {A\sim J_{n}} for some positive integer {n}.
  2. (b) {A} is infinite if {A} is not finite.
  3. (c) {A} is countable if {A\sim J}.
  4. (d) {A} is uncountable if {A} is neither finite nor countable.
  5. (d) {A} is at most countable if {A} is finite or countable.

Remark: A finite set cannot be equivalent to one of its proper subsets. However, this is possible for infinite sets. In fact, we could restate the definition (b): {A} is infinite if {A\sim B} for some {B\subset A}.

Theorem 1 Every infinite subset of a countable set {A} is countable.

Proof: Suppose {B\subseteq A} and {B} is infinite. Arrange the elements of {A} which are all distinct in a sequence {(a_{i})_{i=1}^{\infty}}. Then we construct a sequence {(n_{k})_{k=1}^{\infty}} as follows:

Let {n_{1}\in J} be the smallest number such that {a_{n_{1}}\in B}. Note {n_{1}} exists because {\mathbb{N}} is well-ordered. After choosing {n_{1},...,n_{k-1}}, we let {n_{k}} be the smallest number greater than {n_{k-1}} such that {a_{n_{k}}\in B}.

Then consider the function {f: J\rightarrow B} where {f(k)=a_{n_{k}}}. We then check {f} is indeed a bijection. It is one-to-one because {(a_{i})_{i=1}^{\infty}} is a distinct sequence; then for any {i\neq j}, we have {a_{n_{i}}\neq a_{n_{j}}}. {f} must be surjective for otherwise, there exists {b\in B} is not in the image of {(a_{i})_{i=1}^{\infty}} contradicting the fact that {B\subseteq A}.


Corollary 2 Every subset of an at most countable set is at most countable.

Proof: Let {A} be an at most countable set and {B\subseteq A}. If {A} is finite, then {B} is must also be finite. So let us assume {A} is countable. Then {B} cannot be uncountable by theorem 1.


Corollary 3 An at most countable set that contains a countable subset is countable.

Proof: Let {A} be at most countable and {B\subseteq A} is countable. If {A} is countable then we are done. So we need to prove that {A} cannot be finite. Suppose {A} is finite then there exists a bijection {f: A\rightarrow J_{n}}. Let {g: J\rightarrow B}. Then the composition {f\circ g:\mathbb{N}\rightarrow J_{n}} must be injective. However, by pigeonhole’s principle we know this cannot happen, thus a contradiction.


Theorem 4 Countable unions of countable sets is countable.

Corollary 5 At most countable unions of at most countable sets is at most countable.

Let {\left\{X_{\alpha}|\alpha\in A\right\}} be an arbitrary family of sets. We define the Cartesian product {\prod_{\alpha\in A}X_{\alpha}} to be all the functions {\phi: A\rightarrow\bigcup_{\alpha\in A}X_{\alpha}} such that {\phi(\alpha)\in X_{\alpha}}. We can think of {\phi(\alpha)} as an evaluation of {\phi} at the {\alpha}-th entry. For example if {A=\mathbb{N}}, {\phi(1)} is simply the first entry of the Cartesian product.

Theorem 6 Finitely many Cartesian products of countable sets is countable.

Theorem 7 Countable Cartesian products of countable sets is uncountable.

Proof: Let {S:=\prod_{n=1}^{\infty} A_{n}} where {A_{n}} is countable for each {n\in J}. Let {(f_{i}: i\in J)} be an enumeration. For each {n\in J} we pick two different element {a_{n}, b_{n}\in A_{n}}. Consider the following function:

\displaystyle f(j) = \left\{ \begin{array}{lr} b_{j} & : \mathrm{if}\, f_{j}(j)=a_{j}\\ a_{j} & : \mathrm{otherwise} \end{array} \right.

Note {f\in S} obviously. However, note {f\neq f_{i}} for all {i\in J} because {f} differs from every {f_{i}} at least at {f_{j}(j)}. Thus {S} in not countable.


Corollary 8 Let {A} be the set of all sequences whose elements are the digis 0 and 1. Then {A} is uncountable.

Proof: Remember the set {A} is indeed identified with the Cartisian product {\left\{0,1\right\}^{\mathbb{N}}}. Although we cannot directly apply theorem 7 because {\left\{0,1\right\}} is finite, we still can use the same Cantor trick. Let {(f_{i}: i\in J)} be an enumeration of {A}. We define the following function

\displaystyle f(j) = \left\{ \begin{array}{lr} 0 & : \mathrm{if}\, f_{j}(j)=1\\ 1 & : \mathrm{otherwise} \end{array} \right.

Again {f\in A} obviously, but {f} differs from {f_{i}} for every {i\in J}. Thus {A} is uncountable.


Theorem 9 There exists no surjection from a set {X} to {\mathcal{P}(X)}.

Proof: We prove by contradiction. Let {\varphi: X\rightarrow\mathcal{P}(X)} be a surjection. By definition, for any {A\in\mathcal{P}(X)} there exists {a\in X} such that {\varphi(x)=A}. Consider the following set

\displaystyle Y:=\left\{x\in X| x\notin\varphi(x)\right\}

So {Y} has an pre-image in {X}. Let {y\in X} such that {\varphi(y)=Y}. It is either {y\in Y} or {y\notin Y}. If it is the first case, then {y\in X} and {y\notin\varphi(y)=Y} by definition, but his contradicts the fact that {y\in Y}. If it is the second case, we have {y\notin Y}, so {y\in X} and {y\in\varphi(y)=Y}, contradiction again. Hence {\varphi} cannot be a surjection and the proof is complete.