main09

Definition 9.5.1

We say that a cardinal number m is less or equal than a cardinal number n (i.e. m ≤ n) if and only if there exist sets X and Y such that X ⊂Y and |X| = m, |Y| = n.

We say that the cardinal number m is less than the cardinal number n (i.e. m < n) if and only if m ≤ n and n ≠ m.

Notice, that the relation ≤ is similar to a well-known relation defined over the set of natural numbers.

Conclusion Because the set of natural numbers N is a subset of the set R then alef₀ ≤ c.

Lemma 9.5.1

For any cardinal numbers n, m, u, hold

n ≤ n
if m ≤ n and n ≤ u then m ≤ u.

By definition, in order to prove that two sets have the same cardinality one must establish a bijection between them. The most difficult part of this proof is often to show that the mapping is surjective. To find a one-to-one function is usually easier. The next theorem, called Cantor-Bernstein theorem, allows to prove equality of cardinality using only injective functions.

Theorem 9.5.1 (Cantor-Bernstein theorem )

For arbitrary cardinal numbers n, m, u, if m ≤ n and n ≤ m then n = m .

Example 9.5.2

An infinite set K of pair-disjoint intervals over some straight geometrical line with boundaries placed in rational points, has the cardinality alef₀. We can explain this, if to every interval we ascribe a pair of rational numbers (segment's ending points). This way we construct a one-to-one projection from the set K into the set Q ×Q, thus |K| ≤ |Q²|. On the other hand |N| ≤ |K|. Finally K is a countable set.

Lemma 9.5.2

If there exists a function which projects the set A onto B, then |B| ≤ |A|.

Let f be a function which mapps A onto B, f: A →B. Then any function g : B → A such that g(b) ∈ f^-1({b}) for b ∈ B is one-to-one function from B into A.

Indeed, according to assumed properties of f, for every b ∈B, g(b) belongs to A. Because f is a projection "onto" B (i.e. every b ∈B is an image of some element of the set A), thus f^-1({b}) is at least a one-element set, for all b. Hence, it follows that g is well defined for every b ∈ B. Moreover, if b₁ ≠ b₂ then

{a ∈ A: f(a) = b₁} ∩ { a ∈ A: f(a) = b₂} = f ^-1({b₁}) ∩ f ^-1({b₂})= ∅,

thus g(b₁) ≠ g(b₂). It means that g is a one-to-one function from the set B into the set A. In accordance to the definition 9.5.1, |B| ≤ |A|.