Cardinality

The concept of a bijective function allows us to compare qunatitavely two sets: per sapere se i coperchi sono tanti quanto le pentole, basta coprire ogni pentola con un coperchio: se ogni pentola riceve un coperchio e non restano coperchi vuol dire che i coperchi sono tanti quanto le pentole.

1.8.1 Definition. Two sets X and Y are said to have the same cardinality if there exists a bijection f: X → Y, in which case we write |X| = |Y|. If there is an injection f: X → Y, then X is said to have cardinality less than or equal to that of Y, and we write |X| ≤ |Y|. □

Two finite sets have the same cardinality if, and only if, they have the same number of elements. It is thus common to write |X| for a finite set X to indicate the number of elements in X.

It can be easily verified that the property of having the same cardinality in as equivalence relations among sets. Two equipotent sets are indicate as

1.8.2 Definition. We define the cardinality or cardinal number or power/potency of a set X, the equipotency class to which X belongs to. We indicate it as Card(X).  □

So a cardinal number is the class of sets equipotent to a given set.

1.8.3 Definition. A set A is said finite if for some n ∈ ℕ, n ≠ 0, A is equipotent to I_n = {0, 1, 2, ..., n − 1}. A set which is not finite is said infinite. □

In the case of finite sets the notion of cardinality coincides with the notion of number of elements of the set and the cardinality of I_n is n.

For example, given the set A = {1, 2, 5, Italy, {6,π}, 0.3} we can count the number of elements it contains, a total of six. Thus, the cardinality of the set A is 6, or |A| = 6. Since sets can be infinite, the cardinality of a set can be an infinity.

In other words, natural numbers 0, 1, 2,.. become cardinal numbers (finite): 0 is the cardinal number of the empty set Ø, 1 is the cardinal number of {Ø} (and of any other set belonging to the same equipotency class), 2 is the cardinal number of {Ø,{Ø}} (and of any other set of the same class), 3 is the cardinal number of {Ø,{Ø},{Ø,{Ø}}, and so on. Thus, natural numbers are nothing more that particular cardinalities. The potency of ℕ, is represented by ℵ₀ (read alef-zero) and it known as the cardinality of the countable set.

1.8.3 Theorem. Let f: X ⟶ Y be a function where, X,Y are finite sets. Then,

1. if |X| = |Y| then f is one-to-one if and onlu if it is onto;

2. if |X| > |Y| then f cannot be one-to-one. More generally, if k is a positive integer such that |X| > k|Y| then there exist at least k + 1 distinct points, say x₁, x₂, ..., x_k+1 in X such that f(x₁), f(x₂), ..., f(x_k+1).  □

The second statement is what is called the pigeon-hole principle. In essence it says that if (n+1) pigeons occupy n holes, then some hole must have at least 2 pigeons. Thus if 5 pigeons occupy 4 holes, then there must be some hole with at least 2 pigeons. Another way to state it is

Pigeon-hole principle. Given two sets X and Y with the same cardinality. Let f be a map X ⟶ Y. Then

Countable sets

A countable set is a set with the same cardinality (number of elements) as some subset of the set of natural number. A countable set is either a finite set or a countably infinite set.

1.8.4 Definition. A set is said denumerable (or countable infinite) if it equipotent to ℕ, i.e. if there is a bijection of the set onto the set ℕ of all natural numbers. A set is countable if it is either finite or denumerable. If a set is not countable then we say that the set is uncountable. □

This terminology is not universal. Some texts use the word countable more narrowly to refer to countably infinite sets, and do not include finite sets. Today countable sets form a branch of mathematics called discrete mathematics.

If a set is countable then it is often convenient to write the set as a list, i.e. for a countable set S there exists an enumeration or written as infinite sequence as follows:

Example. The set of even number A = {2, 4, 6, 8, ..} is countably infinite. A bijection f: A ⟶ ℕ is given by f(n) = n/2 − 1.  ■

It is not hard to prove that a subset of a countable set is finite, or it is as well countable. The following theorem allows us to find many countable sets.

The set ℤ of integers and the set ℚ of the rational numbers a countable sets. The set ℝ of the real numbers and the set ℂ of the complex numbers are noncountable sets. These sets are equinumerous to P(ℕ), the power set of the natural numbers, and their cardinality is called continuum.

1.8.5 Axiom of Choice. If {A_i: i ∈ I} is a nonempty set of nonempty sets, then there is a function f: I ⟶ U_{i ∈ I} A_i satisfying f(i) ∈ A_i for each i ∈ I. In other words, the Cartesian product of a nonempty set of nonempty sets is itself a nonempty set.  □

1.8.6 Theorem. The union of a finite or a countably infinite number of countable sets is countable.

Proof. We prove the theorem in the case of a countably infinite lists of countable sets which are pairwise disjoint: the other cases derive from this. Let A₁, A₂, ..., A_j... a countably infinite lists of countable sets. The elements of A_j are thus

Applying the axiom of choice on the set of functions B_j = {all bijections A_j ⟶ ℕ} a nonempty set, we can find a map f: ℕ ⟶ U_j B_j with f(j) in B_j for each j; so A = A₁ ∪ A₂ ∪ A₃ ∪ ... is as well countable. We show this mapping by numbering the elements of A. To this end, we put the elements of this union of sets in a table in which on the j-th row we find the elements a_j,i of the set A_j.

Consider the j-th diagonal, D_j, that is

Every element a_h,k ∈ A belongs to one and only one diagonal, namely the diagonal D_h+k−1. We can set forth the following correspondence between A and ℕ:

The elements of A are thus numbered as follows

we can use arrows to visualize this pairing which is known as Cantor's diagonal argument:

We obtain thus a bijection between A and ℕ, hence the set A is countable. □

1.8.7 Corollary The set ℤ of the integers is countable as ℕ x ℕ.

Proof. It suffices to write these sets as union of a finite numnber or an countably infinite lists of countable sets. We have:

where

is countable for every h. □

1.8.8 Definition. We say that a set A has cardinality less or equal to that of a set B if there exists an injective mapping f: A → B. We write

If it results Card(A) ≤ Card(B) and Card(A) ≠ Card(B), then we write

We shall see now that there exists as well cardinality larger than that of the countable infinity.

Cantor's Theorem

By using the the idea of "power set" we are able to rate bigger infinities. For example if we take the set {1,2,3} (with cardinality 3) its power set contains the empty set, {1}, {2}, {3}, {1,2}, {1,3}, {2,3} and {1,2,3} and so has cardinality 8. The formula is that, if the original set has cardinality n, then its power set has size 2ⁿ. Amazingly, the same conclusion is true for infinite sets: the power set of an infinite set creates a new set of a bigger infinity.

Cantor's Theorem states that the cardinality of a set is strictly less than the cardinality of its power set.

1.8.9 (Cantor's Theorem [1883]) Given an arbitrary countable set A, it results

1^a Proof. The application h: A → P(A) defined as h(x) = {x} ∀x ∈ A is an injective mapping from A to P(A), thus Card(A) ≤ Card(P(A)). Since (see Theorem 1.4.19: there a bijection between P(A) with the function from A to {0,1})

To prove the theorem we must show that f is not surjective. It suffices to find an element in P(A) which is not in the image of f. Such an element is:

(Notice that if B is empty the proof is still valid).

Suppose now that f is surjective. Then there exists ξ ∈ A such that f(ξ) = B. By construction, ξ ∈ B ⟺ ξ ∉ f(ξ) = B. Which is a contradiction. Then, f cannot be surjective. Since, h: A → P(A) defined by x ↦ {x} in an injective function. Consequently, we have Card(A) < Card (P(A)). □

2nd Proof. To prove there is no bijection between 2^A and A, it sufficies to prove that which is not possible arrange in a numerable sequence A₁, A₂, A₃, ..., the set 2^A of the sequences of 0s and 1s. By way of contradiction assume there exists such a correspondence between 2^A and ℕ. This means that every sequence of symbols 0s and 1 we can map an index k ∈ ℕ, that is

all sequences of 0s and 1. If we are able to find a sequences of 0s and 1 not appearing in the list, we would have found a contradiction. To this end we define a sequence S = s₁s₂s₃... in the following way:

it results clearly S ≠ A for every i and the theorem is proves. □

Cantor's continuum hypothesis

Some sets are infinite, these sets have more than n elements for any integer n. For example, ℕ has infinitely many elements, and we canno use any normal number to give its size. Nonetheless, it turns out that inifnite sets do have a well-defined notion of size (or more properly, of cardinality), and not all infinite sets have the same cardinality.

In 1877 Cantor proposed the “continuum hypothesis”: It is the statement that there are no sets intermediate in size between a countable set and its power set. This means that there is no intermediate size between ℕ and P(ℕ). This means that P(ℕ) has the same cardinality of the real numbers ℝ, so |ℝ| = 2^ℵ₀. Cantor therefore denoted it ℵ₁. The continuum hypothesis states that the set of real numbers (the continuum) is in a sense as small as it can be.

Lemma 1.8.10. If a set a is uncountable and A ⊆ B, then B is also uncountable.

Proof. Suppose by way of contradiction that B is countable. Then since A ⊆ B, we can say that A is also countable, which is a contradiction as A is given uncountable. Hence B is uncountable.  □

Proposition 1.8.10 (Cantor [1873]) ℝ is uncountable.

Proof. We will show that the subset I = {x ∈ ℝ | 0 ≤ x ≤ 1} = [0, 1] is uncountable. Suppose on the contrary that [0,1] is countable. Then each element of

can be written in the form of sequence (having distinct elements). So, let each elements in I be written in the form

where a_ij ∈ {0,1,2,..,9} and where each decimal expression contains an infinite number of non-zero elements. Now construct the real number

where b₁ is any digit such taht b₁ ≠ 0, b₁ ≠ a₁₁ and b₂ ≠ a₂₂ and so on (i.e. b_i ≠ 0 and b_i ≠ a_ii, we exclude 0 because *preferring* decimal expansions with an infinite number of non-zero digits). Observe that

Hence, y ≠ I. But clearly y ∈ I. Thus we arrive at a contradiction. Hence I = [0,1] is not countable and by Lemma 1.8.10, ℝ is not countable as well . □

The continuum hypothesis is the first of David's Hilbert famous list of twenty-three unanswered questions posed in 1900. It was proved that the continuum hypothesis is independent of the other axioms of set theory, this implies that it is not possible to prove or disprove the continuum hypothesis, starting from these axioms.

The Generalized Continuum Hypothesis, states for every infinite set X there are not sets with intermediate cardinality between that of X and of P(X).

Axiom of Choice. Let X be a set whose members are nonempty sets. Then there is a function f with domain X which assigns to each A ∈ X an element f(A) ∈ A.

In particular, it should be noticed that the element f(A) is uniquely determined for each A ∈ X. The function f is called a choice function.

the family of set of function F = {{f:A_j ⟶ ℕ | f bijective} | j in ℕ} by the Zermelo's axiom it is possible to pick representative of a particular set {f:A_j -> N | f bijective} of the class F is an injective function f: A_j -> N.