Lecture
Cardinality of a set, the cardinal number of a set (Lat. cardinalis ← cardo «the main circumstance; the basis; the heart») — a characteristic of sets (including infinite ones) that generalizes the notion of the quantity (number) of elements of a finite set.
This concept is based on natural ideas about comparing sets:
Before the theory of set cardinality was built, sets were distinguished by the features: empty/nonempty and finite/infinite; finite sets were also distinguished by the number of elements. Infinite sets, however, could not be compared.
The cardinality of sets makes it possible to compare infinite sets. For example, countable sets are the «smallest» infinite sets.
The cardinality of a set 
is denoted by 
. Sometimes the notations 
, 
, and 
are encountered.
flowchart of the algorithm for determining the cardinality of a set
A cardinal number or, briefly, a cardinal in set theory is an object that characterizes the cardinality of a set. The cardinal number of some set A is denoted as |A|, or Card A.
For a finite set A, the cardinal number |A| is a natural number, which denotes the number of elements of this set. For infinite sets, the cardinal number is a generalization of the notion of the number of elements.
Although the cardinal numbers of infinite sets have no reflection in the natural numbers, they can nevertheless be compared. Let A and B — be infinite sets; then the following four cases are logically possible:
However, deeper investigations in set theory showed that, relying on the axiom of choice, one can prove the impossibility of the existence of the fourth case.
Thus, the cardinalities of any two sets A and B are always comparable with each other. That is, for the cardinal numbers |A| and |B| of arbitrary sets A and B, one of three relations holds: |A|=|B|, |A|≤|B| or |B|≤|A|. If |A|≤|B|, but the set A is not equinumerous to the set B, then |A|<|B|.
Assuming the axiom of choice to be true, the cardinality of a set is formally defined as the smallest ordinal number 
for which a bijective correspondence can be established between 
and . This definition is also called the von Neumann assignment of cardinals.
If one does not accept the axiom of choice, then a different approach is required. The very first definition of the cardinality of a set (it is implicitly present in the works of Cantor and explicitly formulated by Frege, as well as in Principia Mathematica) is the class 
of all sets equinumerous to . In axiomatic systems based on ZFC theory, such a definition is inapplicable, since for nonempty such a collection is too large to fit the definition of a set. More precisely, if 
, then there exists an injective mapping of the universal set into , under which each set 
maps to 
, whence, by the axiom of limitation of size, it follows that — is a proper class. This definition can be used in type theory and in «New Foundations»[en], as well as in related axiomatic systems. In the case of ZFC, the definition can be used if one restricts the collection to equinumerous sets of the smallest rank (this device, proposed by Dana Scott, works because the collection of objects possessing a given rank is a set).
A formal order among cardinal numbers is introduced as follows: 
means that the set can be injectively mapped into 
. By the Cantor–Bernstein theorem, from the pair of inequalities and 
it follows that 
. The axiom of choice is equivalent to the statement that for any sets and , at least one of the inequalities or holds.
A set is called Dedekind-infinite[en] if it has a proper subset such that . Otherwise the set is called Dedekind-finite. Finite cardinal numbers coincide with the ordinary natural numbers — in other words, a set is finite if and only if 
for some natural 
. All other sets are infinite. Under the axiom of choice, one can prove that the Dedekind definitions coincide with the standard ones. Moreover, one can prove that the cardinality of the set of natural numbers 
(aleph-null, or aleph-0 — the name is formed from the first letter of the Hebrew alphabet 
) is the smallest infinitely large cardinal number, that is, any infinite set has a subset of cardinality . The next cardinal number in order is denoted 
, and so on; the number of alephs is infinite. To every ordinal number there corresponds a cardinal number 
, and in this way any infinitely large cardinal number can be described.
is denoted by the symbol («aleph-null»). A set is called infinite if its cardinality 
(is not less than the cardinality of the set of natural numbers); thus, countable sets — are the «smallest» of the infinite sets. The following cardinal numbers in increasing order are denoted 
(where the index runs over all ordinal numbers). Among the cardinal numbers there is no greatest: for any set of cardinal numbers there exists a cardinal number greater than all the elements of this set.
. The assumption that 
is called the continuum hypothesis. and 
only one of three is possible:
, or and are equinumerous;
, or is more powerful than , that is, contains a subset equinumerous to , but and are not equinumerous;
, or is more powerful than — in this case contains a subset equinumerous to , but and are not equinumerous. and are not equinumerous and neither of them has a part equinumerous to the other is impossible. This follows from Zermelo's theorem. Otherwise it would mean the existence of cardinalities incomparable with each other (which is in principle possible if one does not accept the axiom of choice). and is impossible by the Cantor–Bernstein theorem. and are called equivalent if there exists a one-to-one mapping of the set onto the set . 
for some nonnegative integer . The number expresses the number of elements of the finite set. When 
, the set contains no elements (the empty set). If 
, then there exists no injective mapping from 
into 
(the Dirichlet principle), and hence there exists no bijection between them either. Therefore the sets and have different cardinality.
. Countable sets are:
for any natural 
. The correspondence: 
.
. The correspondence: 
.
. The correspondence is obtained by matching the terms of the series 
to its partial sums (the terms of the series are taken without regard to sign).
.
is injectively mapped into the set 
(to an irreducible fraction of the form 
there corresponds a pair of numbers 
). Therefore the set of rational numbers is at most countable. But since it contains the set of natural numbers, it is also at least countable. By the Cantor–Bernstein theorem it is countable. are called uncountable. By Cantor's theorem, the set of infinite sequences composed of the digits 0 and 1 is uncountable. The cardinality of this set is called the continuum.
equals the continuum.
. is equinumerous to the set of all its finite subsets. 
.
The ordinary arithmetic operations on numbers of the natural series can be generalized to the case of cardinal numbers. It can also be shown that in the case of finite cardinal numbers these operations coincide with the corresponding arithmetic operations on numbers. In addition, operations on cardinal numbers preserve many of the properties of ordinary arithmetic operations.
Under the axiom of choice, for each cardinal number 
one can define the number 
following it, and there are no other cardinal numbers between and 
. If is finite, then the next cardinal number coincides with 
. In the case of infinite , the next cardinal number differs from the next ordinal number.
If the sets and have no common elements, then the sum of the cardinalities is defined as the cardinality of their union. When there are common elements, the original sets can be replaced by disjoint sets of the same cardinality — for example, replace by 
, and by 
.
Neutrality of zero with respect to addition:
Associativity:
Commutativity:
Monotonicity (non-decrease) of addition in both arguments:
The sum of two infinite cardinal numbers can be easily computed under the axiom of choice. If one of the numbers or 
is infinite, then
Under the axiom of choice, for any infinite cardinal number 
and an arbitrary cardinal number , the existence of a for which 
is equivalent to the inequality 
. Such a is unique (and coincides with ) if and only if 
.
The product of two cardinal numbers is expressed through the Cartesian product of sets: 
Properties of zero:
Neutrality of one with respect to multiplication:
Associativity:
Commutativity:
Monotonicity (non-decrease) of multiplication in both arguments:
Distributivity of multiplication with respect to addition:
By analogy with addition, the product of two infinite cardinal numbers can be easily computed under the axiom of choice. If the numbers and are different from zero and at least one of them is infinite, then
Under the axiom of choice, for any pair of cardinal numbers 
and , where is infinite and is not equal to zero, the existence of a for which 
is equivalent to the inequality 
. Such a is unique (and coincides with ) if and only if 
.
Exponentiation is defined as follows:
,
where 
denotes the set of all functions from into .
(in particular, 
), see the Empty function
Monotonicity:
Note that 
is the cardinality of the power set and, consequently, 
for any set (see Cantor's diagonal argument). From this it follows that among the cardinal numbers there is no greatest (since for any cardinal number one can indicate a greater number 
). In fact, the class of all cardinal numbers is proper (although in some axiomatizations of set theory this cannot be proved — among such, for example, is the «New Foundations»[en] system).
All the subsequent statements given in this section rely on the axiom of choice.
If and — are finite numbers greater than 1, and 
— is an infinite cardinal number, then 
If the cardinal number is infinite, and is finite and different from zero, then 
.
If 
and 
, with at least one of them infinite, then
.
Using König's theorem, one can prove that for any infinite cardinal number the inequalities hold:
,
where 
denotes the cofinality of .
Provided the axiom of choice holds, for any infinite cardinal and finite cardinal 
there exists a cardinal number for which 
, and moreover 
.
Under the axiom of choice, a cardinal number 
satisfying the condition 
, for a given infinite and finite 
, does not always exist. But if such a does exist, then it is infinite and less than , and any finite cardinal number 
will also satisfy the equality 
.
The logarithm of an infinite cardinal number is the smallest cardinal number satisfying the condition 
. Despite the fact that the logarithms of infinitely large cardinal numbers lack some of the properties characteristic of the logarithms of positive real numbers, they turn out to be useful in some areas of mathematics — in particular, in the study of cardinal invariants of topological spaces.
According to the statement of the continuum hypothesis, between and 
there exist no other cardinal numbers. The cardinal number is also denoted and is the cardinality of the continuum (that is, of the set of real numbers). In this case 
. The generalized continuum hypothesis denies the existence of cardinal numbers lying strictly between 
and , for any infinite set . The continuum hypothesis is independent of the standard axiomatization of set theory, that is, of the Zermelo–Fraenkel system of axioms combined with the axiom of choice (see Zermelo–Fraenkel set theory).
TRANSFINITE NUMBER
Comments