13

Our experience shows that all finitary mathematical objects could be encoded using the natural numbers, and all operations on those objects could be expressed in terms of a few basic operations on numbers: the successor operation, addition and multiplication.

As far as I understand, this is not a theorem in the strict sense (because the notion of a finitary mathematical object is somewhat vague), but is rather a principle with a status similar to the Church–Turing thesis. Nevertheless, the essence of this principle can be expressed by a precise statement, for example, that the theory of hereditary finite sets and the Peano arithmetic are mutually interpretable.

As it turns out, other familiar operations on integers — the exponentiation, prime factorization and in fact (invoking the Church–Turing thesis), every effectively computable operation — can be expressed using the few aforementioned basic operations.

Now, the set theory encompassing infinite sets and the powerset operations is much richer than the Peano arithmetic. But we can observe that the universe of sets contains a subclass similar in some of its properties to the natural numbers — the class of ordinals. So, here is my question:

Is it possible to reduce studying of (finite and infinite) mathematical objects to studying of ordinals, and to build a formal theory free of the concept of an arbitrary set, the theory whose universe consists of ordinals only, that uses only a few basic operations on them, but the theory that is still powerful enough to serve as a foundational theory of all mathematics — in the same sense as it is possible to use the Peano arithmetic as a foundational theory for finitary mathematics? And if so, what could be its language and its axioms?

To clarify, I'm not asking if it would be useful or convenient to use such a theory, but I'm interested in a mere possibility to do that.

Vladimir Reshetnikov
  • 47,122
  • I guess the answer is negative, though we need a concrete formulation of the question. The reasons are: first, power set of some set (such as $\mathcal{P}(\Bbb{N})$.) does not have natural well-order. It is consistent with ZF that the power set of $\Bbb{R}$ is not well-orderable. Second, some set may not definable from ordinals (although we can assume that every set is ordinal-definable). – Hanul Jeon Mar 21 '16 at 03:23
  • @HanulJeon Of course, there are variants of set theory, where not every set admits a well-ordering, and they constitute an important and interesting part of infinitary mathematics. But for the positive answer to my question, it is sufficient if we can model those variants of set theory in the theory of ordinals. – Vladimir Reshetnikov Mar 22 '16 at 03:58
  • You may interested in the class of all hereditarily ordinal definable sets, which forms an inner model of the ZFC. – Hanul Jeon Mar 22 '16 at 16:47
  • Are you asking for a theory where everything is built up from ordinals, or asking for a theory in which all sets are ordinals. I might have an idea for the first one, but the second one isn't as easy since e.g. $\alpha\setminus\beta$ is only an ordinal if $\beta=\emptyset$ or $\alpha\subseteq\beta$ – SK19 Sep 29 '18 at 23:18
  • 1
    I mean a theory where all objects are ordinals (i.e. all variables range over ordinals), and other notions (e.g. arbitrary sets) are encoded in some way using ordinals, similar to how we can encode finite sequences of natural numbers, operations on them, or arbitrary recursive functions in Peano arithmetic using natural numbers. – Vladimir Reshetnikov Sep 30 '18 at 04:14

1 Answers1

4

Edit: I've just been told that Rathjen's definition of proof-theoretic ordinal is intentionally vague for the introduction and not fit to base results off of. However as far as I know one of Rathjen's more specific renderings of Gentzen's result in particular is correct, $$\textrm{PRA+}``\textrm{There exists a provably recursive well-ordering of order type }\varepsilon_0"\vdash\textrm{Con(PA)}$$ (Although another user told me this might be wrong as well, it might work if we fix an ordinal notation in advance as in (14).)

Some analysis of theories where every object in their intended domain of discourse is an ordinal, or "theories of ordinals" as Arai calls them, has been done. For example in the paper Proof theory for theories of ordinals II: $\Pi_3$-reflection, Arai has defined and analyzed a theory $T_3$ for universes that are $\Pi_3$-reflecting ordinals. And this theory proves the consistency of Peano arithmetic:

According to Rathjen's paper "The realm of ordinal analysis", $\textrm{PRA}$ plus transfinite induction of length $\varepsilon_0$ along a certain primitive recursive predicate is sufficient to prove $\textrm{Con(PA)}$. Since the ordinal Arai calibrated $\vert T_3\vert$ to is greater than $\varepsilon_0$, this means $T_3$ proves some primitive recursive ordering of $\omega$ with order type $\varepsilon_0$ to be a recursive well-ordering. If $T_3$ also interprets $\textrm{PRA}$, then $T_3$ proves $\textrm{PRA}+\textrm{PR-TI}(\varepsilon_0)$, and so proves $\textrm{Con(PA)}$.

C7X
  • 1,187