Questions tagged [linear-orders]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
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
0answers
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
1answer
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
1answer
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
2answers
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
1answer
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
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
1answer
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
3answers
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
1answer
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
1answer
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
2answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
2answers
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
0answers
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
4answers
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
0answers
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
1answer
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
1answer
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
3answers
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
2answers
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
1answer
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
2answers
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
0answers
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
2answers
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
0answers
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
2answers
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
2answers
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
1answer
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
2answers
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
3answers
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
3answers
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
2answers
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
2answers
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
1answer
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
1answer
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
1answer
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$ ...