Lecture
Definition. A set is called finite if it contains a finite number of elements, and infinite if it contains an unbounded number of elements.
|
Example. The set A={1,2,3,4,5,6,7,8,9,0} of digits in the decimal number system is finite, whereas the set of points of a circle is infinite. |
To compare sets with one another, the notion of the cardinality of a set is introduced. For finite sets the notion of cardinality corresponds to the number of elements of the set. Infinite sets can be compared by cardinality by establishing a one-to-one correspondence between the elements of one set and the other.
Two sets M and N, are called equivalent in cardinality (notation M ~ N) if a bijection can be established between their elements.
A set is called countable if it is equivalent to the set of natural numbers.
A finite set — is a set whose number of elements is finite, that is, there exists a non-negative integer k equal to the number of elements of this set. Otherwise the set is called infinite. For example,
is a finite set of five elements. The number of elements of a finite set is a natural number and is called the cardinality of the set. The set of natural numbers is infinite:
Finite sets play a special role in combinatorics, which studies discrete objects. Reasoning about finite sets uses the Dirichlet principle, according to which there cannot exist an injection from a larger finite set into a smaller one.
Two sets 
and 
are called equivalent if there exists a bijective mapping of one set onto the other. If the sets X and Y are equivalent, then this fact is written 
or 
and one says that the sets have the same cardinality.
A set is called finite if it is equivalent to the set 
for some non-negative integer 
. In this case the number is called the number of elements of the set , which is written as 
.
In particular, the empty set is a finite set whose number of elements equals 0, that is, 
.
There are also other definitions of a finite set:
The problem of determining the finiteness of sets is in general undecidable (Trakhtenbrot's theorem). There is neither a weakest nor a strongest definition of a finite set. For every logical formula that is a definition of a finite set, there exists a stronger and a weaker formula. There is an unbounded number of logical formulas defining finite sets, and among them an unbounded set of independent definitions.
are pairwise disjoint (that is, 
), then
;
— are finite sets, then
;
— is a finite set, then the cardinality of its power set equals
If a set A is finite, then |A| denotes the number of elements in it. The notation #A is also used, especially when A is written using curly braces. Formally, the number of elements of a finite set can be defined by induction: Definition 1. The empty set is a 0-element set. If a ∈ A and A \ {a} is an n-element set, then the set A is an (n + 1)-element set.
Definition 2. A set A is called finite if it is n-element for some n ∈ N. It is necessary to prove that the definition is correct, i.e. does not depend on the choice of a.
Statement 3. If a1,a2 ∈ A and A \ {a1} is n-element, then A \ {a2} is also n-element.
Proof. We prove the statement by induction. As the base case take n = 0. In this case A \ {a1} is empty, whence A = {a1}. Since a2 ∈ A, we obtain that a2 = a1. Hence A\{a2} = A\{a1} = ∅, that is A\{a2} is also 0-element. Suppose the statement is proved for n. Let us prove it for n + 1. The case a1 = a2 is obvious, so consider the case a1 ≠ a2. In that case a2 ∈ A \ {a1}. Since A \ {a1} is (n+ 1)-element, by the induction hypothesis we obtain that A\{a1,a2} = (A \{a1}) \{a2} is n-element. And since a1 ∈ A \{a2} and (A \{a2}) \{a1} = A \ {a1,a2}, we obtain that the set A \ {a2} is also (n + 1)-element, which was to be proved.
Corollary 4. A finite set A is n-element for exactly one n. This number n is called the number of elements in the set and is denoted |A|
Statement 5. Let A and B be finite sets. Then there exists a bijection between them if and only if |A| = |B|. Proof. We prove the statement by induction. Suppose there exists a bijection F : A → B and |A| = n. If n = 0, then A = ∅ and by bijectivity B must also be empty. Otherwise nothing would correspond to an element of B. If n > 0, then A contains some element a. By bijectivity some element b corresponds to it. Then A \ {a} is (n − 1)-element, and F|A\{a} is a bijection between A \ {a} and B \ {b}. By the induction hypothesis |B \ {b}| = n − 1 and therefore |B| = n, which was required. Conversely, let |A| = |B| = n. If n = 0, then A = B = ∅ and the unique mapping F : ∅ → ∅ is a bijection. If n > 0, then choose arbitrary a ∈ A and b ∈ B. Then |A \ {a}| = |B \ {b}| = n−1 and there exists a bijection F : A \ {a} → B \ {b}. Extending it by the value F(a) = b, we obtain a bijection between A and B
An infinite set — is a set that is not finite. Several more equivalent definitions of an infinite set can be given:
, there is a finite subset of elements.For any infinite set there exists a set of even greater cardinality — thus, there is no infinite set of greatest cardinality. The cardinalities of infinite sets are called alephs («aleph», א — the first letter of the Hebrew alphabet) and are denoted 
where the index 
runs over all ordinal numbers. The cardinalities of infinite sets form a well-ordered class — the smallest cardinality of an infinite set is 
(aleph-0, the cardinality of the set of natural numbers), followed by 
integers 
rational numbers 
real numbers 
complex numbers 
— are infinite sets.
is infinite.
Let us consider several examples of countable sets.
1. The set of all integers. Let us establish a bijection between the set of all integers and the set of all natural numbers. To do this, we arrange the elements of these sets one under the other in pairs as follows
|
0 |
-1 |
1 |
-2 |
2 |
-3 |
3 |
-4 |
4 |
. |
. |
. |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
. |
. |
. |
In this way the bijection is established, which means the equivalence of these sets is proved.
2. The set of all rational numbers. Every rational number is written uniquely in the form of an irreducible fraction: α=p/q, q>0. We call the sum
the height of the rational number α. The number of fractions with a given height is finite. For example, only the number 0/1 has height 1. Height 2 - the numbers 1/1 and -1/1. Height 3 - the numbers 2/1, 1/2, -2/1 and -1/2, and so on. We number all rational numbers in increasing order of height. In doing so every rational number receives some number, i.e. a bijection is established between all natural and all rational numbers.
Among all infinite sets there exist those that are not countable - these are uncountable sets. A bijection cannot be drawn between a countable set and an uncountable set; the latter always has “more” elements. Let us show that the set of real numbers lying between zero and one is uncountable.
Suppose the set P=[0,1] is countable, i.e. all points of this segment can be numbered consecutively: x1,x2,..., xn,... Let us divide the segment [0,1] into three equal segments. Then at least one of the segments does not contain the point x1. The point x1 may belong to either one segment or two, if it lies on their boundary. The segment A1, which does not contain the point x1, we again divide into three equal segments. At least one of them A2 does not contain the point x2. The segment A2 which does not contain x2, we again divide into three equal segments, and so on. As a result we obtain a sequence of nested segments A1,A2,..., An. Let xk - be a point that belongs to all these segments. Then, on the one hand, 
and by the countability of the points of the segment it enters the sequence x1,x2,..., xn,... On the other hand, the point xk cannot coincide with any of the points of this sequence, since the segments A1, A2… are so constructed that none of the points of the countable set x1,x2,..., xn,... belongs to them. From this it follows that the accepted assumption that the set P=[0,1] is countable is incorrect, i.e. the set is uncountable.
Uncountable sets can also be compared with one another by constructing a bijection. If a bijection can be constructed, then the equivalence of the sets is thereby proved.
Let us consider examples. The sets of points on any two segments are equivalent to one another. In Fig. 4 it is shown how a bijection can be established between two different segments ab and cd.
Fig. 4. Construction of a bijection between the elements of the sets ab and cd
The set of points in the interval 0,1 is equivalent to the set of all points on a line. A bijection can be established, for example, by means of the function
From the given examples it follows that the set of points of any segment is equivalent to the set of points of an infinite line; any segments are equivalent to one another.
It is easy to establish from the given examples that every infinite set (countable and uncountable) is equivalent to its proper subset (infinite).
For example, there turn out to be “just as many” natural numbers as all integers, as all even, odd, rational numbers, and so on. On any segment one can single out a part of it, and then construct a bijection between the segment and its part, i.e. the part turns out to be equivalent to the whole. This property is characteristic of any infinite set. The cardinality of an infinite set of points on a line is called the cardinality of the continuum.
Let M - be some set and let 2m - be the power set of M. Then 2m has a cardinality greater than the cardinality of the original set M. If we consider the power set of a countable set, then it turns out that its cardinality equals the cardinality of the continuum. For any set of the cardinality of the continuum we can consider its power set, and the cardinality of this new set will be greater than the cardinality of the continuum. Then we can again consider the power set of this new set, and again its cardinality will be greater. Thus, there is no upper bound on the cardinality of sets, just as there is no “largest” number.
Comments