Questions tagged [order-theory]
The order-theory tag has no usage guidance.
118 questions
8
votes
2
answers
697
views
Order type of $\alpha$-computable well-orderings
One of the nice features of the first admissible ordinal after $\omega$, i.e. $\omega_1^{CK}$, is that it is the collection of ordinals whose order type is that of a computable well-ordering on $\...
- 2,221
16
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}(...
- 642
4
votes
3
answers
531
views
Antichain on $\mathcal{P}(\omega)/fin$ of cardinality $2^{\aleph_0}$?
We define an equivalence relation on $\mathcal{P}(\omega)$: for $x,y\in\mathcal{P}(\omega)$ we say $$x\simeq_{fin} y \text{ iff there is } n \in \omega \text{ such that }
x\setminus \{0,\ldots,n\} = y ...
- 48.9k
34
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 ...
- 65.4k
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.
...
- 236k
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 ...
- 1,872
12
votes
11
answers
1k
views
Lattices on classical combinatorial families
I am asking for examples of lattices defined on classical combinatorial families, such as Permutations, Catalan objects, set partitions or integer partitions, graphs.
I am mosty interested in lattices ...
- 5,822
3
votes
1
answer
318
views
Properties of the interval topology of the lattice of functions
Let $(P,\leq)$ be a poset. The interval topology $\tau_i(P)$ on $P$ is generated by
$$\{P\setminus\downarrow x : x\in P\} \cup \{P\setminus\uparrow x : x\in P\},$$
where $\downarrow x = \{y\in P: y\...
- 48.9k
2
votes
1
answer
973
views
Compactness and completeness in Gödel logic
The standard proof of the completeness theorem in first-order Gödel logic is based
on a first-order countable language. I want to know that is there any proof of the completeness theorem in first-...
- 49
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
...
- 236k
24
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 ...
- 236k
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 ...
- 63.1k
16
votes
4
answers
4k
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 ...
- 1,593
15
votes
3
answers
731
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{...
- 173
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 ...
- 656
7
votes
2
answers
544
views
A linearly orderable monoid which does not embed into a linearly orderable group
It is known (after an example of A.I. Mal'cev) that there exist cancellative semigroups which do not embed into a group. On the other hand, it is not difficult to see that every linearly orderable ...
- 10.5k
6
votes
1
answer
223
views
Minimal Hausdorff topologies compatible with a bunch of functions
Let $X$ be an infinite set, let ${\cal F}$ be a set of functions $f: X\to X$. We say that a topology $\tau$ is compatible with ${\cal F}$ if every $f\in {\cal F}$ is a continuous function $f:(X, \tau)\...
- 48.9k
5
votes
3
answers
542
views
Congruences that aren't "finite from above"
Let $\mathfrak{A}=(A;...)$ be an algebra in the sense of universal algebra. Say that a congruence $\sim$ on $\mathfrak{A}$ is parafinite iff there is an equivalence relation $E\subseteq A^2$ with ...
- 21.2k
4
votes
2
answers
467
views
Is every finite poset a subset of a finite complemented distributive lattice?
Let $(X,\succeq)$ be a poset. I have the following two questions:
Is it true that there exists a finite complemented distributive lattice (a Boolean lattice) $(S, \succeq^*)$ such that $X\subseteq S$ ...
- 97
3
votes
1
answer
146
views
Maximal elements in the partially ordered set of image spaces
If $(X,\tau)$ is a topological space, let $\text{Im}(X)$ denote the collection of subsets $S$ of $X$ such that there is a continuous function $f:X\to X$ with $\text{im}(f) = S$.
Is there a space $(X,\...
- 48.9k
3
votes
1
answer
228
views
Computing the Heyting operation on the frame of nuclei
(The following definitions are meant to be standard and are reproduced for completeness of the question.) A frame is a partially ordered set in which every finite subset has a greatest lower bound (“...
- 32.5k
2
votes
1
answer
151
views
Efficiently embedding finite Boolean algebras into lattices of set partitions?
Let $P_n$ be the lattice of set partitions of $[n] = \{1,2,\dots,n\}$, let $B_n$ be the Boolean algebra of subsets of $[n]$.
Is there some $n_0$ such that for all $n \ge n_0$ it is possible to ...
- 2,350
1
vote
1
answer
142
views
Congruences that aren't "finite from above," take 2: semigroups
This is a hopefully less trivial version of this question. Briefly, say that a congruence is parafinite if it is the largest congruence contained in some equivalence relation with finitely many ...
- 21.2k
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\...
- 236k
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) ...
- 11.2k
24
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?
- 343
20
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:
$...
- 6,819
18
votes
1
answer
11k
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 ...
- 321
15
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.7k
14
votes
1
answer
318
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$.
...
- 48.9k
12
votes
1
answer
898
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| := \...
- 19.7k
12
votes
3
answers
322
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$ ...
user62017
11
votes
1
answer
418
views
A monotone countably cofinal function from $\omega^\omega$ to $\omega^{\omega_1}$
For a set $X$ we endow the set $\omega^X$ of all functions from $X$ to $\omega$ with the natural partial order $\le$ defined by $f\le g$ iff $f(x)\le g(x)$ for all $x\in X$.
A function $f:\omega^\...
- 41.8k
10
votes
0
answers
400
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 ...
- 32.5k
10
votes
1
answer
889
views
What is the theory of the random poset?
$\DeclareMathOperator\Th{Th}$The random poset is the Fraisse limit of the class of finite posets, just like the random graph is the Fraisse limit of the class of finite graphs? That is, the random ...
- 4,597
10
votes
1
answer
821
views
How can you order a free group?
A left order on a (discrete) group $G$ is a total order on $G$ satisfying $\forall g,h,k \in G: g < h \implies kg < kh$. A right order is defined symmetrically, and a biorder is an order that is ...
- 6,652
10
votes
1
answer
492
views
is there a ‘nice’ lattice on the set of unlabelled graphs with $n$ vertices?
It is easy to endow the set of vertex-labelled graphs with $n$ vertices with a lattice structure: take the union and the intersection of the edge set as meet and join respectively.
However, I wonder ...
- 5,822
10
votes
1
answer
904
views
A categorical characterization of the lexicographic order
In $Pos$ (the category of partial ordered sets and order preserving maps) there is the categorical product of two objects, but on the set product there is (naturally) also the lexicographic order. I ...
- 4,165
10
votes
0
answers
381
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 ...
- 236k
9
votes
2
answers
1k
views
Given a cardinal k, what's the biggest dense linear order with a dense subset of size k?
It's not hard to show that for any cardinal $\kappa$, there is no dense linear order without endpoints (DLO) of size greater than $2^{\kappa}$ that has a dense subset of size $\kappa$. But one can ...
- 3,982
8
votes
1
answer
436
views
Terminology question for poset maps
Is there a standard name for order-preserving maps $f\colon P\to Q$ of posets with the property that the image of a lower set is a lower set, or equivalently if $q\leq f(p)$ then there exists $p'\leq ...
- 38.6k
8
votes
1
answer
634
views
Verification of a maximal antichain
In order theory, an antichain (Sperner family/clutter) is a subset of a partially-ordered set, with the property that no two elements are comparable with each other. A maximal antichain is the ...
- 37
8
votes
1
answer
390
views
Order bounded version of monotone complete $C^*$-algebras
Let $A$ be a $C^*$-algebra with self-adjoint part $A_{\operatorname{sa}}$. Then $A$ is called monotone complete if every increasing norm bounded net in $A_{\operatorname{sa}}$ has a supremum (with ...
- 12.5k
8
votes
1
answer
356
views
Example of trickiness of finite lattice representation problem?
I'm trying to come up with a good explanation for my students of why the finite lattice representation problem is difficult. I've already shown that the "greedy approach" to representing the ...
- 21.2k
8
votes
2
answers
1k
views
How this set of functions is ordered?
Notation:
$k, m, n$ are non-negative integers
$f, g, h$ are functions $\mathbb{N} \to \mathbb{N}$
$f^k$ is $k$-th iterate of the function $f$: $f^0(n)=n, f^{k+1}(n)=f^k(f(n))$
$f \prec g$ means ...
- 6,819
8
votes
1
answer
403
views
Smallest relation in complement of partial order that prohibits its extension
Let $P$ be a partial order on a finite set $S$ (assume that every element is related to at least one other element besides itself…this raises a few quick questions: is this implied by the definition ...
- 870
8
votes
1
answer
345
views
Partial Orders realized by Prime Ideals on commutative rings
Is there a general criterion for which partial orders can be realized by the prime ideals of commutative rings (like we have for topological spaces - https://en.wikipedia.org/wiki/Spectral_space)?
...
- 529
7
votes
4
answers
2k
views
Strict and non-strict orderings
Consider a set $A$ equipped with two binary relations $\le$ and $<$, related in the appropriate ways for the strict and non-strict version of an ordering. One might make different choices about ...
- 66.8k
7
votes
1
answer
278
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
7
votes
1
answer
434
views
Monotonic maximal chains in a Coxeter group
Let $(W, S)$ be a Coxeter system, and let $T = \bigcup_{w \in W, s \in S} wsw^{-1}$. Associated to every element $t \in T$ is a unique positive root $\alpha_t \in \Phi^{+}$ considered as a vector in ...
- 118k