Questions tagged [linear-orders]

The tag has no usage guidance.

66 questions
Filter by
Sorted by
Tagged with
171 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 ...
• 1,250
114 views

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 ...
• 64.4k
66 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 ...
• 4,489
71 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$ ...
94 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 ...
59 views

142 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....
• 2,495
185 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,937
229 views

• 5,586
566 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. ...
• 4,015
207 views

• 4,015
304 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 ...
• 40.1k
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 ...
144 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 ...
• 40.1k
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 ...
• 18.4k
141 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 ...
289 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 ...
• 8,878
583 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,631
463 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 ...
• 10.1k
128 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 ...
• 1,379
217 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 ...
• 449
266 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 ...
• 449
187 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 ...
• 6,641
406 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,922
109 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 ...
171 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 ...
• 2,307
834 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
82 views

• 433