Questions tagged [linear-orders]
The linear-orders tag has no usage guidance.
66
questions
4
votes
1
answer
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
5
votes
0
answers
114
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 ...
- 64.4k
3
votes
0
answers
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
2
votes
0
answers
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$ ...
- 246
-3
votes
1
answer
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 ...
- 44.4k
2
votes
0
answers
59
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 $...
- 4,015
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?
- 103
5
votes
0
answers
186
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 ...
- 559
10
votes
0
answers
354
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 ...
- 218k
4
votes
1
answer
146
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 ...
- 317
1
vote
0
answers
170
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)$ ...
- 580
4
votes
0
answers
201
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 \...
- 19k
3
votes
1
answer
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
6
votes
0
answers
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
6
votes
1
answer
229
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&...
- 171
3
votes
1
answer
152
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,...,...
- 343
9
votes
1
answer
257
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 ...
- 5,273
17
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 ...
- 11.4k
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), (...
- 343
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 \...
- 5,586
14
votes
1
answer
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
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,\...
- 4,015
8
votes
2
answers
508
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 ...
- 5,391
4
votes
1
answer
245
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 ...
- 249
1
vote
1
answer
180
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\}...
- 4,015
8
votes
1
answer
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
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
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
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 ...
- 18.4k
4
votes
1
answer
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 ...
- 455
2
votes
1
answer
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
9
votes
3
answers
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
6
votes
1
answer
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
5
votes
1
answer
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
4
votes
2
answers
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
7
votes
1
answer
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
4
votes
1
answer
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
11
votes
0
answers
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
2
votes
1
answer
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 ...
- 297
3
votes
1
answer
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
18
votes
0
answers
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 ...
- 218k
1
vote
0
answers
82
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 = ...
- 459
4
votes
2
answers
499
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 ...
- 3,666
19
votes
0
answers
763
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 $...
- 433
3
votes
4
answers
898
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,345
1
vote
0
answers
209
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$-...
- 178
3
votes
1
answer
292
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 ...
- 63
3
votes
1
answer
359
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 ...
- 31
2
votes
3
answers
407
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 ...
- 203
4
votes
2
answers
511
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)$ ...
- 3,683