4.8 Let $(A,<)$ be linearly ordered. Define $\prec$ on $\text{Seq}(A)$ by: $\big\langle a_0,...,a_{m-1}\big\rangle \prec \big\langle b_0,...,b_{n-1} \big\rangle$ if and only if there is $k<n$ such that $a_i=b_i$ for all $i<k$ and either $a_k<b_k$ or $a_k$ is undefined (i.e.,$k=m<n$). Prove that $\prec$ is a linear ordering. If $(A,<)$ is well-ordered, $(\text{Seq}(A),\prec)$ is also well-ordered.

$\text{Seq}(A)$ is the set of all finite sequences.

I don't understand why $\prec$ is well-ordering, when $(A,<)$ is well-ordered. Let $A$ be the set of natural numbers. Then what is the least element of this subset $\{\big\langle 0,0,..., \underbrace{1}_{i} \big\rangle;i \in N\}$ of $(\text{Seq}(A),\prec)$?

  • $\begingroup$ What do the $\dots$ mean there? How many of them are there? $\endgroup$ – Asaf Karagila Apr 14 at 17:43
  • $\begingroup$ (I mean in the $\langle 0,0,\dots,1\rangle$ one, that is.) $\endgroup$ – Asaf Karagila Apr 14 at 17:47
  • $\begingroup$ @AsafKaragila, excuse me, i'm not sure, that i'm understand you. $\endgroup$ – Alex Ivanov Apr 14 at 17:54
  • $\begingroup$ When you write $\langle 0,0,\ldots\rangle$, how many $0$s are there? $\endgroup$ – Asaf Karagila Apr 14 at 18:00
  • $\begingroup$ @AsafKaragila, It's depend from $i$. $i-1$ i suppose. $\endgroup$ – Alex Ivanov Apr 14 at 18:04

As written, you're quite correct that this would not be a well-ordering, since for instance, $$\langle 1\rangle\succ\langle 0,1\rangle\succ\langle 0,0,1\rangle,\dots.$$

I suspect that what was meant is that if $a,b\in\text{Seq}(A),$ then $a\prec b$ if there is some $k$ in the domain of $b$ such that

  1. $a_k$ doesn't exist, or
  2. $a_k<b_k,$ and $a_i=b_i$ for all $i<k.$

Condition 1 means that the sequences are ordered by length (shorter sequences are definitionally "less" than longer ones), and condition 2 means that sequences are otherwise ordered lexicographically.

In that case, $\langle 1\rangle$ is the least element of your set, since it is the shortest sequence.

  • $\begingroup$ Thank you for an answer, i understand you. But i don't think, that author mean this, because next exercise 4.9 tells about Kleene-Brouwer ordering, which very similar to the ordering from 4.8 en.wikipedia.org/wiki/Kleene%E2%80%93Brouwer_order, $\endgroup$ – Alex Ivanov Apr 14 at 19:02
  • 1
    $\begingroup$ That is very similar! The only difference is the case that one is a prefix of the other. The first sentence in the linked article is "In descriptive set theory, the Kleene–Brouwer order or Lusin–Sierpiński order is a linear order on finite sequences over some linearly ordered set $(X,<),$ that differs from the more commonly used lexicographic order in how it handles the case when one sequence is a prefix of the other. In the Kleene–Brouwer order, the prefix is later than the longer sequence containing it, rather than earlier." Given that, my suspicion has not been eliminated, but strengthened. $\endgroup$ – Cameron Buie Apr 14 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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