3
$\begingroup$

An ordinal $\alpha$ is said to be computable if there is a computable relation on a subset of integers that is well-ordered and its order type equals $\alpha$.

But let's consider well-founded trees on $\Bbb N$. Such a tree $T$ is a set of finite sequences $(x_1,\dots,x_n)$ of $\Bbb N$ closed under taking initial segments and such that there is no infinite sequence $(x_i)_{i<\omega}$ for which $(x_1,\dots,x_n) \in T$ for any $n$.

There is a natural way to assign an ordinal rank for nodes in such trees (rank of a node is 1 plus the supremum of ranks of its children). For any countable ordinal $\alpha$ we can construct a tree with the root having ordinal rank $\alpha$.

Sure, we can view a tree as a relation on the set of its nodes. And say that a tree is computable if the corresponding relation is computable.

But there is another way to define computable well-founded trees — recursively. We can say that

  1. the trivial tree with the single root node is computable
  2. a tree is computable if all subtrees of its root node are computable and there is a computable enumeration of them

It's not hard to come up with a concrete notation for such computable trees.

Since trees have ordinal ranks it gives us an alternative definition of computable ordinals.

I wonder if this definition is actually the same as the common one. And if not what are the implications? Can we compare their supremum with the Church-Kleene ordinal?

As an encoding of trees I'm thinking of programs (in some Turing complete language) that produce sequences of numbers $n$, where each $n$ is the encoding of a program that produces a subtree. As a special case, $0$ encodes the trivial tree directly. The encoding of programs by numbers is computable.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ In clause 2 of your definition of computable trees, you'll need an indexing of trees to talk about "a computable enumeration of them." If you set up the indexing reasonably, you'll get exactly the computable ordinals as the ranks of your computable trees. (This ought to be in textbooks that cover the theory of $\Pi^1_1$ sets.) $\endgroup$
    – Andreas Blass
    Oct 16, 2022 at 18:57
  • $\begingroup$ @AndreasBlass, thanks, I clarified the indexing. $\endgroup$
    – Dan
    Oct 16, 2022 at 19:58
  • $\begingroup$ As Andreas said, this is the same. In one direction, from a computable well-ordering, make the tree of descending sequences. In the other direction, give a computable well-founded tree the Kleene-Brouwer ordering to get a well-ordering at least as large as the tree rank (and then invoke downward closure of computable ordinals). $\endgroup$
    – Dan Turetsky
    Oct 16, 2022 at 21:42
  • $\begingroup$ @DanTuretsky I think you may have misinterpreted the original question (though since I'm not the OP I'm not totally sure). I interpreted the question as "if we define computable tree in a slightly different way than normal, is the set of possible ranks still exactly $\omega_1^{CK}$?" The answer is "yes" and the proof is easy but it's not quite what you and Andreas mentioned. $\endgroup$
    – Patrick Lutz
    Oct 16, 2022 at 22:39
  • $\begingroup$ @DanTuretsky As I understand, for a computable well-ordered relation we can enumerate all lesser relations. So the alternative definition is not less restrictive. But the reverse statement is not that obvious. Why the corresponding Kleene-Brouwer well-ordering has a computable relation? I guess we need to show that the alternative definition implies that there is a concrete notation for all nodes in a tree. And from this notation we can get a computable relation. $\endgroup$
    – Dan
    Oct 17, 2022 at 6:19

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.