applet-magic.com Thayer Watkins Silicon Valley & Tornado Alley USA |
---|
and Their Arithmetic |
There are two related but distinct concepts of enumeration, cardinal and ordinal. A cardinal number is one of the families consisting of all sets that can be put into one-to-one correspondence with each other. Thus 2 is the family of all sets that can be put into one-to-one correspondence with {1, 2}. In a sense, 2 represents the property of two-ness. While cardinality involves only sets, ordinality involves sets and order relations on those sets. An order relation is like that of "≤" although it doesn't have to be numerical inequality. For example, the ordering can the the lexicographic (alphabetical) ordering of words; "adz" comes before "bowl" in the dictionary.
Order relations may be reflexive as is ≤ or nonreflexive as is <. For simplicity "≤" will be used for any reflexive order relation.
A set is totally ordered if for any two elements a and b from A either a≤b, b≤a, or both, which means a=b.
A set is well ordered if all of its nonempty subsets have first elements under the order relation. That is to say, if S is a subset of A then there exists an element of S, say x, such that for any element y in S, x≤y. (Here it is important that the relation is reflexive; i.e., x≤x.)
An ordinal number is a family of well-ordered sets that can be put into one-to-one correspondences that preserve the order relations; i.e., if f:A→B and a_{1} ≤_{A} a_{2} for a_{1},a_{2} ∈ A then b_{1}=f(a_{1}) ≤_{B} b_{2}=f(a_{2}). Thus if a is the first element of A_{1} ⊂ A then f(a) is the first element of the set f(A_{1}).
The collection of well-ordered sets is partitioned into equivalence classes. Each equivalence class contains all the well-ordered sets that are similar to each other. The equivalence classes may be thought of as having labels or indices.
In a well-order set A, the initial segment s(x) of an element x belonging to A is the set of all elements which precede x in A under the order relation; i.e., )
Theorem 1: Let S(A) be the family of all initial segments of A. S(A) is ordered by set inclusion. The function f that maps an element x to its initial segment is one-to-one and onto; i.e., f:A→S(A). Furthermore f preserves order so A is similar to S(A).
Theorem 2: Suppose A is a well-ordered set and B is a subset of A such that there exists a similarity mapping f of A into B. Then for every element x of A, x≤f(x).
Proof: Let D={x|f(x)≤x}. If D=φ, the empty set, then the theorem is true.
Suppose D is not empty. Then, since A is a well-ordered set, D has a first element d. Since d ∈ D, f(d)≤d. But, since f is a similarity mapping which preserves order f(f(d))≤f(d) and hence f(d) ∈ D. But f(d)≤d so there is a contradiction with the assumption that d is the first element of D. Therefore D must be empty.
The next theorem is a very useful one.
Theorem 3: A well-ordered set cannot be similar to one of its initial segments.
Proof: Let A be a well-ordered set and f a similarity mapping of A onto the initial segment s(x) for some x ∈ A. By definition all elements of s(x) are less than x. Therefore f(x)≤x. But this contradict Theorem 2. Therefore a well-ordered set cannot be similar to one of its initial segments.
Theorem 4: If A and B are well-ordered sets then either A and B are similar or one is similar to an intial segment of the other.
Proof: Consider the elements of each set whose initial sets are similar to the initial sets of elements in the other set; i.e., let
For example, suppose A = {1,2,3,4} and B = {a,b,c,d,e}. Then S = {1,2,3,4} and T = {a,b,c,d}.
Continuation with the proof of Theorem 4. Claim: S is similar to T.
Proof of Claim: Consider an element of x. By definition there is an element y ∈ B such that s(x) is similar it s(y). This y is unique because otherwise there would be two initial segments of B, say s(y_{1}) and s(y_{2}) which were both similar to s(x) and hence similar to each other. But this implies that s(y_{1})=s(y_{2}) and hence y_{1}=y_{2}. Likewise x the element of A such that s(x) is similar to y ∈ B is unique. This correspondence defines a one-to- one relationship between the elements of S and T. Thus S and T are similar.
There are three possibilities:
The fourth possibility of S=s(a) for some a ∈ A and T=s(b) for some b ∈ B cannot occur. This would imply that a ∈ S, since its initial segment is similar to the initial segment of an element (E S) of B, but since S=s(a) this would have a belonging to its own initial segment. Thus there would be a contradiction.
Definition: The order type of a well-ordered set is the family of well-ordered sets it is similar to. In other words, the order type of a well-ordered set A, denoted ord(A), is the equivalence class A belongs to. If ord(A)=λ then A ∈λ.
There is a particular sequence of ordered sets that are appropriate to use to represent order types. For finite sets the following are "standard" order types:
where φ is used to denote the empty set.
Because this gets tedious to write the following labels are adopted:
Thus
The order type of the natural numbers, {0, 1, 2, 3, … } is denoted as omega, ω.
The ordering of ordinal numbers is achieved through the following construction. If λ and μ are ordinal numbers and A and B are well-ordered sets such that ord(A)=λ and ord(B)=μ then:
λ < μ if A is similar to an initial segment of B
λ = μ if A is similar to B
λ > μ if B is similar to an initial segment of A
λ ≤ μ if λ ≤ μ
or λ = μ
λ ≥ μ if λ > μ
or λ = μ.
Theorem 5: Any set of ordinals is well-ordered by ≤.
Theorem 6: Let s(λ ) be the set of all ordinals less than λ . Then ord(s(λ ))=λ .
Theorem 7: Every ordinal has an immediate successor.
Definition of a limit element: An element of a well-ordered set is a limit element if it does not have an immediate predecessor and it is not the first element. A limit number is an ordinal which is a limit element of the ordinals.
Theorem 8: For any infinite ordinal λ there exists ordinal numbers μ and n such that μ is a limit number and n is a finite ordinal.
Definition of concatenation of well-ordered sets: Let A and B be
well-ordered sets. Then (A ; B) is the union of A and B ordered
by the relation R where any two elements x and y are ordered
according their relation in A or B if they both belong to A or
both belong to B and x
For this definition to be proper it must be established that λ+μ is independent of the representative A and B used in the construction.
Addition is not necessarily commutative; λ+μ is not necessarily the same as μ+λ . For example, 1+ω is not the same as ω+1; i.e., ω+1 = ord({0,1,2,...; 0}) but 1+ω is ord({0,0,1,2,3,...})=ω.
Addition is associative; (λ +μ)+ ν = λ +(μ + ν). There also exists an additive identity; i.e., the empty set φ.
Theorem 9: The immediate successor of any ordinal λ is λ +1.
Let A and B be well-ordered sets. Then (A X B) is the cartesian product of A and B, order pairs (a,b) where a ∈ A and b ∈ B, ordered by the relation R where any two elements (x,y) and (z,w) are ordered according to
This is called a reverse lexicographic ordering.
Definition of multiplication of ordinals:
Definition of multiplication of ordinals: For any two ordinals λ and μ let A and B be well-ordered sets such that ord(A)=λ and ord(B)=μ . Then
Again, for this definition to be proper it must be established that λ*μ is independent of the representative A and B used in the construction.
Multiplication is not commutative. For example, 2*ω is not the same as ω*2; i.e., 2=ord({a,b}) and ω=ord({1,2,..}) so
However, multiplication is associative.
In the folowing let card(A) stand for the cardinality of a set A.
Theorem 10: Let A and B be well ordered sets. Then card(A)≤card(B) implies that ord(A)≤ord(B), and ord(A)≤ord(B) implies that card(A)≤card(B).
The order of the ordinals is 0,1,2,3,..., then ω,ω+1,ω+2,... then ω^{2},ω^{2}+1, ω^{2}+2,... to ω^{3} and so on to ω^{ω}.
From there the sequence goes on to ω to the power of ω^{ω}.
Next comes (ω to the power of ω^{ω}) to the power of ω
and on to (ω to the power of ω to the power of ω … .
But there is always a successor to any ordinal.
Definition of functions from one well-ordered set to another: Let A and B be well-ordered sets. Then A^{B} is the set of all functions from A to B.
The Burali-Forti Paradox: The concept of the set of all ordinal numbers is contradictory.
Proof not given.
Modeling ordinal arithmetic in the programming language LISP is convenient because a list is exactly a well-ordered set. For any list one can construct the corresponding ordinal by creating a list that begins with "0" and ends with a cardinal that is one less than the length of the list. The middle of the ordinal list is just the ellipsis "…". Infinite ordinals are ones in which the … has no successor (other than the delimiters ";" and ")".
HOME PAGE OF Thayer Watkins |