Scribd
Upload
54 views2 pages

Ordinal Arithmetic and Infinite Numbers

The document discusses ordinal arithmetic, which extends arithmetic to infinite numbers as developed by Cantor. It covers definitions of ordinals, their addition, ordering, multiplication, exponentiation, prime ordinals, and the significance of the ordinal ε₀. The document highlights the unique properties of ordinal operations, including non-commutativity and the existence of limits and continuity in certain operations.

Uploaded by

유인웅
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
54 views2 pages

Ordinal Arithmetic and Infinite Numbers

The document discusses ordinal arithmetic, which extends arithmetic to infinite numbers as developed by Cantor. It covers definitions of ordinals, their addition, ordering, multiplication, exponentiation, prime ordinals, and the significance of the ordinal ε₀. The document highlights the unique properties of ordinal operations, including non-commutativity and the existence of limits and continuity in certain operations.

Uploaded by

유인웅
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Ordinal arithmetic

Berkeley Math Circle


2018-3-5

Problem: How can we extend arithmetic to infinite numbers in an interesting


way? The answer was found by Cantor: use ordinal arithmetic.

1 Definition of ordinals
Countable ordinals can be represented as subsets of the real line so that one can
only make a finite number of leftward jumps in the subset. We only care about
the order of points in the ordinal, so two subsets ordered in the ”same way”
count as the same ordinal. For example, {0, 1, 2} and {−37, 3, π} count as the
same ordinal. Equivalently any nonempty subset of the ordinal has a smallest
element.
Examples: 0, 1, 2, ... are subsets with 0, 1, 2, ... points. ω is the smallest
infinite ordinal and can be represented as a subset 0,1/2, 2/3, 3/4,... with an
infinite number of points.

2 Addition of ordinals
α + β is given by putting β to the right of α. So ω + 1 might be represented
by 0, 1/2, 2/3, 3/4, ...., 1. Note that 1 + ω = ω 6= ω + 1 (Hilbert’s hotel). In
particular addition is not commutative, but is associative.
In general about half of the usual rules of arithmetic hold for ordinals.

3 Ordering of ordinals
We can compare α with β by matching their first elements, then their second
elements, and so on. We find that either α < β (if α runs out first) or α = β
or α > β (if β runs out first). Most of the usual rules hold for < (but note that
1 + ω = ω).
Limits. An increasing sequence of ordinals may get ”closer and closer” to α:
we say the sequence has limit α. For example 0, 1, 2, ... has limit ω. Continuity
of functions can be defined as for real functions. Note that α + β is continuous
in β but not in α: look at n + 1.
Subtraction. If α ≥ β we can define α − β. so that β + (α − β) = α.

1
4 Multiplication of ordinals
The product αβ means ”take β copies of α”. It can also be defined by α.0 = 0,
α.(β +1) = α, β +α, αβ is continuous in β. (But αβ is not continuous in α: look
at (limn→ω n)ω = ωω 6= ω = limn→ω (nω).) Multiplication is associative but not
commutative (2ω 6= ω.2). Example: ωω is the ”lexicographic” order of points
in a quadrant. Multiplication is sort of half distributive: α(β + γ) = αβ + αγ,
but (ω + 1)2 6= ω2 + 1.2.
Division-with-remainder: if β > 0 and α is an ordinal then α = βq + r for
unique q, r with r < b.
Ordinals up to ω ω are polynomials in ω with coefficients 0, 1, 2, ....

5 Exponentiation
Exponentiation can be defined by: αβ continuous in β, αβ+1 = αβ .α, α0 = 1.
αβ can be represented by functions from a finite subset of β to α, which can be
thought of as words of length β to an alphabet α with most letters of the words
missing 0, or as polynomials in α with coefficients < α and exponents in β. It
is continuous in β but not continuous in α: nω = ω. αβ+γ = αβ αγ .
Ordinals have a base α expansion (if α > 1). Cantor normal form is base ω
expansion. Example: (ω 3 .2 + 2)(ω + 5) = ω 4 + ω 3 .15 + ω + [Link] e

6 Prime ordinals
The prime ordinals are 2, 3, 5, ..., ω, ω + 1. ω + 2 = (ω + 1)2. ω 2 + 1, ω 3 + 1,...ω ω ,
α
ω ω + 1, ...In general the primes are finite primes, ω ω and ω α + 1.
Factorization in to primes need not be unique. 2 × 3 = 3 × 2, 2 × ω = ω,
ω × ω ω = ω ω . Unique if (1) limits come first (2) limits in decreasing order (3)
successors in decreasing order.

7 The ordinal 0
Problem with cantor normal form: ω α is usually far bigger than α, but some
ω
ordinals may satisfy α = ω α 0 is the limit of ω, ω ω , ω ω ,.... and is the smallest
ordinal that cannot be written using ω and 0 and addition and multiplication
and exponentiation. Ordinals up to 0 can be represented as rooted trees.
α is the α’th ordinal with α = ω α . More generally we get the Veblen
hierarchy: φ0 (α) = ω α . ψβ (α) enumerates fixed points of φγ for γβ . So α =
φ1 (α. Γ0 is the smallest ordinal that cannot be written even using φ. There are
also even bigger ordinals Γα .
Some even bigger ordinals: the Church-Kleene ordinal is the smallest that
cannot be described in a computable (recursive) way. Far beyond this is the
first uncountable ordinal ℵ1 .

Common questions

Powered by AI

The non-commutativity of ordinal arithmetic affects subtraction and division as these operations cannot be universally defined. Subtraction is defined for ordinals α ≥ β by ensuring β + (α − β) = α, while division-with-remainder for ordinals holds that α = βq + r with r < β, reflecting careful order considerations not present in standard arithmetic .

Prime ordinals include not only finite primes but also larger ordinals like ω, ω + 1, and ω2. This extension implies that factorization into primes is not always unique, as demonstrated by ω × ωω = ωω. For ordinals, unique factorization occurs only under specific conditions regarding the order of limits and successors .

The addition of ordinals involves putting the second ordinal to the right of the first. Unlike standard addition, it is not commutative; for example, ω + 1 is different from 1 + ω, illustrating that the order of addition matters. However, it is associative .

Countable ordinals are defined as subsets of the real line where one can only make a finite number of leftward jumps. They are represented by subsets where two subsets ordered in the 'same way' count as the same ordinal. For example, {0, 1, 2} and {-37, 3, π} are the same ordinal .

Multiplication of ordinals is similar to standard multiplication in that it is associative, but it differs in not being commutative, as demonstrated by the fact that 2ω ≠ ω2. Additionally, ordinal multiplication is 'half-distributive', meaning α(β + γ) = αβ + αγ, but this property does not always hold, as shown by (ω + 1)2 ≠ ω2 + 1.2 .

Ordinal exponentiation is defined such that α raised to the power β is continuous in β. It follows different rules than traditional exponentiation, where αβ+1 = αβ.α and α0 = 1. The process can be represented as functions from a finite subset of β to α, interpreted as words or polynomials. Unlike traditional exponentiation, it is continuous in β but not in α .

The limit of an increasing sequence of ordinals is the smallest ordinal that the sequence approaches. This is similar to limits in real analysis, but for ordinals, the sequence is a well-ordered set. For example, the sequence 0, 1, 2,... has a limit of ω, indicating the first infinite ordinal. The concept of limits is used to define continuity for functions of ordinals, where α + β is continuous in β but not in α .

ε0 represents the limit of sequences like ω, ωω, ωωω,..., and it is the smallest ordinal that cannot be expressed simply using the operations of addition, multiplication, and exponentiation with natural numbers. Within the Veblen hierarchy, εα = φ1(α) indicates ordinals that equate to their power tower form, signifying important fixed points where α = ωα. The Veblen hierarchy is an extension that organizes such ordinal phenomena beyond ε0 .

Cantor normal form expresses ordinals as a sum of decreasing powers of ω with natural coefficients, aiding in their classification and comparison. However, it faces limitations because some ordinals, like ε0, cannot be fully described using just ω and standard operations, indicating a need for more complex means such as the Veblen hierarchy .

You might also like