5
$\begingroup$

The Kleene-Brouwer order $<_{KB}$ transforms a computable tree $T$ on $\omega^{< \omega}$ into a computable linear order (mapping infinite paths through $T$ into infinite descending sequences). What recursive linear orders are isomorphic to the Kleene-Brouwer order on some tree?

Define as in [1] an adequate linear order to be one with least element $0$, every element has an immediate successor and every element is either finitely above $0$ or finitely above a limit point (and may as well demand the field be equal to $\omega$). Is every adequate linear order represented by $<_{KB}$ on some computable tree? What about adequate orders with no hyperarithmetic descending sequences?


The motivation here (and I guess a second question if the answer to the main question is negative) is that in [1] Friedman proves there are some adequate computable linear orders that don't support any jump-hierarchy. In other words, you can't define sets that look like $0^{\alpha}$ on those orders (i.e. with $\alpha$ ranging over elements in the ordering not true notations). Does that also mean that there is a computable tree with some branches but no hyperarithmetic ones such that $<_{KB}$ on that tree but doesn't support a jump-hierarchy? What if $<_{KB}$ on that tree produces an adequate order?


1: Friedman, UNIFORMLY DEFINED DESCENDING SEQUENCES OF DEGREES

$\endgroup$
1
  • $\begingroup$ Note that, it's not too hard to produce a tree which has branches but no hyperarithmetic branches that does support a jump hierarchy via the recursion theorem but it's not clear that every computable tree or even every tree whose KB ordering is nice enough has that property. $\endgroup$ Commented Jan 26 at 14:41

1 Answer 1

5
$\begingroup$

The computable linear orders isomorphic to the Kleene-Brouwer order of a computable tree are precisely the orders with a greatest element.

In one direction, the root of the tree is always greatest in the KB-ordering.

In the other direction, given a computable linear order $L$ with a greatest element, non-uniformly fix the greatest element and WLOG assume it is the first element of the domain. We will build a tree $T$ and a map $f: L \to T$ such that $f$ is an isomorphism between $L$ and the KB-ordering on $T$.

At stage $s=0$, add the root to $T$ and define $f$ to send the greatest element of $L$ to the root.

At stage $s+1$, let $x$ be the next element of the domain of $L$. Let $y$ be the least element of $L$ which is greater than $x$ and already an element of the domain (such element must exist, because we have already dealt with the greatest element). Add a new child to $f(y)$ greater than any existing child, and define $f(x)$ to be this new child.

One verifies by induction that $f$ is order-preserving between $L$ and the KB-ordering of $T$.

$\endgroup$
1
  • 1
    $\begingroup$ Ok, and then you can prove that there is such an order without a jump-hierarchy by simply pointing out that if if we add a top element to $<$ then the new ordering supports a jump hierarchy iff the original ordering did. Hence we can transform the Freidman ordering to one with a maximal element. $\endgroup$ Commented Jan 26 at 20:37

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.