# Questions tagged [linear-orders]

The linear-orders tag has no usage guidance.

**7**

votes

**1**answer

203 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

32 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

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

**13**

votes

**1**answer

487 views

### $\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

99 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

253 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

469 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

224 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

95 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

196 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

225 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

117 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

277 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

71 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

144 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

459 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

360 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

670 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

453 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

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

**2**

votes

**1**answer

216 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

250 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

346 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

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

**1**

vote

**1**answer

126 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

562 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

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

**13**

votes

**2**answers

935 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

192 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

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

**2**

votes

**1**answer

166 views

### Linear order extensions 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

484 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

210 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

914 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

518 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

301 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

268 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

458 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

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