Questions tagged [order-theory]
The order-theory tag has no usage guidance.
645
questions
43
votes
4
answers
4k
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 ...
41
votes
3
answers
2k
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\...
35
votes
3
answers
2k
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 ...
34
votes
11
answers
3k
views
Open questions about posets
Partially ordered sets (posets) are important objects in combinatorics (with basic connections to extremal combinatorics and to algebraic combinatorics) and also in other areas of mathematics. They ...
34
votes
5
answers
1k
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
...
33
votes
7
answers
4k
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) ...
32
votes
9
answers
5k
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.
...
31
votes
3
answers
2k
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 ...
28
votes
1
answer
6k
views
What is the cofinality of the co-infinite subsets of ${\bf N}$?
Let ${\mathcal A}$ be the family of subsets $A$ of the natural numbers ${\mathbf N}$ which are co-infinite (i.e., their complement is infinite). We partially order this family by set inclusion. A ...
26
votes
3
answers
2k
views
When does a graph underlie the Hasse diagram of a poset?
For any finite poset $P=(X,\leq)$ there is a graph $G$ underlying its Hasse diagram $H=(X,\lessdot)$, so that $V(G)=X$ and $E(G)=\{\{u,v\}:u\lessdot v\}$. With that said, is it possible to ...
26
votes
3
answers
2k
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 \...
25
votes
1
answer
1k
views
Expected height of a poset?
I am interested in any known results/empirical studies done on the average height of a poset with $N$ elements. Obviously this would depend on how that poset relation was randomly defined, however, at ...
25
votes
0
answers
536
views
A conjecture about inclusion–exclusion
$\newcommand\calF{\mathcal{F}}
\def\cupdot {\stackrel{\bullet}{\cup}}
\def\minusdot {\stackrel{\bullet}{\setminus}}$This post presents a conjecture that we have with some colleagues. It is about ...
24
votes
2
answers
660
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)$...
23
votes
3
answers
2k
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?
23
votes
2
answers
1k
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 ...
22
votes
1
answer
2k
views
Why do we need "canonical" well orders?
(I asked this question on Math.SE earlier but received no response and am therefore moving it here, please note that I realise this question is probably incredibly naïve for the experienced set-...
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:
$...
19
votes
4
answers
1k
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 ...
19
votes
1
answer
1k
views
Is the theory of a partial order bi-interpretable with the theory of a pre-order?
A partial order relation $\leq$ on a set $A$ is a binary relation that is reflexive, transitive, and antisymmetric.
A preorder relation $\unlhd$ (also sometimes known as a quasi order or pseudo order) ...
19
votes
1
answer
457
views
Large Borel antichains in the Cantor cube?
Let $2^\omega$ be the Cantor cube $\{0,1\}^\omega$, endowed with the standard compact metrizable topology and the standard product measure, called the Haar measure. The Cantor cube is considered as a ...
19
votes
0
answers
765
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 $...
18
votes
3
answers
759
views
What is the minimum size of a partial order containing all partial orders of size 5?
This earlier MO question asks to find the minimum size of a partial order that is universal for all partial orders of size $n$, i.e. any partial order of size $n$ embeds into it, preserving the order. ...
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 ...
18
votes
3
answers
1k
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 ...
18
votes
4
answers
1k
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....
18
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$-...
18
votes
1
answer
1k
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 ...
18
votes
1
answer
10k
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 ...
17
votes
4
answers
3k
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 ...
17
votes
2
answers
332
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 ...
17
votes
1
answer
1k
views
Has the exponentiation of ordinals a nice geometric model?
It is well known that the sum $\alpha+\beta$ of two ordinals $\alpha,\beta$ can be defined "geometrically" as the order type of the sum $(\{0\}\times \alpha)\cup(\{1\}\times\beta)$ endowed ...
17
votes
1
answer
1k
views
How is this fixed point theorem related to the axiom of choice?
I'm hoping the answer to this is well-known.
Let $X$ be an ordered set (i.e. poset). An inflationary operator $f$ on $X$ is a function $f: X \to X$, not necessarily order-preserving, such that $f(x) \...
16
votes
4
answers
1k
views
Can Suslin (or Aronszajn) lines ever be orderings of abelian groups?
I am interested in realizing linear orders as orderings of abelian groups. In particular, can Suslin lines (and other classes of line) be realised in this way?
Let $\mathcal{C}$ be a class of (...
16
votes
3
answers
10k
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
5
answers
7k
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 ...
15
votes
3
answers
714
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{...
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 ...
14
votes
1
answer
781
views
Does there exist an ordering-functor?
This sounds like a very silly question which should have have a negative answer but I don't see an argument. The precise question is this:
Does there exist a covariant functor $ord$ from the category ...
14
votes
1
answer
312
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$.
...
14
votes
5
answers
804
views
Birkhoff's representation theorem vs matroid-geometric lattice correspondence
This question is motivated by the superficial observation that Birkhoff's representation theorem and the cryptomorphism between matroids and geometric lattices are sort of similar. The former says ...
14
votes
1
answer
2k
views
totally ordered chain in the powerset with big cardinality
Let $B$ be some set. The problem is to find a set $A\subset\mathcal{P}(B)$ of subsets of $B$ which is totally ordered by inclusion and such that there exists a bijection $A\leftrightarrow \mathcal{P}(...
14
votes
1
answer
349
views
Comparing sizes of sets of integers
Is there a total preorder $\lesssim$ on the power set of $\mathbb Z$ such that:
$A<B$ if $A\subset B$ (proper subsets are smaller)
$1+A\lesssim 1+B$ iff $A\lesssim B$ (where $1+C = \{1+c:c\in C\})...
14
votes
1
answer
1k
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 ...
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.
...
13
votes
2
answers
2k
views
Ordinals that are not sets
The class of all ordinal numbers $\mathbf{Ord}$, aside being a proper class, can be thought of an ordinal number (of course it contains all ordinal numbers that are sets, not itself). Then one could ...
13
votes
2
answers
678
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 ...
13
votes
1
answer
262
views
Can any poset of cardinality $\leq 2^{\aleph_0}$ be embedded in ${\cal P}(\omega)/(\text{fin})$?
We endow ${\cal P}(\omega)$ with an equivalence relation by saying that $A\simeq_{\text{fin}} B$ iff the symmetric difference $A\Delta B$ is finite. The resulting set of equivalence classes is denoted ...
13
votes
1
answer
938
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
4
answers
1k
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 ...