transfinite 0.1.1

Transfinite ordinal arithmetic library supporting ordinals up to epsilon-zero (ε₀) using Cantor Normal Form
Documentation

Transfinite Ordinal Arithmetic

A Rust library for performing arithmetic operations on transfinite ordinal numbers up to ε₀ (epsilon-zero), using Cantor Normal Form representation.

Crates.io Documentation

What Are Ordinal Numbers?

Ordinal numbers extend the natural numbers to describe the order type of well-ordered sets. While natural numbers (0, 1, 2, ...) work well for finite sequences, ordinals continue into the infinite:

  • ω (omega) represents the order type of all natural numbers
  • ω + 1 comes after all natural numbers, then one more
  • ω · 2 represents two copies of the natural numbers placed end-to-end
  • ω², ω^ω, and beyond represent increasingly large infinite ordinals

Unlike cardinal numbers (which measure "how many"), ordinals measure "what position" and preserve order information. Ordinal arithmetic has unique properties:

⚠️ Addition and multiplication are NOT commutative:

  • 1 + ω = ω (add one natural number to infinity, still get infinity)
  • ω + 1 > ω (but infinity plus one is a distinct ordinal!)
  • 2 · ω = ω (two copies of infinity, each infinite, is still infinity)
  • ω · 2 = ω + ω (infinity doubled is larger than infinity)

This library implements ordinals up to ε₀ (epsilon-zero), the first ordinal that satisfies ωε₀ = ε₀, which is the limit of the finite tower: ω, ωω, ω(ωω), ...

Features

  • ✓ Ordinal arithmetic: addition, multiplication, exponentiation
  • ✓ Cantor Normal Form representation for efficient computation
  • ✓ Type-safe construction with validation
  • ✓ Comparison and ordering of ordinals
  • ✓ Zero dependencies (except for traits and error handling)
  • ✓ Comprehensive test suite with mathematical examples

Quick Start

Add this to your Cargo.toml:

[dependencies]
ordinal = "0.1.0"

Basic Example

use ordinal::Ordinal;
use num_traits::Pow;

// Create finite ordinals
let zero = Ordinal::zero();
let five = Ordinal::new_finite(5);

// Create the first infinite ordinal
let omega = Ordinal::omega();

// Ordinal arithmetic
let omega_plus_five = omega.clone() + five.clone();
let omega_times_two = omega.clone() * Ordinal::new_finite(2);
let omega_squared = omega.clone().pow(Ordinal::new_finite(2));

println!("ω + 5 = {}", omega_plus_five);     // Prints: ω + 5
println!("ω · 2 = {}", omega_times_two);     // Prints: ω * 2
println!("ω² = {}", omega_squared);          // Prints: ω^2

Non-Commutativity Example

use ordinal::Ordinal;

let one = Ordinal::one();
let omega = Ordinal::omega();

// Addition is NOT commutative
let one_plus_omega = one.clone() + omega.clone();
let omega_plus_one = omega.clone() + one.clone();

assert_eq!(one_plus_omega, omega);  // 1 + ω = ω
assert_ne!(omega_plus_one, omega);  // ω + 1 ≠ ω

println!("1 + ω = {}", one_plus_omega);   // Prints: ω
println!("ω + 1 = {}", omega_plus_one);   // Prints: ω + 1

Key Concepts

Cantor Normal Form (CNF)

Every ordinal α < ε₀ can be uniquely written as:

α = ω^β₁·c₁ + ω^β₂·c₂ + ... + ω^βₙ·cₙ

where:

  • β₁ > β₂ > ... > βₙ (exponents in strictly decreasing order)
  • c₁, c₂, ..., cₙ are positive finite coefficients
  • This is called the Cantor Normal Form

For example:

  • ω² + ω·3 + 7 is in CNF
  • 42 = ω⁰·42 is in CNF (finite ordinals are CNF with exponent 0)
  • ω^ω + ω² + 1 is in CNF

This library represents transfinite ordinals internally using CNF, enabling efficient arithmetic operations.

Limit vs Successor Ordinals

  • Limit ordinal: No immediate predecessor (e.g., ω, ω·2, ω²)
    • Informally: "comes from below" via an infinite sequence
  • Successor ordinal: Has an immediate predecessor α+1 (e.g., 1, 5, ω+1)
    • Informally: "one step after" another ordinal
use ordinal::Ordinal;

let omega = Ordinal::omega();
assert!(omega.is_limit());          // ω is a limit
assert!(!omega.is_successor());

let omega_plus_one = omega.successor();
assert!(!omega_plus_one.is_limit());     // ω+1 is a successor
assert!(omega_plus_one.is_successor());

This distinction matters for multiplication and exponentiation algorithms.

Ordinal Arithmetic Rules

Operation Property Example
Addition Not commutative 1 + ω = ω but ω + 1 ≠ ω
Addition Associative (α + β) + γ = α + (β + γ)
Multiplication Not commutative 2 · ω = ω but ω · 2 = ω + ω
Multiplication Associative (α · β) · γ = α · (β · γ)
Exponentiation Not commutative 2^ω = ω but ω^2 = ω · ω

Examples

Building Complex Ordinals

use ordinal::{Ordinal, CnfTerm};

// ω² (omega squared)
let omega_squared = Ordinal::new_transfinite(&vec![
    CnfTerm::new(&Ordinal::new_finite(2), 1).unwrap()
]).unwrap();

// ω² + ω·3 + 7
let complex = Ordinal::new_transfinite(&vec![
    CnfTerm::new(&Ordinal::new_finite(2), 1).unwrap(),  // ω²
    CnfTerm::new(&Ordinal::one(), 3).unwrap(),          // ω·3
    CnfTerm::new_finite(7),                             // 7
]).unwrap();

println!("{}", complex);  // Prints: ω^2 + ω * 3 + 7

Exponentiation

use ordinal::Ordinal;
use num_traits::Pow;

let omega = Ordinal::omega();

// ω^ω (omega to the omega)
let omega_omega = omega.clone().pow(omega.clone());
println!("ω^ω = {}", omega_omega);  // Prints: ω^ω

// ω^(ω^ω) (tower of omegas)
let tower = omega.clone().pow(omega_omega);
println!("ω^(ω^ω) = {}", tower);

Comparison and Ordering

use ordinal::Ordinal;

let five = Ordinal::new_finite(5);
let omega = Ordinal::omega();
let omega_plus_one = omega.successor();

// All finite ordinals are less than all transfinite ordinals
assert!(five < omega);
assert!(omega < omega_plus_one);

// Standard comparison operators work
assert!(Ordinal::zero() <= Ordinal::one());
assert!(omega.clone() >= omega.clone());

API Overview

Core Types

  • Ordinal - Main ordinal number type (finite or transfinite)
  • CnfTerm - A term in Cantor Normal Form (ω^exponent · multiplicity)
  • OrdinalError - Error type for construction failures
  • Result<T> - Type alias for Result<T, OrdinalError>

Key Methods

Constructors:

  • Ordinal::zero(), Ordinal::one(), Ordinal::omega()
  • Ordinal::new_finite(n) - Create finite ordinal
  • Ordinal::new_transfinite(terms) - Create from CNF terms

Query Methods:

  • is_finite(), is_transfinite()
  • is_limit(), is_successor()
  • successor() - Get the next ordinal (α + 1)

Arithmetic (trait implementations):

  • Add (+) - Ordinal addition
  • Mul (*) - Ordinal multiplication
  • Pow (.pow()) - Ordinal exponentiation

Comparison:

  • PartialOrd, Ord - Standard Rust ordering

See the API documentation for complete details.

Performance Considerations

  • Representation: Finite ordinals use native u32 for efficiency. Transfinite ordinals use a vector of CNF terms.
  • Cloning: Current implementation clones data in arithmetic operations. Future optimizations planned.
  • Exponentiation: Currently uses repeated multiplication for finite exponents (O(n)). Binary exponentiation (O(log n)) is planned.
  • Memory: CNF terms are stored as vectors. Most ordinals have 1-3 terms, but deeply nested ordinals can be larger.

Mathematical Background

This library implements the theory of ordinal arithmetic developed by Georg Cantor in the late 19th century. For more information:

Proof of Correctness

The algorithms in this library are based on standard constructions in ordinal arithmetic:

  • Addition: Right-hand dominance for transfinite ordinals
  • Multiplication: Exponent shifting and coefficient multiplication
  • Exponentiation: Distinct handling of limit vs successor ordinals

The implementation follows the definitions in:

  • Cantor, Georg. "Contributions to the Founding of the Theory of Transfinite Numbers" (1897)

Limitations

  • Ordinals up to ε₀ only: Cannot represent ε₁, ε₂, or larger ordinals
  • Finite coefficients: CNF multiplicities are limited to u32 (0 to 4,294,967,295)
  • No ordinal subtraction: Ordinal subtraction is not well-defined for all ordinals
  • No division: Ordinal division is complex and not yet implemented

Contributing

Contributions are welcome! Please feel free to:

  • Report bugs or issues
  • Suggest features or improvements
  • Submit pull requests
  • Improve documentation
  • Add more test cases

See the issue tracker for planned improvements.

License

This project is licensed under either of:

at your option.

Acknowledgments

This library was inspired by the need for ordinal arithmetic in proof theory, type theory, and theoretical computer science. Special thanks to the Rust community for excellent documentation standards and tooling.

Note: This library is under active development. The API may change in minor versions before 1.0.0.