Cardinality

Cardinality and Properties

Cardinality

With every set A we associate a symbol , called the cardinality or cardinal number of A, which obeys the following rules:

• If two sets and are equinumerous, then .
• For the empty set we set .
• For any we set .
• We set and .
• For two sets and , if is equinumerous to a subset of , then .
• If and , we write .

Proposition

if and only if there exists injection .

Proof forms a bijection, .

Pigeonhole Principle

There does not exist an injective function whose codomain is smaller than its domain.

Proposition

The following properties hold:

1. .
2. For any infinite set there holds .
3. and implies .

Proof is obvious. We have as any denumerable set is infinite. And since the set of real numbers is denumerable we have . The second statement is a direct result of any infinite set has a denumerable subset. Since and , there exist injections and . Thus is an injection. This means .

Disjoint Sets

Given two sets and , if , then and are called disjoint. For a family of sets , if for any two distinct indices , then is called mutually disjoint.

Lemma Let and be two families of mutually disjoint sets over the same index set . If for all , then Thrm Schröder-Bernstein Theorem Let and be two sets. If and , then . e.g. Recall that . Since , we have . Since , we also have . By the theorem, .

Thrm Any subset of a countable set is countable. Proof Let be countable and . If is finite, nothing needs to be proved. If is infinite, it follows from that . On the other hand, since and is countable, we have . By Schroder-Bernstein Theorem, we have .

Thrm A countable union of countable sets is countable.

Corollary If are countable sets, then is also a countable set. Proof We define . Then and the latter is countable by the above theorem.

Corollary Let and be two sets. If , show that either or . Proof Assume that and . Since , there is a bijection . Let and . Then Let and . Then both and have cardinality . Let and denote the projections of onto and respectively. We claim that and . If , since is a surjection, this means that is equinumerous to a subset of and hence , contradicting . By a similar argument we can obtain . Therefore, there exists such that for all and for all . Thus , yielding a contradiction.

Thrm The set of rational numbers is denumerable. Proof By definition, we haveIndeed by mapping . Hence by theorem. As , . Therefore .

Theorem

Let be an infinite set and a countable set. Then .

Proof Since is infinite, by proposition we can pick a denumerable subset . Since is countable, by theorem is also countable. It then follows from corollary that is countable, that is . Note that . By the Schroder-Bernstein Theorem we have , thus . Therefore, we may use lemma to obtainas required.

Corollary The set of irrational numbers has cardinality , that is . Proof Note that . Recall that is denumerable. If is finite, then the corollary would imply is countable, contradicting the fact . Thus must be infinite. It then follows from theorem that .

Thrm If are countable, then is also countable. Proof The result holds trivially for . Assume the result is true for , that is the product of any countable sets is countable. The consider . Let be countable sets. Since is countable, we may write . Let for each . Then by simply . Hence each is countable by inductive hypothesis. Therefore, is countable as countable union of countable sets is countable.

Thrm Let denote the set of all sequences consisting of real numbers, that is Then .

Corollary For any there holds .

Corollary Let be nonempty sets with for each and at least one of them has cardinality . Then has cardinality .

Thrm Let be a family of sets with and for all . If one of has cardinality , then Proof According to corollary we have . Since , there exists an injection for each . Consider the function such that for all . Observe that is injective, therefore On the other hand, since there is such that and , we haveHence .

Power Sets

Def Power Set Given a set , the set consisting of all subsets of is called the power set of , denoted as . e.g. For we have

Thrm For any set there holds . Proof Note that the function defined by for all is an injection. Therefore . If , then there exists a bijection . Define which is a subset of and hence is contained in . Thus there exists such that . We have either or . If ,then as an element in we must have which is a contradiction; if , then , by definition of we must have , a contradiction again. This shows . Consequently .

Corollary There is no maximal cardinality. Proof A direct consequence of the above theorem.

Thrm .

Hypo Continuum Hypothesis There does not exist a set with .

Thrm The continuum hypothesis is consistent while independent with the accepted axioms of set theory. Therefore, the continuum hypothesis is undecidable within the existing axioms of set theory.