All Questions
Tagged with order-theory reference-request
69 questions
13
votes
2
answers
1k
views
What's the deal with De Morgan algebras and Kleene algebras?
The notion of Boolean algebras, and the corresponding classical propositional logic, is very standard, and it is easy to find information about them (for example, among many other such works, there is ...
- 32.5k
3
votes
1
answer
135
views
Concentration of sample median for iid Gaussians
Let $X_1, \dots, X_n$ be iid according to $\mathcal{N}(0, 1)$, and let $M_n$ be the median of the $X_1, \dots, X_n$. I recall reading a concentration inequality for $M_n$ that was (roughly) as follows:...
- 75
6
votes
1
answer
237
views
Resource on how the definitions of subobjects for various categories can vary
I am looking for a reference on the different possible definitions of subobjects. According to a particular friend of mine, subobjects should be at least monomorphisms (up to slice isomorphism) and at ...
- 591
9
votes
1
answer
542
views
Reference request: number of antichains of a partially ordered set
Let $\mathbb{N}$ denote the set of all positive integers. For each $n \in \mathbb{N}$, define the set $$ P_n = \{ (a,b) \in \mathbb{N} \times \mathbb{N} : 1 \leq a \leq b \leq n \} $$ and consider the ...
- 563
0
votes
0
answers
75
views
Conditions for logarithmic upper bound on size of antichains in a partial order
Suppose I have a partial order $(P,\le)$ (in practice I have a very specific one, but let's start with a generic question).
Are there known conditions that would imply that the size of any antichain ...
- 121
7
votes
1
answer
579
views
Progress on determining which partial orders embed into the rationals
The following result is relatively well-known: (for example in Math StackExchange answer #37161)
For every countable linear order $(R,\prec)$, there is an $X\subseteq\mathbb Q$ such that $(R,\prec)$ ...
- 2,031
5
votes
0
answers
201
views
Is this "trimming" of a supersolvable semimodular lattice known?
Let $L$ be a finite (upper) semimodular lattice. Recall that this means $L$ is graded and its rank function $\rho\colon L \to \mathbb{N}$ satisfies
$$ \rho(x) + \rho(y) \geq \rho(x\vee y)+\rho(x \...
- 24.2k
3
votes
2
answers
320
views
Topological characterisations of properties of posets
Finite connected partially ordered sets are in bijective correspondence to connected finite topological spaces that satisfy T_0, see for example the Wikipedia article Finite topological space. Here ...
- 26.5k
2
votes
1
answer
94
views
Request for literature recommendations on isotonic mappings
An isotonic mapping is a function between two partially ordered sets that preserves the ordering between the elements. Specifically, given two partially ordered sets $(X,\le)$ and $(Y,\le)$, a ...
- 21
4
votes
1
answer
209
views
Exactly how much (and how little) can partial ordered sets (classes) embed to the cardinalities
In the paper "Convex Sets of Cardinals", Truss mentioned a result of Jech:
If $M$ is a countable transitive model of ZFC, and $(P,<)∈M$ is a poset, then there exists a Cohen extension of ...
- 1,676
4
votes
0
answers
234
views
To whom is the classification of atomic, modular finite lattices due?
Here lattice means a poset with meets and joins. A lattice is called atomic if every element is a join of atoms. There are a few different ways to define modular for finite lattices: one is that the ...
- 24.2k
1
vote
0
answers
95
views
Reference request: Time and proofs of shared pasts
Is there research about structures for notions of time with distributed systems of information, as with blockchains?
I am thinking of tuples $(I, T, P, A, \prec, s, \eta, u)$ where
$I$, $T$ and $P$ ...
- 3,249
2
votes
0
answers
97
views
References discussing the category of ordered commutative rings
Is there a reference anywhere discussing the category of ordered commutative rings?
I'm thinking of ordered commutative rings and ring homomorphisms preserving the order, but I would also be ...
- 10.1k
3
votes
1
answer
162
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,585
3
votes
0
answers
95
views
When is it possible to extend several linear orders defined "locally" into a single linear order defined "globally"?
This is a somewhat fuzzy question, so I will try my best to give a formulation which includes everything relevant while excluding everything else. I would like to find out if anyone else has studied ...
- 183
3
votes
1
answer
173
views
Well-foundedness of divisibility vs well-foundedness of right- and left-divisibility
Say that a preorder (i.e., a reflexive and transitive binary relation) $\preceq$ on a set $X$ is
artinian if there is no sequence $(x_n)_{n \ge 1}$ of elements of $X$ with $x_{n+1} \prec x_n$ for ...
- 10.5k
10
votes
1
answer
396
views
Generalising the union-closed sets conjecture from lattice to a larger class of posets
(edit: I decided to simplify the question and only pose it for bounded posets first)
The Union-closed sets conjecture is equivalent for lattices P to:
There exists a join-irreducible element $a$ with ...
- 26.5k
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
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
5
votes
0
answers
109
views
Reference request: a survey of (linear) Krein-Rutman theory
I'm looking for a survey article or book chapter where a rather exhaustive treatment of the Krein-Rutman theory of positive linear operators an ordered Banach spaces is given.
Motivation. Some ...
- 12.5k
2
votes
1
answer
88
views
Dubious matrix monotonicity
Coming from a problem in game theory, I arose at some dubious monotonicity like property for matrices of the following art. Let $H=\lbrace h\in\mathbb{R}^{n}\colon h_{1}+\dots+h_{n}=0\rbrace$. I'm ...
- 289
2
votes
1
answer
430
views
Generalizing König's Lemma
In some recent work, I need a strengthening of König's Lemma to "trees" of arbitrary ordinal heights. Trees, in this context, are really just well-founded partially ordered sets. See, for instance, ...
- 18.7k
1
vote
2
answers
195
views
Reference request: lower sets of a preorder form a lattice
Consider a set $S$ with a preorder $\preceq$ (a preorder is a reflexive and transitive relation). A lower set $A$ of $S$ is defined as a subset of $S$ such that for all $x \in S$ and $y \in A$, if $...
- 695
2
votes
1
answer
176
views
Generating totally ordered free commutative monoids
Let’s say I have a set $A$. I build the free commutative monoid $M$ generated by $A$.
When can a well-order on $A$ be extended to $M$, in a way that is compatible with its monoid structure? I am ...
- 341
5
votes
2
answers
352
views
The cofinality of the poset $[\kappa]^{<\kappa}$ for a singular cardinal $\kappa$
For a cardinal $\kappa$ let $[\kappa]^{<\kappa}$ denote the family of subsets of cardinality $<\kappa$ in $\kappa$. The family $[\kappa]^{<\kappa}$ is endowed with the partial order of ...
- 41.8k
4
votes
1
answer
119
views
Antisymmetry of the stochastic order
An ordered topological space is a topological space $X$ equipped with a partial order $\leq$ which is closed as a subset of $X\times X$. By antisymmetry of $\leq$, it follows that the diagonal of $X$ ...
- 6,406
11
votes
2
answers
682
views
On Applications of Forcing in Domain Theory
An interesting feature of domain theory is to use partial orders in order to provide a mathematical model for the computational approximation in a potentially infinite computational process (e.g. ...
3
votes
2
answers
138
views
In the context of directed graphs is it standard notation to allow an element of an independent vertex set to be contained in a loop?
Given any relation $R$, that is, any set of ordered pairs, we can associate a unique digraph $D$ to our relation $R$ by setting $D=(\text{fld}(R),R)$ where $\text{fld}(R)=\text{dom}(R)\cup\text{rng}(R)...
- 2,506
5
votes
2
answers
337
views
A "strong" Galois-Tukey connection between orders with suborders
(Background, may be skipped by the knowledgeable reader: A Galois-Tukey connection between two partial orders $(P,\le)$ and $(Q,\le)$ is a pair of maps $\varphi^+:P\to Q$ and $\varphi^-:Q\to P$ ...
- 14k
8
votes
0
answers
227
views
Is there a 'local' version of Near Coherence of Filters?
The axiom Near Coherence of Filters (NCF) is known to be independent of ZFC.
Axiom (NCF I): For any two free ultrafilters $\mathcal D$ and $\mathcal E$ on $\mathbb N$, there exist finite-to-one ...
- 1,955
7
votes
0
answers
118
views
Dimension of a union of downsets
We have established the following result regarding the Dushnik–Miller dimension of posets.
Let $P$ be a poset with downsets $C, D \subseteq P$. If the dimensions of $C$ and $D$ are $m$ and $n$, ...
- 316
5
votes
0
answers
64
views
Characters on monotone functions
Characters on the semigroup $(C_{+}^{b}(\mathbb{R}^{d}),+)$, i.e. on bounded positive continuous functions with the ususal pointwise addition, are known to be of the form $C_{+}^{b}(\mathbb{R}^{d})\ni ...
- 289
0
votes
0
answers
131
views
terminology: monotone maps of posets such that the image of a lower set is a lower set
How are called in combinatorics
monotone maps of partially ordered sets such that the image of a lower set is a lower set, i.e. closed (or open) maps of finite topologies? Is there a classification ...
- 113
3
votes
0
answers
132
views
Duality for continuous lattices based on [0, 1]
A continuous lattice may be defined as a complete lattice in which arbitrary meets distribute over directed joins. A continuous lattice is naturally regarded as an algebraic structure where the ...
- 133
1
vote
0
answers
98
views
Continuous dcpos are $\omega_1$-algebraic
Recall that a poset is directed if every finite subset has an upper bound, and directed-complete (a dcpo) if every directed subset has a join (supremum). In a dcpo, $x \ll y$ is defined to mean that ...
- 133
8
votes
2
answers
483
views
Posets obtained from a semigroup by the definition $x \leq y \iff x \cdot y = x$
A po-groupoid is a groupoid $\langle A,\cdot\rangle $ such that the relation
defined by
$$
x \leq y \text{ if and only if } x \cdot y = x
$$
is a partial order on $A$, the order related to $\langle ...
- 1,124
1
vote
0
answers
731
views
"Downward closed" relation on a poset
I say that a relation $R$ on a poset $P$ is downward closed if for each $(x,y)\in R$, and $x'\le x$, then $(x',y)\in R$.
Is there a reference where this thing is studied, maybe under a different name?
...
- 13.6k
5
votes
1
answer
377
views
Generalized ordering on simplicial complex
The vertices of simplicial complexes are usually totally ordered so that face maps of each simplex can be defined easily for the purposes of homology. That gives an "oriented" simplicial complex.
But ...
- 221
3
votes
0
answers
119
views
Generalizing disjointness
The following definition generalizes set-theoretic disjointess:
Definition 0. (Autonomy). Given a Lawvere theory $\mathsf{T}$, a $\mathsf{T}$-algebra $X$, and an indexed family $S$ of subalgebras ...
- 3,793
1
vote
2
answers
248
views
Is there a name for a partial order in which there is a countable chain which "dominates" the whole space?
Is there a name for a partial order $\preceq$ on a set $X$ with the following property: "there exists a countable set $S \subset X$ such that for all $x \in X$ there exists $y \in S$ with $x \preceq y$...
- 708
6
votes
2
answers
412
views
Characterising subsets of the reals as ordered spaces
There are concise and elegant characterisations of the real line as a topological space and as an ordered space in the literature. I am interested in the harder case of characterising subsets of the ...
- 188
2
votes
0
answers
116
views
Isomorphic subcategories of directed graphs and presets
For the purposes of this post, a digraph (directed graph) has neither loops nor multiple parallel edges, and a preset is an ordered pair consisting of a set $S$ and a preorder (viz., a reflexive and ...
- 10.5k
3
votes
1
answer
210
views
Terminology question for maps between posets
Let $P$ and $Q$ be two poset (partially ordered sets) and $\phi : P \to Q$ an order-preserving function.
I would like to know whether there is a name and perhaps a different characterizations of such ...
- 408
0
votes
1
answer
363
views
Examples of groups such that order isomorphism of the subgroups of $G\times G$ and $H\times H$ does not imply isomorphism of $G$ and $H$
Let $G$ and $H$ be groups, $\operatorname{Sub}(G\times G)$ be the set of all subgroups of $G\times G$ and $\operatorname{Sub}(H\times H)$ be the set of all subgroups of $H\times H$. Assume there ...
- 1,145
4
votes
2
answers
393
views
Embedding a linearly ordered free monoid into a linearly ordered group
A linearly ordered (shortly, l.o.) monoid is a triple $\mathbb M = (M, \cdot, \le)$ for which $(M, \cdot)$ is a (multiplicatively written) monoid and $\le$ is a total order on $M$ such that $xy < ...
- 10.5k
2
votes
1
answer
208
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 ...
- 3,793
2
votes
0
answers
417
views
An equivariant Hahn embedding theorem?
The Hahn Embedding Theorem asserts that for any (linearly) ordered abelian group $\Lambda$, there exists a linearly ordered indexing set $\Omega$ such that $\Lambda$ admits an order-preserving group ...
- 1,089
2
votes
1
answer
260
views
Characterizing Inf and Sup sets
For a poset $(X,R)$, where $R$ is a partial order on $X$,
let $\operatorname{Inf}(R)$ be the set of all $A\subseteq X$ which have an infimum in $(X,R)$.
let $\operatorname{Sup}(R)$ be the set of all $...
- 1,145
5
votes
1
answer
177
views
Reference for statement that almost every $n$-element partial order has trivial automorphism group
I'm looking for a reference for the statement that almost every partial order on $n$ elements has trivial automorphism group. I've been told that this is a folklore result. Does anyone know of a ...
- 462
2
votes
1
answer
131
views
Has the single sorted case of formal concept analysis been investigated?
A formal context in formal concept analysis is a triple $K = (G, M, I)$ where $G$ is a set of objects, $M$ is a set of attributes and the binary relation $I \subset G \times M$ shows which objects ...
- 2,464