# Questions tagged [linear-orders]

The linear-orders tag has no usage guidance.

48
questions

**0**

votes

**0**answers

59 views

### Closed set in product topology implies convergence of monotonic sequences

Let $(X,\succsim)$ be a metrizable and connected, totally ordered topological space with the order topology. Let $\succeq$ be another order relation on $X \times X$ such that the two orders are ...

**1**

vote

**0**answers

74 views

### Name for partial orders which are total on connected components

In my context, I encounter a lot of partial orders with the distinguished property that the order is total on connected components. Equivalently, they satisfy the condition
$$x \le y,z \enspace \lor \...

**11**

votes

**1**answer

278 views

### On certain order-automorphisms of the rationals

Consider the rationals $\mathbb{Q}$ with the usual order $\leq$. Now let $A$ be a subset of $\mathbb{Q}$, such that foreseen with the induced order $\leq$, $(A,\leq)$ is a dense linear order.
...

**2**

votes

**1**answer

181 views

### Fundamental theorem of linear orders

Let $(\Omega,\leq)$ be a countable linear order. Suppose that for every finite $m \in \mathbb{N}$, and all subsets $S_1$ and $S_2$ of $\Omega$ of order $m$, there is an order-automorphism of $(\Omega,\...

**8**

votes

**2**answers

304 views

### Ordinal notations within non-standard models of arithmetic

It is well-known that the order type of any countable non-standard model of arithmetic $\mathfrak{A}$ is $\omega+(\omega^*+\omega)\eta$. My question is what could be said about the order types of ...

**4**

votes

**1**answer

101 views

### Characterization of Archimedean linearly ordered monoids

In this question, it is shown that all Archimedean ordered groups are isomorphic to an ordered subgroup of $\mathbb R$. Additionally, it is shown that if such a group is complete, then it is ...

**1**

vote

**1**answer

127 views

### Self-embeddings of uncountable total orders

A nice theorem of Dushnik and Miller (from 1940) states that if $(\Omega,\leq)$ is a countable total order, then either
there is an element $\omega \in \Omega$ such that $(\Omega \setminus \{\omega\}...

**8**

votes

**1**answer

232 views

### A strictly decreasing function between uncountable subsets of the reals

By a standard technique of inductive killing everything relevant (in this case decreasing homeomorphisms between uncountable $G_\delta$-subsets of the real line) it is possible to prove the following ...

**3**

votes

**0**answers

33 views

### Maximal number of sets, obtained as intersections of semiintervals of $k$ linear orders

Given a finite set $S$ with $n$ elements, and a fixed small $k$ (say $k=3$), how to find $k$ linear orders $\leq_1, \dots, \leq_k$ on $S$, such that the number of feasible subsets of $S$ is ...

**3**

votes

**2**answers

116 views

### What is the dimension of a subspace of the product of $n$ linearly ordered compacta

This question is motivated by this problem of Dominic van der Zypen.
Problem. Let $X=\prod_{i=1}^nX_i$ be the Tychonoff product of linearly ordered compact Hausdorff spaces $X_1,\dots,X_n$. Is it ...

**14**

votes

**1**answer

659 views

### Characterizing $\mathbf{R}$ as an ordered group

A standard characterization of $\mathbf{R}$ uses the order and the field structure: any linearly ordered field that is archimedean and complete is isomorphic to $(\mathbf{R}, +, \times, <)$ as an ...

**4**

votes

**1**answer

113 views

### Kruskal's tree theorem and $\Pi_1$ sentences of linear orderings with finitely many constants

In their paper "Theories with recursive models" [1] Lerman and Schmerl used a version of Kruskal's tree theorem about finite n-augmented trees.
An n-augmented tree is a tree T together with $n$ unary ...

**2**

votes

**1**answer

262 views

### Name for this algebraic structure?

I've found myself looking at a structure $\mathbb{M}$ whose important properties are:
$\mathbb{M}$ is a discretely ordered additive monoid.
$\mathbb{M}$ has a least element, and this least element is ...

**9**

votes

**3**answers

485 views

### Associative mean

Can there be a function $m(a,b)$ that is both associative and a mean, i.e.,
$\min (a,b) \leq m(a,b) \leq \max (a,b)$? The obvious solutions are $m(a,b) = \max(a,b)$ or $\min(a,b)$, but are there ...

**5**

votes

**1**answer

279 views

### Upward Löwenheim–Skolem theorem for well-ordered models with/without measurable cardinals

Consider a complete first order theory $T$ whose language contains a binary predicate $\leq$. Assume that $T$ has an uncountable model that is well-ordered by $\leq$ so that this question isn't stupid ...

**5**

votes

**1**answer

104 views

### Is there literature on finite geometries with ordered lines?

A difference between finite geometries and (e.g.) Euclidean space is that "lines" in finite geometries are unordered subsets of the universe, while "lines" in Euclidean space are ordered subsets of ...

**4**

votes

**2**answers

200 views

### locally incomparable dense linear orderings extending $\langle \mathbb{R}, < \rangle$

This follows up on Incomparable dense linear orderings extending $\langle \mathbb{R},< \rangle$
and hopefully sparks more discussion.
Where $a<b$, say that the four “types” of nonempty bounded ...

**7**

votes

**1**answer

235 views

### Incomparable dense linear orderings extending $\langle \mathbb{R},< \rangle$

Where $a<b$, say that the four “types” of non-empty bounded intervals are:
$(a,b)$, $[a,b]$, $(a,b]$, and $[a,b)$.
Let $\langle X,< \rangle$ and $\langle Y,< \rangle$ be dense linear ...

**4**

votes

**1**answer

136 views

### An algebraically generated set of linear orders

Notation: Let $L_1,L_2,...$ be linearly ordered sets.
$L_{i}^{-1}$ denotes the reverse linear order of $L_{i}$,
$L_1+L_2$ denotes the sum of linear orders, i.e. the disjoint union $L_1\cup L_2$ with ...

**11**

votes

**0**answers

312 views

### Example of $\aleph_1$-categorical linear order

Is it possible to have an $L_{\omega_1,\omega}$-sentence $\phi$ in a vocabulary that includes $<$ that satisfies the following?
$<$ is a linear order on a definable subset;
$\phi$ is $\aleph_1$-...

**2**

votes

**1**answer

83 views

### The pseudo-metric and linear orders

Is there a necessary and sufficient condition for a linearly ordered topological space to be pseudo-metrizable? (by a pseudo-metric, I mean a map $X\times X\rightarrow\mathbb{R}$ in which all the ...

**3**

votes

**1**answer

150 views

### Least ordinal not embedded in a total order

If $(E,<)$ is a linear order, let $s(E,<)$ denote the least ordinal which doesn't embed in $(E,<)$.
I am trying to prove the following:
If $(M,+,.,0,1)$ is a model of open induction, (or ...

**14**

votes

**0**answers

520 views

### Is the universality of the surreal number line a weak global choice principle?

I'd like to consider the principle asserting that the surreal
number line is universal for all class linear orders, or in other
words, that every linear order (including proper-class-sized)
linear ...

**1**

vote

**0**answers

78 views

### reconstructing a linear order corrupted by noise

Suppose we have a partial order (efficiently computable), $\leq$, on $\mathbb{R}^n$, a set $S \subset \mathbb{R}^n$, and let $\rho$ be the standard Euclidean metric. We want to find a set $S^\prime = ...

**4**

votes

**2**answers

402 views

### Maximal cones and lexicographic orderings

Let $V$ be a real vector space. It is well known that, given a totally ordered basis of $V$ (say $(b_i)_{i\in I}$ where $I,<$ is totally ordered), $V$ is totally ordered by the lexicographic ...

**19**

votes

**0**answers

701 views

### A Linear Order from AP Calculus

In teaching my calculus students about limits and function domination, we ran into the class of functions
$$\Theta=\{x^\alpha (\ln{x})^\beta\}_{(\alpha,\beta)\in\mathbb{R}^2}$$
Suppose we say that $...

**3**

votes

**4**answers

677 views

### Is there a compact connected Hausdorff space in which every non-empty $G_\delta$ set has non-empty interior?

Q1.
Is there a compact connected Hausdorff space (with at least two points) in which every non-empty $G_\delta$ set has non-empty interior? (Without the requirement for connectedness, every finite $...

**1**

vote

**0**answers

200 views

### Existence of $\lambda$-transitive linear orders for $\lambda \geq \aleph_0$

A linear order $(L, <)$ is $\lambda$-transitive iff any order-preserving bijection between sets of size $\lambda$ can be extended to an order automorphism of $L$.
For $\lambda < \aleph_0$, $2$-...

**3**

votes

**1**answer

250 views

### Normal subgroup of a totally ordered group

A totally ordered group is a group equipped with a compatible total order, that is, $x\leq y$ and $z\leq t$ imply $x+z\leq y+t$ for all $x,y,z,t$ in the group.
Is it true that every totally ordered ...

**3**

votes

**1**answer

276 views

### reduction to np hard ordering problem

I am trying to show a reduction from a problem of ordering problem to an np-hard problem that has approximation poly-time algorithm.
My problem is: I have M auctions and in each auction I have N ...

**2**

votes

**3**answers

375 views

### Compact, densely ordered spaces

During my work with order preserving homeomorphisms, I got interested in the double arrow space and, subsequently, in the lexicographic square.
I would really like to find examples of spaces like ...

**4**

votes

**2**answers

453 views

### Is it consistent with ZFC that $\mathrm{dv}(\kappa) = \kappa$ for all infinite cardinal numbers $\kappa$?

Whenever $\kappa$ is an infinite cardinal number, write $L(\kappa)$ for the powerset of $\kappa$ ordered lexicographically. (Where the "$L$" stands for linear order.) Furthermore, write $B(\kappa)$ ...

**2**

votes

**1**answer

142 views

### Linearly ordered set arithmetic: reference request

A lot has been written about the arithmetic of ordinal numbers. However, we can also do arithmetic with linearly ordered sets.
Question. Is there an article or book where I can learn the basics of ...

**7**

votes

**2**answers

630 views

### Which linearly ordered sets have the property that their completion is equipotent with their powerset?

As is well-known, ZFC proves the equipotency of $\mathbb{R}$ and $\mathcal{P}(\mathbb{Q}).$ Is there a nice characterization of those linearly ordered sets $L$ which, like $\mathbb{Q}$, have the ...

**12**

votes

**0**answers

445 views

### Do all linear orders in this class have computable copies?

This is a question which has been bothering me now for quite some time. I've talked to a number of people about it, and we've shown that a few basic ideas can't work, but other than that haven't made ...

**14**

votes

**2**answers

1k views

### Order homomorphism functions on $\omega_1$

This question has now been published in a math journal, see update at the bottom.
I posted the following question more than two years ago on MO (and then reposted on MSE), but the answer remains ...

**4**

votes

**0**answers

195 views

### The theory of two finite linear orders

My colleague Matthias Baaz is looking for a reference for the following question (or possibly theorem):
Let T be the "theory of pairs of finite linear orders". That is, consider all finite ...

**15**

votes

**2**answers

468 views

### Can a Suslin line be 2-entangled?

A Suslin line is a linear order $L$ which is dense with no endpoints, complete, and ccc but not separable. I'm wondering what kind of order-preserving maps there are from $L$ into $L$. Specifically,
...

**21**

votes

**2**answers

1k views

### An order type $\tau$ equal to its power $\tau^n, n>2$

(This is a re-post of my old unanswered question from Math.SE)
For purposes of this question, let's concern ourselves only with linear (but not necessarily well-founded) order types.
Recall that:
$...

**3**

votes

**1**answer

180 views

### Extensions of partial orders to linear orders on (nonabelian) groups

If $G$ is a group with a (left) linear order, does every (left) partial order on $G$ extend to a (left) linear order?
The answer is affirmative on abelian groups, where being torsion-free is ...

**11**

votes

**2**answers

522 views

### Extending a partial order while preserving an automorphism

It is well known that if $(P, \leq)$ is a partial order then $\leq$ can always be extended to a linear order. This is sometimes called Szpilrajn´s theorem although it had been previously proved by ...

**10**

votes

**3**answers

218 views

### Maximal chains in a quasi-order of linear order types

Let $\mathcal{T}_\kappa$ be the set of all linear order types of cardinality $\kappa$. Let $\prec$ denote a binary relation on $\mathcal{T}_\kappa$ representing embeddability of order types (note that ...

**23**

votes

**3**answers

1k views

### Is it possible to construct an infinite subset of $\Bbb R$ that is not order isomorphic to any proper subset of itself?

Is it possible to construct an infinite subset of $\Bbb R$ that is not order isomorphic to any proper subset of itself?

**13**

votes

**2**answers

557 views

### How many subsets of $\mathbb{R}$ are order isomorphic to $\mathbb{Q}$?

How many subsets of $\mathbb{R}$ are order isomorphic to $\mathbb{Q}$?
How many subsets of the long line $\omega_1\times[0,1)$ are order isomorphic to $\mathbb{Q}$?
I can see that results in both ...

**17**

votes

**2**answers

309 views

### Is it possible to reconstruct an order type from its initial segments?

Suppose
$T$ is a totally ordered set without a maximal element,
$\tau$ is the order type of $T$,
$S$ is the set of order types of all proper initial segments (downward closed subsets) of $T$.
Is it ...

**5**

votes

**1**answer

270 views

### Rotation-invariant strict-inclusion-preserving preorderings on subsets of the circle

Say that a preordering $\le$ on a set of subsets of some space preserves strict inclusion provided that $A\lt B$ whenever $A\subset B$ (where $A\lt B$ iff $A\le B$ and $B \not\le A$).
Let the space ...

**5**

votes

**1**answer

485 views

### Characterizing $\omega_1$-like dense linear orderings

I recently came upon the following theorem which was attributed to J. Conway:
For each $A\subset \omega_1$, let $\Phi(A)$ be a linear ordering of type $\sum_{\alpha<\omega_1} \tau_\alpha$, where $\...

**1**

vote

**1**answer

161 views

### The proper name for a kind of ordered space [closed]

I'm trying to find the correct term for a specific kind of totally ordered space:
Let $S$ be a totally ordered space with strict total order $<$.
Property: For any two $s_{1}$ and $s_{2}$ in $S$ ...