Transcript Ordinal numbers

ORDINAL NUMBERS
VINAY SINGH
MARCH 20, 2012
MAT 7670
Introduction to Ordinal Numbers

Ordinal Numbers
Is an extension (domain ≥) of Natural Numbers (ℕ)
different from Integers (ℤ) and Cardinal numbers (Set
sizing)
 Like other kinds of numbers, ordinals can be added,
multiplied, and even exponentiated
 Strong applications to topology (continuous
deformations of shapes)

 Any
ordinal number can be turned into a topological space
by using the order topology

Defined as the order type of a well-ordered set.
Brief History
Discovered (by accident) in 1883 by Georg Cantor to
classify sets with certain order structures

Georg Cantor
Known as the inventor of Set Theory
 Established the importance of one-to-one
correspondence between the members of
two sets (Bijection)
 Defined infinite and well-ordered sets
 Proved that real numbers are “more
numerous” than the natural numbers
…

Well-ordered Sets


Well-ordering on a set S is a total order on S where
every non-empty subset has a least element
Well-ordering theorem
Equivalent to the axiom of choice
 States that every set can be well-ordered


Every well-ordered set is order isomorphic (has the
same order) to a unique ordinal number
Total Order vs. Partial Order

Total Order
Antisymmetry - a ≤ b and b ≤ a then a = b
 Transitivity - a ≤ b and b ≤ c then a ≤ c
 Totality - a ≤ b or b ≤ a


Partial Order
Antisymmetry
 Transitivity
 Reflexivity - a ≤ a

Ordering Examples
Hasse diagram of a Power Set
Partial Order
Total Order
Cardinals and Finite Ordinals

Cardinals
Another extension of ℕ
 One-to-One correspondence with ordinal numbers

 Both
finite and infinite
Determine size of a set
 Cardinals – How many?
 Ordinals – In what order/position?


Finite Ordinals

Finite ordinals are (equivalent to) the natural numbers
(0, 1, 2, …)
Infinite Ordinals

Infinite Ordinals
Least infinite ordinal is ω
 Identified by the cardinal number ℵ0(Aleph Null)
 (Countable vs. Uncountable)
 Uncountable many countably infinite ordinals


ω, ω + 1, ω + 2, …, ω·2, ω·2 + 1, …, ω2, …, ω3, …, ωω, …, ωωω, …, ε0, ….
Ordinal Examples
Ordinal Arithmetic

Addition

Add two ordinals




Not commutative ((1+ω = ω) ≠ ω+1)
Multiplication

Multiply two ordinals




Concatenate their order types
Disjoint sets S and T can be added by taking the order type of S∪T
Find the Cartesian Product S×T
S×T can be well-ordered by taking the variant lexicographical order
Also not commutative ((2*ω = ω) ≠ ω*2)
Exponentiation


For finite exponents, power is iterated multiplication
For infinite exponents, try not to think about it unless you’re Will
Hunting

For ωω, we can try to visualize the set of infinite sequences of ℕ
Questions
Questions?