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
    @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$.