0
$\begingroup$

Is there a term for a set that is:

  1. discrete
  2. totally ordered
  3. has finite subranges (not a technical term), i.e. for any a and b, $\{x|a is finite

At first glance, it seems this implies that the set is either finite or isomorphic (in some sense) with the integers. Is there a counterexample? What if condition 3 is relaxed? (For example, if the subrange is finite only for certain a and b.)

  • 0
    The sets $\{ x : a \le x \le b \}$ are called _intervals_ (I guess you wrote down the _open_ intervals) and the third condition is called being _locally finite._2012-06-14

2 Answers 2

1

I am not sure if a such a linear ordering has a name.

However they are not all order isomorphic to finite linear ordering or $\mathbb{Z}$. For example the order type $\omega$ also has this property. As well as the order type $\omega^*$, which is the backward $\omega$.

The finite case is fine. Suppose that $L$ is an infinite linear order. Let $S$ denote the successor relations. Define $x \equiv y$ if there exists a natural number $n$ such that $S^n(x) = y \vee S^n(y) = x$. In order to satisfy these properties, you can see that there can only be one equivalence class. Now ask if the equivalence class has a least element or a greater element. Note that it is impossible to have both and satisfy the three properties above. If it has a least element then you have $\omega$, if it has greater element you have $\omega^*$, if it has neither you have $\mathbb{Z}$.

I think the above sketches the possible linear ordering with the above property.

  • 1
    To state it clearly, such order type can be embedded into $\mathbb Z$ as an interval, but it need not be everything or unbounded from both sides.2012-06-14
1

This is just to extend William’s answer to show what happens if you drop condition (3).

Let $\langle X,\le\rangle$ be any linear order. Then we can form a new linear order as follows: the underlying set is $X\times\Bbb Z$, and for $\langle x,m\rangle,\langle y,n\rangle\in X\times\Bbb Z$ we set $\langle x,m\rangle\preceq\langle y,n\rangle$ iff $x, or $x=y$ and $m\le n$. (In other words, $\preceq$ is the lexicographic order on the product $X\times\Bbb Z$.) It’s clear that $\langle X\times\Bbb Z,\preceq\rangle$ satisfies conditions (1) and (2).

Conversely, any linear order satisfying (1) and (2) is order-isomorphic to a lexicographically ordered product $X\times\Bbb Z$. (Here I’m taking (2) in a strong sense that rules out finite orders: every element has an immediate predecessor and an immediate successor.) This is easily seen using William’s equivalence relation. Let $\langle Y,\le\rangle$ be a linear order satisfying (1) and (the strong form of) (2). Each equivalence class of $Y$ must be order-isomorphic to $\Bbb Z$. Now let $\mathscr{C}$ be the set of equivalence classes; each class is an order-convex subset of $Y$, so the linear order on $Y$ naturally induces a linear order $\preceq$ on $\mathscr{C}$ by $C_0\preceq C_1$ iff there are $y_0\in C_0$ and $y_1\in C_1$ such that $y_0\le y_1$ iff $y_0\le y_1$ for all $y_0\in C_0$ and $y_1\in C_1$. It’s easy to check that $Y$ is order-isomorphic to the lexicographic order on $\mathscr{C}\times\Bbb Z$.

If you allow the order to have a first or last element but otherwise satisfy (2), you must extend slightly the range of possibilities: besides $X\times\Bbb Z$ with neither a first nor a last element, you can have $\omega+(X\times\Bbb Z)$ with a first element, $(X\times\Bbb Z)+\omega^*$ with a last element, or $\omega+(X\times\Bbb Z)+\omega^*$ with both a first and a last element. (Here ‘$+$’ just means that the second order is appended to the first.)