The order-theory tag has no usage guidance.

**34**

votes

**3**answers

1k views

### Is the fixed point property for posets preserved by products?

Recall that a partially ordered set (poset) $P$ has the fixed point property (FPP) if any order preserving function $f:P\longrightarrow P$ has a fixed point.
Theorem. Suppose $P$ and $Q$ are posets ...

**30**

votes

**4**answers

2k views

### A principle of mathematical induction for partially ordered sets with infima?

Recently I learned that there is a useful analogue of mathematical induction over $\mathbb{R}$ (more precisely, over intervals of the form $[a,\infty)$ or $[a,b]$). It turns out that this is an old ...

**28**

votes

**9**answers

3k views

### How many groups of size at most n are there? What is the asymptotic growth rate? And what of rings, fields, graphs, partial orders, etc.?

Question. How many (isomorphism types of) finite groups of size at most n are there? What is the asymptotic growth rate? And the same question for rings,
fields, graphs, partial orders, etc.
...

**28**

votes

**2**answers

708 views

### What is the minimal size of a partial order that is universal for all partial orders of size n?

A partial order $\mathbb{B}$ is universal for a class $\cal{P}$ of partial orders if every order in $\cal{P}$ embeds
order-preservingly into $\mathbb{B}$.
For example, every partial order
$\langle\...

**28**

votes

**5**answers

906 views

### Does the exact pair phenomenon for partial orders occur in your area of mathematics?

Suppose that I have a partial order P and an increasing sequence $a_0< a_1<a_2<\cdots$ of elements of $P$. A pair of elements (b,c) from P is said to be an exact pair for this sequence, if
...

**25**

votes

**2**answers

791 views

### How much choice is needed to show that formally real fields can be ordered?

Background: a field is formally real if -1 is not a sum of squares of elements in that field. An ordering on a field is a linear ordering which is (in exactly the sense that you would guess if you ...

**23**

votes

**2**answers

519 views

### Order type of the smallest set containing the identity function and closed under exponentiation

Let $E$ be the smallest set of functions $\mathbb{N}^+\to\mathbb{N}^+$ containing the identity function $n \mapsto n$ and closed under exponentiation $(f,g) \mapsto \left(n \mapsto f(n)^{g(n)}\right)$...

**22**

votes

**6**answers

2k views

### What's a non-abelian totally ordered group?

Because I have heard the phrase "totally ordered abelian group", I imagine there should be non-abelian ones. By this I mean a group with a total ordering (not to be confused with a well-ordering) ...

**21**

votes

**3**answers

627 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?

**20**

votes

**4**answers

1k views

### When does a Galois connection induce a topology?

Let $(X,\leq)$ and $(Y,\leq)$ by partially ordered sets. Recall that a(n antitone) Galois connection between $X$ and $Y$ is a pair of order-reversing maps
$\Phi: X \rightarrow Y, \ \Psi: Y \...

**18**

votes

**2**answers

720 views

### Which are the rigid suborders of the real line?

Which are the rigid suborders of the real line?
If A is any set of reals, then it can be viewed as an order structure itself under the induced order (A,<). The question is, when is this structure ...

**18**

votes

**0**answers

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

**17**

votes

**2**answers

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

**16**

votes

**2**answers

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

**16**

votes

**2**answers

1k views

### Can all $\aleph_2$-dense subsets of $\mathbb{R}$ be isomorphic?

Let $\kappa$ be an infinite cardinal. For a subset $A \subseteq \mathbb{R}$, we say that $A$ is $\kappa$-dense if $|A \cap (a, b)| = \kappa$ for every interval $(a, b)$. By Cantor, any two $\aleph_0$-...

**16**

votes

**1**answer

2k views

### Is every continuous function measurable?

This question has already been asked on Math StackExchange here, but was too old to be migrated, and I think will be more appropriate to MathOverflow.
In non-Hausdorff topology it is standard to ...

**15**

votes

**4**answers

465 views

### Representation theorem for modular lattices?

Birkhoff's representation theorem implies that every distributive lattice embeds into the lattice of subsets of a set. Is there also some representation theorem for modular lattices?
For example, I ...

**15**

votes

**3**answers

4k views

### Proving that a poset is a lattice

I discovered experimentally that a certain finite poset (sorry, I cannot give its definition here) seems to be in fact a (non-distributive, non-graded) lattice. The covering relations are reasonably ...

**15**

votes

**3**answers

896 views

### Subposets of small Dushnik-Miller dimension

The Dushnik–Miller dimension of a partial order $(P,{\leq})$ is the smallest possible size $d$ for a family ${\leq_1},\ldots,{\leq_d}$ of total orderings of $P$ whose intersection is ${\leq}$, i....

**14**

votes

**2**answers

516 views

### Is there a natural measurable structure on the $\sigma$-algebra of a measurable space?

Let $(X, \Sigma)$ denote a measurable space. Is there a non-trivial $\sigma$-algebra $\Sigma^1$ of subsets of $\Sigma$ so that $(\Sigma, \Sigma^1)$ is also a measurable space?
Here is one natural ...

**13**

votes

**2**answers

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

**13**

votes

**1**answer

871 views

### Kuratowski closure-complement problem for other mathematical objects?

The original Kuratowski closure-complement problem asks:
How many distinct sets can be obtained by repeatedly applying the set operations of closure and complement to a given starting subset of a ...

**12**

votes

**5**answers

2k views

### Explicit ordering on set with larger cardinality than R

Is it possible to construct (without using Axoim of Choice) a totally ordered set S with cardinality larger than $\mathbb{R}$?
Motivation: A total ordering is often called a “linear ordering”. I have ...

**12**

votes

**2**answers

384 views

### What is the least ordinal than cannot be embedded in $\mathbb{R}^\mathbb{R}$?

Let $\mathbb{R}^\mathbb{R}$ be the set of functions $\mathbb{R}\to\mathbb{R}$ patially ordered by eventual domination. Obviously, every ordinal below $\omega_1$ can be embedded in $\mathbb{R}^\mathbb{...

**12**

votes

**1**answer

658 views

### Converse to Banach’s fixed point theorem for ordered fields?

Suppose $R$ is an ordered field. Call a continuous map $f: R \rightarrow R$ a contraction if there exists $r < 1$ (in $R$) such that $|f(x)-f(y)| \leq r |x-y|$ for all $x,y \in R$ (where $|x| := \...

**12**

votes

**1**answer

676 views

### Does every feasible partial order relation on the natural numbers extend to a feasible linear order relation?

It is well known that every partial order on a set can be extended
to a linear order on that set. That is, for every partial order
$\lhd$ on a set $X$, there is a linear order $\prec$ on $X$ such
that ...

**12**

votes

**1**answer

346 views

### How long can a cycle of antichains in a finite partial order be?

Suppose that $X$ is a finite partially ordered set. Then a subset $A\subseteq X$ is said to be an antichain if there do not exist elements $a,b\in A$ with $a<b$. Let $\mathcal{A}_{X}$ be the set of ...

**11**

votes

**1**answer

467 views

### Partial word orders on groups

This is a followup question related to this question. Recall that a left-invariant partial order on a finitely generated group $G$ is called a partial word order if for every $a\le b\le c$ we have $|...

**11**

votes

**1**answer

539 views

### Any further applications of Freudenthal's 1936 Spectral Theorem?

Seemingly completely forgotten, back in 1936, the Dutch mathematician Freudenthal, quite well known at the time, proved his so called Spectral Theorem, see chapter 6 in Luxemburg & Zaanen : Riesz ...

**10**

votes

**5**answers

1k views

### Questions about ordering of reals and irrationals

Three problems from G.Rosenstein "Linear orderings" (from the end of Chapter 2 and beginning of Chapter 4):
1) Is there a nondecreasing function from irrationals onto reals?
2) Is there a ...

**10**

votes

**5**answers

4k views

### infinite permutations

This question is related to this one: Continued fractions using all natural integers. Suppose we have the set of natural numbers $N$ with order and we perform permutation on it. So we obtain the same ...

**10**

votes

**2**answers

380 views

### Do operations generate well-ordered sets only?

I've read @TauMu's question about the set of functions $\mathbb N\rightarrow\mathbb N$ generated from the identity map by repeatedly applying exponentiation of two already ...

**10**

votes

**2**answers

386 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

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

**10**

votes

**1**answer

808 views

### Discrete version of Nullstellensatz?

Hi. I was reading the paper "On the foundations of combinatorial theory (VI): The idea of a generating function" by Doubilet, Rota and Stanley, and there is a relation treated which is very ...

**10**

votes

**1**answer

236 views

### Order dimension and weak poset partitions

The order dimension of a poset $(P,\leq)$ is the least number of linear extensions of $(P,\leq)$ such that the intersection of these extensions is $(P,\leq)$. The wikipedia entry provides some ...

**10**

votes

**0**answers

278 views

### Computing the ordinal of a rational language well-partially-ordered by the subword relation

Let $\Sigma$ be a finite set or "alphabet", $\Sigma^*$ the free monoid on $\Sigma$ or set of "words". If $w,w'\in \Sigma^*$, write $w\leq w'$ when $w$ is a "subword" of $w'$, i.e., can be obtained by ...

**9**

votes

**4**answers

881 views

### Universal order type

Every countable order type, such as the countable ordinals, $\mathbb Z$, etc. can be embedded in $\mathbb Q$, so it is universal for countable order types. Is there a universal space for all linear ...

**9**

votes

**3**answers

239 views

### Is the homomorphism poset directed if the codomain is directed?

Let $P,Q$ be partially ordered sets (posets). We consider the set $\text{Hom}(P,Q)$ of order-preserving functions $f:P\to Q$. (We call a function $f:P\to Q$ order preserving if $x\leq y$ in $P$ ...

**9**

votes

**1**answer

172 views

### Are these two quotients of $\omega^\omega$ isomorphic?

Let $\omega^\omega$ denote the set of all functions $f:\omega\to\omega$. For $f,g\in\omega^\omega$ we say $f\simeq_{\text{fin}} g$ if there is $n\in \omega$ such that $f(k) = g(k)$ for all $k\geq n$.
...

**9**

votes

**0**answers

198 views

### Reference for sparseness of incomparability graphs implying sparseness of covering graphs

If a partial order on $n$ elements has $m$ incomparable pairs, then its covering graph (aka Hasse diagram aka transitive reduction, the graph of pairs of elements that are comparable but are not the ...

**8**

votes

**6**answers

2k views

### Generalizations of Boolean posets/lattices

A Boolean lattice has a number of rather nice properties which give it a central role in many parts of combinatorics. For instance, it's a lattice, it can be augmented with a ring structure, it can ...

**8**

votes

**4**answers

890 views

### Order types of positive reals

Suppose one has a set $S$ of positive real numbers, such that the usual numerical ordering on $S$ is a well-ordering. Is it possible for $S$ to have any countable ordinal as its order type, or are the ...

**8**

votes

**2**answers

300 views

### Posets isomorphic to their endomorphism poset

Let $(P,\leq)$ be a poset. We set $$\text{End}(P)=\{f: P\to P: f\text{ is order-preserving}\}$$ and order $\text{End}(P)$ pointwise.
Is there a poset with more than 1 point such that $P\cong \text{...

**8**

votes

**1**answer

673 views

### Which countable linear orders are $\aleph_0$-categorical?

The question is: Which countable linear orders are $\aleph_0$-categorical?
I have a bit of progress on this:
Define a discrete tuple to be a set of elements, ordered discretely, such that if $a$ and ...

**8**

votes

**1**answer

312 views

### Does every countably infinite interval-finite partial order embed into the integers?

A partially ordered set $(S,\le)$ is called interval finite if the open intervals $(x,z):=\{y|x\le y\le z\}$ are finite for all choices of $x,z$ in $S$. An embedding $(S,\le)\rightarrow(S',\le')$ of ...

**8**

votes

**1**answer

400 views

### Does this “flipping lexicographic” ordering have a standard name?

I’ve run into the following straightforward variant of lexicographic ordering, and am wondering if it has a standard name. I’ve been calling it the flipping lexicographic ordering, for evident ...

**8**

votes

**2**answers

733 views

### Is $Ded(\kappa)<Ded(\kappa)^\omega$ consistent?

Hello,
I want to ask if anyone can tells us what is known (consistently) about $Ded(\kappa)$, $\kappa$ an infinite cardinal.
Definition If there is a dense linear order w/o endpoints of size $\...

**8**

votes

**1**answer

343 views

### Decomposing posets into countably many chains

A conjecture of Galvin's is that the following is possible (which I take to mean that the consistency of the following can be proven relative to the consistency of something like ZFC, or ZFC plus some ...

**8**

votes

**1**answer

147 views

### Optimal strategy for game of 'online sorting' into a poset

Consider a single-player game played with an arbitrary finite poset, and a random number generator with a known distribution:
Each turn, the RNG produces a number, and the player must assign that ...