Questions tagged [linear-orders]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
86 views

Permutations which respect a partial order

I have been studying the following situation, and I have a claim I believe to be true, but am unsure on how to approach it. I would appreciate any references I could look into where others have ...
0 votes
0 answers
24 views

Reference for tree of bad sequences of WPO

I'm looking for a reference to give in Wikipedia for the following result: Let $X$ be a WPO. Let $T_X$ be the tree of bad sequnces of $X$, and let $o(X)$ be the ordinal height of the root of $T_X$. ...
4 votes
1 answer
175 views

Find an order-embedding of $S_3\times{\bf2}\times{\bf2}$ into ${\mathbb Z}^4$

A function $f:P\to Q$ from a poset $(P,\le_P)$ to a poset $(Q,\le_Q)$ is an order-embedding if, for all $p,p'\in P$, $p\le_P p'$ if and only if $f(p)\le_Q f(p')$. We partially order the Cartesian ...
14 votes
1 answer
582 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. ...
5 votes
0 answers
125 views

Which monomials are "leadable"?

Question: Let $k$ be a field, let $f \in k[t_1,\ldots,t_N]$ be a nonzero polynomial. Which monomials $m_a = t_1^{a_1} \cdots t_N^{a_n}$ appearing in $f$ are leadable in the sense that they are the ...
3 votes
0 answers
69 views

What are all the order types of maximal chains of $\Delta^0_2$ sets?

A set of natural numbers is $\Delta^0_2$ if it’s computable from the halting set. Consider the quasi-order/pre-order of all $\Delta_0^2$ sets ordered by $m$-reduction, or equivalently consider the ...
2 votes
0 answers
79 views

Ordered vector space that can be embedded into its bidual

We say that an ordered vector space $(V, \ge)$ (over $\mathbb{R}$) is "bidual embeddable" (I made up this name, not sure whether this concept already exists) if for every $x \in V$, if $x$ ...
-3 votes
1 answer
96 views

Order-embeddability of ${\frak b}$ and ${\frak d}$ in $\mathbb{R}$ [duplicate]

The starting point of this question is the observation that in ${\sf (ZFC)}$, all ordinals $\alpha < \omega_1$ can be order-embedded in $\mathbb{R}$. Let $\omega^\omega$ denote the set of all ...
2 votes
0 answers
60 views

Countable highly order-transitive subgroups of $\mathrm{Aut}(\mathbb{Q},\leq)$

Consider $A := \mathrm{Aut}(\mathbb{Q},\leq)$, the group of order-automorphisms of $(\mathbb{Q},\leq)$. Call a subgroup $U$ highly order-transitive if for any two finite ordered sequences $s_1$ and $...
2 votes
0 answers
97 views

Closed images of linearly ordered spaces

Is there a description of the class of continuous closed images of linearly ordered spaces?
5 votes
0 answers
189 views

Given a totally ordered system of Banach spaces, can we we always change the norms to get isometric embeddings?

Given a real vector space $V$ which is the union of a totally ordered family of vector subspaces $V=\bigcup_{i\in I} V_i$. By that I mean that we assume that $(I,\leq)$ is a totally ordered set and ...
10 votes
0 answers
361 views

Can one define in ZFC a directed system of embeddings on the class of all linear orders realizing the surreal line as the direct limit?

Consider the surreal line $\langle\newcommand\No{\text{No}}\No,\leq\rangle$, in its order structure only. This is a proper class linear order, which is universal for all set-sized linear orders, as ...
4 votes
1 answer
155 views

Classifying the endofunctors of the category $\Delta$ of finite linear orders

Is there a theory of endofunctors of the category $\Delta$ of finite linear orders ? Can they be classified ? Is there a reference on this ? Can one classify endofunctors $T:\Delta\to\Delta$ which ...
1 vote
0 answers
180 views

A variant of Buchholz's ordinal notation

Buchholz here introduced an ordinal notation, consisting of a set $\mathcal{T}$, a linear order $\prec$ on $\mathcal{T}$ and some $\mathcal{OT} \subset \mathcal{T}$ such that $(\mathcal{OT}, \prec)$ ...
4 votes
0 answers
205 views

Is there a ${\bf 0'}$-computable linear order with "all intervals wild"?

Say that a linear order $L$ is a thicket iff $L$ is infinite, and for all elements $a,b,c_1,...,c_n\in L$ with $a<_Lb$ and $[a,b]_L$ infinite the following are equivalent: $\{a,b\}\subseteq \...
6 votes
0 answers
188 views

A representation of a partial order by a slowly changing sequence of linear orders

We study visualizations of attractors, which occur in chaotic dynamic systems, and for a few years trying to prove or refute Conjecture [3]. It has an equivalent formulation in terms of order theory, ...
3 votes
1 answer
152 views

A closed subset of a Dedekind-complete order has subspace topology equal to order topology

Here's a fairly easy fact from point-set topology that I'm having trouble finding a reference for. Say $X$ is a total order satisfying the least-upper bound property, and $S$ is a closed subset of it....
6 votes
1 answer
231 views

Ordering preference for two zero mean Gaussian outcomes

Let $X\sim \mathcal{N}(0,1)$ be a standard Gaussian random variable. If we let $f_a(x)\triangleq\mathbb{E}[\max\{aX,x\}]$ for $a,x >0$, how to prove that $$f_a(f_b(1))<f_b(f_a(1))~~\text{for }0&...
6 votes
1 answer
475 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 ...
14 votes
3 answers
1k views

Order homomorphism functions on $\omega_1$

I posted the following question more than two years ago on MO (and then reposted on MSE), but the answer remains incomplete, so I thought I would rephrase it a bit (to make the statement clearer) and ...
18 votes
0 answers
854 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 ...
3 votes
1 answer
164 views

Is there an explicit linear extension for the subsequence partial order?

Consider the set of finite sequences (of bounded length $\leq k$, if necessary) whose elements are taken from some finite alphabet $\Sigma$. We define a partial order on this set so that $X = (X_1,...,...
9 votes
1 answer
262 views

Is a Banach lattice isomorphic to a Hilbert space in fact a Hilbert lattice?

The title says it all: Let $E$ be a Banach lattice, which is isomorphic to a Hilbert space (as normed spaces). Is there an equivalent Hilbert norm on $E$, which still makes it a Banach lattice with ...
18 votes
1 answer
1k views

Suprema of directed sets

Let $(X, \le)$ be a partially ordered set. We call a subset $S \subseteq X$... ... a chain if each two elements in $S$ are comparable with respect to $\le$ (in other words, $S$ is linearly ordered ...
1 vote
0 answers
99 views

About a type of permutations

How many permutations are there on the set $\{1,2, \cdots, n\}$ ($n\geq 3$), such that any three elements are not in increasing or decreasing order? For example, for $n=3$ we have $(1,3,2), (2,1,3), (...
8 votes
2 answers
537 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 ...
3 votes
1 answer
224 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 ...
4 votes
1 answer
275 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 ...
3 votes
1 answer
301 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 ...
14 votes
1 answer
1k 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 ...
1 vote
0 answers
85 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 \...
2 votes
1 answer
207 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,\...
1 vote
1 answer
191 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
313 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
44 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
147 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 ...
4 votes
1 answer
142 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 ...
12 votes
0 answers
492 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 ...
2 votes
1 answer
293 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
590 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 ...
4 votes
2 answers
501 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 ...
5 votes
1 answer
133 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
1 answer
196 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 ...
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: $...
4 votes
2 answers
218 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
273 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 ...
11 votes
0 answers
423 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
110 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
175 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 ...
1 vote
0 answers
83 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 = ...