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

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, .

Theorem

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 .

Theorem

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.

Theorem

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 .

Theorem

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.

Proposition

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 .

Theorem

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

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 .

Cantor's Theorem

For any set there holds . Thus there is no maximal cardinality.

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 .

Theorem

.

Continuum Hypothesis

There does not exist a set with .

Theorem

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.