Cardinal numbers are used to denote the size of a set. To describe the size of a finite set we use natural numbers, the problem arises when we talk about infinite sets.

Let's accept the following notation: the cardinal number of the set X = the power of the set X = |X|.

According to the above definition, if X ∼ Y then |X| = |Y| and  if |X| = |Y| then  X ∼ Y.

Example 9.4.1

1. The set A = {x ∈ R: x² -2x +1 = 0 } has just one element because x² - 2x +1 = (x-1)², thus A = {1}, hence |A| = 1.
   
   
2. The set B = {x ∈ Z: x = sin y for some y ∈ R} has three elements because -1 ≤ sin y ≤ 1 for every y, it follows that the only integer values of function sin are -1, 0, +1. Hence |B| =|{-1,0,1}| = 3.

In order to prove Lemma 9.4.1 we assume that f is a function which establishes the equipotence of sets X and Y and let g: P(X) → P(Y) be a function, such that

We want to show, that g is a one-to-one function. If A ≠ A', A, A' ∈ P(X) then there exists an element a which belongs to only one of the sets A,   A'. Let  a ∈A, a ∉ A' and let b = f(a). Then b ∈ g(A) but b ∉ g(A') (since in the other case, there exists an element a' ∈ A' such that f(a') = b, that is, f would not  be one-to-one function). Therefore, g(A) ≠ g(A').

For any set B, B ∈ P(Y) we have  f ^-1(B) ⊆ X as well as g(f ^-1(B)) = B. Hence, the function g is a mapping onto P(Y).

It follows that g is a bijection of P(X) onto P(Y), thus, by definition 9.4.1, |P(X)| = |P(Y)|.

Cardinality of the set of natural numbers is usually denoted with the first letter of the Hebrew alphabet, alef₀, and cardinality of the set of real numbers with c (continuum).

Example 9.4.2

Cardinality of the set I of all intervals situated on the axis of real numbers with boundaries in rational points is equal to alef₀.

Justification: every interval can be unambiguously defined by giving its end-points. Let's construct a function f which to every interval ascribes a pair of rational points (interval's boundaries). This method creates a one-to-one assignment from the set I of intervals into the set of pairs (x,y) of rational numbers such that x<y. Because both sets Q as well as Q² are infinite countable sets and because I is equipotent to an infinite  subset of Q², the cardinality of  I  is equal to alef₀.

Example 9.4.3

Cardinality of any open-close interval is equal to the continuum. Let's take a function f which maps  the set {1/n}_n=2,3,4,... onto the set {1/n}_{n =1,2,3,...} f(1/n) = 1/(n-1) for n = 2,3,4,... . Let g: (0,1) → (0,1] such that g(1/n) = f(1/n) for n = 2,3,4.. . and g(x)= x for x ∉ {1/2,1/3,1/4,...}. The function g characterized in such a manner is a one-to-one mapping (both f as well as identity functions are one-to-one functions). Furthermore, the function g mapps  (0,1) onto  (0,1]. Thus, |(0,1]| = |(0,1)| = |R| = c.

Example 9.4.4

If A is a set of power alef₀, |A| = alef_0, and B is a set of power c,  |B| = c, then the cardinality of the product set A × B is equal to c.

Let (a₀,a₁,a₂,...) be an infinite sequence of all elements of set A. Because any two intervals of real numbers' set have the same power c, then there exist bijections f₀ : {(a₀, b) : b ∈ B} → (0, 1] , f₁ : {(a₁, b) : b ∈B} → (1, 2] etc., ... , f_i : {(a_i, b) : b ∈ B} → (i, i+1]. Assuming that f((a_i,b)) = f_i (b) we may define a one-to-one function which mapps the set A ×B onto R₊. Because |R₊| = |R| = c thus, |A × B| = c.

According to the reasoning form previous subsection and definition, the set of natural numbers is enumerable and the set of all real numbers is not enumerable.  Therefore,

Question 9.4.1 Estimate cardinality of the set of all points of the plane.

« previous section

next section »