3
$\begingroup$

This question was motivated by a statement in Simpson's Subsystems of Second Order Arithmetic (second edition), p. 168.

It is straightforward to verify (in $\mathsf{RCA}_0$ for instance) that $\leq_{KB}$ is a dense liner [sic] ordering with no left endpoint and with the empty sequence $\langle \rangle$ as its right endpoint.

(My emphasis.)

That it's a linear ordering with no left endpoint and $\langle \rangle$ as its right endpoint is indeed straightforward to verify. So is the Kleene/Brouwer ordering dense, too?


Let $Seq$ be the set of codes for finite sequences of natural numbers, and let $KB$ be the set of all pairs $(\sigma, \tau) \in Seq \times Seq$ such that either $\sigma \supseteq \tau$ or

$$\exists{j < \min(lh(\sigma), lh(\tau))} \, [ \sigma(j) < \tau(j) \wedge \forall{i < j} (\sigma(i) = \tau(i)) ].$$

Now consider the following: $\langle 0 \rangle <_{KB} \langle \rangle$, so if the order is dense then there must be some $\upsilon$ such that $\langle 0 \rangle <_{KB} \upsilon <_{KB} \langle \rangle$. Clearly it can't be the case that $\langle 0 \rangle \supset \upsilon \supset \langle \rangle$. And there is no point that $\upsilon$ can diverge from the empty sequence at. So it must be the case that $\upsilon \supset \langle \rangle$ and there exists some $j$ such that $\upsilon(j) < 0$. But since there is no natural number $n < 0$ this can't be the case either. So we have a counterexample to the density of the Kleene/Brouwer ordering.

  • 0
    Maybe you are misreading the definition. Is it not the case that $\langle 0 \rangle <_{KB} \langle 1 \rangle <_{KB} \langle \rangle$?2012-07-13
  • 0
    @ccc that was my first thought, but the definition seems quite clear, and tallies with [the Wikipedia entry](http://en.wikipedia.org/wiki/Kleene–Brouwer_order) and what I've seen in books on descriptive set theory. In Chi Tat Chong and Liang Yu's book on higher recursion theory, they say "$\sigma <_{KB} \tau$ whenever either $\sigma$ extends $\tau$ or $\sigma$ is 'left' of $\tau$."2012-07-13
  • 2
    But even according to the definition you wrote, $\sigma = \langle 0 \rangle$ is less than $\tau = \langle 1 \rangle$ since $\sigma(0) < \tau(0)$ and for all $i < 0$, $\sigma(i) = \tau(i)$ (vacuously). What am I missing?2012-07-13
  • 0
    You are looking for some $v$ which is $KB$-bigger than $\langle 0 \rangle$. I don't know why you would try to find $v$ such that $v(j) < 0$.2012-07-13
  • 0
    @ccc, William: thanks, yes, just a comprehension error on my part. I was trying to prove the density part earlier and obviously just got a bit mixed up about the order. Obviously one can always find a greater element (below the right element), but my question as to whether the order is dense still stands.2012-07-13
  • 1
    What we just discussed generalizes to yield $\upsilon$ with $\sigma < \upsilon < \tau$ whenever $\sigma$ extends $\tau$. And if $\sigma$ does not extend $\tau$, then any proper extension $\upsilon$ of $\tau$ satisfies $\sigma < \upsilon < \tau$.2012-07-13
  • 0
    Actually thinking about this seems to answer the density question too: any $\upsilon \supset \langle 1 \rangle$ will be greater than $\langle 0 \rangle$ but less than $\langle 1 \rangle$, for example. So it seems as though you can always extend to find a longer sequence between two elements.2012-07-13
  • 0
    @ccc I didn't see your comment before posting mine. But why don't you post it as an answer? Happy to accept it.2012-07-13

1 Answers 1

1

Proof of density:

Suppose that $\sigma <_{KB} \tau$.

The first case is that $\tau \prec \sigma$ (where $\prec$ is proper initial segment relation). Then $|\tau| < |\sigma|$. Define $\gamma$ or length $|\tau| + 1$ as follows

$\gamma(n) = \begin{cases} \sigma(n) & \quad n < |\tau| \\ \sigma(|\tau|) + 1 & \quad n = |\tau| \end{cases}$

$\sigma <_{KB} \gamma$ since for all $n < |\tau|$, $\sigma(n) = \tau(n)$ but $\sigma(|\tau|) < \sigma(|\tau|) + 1 = \gamma(|\tau|)$. $\gamma <_{KB} \tau$ since $\tau \prec \gamma$.

The second case is that there exists a $j < \min\{|\sigma|, |\tau|\}$ such that for all $n< j$, $\sigma(n) = \tau(n)$ and $\sigma(j) < \tau(j)$. Then define $\gamma$ to be the string of length $|\tau| + 1$ define by $\tau0$, i.e. $\tau$ concatenated by $0$. Than $\sigma <_{KB} \gamma$ since $j$ witnesses this property again. $\gamma <_{KB} \tau$ since $\tau \prec \gamma$.