Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Maybe you are misreading the definition. Is it not the case that $\langle 0 \rangle <_{KB} \langle 1 \rangle <_{KB} \langle \rangle$? – user83827 Jul 13 '12 at 17:55
@ccc that was my first thought, but the definition seems quite clear, and tallies with the Wikipedia entry 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$." – Benedict Eastaugh Jul 13 '12 at 18:12
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? – user83827 Jul 13 '12 at 18:22
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$. – William Jul 13 '12 at 18:29
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$. – user83827 Jul 13 '12 at 18:47
up vote 1 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.