1
$\begingroup$

According to Wikipedia, an ordinal notation is a function that maps a subset of ordinal encodings to a subset of ordinals. It then mentions Gödel numbering which maps the set of well-formed formulae of some formal language to a subset of natural numbers. Then proceeds to define a recursive ordinal notation as having two additional properties:

  1. the subset of natural numbers is a recursive set.
  2. the induced well-ordering on the subset of natural numbers is a recursive relation.

This set of requirements seems confusing. What does the subset of natural numbers refer too? Whilst Gödel numbering does map to a subset of natural numbers, it is just a special case of the ordinal notation map which maps to a subset of ordinals!

I have found the following ordinal notation system described in the "Constructive Ordinal Notation Systems" paper:

  1. Encodings are of the form $2^{n}$ and $2^{n}*3$
  2. A function that maps these encodings to ordinals is: $$ f(x) = \left\{\begin{matrix} n & \text{if}~x=2^{n}\\ \omega + n & \text{if}~x=2^{n}*3 \end{matrix}\right. $$

$f(x)$ is clearly mapping to a subset of ordinals (e.g. $\omega$ is not a natural number).

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

The subset of natural numbers referred to is essentially the set of notations, encoded as natural numbers. In your example, it is the set of numbers having form $2^n$ or $2^n\cdot 3$. The ordinal notation interpretation map goes from these numbers, that is, from the notation, to the ordinals that they represent.

The relevance of Gödel numbering is that essentially any formal system of finite notations can be encoded into arithmetic, and we will often want to perform computable operations on the notations. For example, in your notational system, we can compute the order relation on the codes, and we can computably identify which notations represent successor ordinals and which represent limit ordinals, and we can computably add ordinals (when the sum exists) and so forth. Many ordinal notation systems will have these further computability properties. (In general, one cannot compute these additional things just knowing that a computable relation is a well order.)

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Joel David Hamkins, thanks for your reply! It just dawned on me a sentence from the article I referred to "It is traditional and [...] common practice in computability theory to to restrict oneself to natural numbers as the inputs and outputs of algorithms" as I went for a walk :) Because of Gödel numbering one can think of f(x) mapping as mapping ordinal notations to ordinals <=> Gödel's number of ordinal notation to Gödel's number of ordinals <=> natural numbers to natural numbers. $\endgroup$
    – mmiliauskas
    Commented Apr 4 at 14:06
  • $\begingroup$ Do I understand correctly that what the second property requires is for an algorithm less to exist that less(Gödel number(ordinal_1), Gödel number(ordinal_2)) is the same as comparing ordinal_1 with ordinal_2? $\endgroup$
    – mmiliauskas
    Commented Apr 4 at 14:20
  • $\begingroup$ Yes. You want to be able to computably decide the intended order, based only on the notations. $\endgroup$
    – Joel David Hamkins
    Commented Apr 4 at 14:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .