§2   Ordinal and cardinal numbers

 

    In addition to providing a common formal basis for all branches of mathematics , the main achievement of set theory itself is the theory of ordinal numbers and cardinal numbers. Both ordinal numbers and cardinal numbers are generalizations of positive integers . Basic concepts related to sets are introduced in § 1 , but no Expose to the general definitions of finite, infinite, positive integers, etc., which will be explained in detail in this section .

 

1.   Queuing (well-ordered) set

 

    [ Relation ] Assuming that A is a set, G A A , then G is called a relation in A. If < x , y > G , then x and y are said to have the relation G.  

    [ Size relation and branch ( partial order ) set ] Assuming that G is a relation in set A , by < x , y> G and < y, z> G , there must be < x , z> G , and for any x A ,<x,x> G , then G is called a size relationship in A. Assuming < x,y> G , denoted as x < y . If there is a size relationship in A , then A is called a branch ( partial order )  ) set .

    [ Order and single-row sets ] Assume that there is a size relation ( < ) in set A that satisfies the condition :  

    (i) For any x A and y A , the following equations

                         x < y , x = y , y < x

There must be one and only one, where x=y means that x and y are the same .

    (ii) For any x A , y A and z A , if x < y and y < z both hold , then x < z holds .

    Then call this relation an order in A , and call A a single-row set in this order .

    [ Queued set ] Assuming that any non-empty subset of A has the smallest element according to an order in set A , then A is said to be queued according to this order , and A is called a queued ( well -ordered ) set . If A is in a certain order Queue , then any subset of A is also queued in this order .  

    [ Small head ] Assuming that B is a subset of the queued set A , and any element of B is smaller than any element of A \ B , then B is a small head of A ( note that A itself is also a small head of A head , because A \ A = φ , the above assumption holds naturally ). If A \ B 1 , then B is called the true small head of A.  

    [ Order-preserving transformation ] Suppose a transformation transforms a one-row set ( not necessarily a queued set ) A into a one-row set B one-to-one , and the image source is small and the image is small , then the transformation is said to preserve the order . It can be proved that , assuming that A and B are both non-empty queued sets , then one of them must be changed to a small head of the other set in order , and this transformation is unique . 

 

Second, the   ordinal number

 

    [ Ordinal ] If the set α satisfies the condition : 

           (i) each element of α is a set ;

    (ii) If x α , y x , then y α ;

           (iii) α can be used as an order ( that is, x < y is understood as x y ) to line up .

    Then the set α is called an ordinal number .

    Ordinal numbers exist , § 1 , 1 , the positive integers such as 0 and 1 , 2 , 3 , 4 , etc. described in the example of the set are all ordinal numbers , for example , 2 = { φ , { φ }} obviously has ( i ), ( ii ), ( iii ) these three conditions .

    [ Subsequent ordinal number ] Assuming that α is an ordinal number , then the smallest ordinal number greater than α is called the subsequent ordinal number of α . 

    [ Limit ordinal ] Assuming that α is an ordinal number , if α does not have the largest element , then the smallest ordinal number that is greater than all elements of α is called the limit ordinal number . 

    [ Properties of Ordinal Numbers ]

1°      For any ordinal α and β , the formula

                        α β , α = β , β α

There must be one and only one .

2°      If α , β , γ are all ordinal numbers , and α β , β γ , then α γ .

3°      If both α and β are ordinal numbers , and α β , then α is equal to a small head of β .

    The above properties show that if it is regarded as < , any ordinal α and β can be compared in size , and the small ordinal is both an element of the large ordinal and a small head of the large ordinal .

4°       φ is the smallest ordinal number .

5°    Any ordinal α has a unique successor ordinal. If the successor ordinal is recorded as α + 1 , then

α + 1= α ∪ { α }

6°    An ordinal α is the totality of all ordinal numbers smaller than α . If α has the largest element γ , then α is the successor ordinal number of γ, and γ may be recorded as α - 1. If α does not have the largest element, then α is not The successor of any ordinal, in which case α is the limiting ordinal .

7°    For any ordinal set { α _h | h H } , there is an ordinal larger than all α _h . When this ordinal set does not have the largest element, α = is the smallest ordinal larger than all α _h , α is a limiting ordinal; when the ordinal set has the largest element α _k , , and the smallest ordinal greater than all α _h is α = α _k ∪ { α _k }=( ) ∪ { α _k }.

    [ Blarley - Furty Strange ] Assuming that "the set of all ordinal numbers" is a set, then by the property 7 ° , there is an ordinal number that is greater than all ordinal numbers in this set, that is, there is an ordinal number that is greater than all ordinal numbers, this The paradoxical conclusion is called the Bradley - Furty weirdness . This is another well-known weirdness besides the Russell weirdness in the history of set theory .

    From the perspective of axiomatic set theory, this simply means that "the set of all ordinal numbers" is not a set . Therefore, to avoid involving this concept, at most only say " the set of all ordinal numbers less than a certain ordinal number α " .

 

3.   Positive integer × transfinite ordinal × transfinite induction

 

    [ Positive integer ] Assuming that n is a successor ordinal, and all ordinal numbers smaller than n are zero ( φ ) or successor ordinals, then n is a positive integer . 

    [ Finite ordinal and transfinite ordinal ] A zero or positive integer is called a finite ordinal . If an ordinal is not finite, then this ordinal is called a transfinite ordinal . 

When φ is regarded as an ordinal number, it is recorded as 0 .

    [ Infinity Axiom ] At least one set A has the following properties : ( i ) φ A ; ( ii ) x A must have x ∪ { x } A . 

    Theorem The set of all finite ordinal numbers is a set ω , and ω is the smallest transfinite ordinal number . The set of all positive integers is also a set .

    In fact , every finite ordinal must belong to the kind of set A that the axiom of infinity says . So the conclusion of the theorem is obtained from the axiom of division .

    Knowing from this theorem , the infinity axiom can be replaced by the following arguments : "The whole of all positive integers is a set" or "The whole of all finite ordinal numbers is a set . "

    [ Example of transfinite ordinals ]

                      ω , ω +1, ω + 2, ω +3, × × ×

The set of all these ordinals is obviously a set { x _n | n ω } with ω as the set of labels , where x _n = ω + n , where ω is the set of all finite ordinals . Hence there is a smallest larger than all of them Ordinal, which is a limit ordinal, denoted as ω 2 . Similarly, from the set of ordinal numbers { ω 2+ n | n ω } , a limit ordinal ω 3 greater than all ω 2+ n is obtained . Then the following ordinal numbers are obtained:

0, ω , ω 2, ω 3, × × ×

The smallest ordinal number greater than all of these ordinal numbers ω n is written as ω ² = ωω . Similarly, ω ⁿ is obtained . The smallest ordinal number greater than all of ω ⁿ ( n ω ) is written as ω ^ω .

    In the same way, from ω , ω ^ω , , , × × × we can get a smallest ordinal larger than them, denoted as e ₀ .

    You can also compare

e ₀ , e ₀ +1,

The smallest ordinal number that is larger than these ordinal numbers is denoted as e ₁ . For any positive integer n + 1 , use e _{n +1} to represent the smallest ordinal number that is greater than e _n + 1, and then take the ratio of e ₀ , e ₁ , e ₂ , · · · is the smallest ordinal number which is larger as e _ω .

    In a similar way , the ordinal number can also be obtained . Of course, the ordinal number can also be obtained , so I won't say more .

    The above is to use those ordinal numbers that use ω as the label set to get new ordinals . In fact, you can also use those ordinal numbers that use any ordinal α as the label set to get new ordinals; when α is a limit ordinal, From the ordinal family { e _β | β < α } , a smallest ordinal larger than all e _β ( β < α ) can be obtained, and this ordinal number can be recorded as e _α ; when α is the successor ordinal number, e _α Defined as the following family of ordinal numbers with ω as the set of labels

                         { }

The smallest ordinal for which each ordinal is greater .

    [ Mathematical induction ] Suppose ω is the set of all finite ordinals, A ω . If φ A and n + 1 A can be derived from n A , then A = ω .

    Practically, A is regarded as the set of all finite ordinals that make a certain argument true . If A satisfies the above assumption of mathematical induction, then A is the set of all finite ordinal numbers , so all finite ordinal numbers make that thesis true .

    Mathematical induction is only for special ordinals ω . In fact, for general ordinals (especially transfinite ordinals) α , a similar conclusion is also established, which is transfinite induction .

    [ Transfinite induction ] Assuming that α is an ordinal, A a , if φ A , and for any β α , β A can be deduced from all ordinal numbers γ A smaller than β , then A = a .

    Transfinite induction can obviously be expressed in the form of the following corollary, which is sometimes convenient to apply:

    Corollary  Assuming that α is an ordinal, φ A ì α , then there is an ordinal β that holds for all but β A .

 

4.   Choice Axiom and Queuing Theorem

 

    [ Axiom of choice and transformation of choice ] Assuming that { A _h | h H } is a family of sets, where each set A _h ≠ φ , then there is a transformation f defined in this family : for all h H , 

f ( A _h ) = x _h A _h

The transformation f is called the selection transformation .

    [ Queue Axiom ] A set must be queued in an order . 

    Note that 1 ^o  a non-empty queued set can be changed to an ordinal in order, and both the ordinal and the transformation are uniquely determined by the queued set, and the ordinal is called the ordinal of the queued set .

    2 ^o  A set A can be formed into different queuing sets in different orders, and the ordinal numbers of these different queuing sets are also different. Every even number is smaller than any odd number, and even and even or odd and odd in the original order, the resulting queued set is

{ 0 , 2 , 4 , × × × , 1 , 3 , 5 , × × × }

If you keep it in order and change it to an ordinal number, the ordinal number can only be

{ 0 , 1 , 2 , × × × , ω +1, ω +2, ω +3, × × × }

That is ω + ω = ω 2 , not the original ordinal ω .

    3 oThe queuing theorem is deduced from the ^axiom  of choice (and other axioms); conversely, the axiom of choice can be deduced from the axiom of queuing . So the queuing theorem can also be regarded as an axiom, and the axiom of choice can be regarded as a theorem .

    [ Cang En's Theorem ] Assuming that any single-row subset of a branch set A has an upper bound (that is, an element of A that is greater than or equal to each element of this single-row subset), then A must contain a maximum element (that is, no other element is larger than it) . 

    The theorem assumes that in the set theory axiom system ZFC , except for the axiom of choice, all other axioms are established, then any one of the axiom of choice, queuing theorem, and Cang En's theorem is equivalent to any other . 

 

5.   Ordinal arithmetic

 

    The arithmetic of specifying ordinal numbers by transfinite induction is as follows:

    [ Addition ] α + 0 = α , α + β =sup{ α + γ | γ < β } 

    [ Multiplication ]  α 0=0, α ( β +1)= α β + α , α β =sup{ α γ | γ < β }

    [ square power ] α ⁰ =1, α ^{β +1} = α ^β α , α ^β =sup{ α ^γ | γ < β }  

    Note that the above assumes that β is a limit ordinal and that both addition and multiplication are not commutative . For example

                  1+ ω = sup{1+ n | n < ω }= ω < ω +1

                     2 ω =sup{2 n | n < ω }= ω

But ω 2 = ω (1+1) = ω + ω > ω .

    [ Division ] Assuming that α and β are ordinal numbers, β > 0 , then there is a unique ordinal x and a unique ordinal h , h < β , so that 

                           α = β x + h

The necessary and sufficient condition for α to be a limit ordinal is: α = ω x , where x is uniquely determined by α ; and the necessary and sufficient condition for α to be a finite ordinal number is α = ω x + n , where both x and positive integer n are uniquely determined by α .

 

6.   Base

 

    [ Cardinality ] Assuming that set A can be changed to set B one-to-one , then record it as 

                      card ( A ) = card ( B )

" card ( A ) " is read as " A 's cardinality" or potential .

    For the sake of convention, card ( A ) is further defined as " the smallest ordinal number that can be changed to A one-to-one" . This definition may be used here, but it should be noted: 1 ° cardinality is not the same as the arithmetic of ordinal numbers, so despite this Definition, but generally do not use the notation of the ordinal number to represent the said cardinal number, for example, card ( ω ) is not recorded as ω or other ordinal numbers; 2 ° Although it is known from the axiom of choice that the smallest ordinal number that can be changed one-to-one on the set A exists And unique, but not all fundamental principles about cardinality are related to the axiom of choice, the following theorems are examples .  

    Assuming that set A can be transformed into set B one-to-one , then record as

                     card ( A ) ≤ card ( B )

In particular, when card ( A ) ≤ card ( B ) and card ( A ) ≠ card ( B ) , write

                         card ( A ) < card ( B )

    The above stipulates how to compare the size of the bases, but this is only superficial, and it is only after the establishment of the following theorem that it can be shown that this regulation is reasonable .

    [ Cantor - Bernstein theorem ] Suppose card ( A ) ≤ card ( B ) , card ( B ) ≤ card ( A ) 

then

card ( A ) = card ( B )

    inference

1°      For any set A and set B , the following formula

                   card ( A ) < card ( B ), card ( A ) = card ( B )

                          card ( B ) < card ( A )

There must be one and only one .

2°      Assume card ( A ) < card ( B ), card ( B ) < card ( C ), then

                         card ( A ) < card ( C )

    [ Cantor's Theorem ] Assuming that A is not an empty set, then 

                            card ( A ) < card ( )

    [ Finite cardinality and finite set ] A cardinality of a finite ordinal is called a finite cardinality . If card ( A ) is a finite cardinality, then A is called a finite set . 

    The theorem assumes that h and k are finite ordinal numbers, h < k , then 

                        card ( h ) < card ( k )

    It can be seen from this theorem that the whole of all finite cardinal numbers can be changed to the whole of all finite ordinal numbers ω in order . For this reason, assuming that n is a finite ordinal number, then n can be used to represent card ( n ), which is written as

                        card ( n ) = n

In this way, positive integers and zero are not only finite ordinal numbers, but also finite cardinal numbers, and as cardinal numbers, the magnitude relationship between them is still maintained .

    [ Exceeded cardinal number ] Any cardinal number is always the cardinal number of a certain ordinal number. The cardinal number of a finite ordinal number is a finite cardinal number, and the cardinal number of an ultra-limited ordinal number must not be a finite cardinal number, which is called an ultra-limited cardinal number . 

    A large cardinality must be the cardinality of a large ordinal number . Therefore, the totality of the overlimit cardinality is a queuing set . Therefore, all overlimit cardinalities smaller than a certain overlimit cardinality can be queued with ordinal numbers as subscripts from small to large:

                      

where is the smallest transfinite cardinality card ( ω ) . " " is pronounced "Aleph" .

    It is known from the above description that any base can be represented , where α is an ordinal number, and is the smallest base larger than all ( β < α ) . Conversely, for any ordinal α , such a number exists . Because it is assumed that there is , then it must exist, because there is always a cardinality ratio greater than that, so the property of the queue set knows that there is a minimum cardinality ratio greater than that, and then it is known by mathematical induction that for any positive integer n , there is .

    It can be proved by transfinite induction for the general ordinal α , since it is assumed that for every ordinal δ smaller than the ordinal β , there exists, then there exists an ordinal γδ such that card ( γδ) = _an ordinal _larger than all of these γδ _exists , take any one and denote it as γ , then card( )>card( γ ) ≥ card( γ _δ )= . So there is a cardinality that is larger than all of them . Therefore, it is known from the property of queuing set that there is a minimum cardinal number that is larger than all of them. The cardinality of , the smallest cardinality is . Therefore, it is known by transfinite induction that for any ordinal α , there exists .

    [ Countable sets and uncountable sets ] is called the cardinality of countable infinite sets, because = card ( ω ), any set of cardinal numbers can be changed to ω one-to-one (that is, zero and all positive integers) . Both finite sets and countably infinite sets are called countable sets . 

    By Cantor's theorem (the cardinality of the set of the entirety of all subsets of a non-empty set), the set whose cardinality is equal to is uncountable . It is exactly the cardinality of the entirety (continuous field) of all real numbers, because the entirety of real numbers is binary The whole number of decimals . But what exactly is an overrun base? Cantor guess is the smallest uncountable cardinality, which is famous below

    [ Continuous Domain Assumption ] 

    The [ generalized continuous field hypothesis ] holds for any ordinal α . 

    Continuous domain assumption right? This question has been unanswered for a long time, and an unexpected result was discovered in the late 1930s: if the axiom system of set theory itself is not contradictory, then the continuous field hypothesis and this axiom system are not contradictory . Later, the continuous field hypothesis was further proved. Negation (not) (is ) is also not inconsistent with this axiom system . That is to say, the continuous field hypothesis is not solvable (from the existing axiom system) . Due to the importance of real numbers in mathematics, this problem is unsolvable It shows that the axioms of set theory are not complete .

 

7.   Radix Arithmetic

 

    [ Formula ] Assuming that A and B are sets, A ∩ B ≠ φ , then specify 

card ( A )+ card ( B )= card( Α ∪ B )

card ( A ) card ( B ) = card ( A B )

card ( B ) ^{card( Α )} = card ( ^A B )

    Both base addition and multiplication are commutative .

    theorem

                          

    inference

1°      ( n is a positive integer)      

2°     

3°     

    [ Cardinality calculation of several special number sets * ]

1°     The base of all integers is equal . This is because

card (all integers) = card (all positive integers)

+ card (all negative integers) + card ( { 0 } )

                      =

2°      The base of all rational numbers is equal to . Because each rational number is the quotient of a pair of integers, the base of all rational numbers does not exceed the base of all integers, so the base of all rational numbers does not exceed . But integers can be regarded as rational numbers A special case of , this base is not less than . So the base of all rational numbers is equal to .

 * The numbers in the set of numbers in this paragraph are defined in the usual sense, see Chapter 1, § 1 , 1 .

3°      The base of all irrational numbers is equal . Otherwise, the base of all real numbers will not be equal .

4°      The cardinality of all real algebraic numbers (roots of integer-coefficient algebraic equations) is equal . This is because there are only an infinite number of different integer-coefficient algebraic equations, and each equation has only a finite number of roots .

5°      The base of all real transcendental numbers (real numbers that are not algebraic numbers) is equal to .

6°      The base of all complex numbers is equal . This is because a complex number is a pair of real numbers .

    [ Cantor 's triplet ] Represent all real numbers in the closed interval [0 , 1] as ternary infinite decimals * . All those ternary infinite decimals whose digits are not 1 are denoted as T , then T is called Cantor 's triplet . From a geometrical point of view, divide T ₀ = [0 , 1] into three equal parts, remove the middle part, and denote the remaining part [0 , ] ∪ [ , 1] as T ₁ . Also denote [0 , ] and [ , 1] Each is divided into three sections, the middle section is removed, and the remaining section is recorded as T ₂ . Continue to get a set family { T _n | n ω }, the general set of this family is.

    Divide each number in T by 2 , and you get the totality of binary infinite decimals, so card ( T ) = .