Constructive Ordinal Exponentiation

In classical mathematics, ordinal arithmetic is well-studied; constructively, addition and multiplication are well-known. We study constructive ordinal exponentiation, where ordinals are taken to be transitive, extensional, and wellfounded orders on sets. We present a negative result showing that general constructive ordinal exponentiation is impossible, but we suggest two definitions that come close. The first definition is abstract and solely motivated by the expected equations; this works as long as the base of the exponential is positive. The second definition is based on decreasing lists and can be seen as a constructive version of Sierpiński’s definition via functions with finite support; this requires the base to have a trichotomous least element. Whenever it makes sense to ask the question, the two constructions are equivalent, allowing us to prove algebraic laws, cancellation properties, and preservation of decidability of the exponential. The core ideas do not depend on any specific constructive set theory or type theory, but a concrete computer-checked mechanization using the Agda proof assistant is given in homotopy type theory.

Authors

Institutions

Publication Details

Journal
Journal of the ACM
Published
2026-11-17
DOI
https://doi.org/10.1145/3864019
Primary Topic
Logic, programming, and type systems
Type
article
Field-Weighted Citation Impact
0.00

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Constructive Ordinal Exponentiation

Tom de Jong, Nicolai Kraus, Fredrik Nordvall Forsberg
1 links
Journal of the ACM
Logic, programming, and type systems
article

Constructive Ordinal Exponentiation

Tom de Jong, Nicolai Kraus, Fredrik Nordvall Forsberg
article en

Abstract

In classical mathematics, ordinal arithmetic is well-studied; constructively, addition and multiplication are well-known. We study constructive ordinal exponentiation, where ordinals are taken to be transitive, extensional, and wellfounded orders on sets. We present a negative result showing that general constructive ordinal exponentiation is impossible, but we suggest two definitions that come close. The first definition is abstract and solely motivated by the expected equations; this works as long as the base of the exponential is positive. The second definition is based on decreasing lists and can be seen as a constructive version of Sierpiński’s definition via functions with finite support; this requires the base to have a trichotomous least element. Whenever it makes sense to ask the question, the two constructions are equivalent, allowing us to prove algebraic laws, cancellation properties, and preservation of decidability of the exponential. The core ideas do not depend on any specific constructive set theory or type theory, but a concrete computer-checked mechanization using the Agda proof assistant is given in homotopy type theory.

Journal of the ACM
University of Nottingham (GB), Radboud University Nijmegen (NL), University of Strathclyde (GB)
Royal Society, Deutsche Forschungsgemeinschaft, Engineering and Physical Sciences Research Council, National Physical Laboratory
Logic, programming, and type systems
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon