Questions tagged [order-theory]
The order-theory tag has no usage guidance.
669 questions
3
votes
0
answers
52
views
Does there exist a multi-valued "monotone" and "compact" map from a Boolean algebra to the "free" part of $\mathcal{P}(\kappa)$?
This is a follow-up to my previous question, which has a negative answer. Here is the most general version that I'm interested:
Does there exist a Boolean algebra $A$, an infinite cardinal $\kappa$, ...
- 2,830
5
votes
1
answer
148
views
Does there exist a section of $\mathcal{P}(\kappa)\to\mathcal{P}(\kappa)/(\text{fin})$ that is "nearly Boolean"?
The following might be a somewhat esoteric question:
Does there exist an infinite cardinal $\kappa$ and a section $f$ of the quotient map $\pi:\mathcal{P}(\kappa)\to\mathcal{P}(\kappa)/(\text{fin})$ (...
- 2,830
0
votes
0
answers
62
views
Co-boundary crossed homomorphism & "sign" preserving. Why 2-valued components is special?
Suppose $h_{g}: \mathbb{R}^n \to \mathbb{R}^{n-1}$ be a coboundary crossed homomorphism with action $g$ as a cyclic permutation of coordinates on $\mathbb{R}^n$ vectors. So, the acting group is a ...
- 11
3
votes
1
answer
132
views
Is the interval topology on ${\cal P}(\omega)/(\text{fin})$ connected?
If $(P,\leq)$ is a poset and $x\in X$, we let $\downarrow x = \{p\in P: p \leq x\}$, and $\uparrow x$ is defined dually. The collection $$\Big\{P\setminus (\downarrow x): x\in P\Big\} \cup \Big\{P\...
- 48.9k
0
votes
0
answers
62
views
Order-convergence and interval topology on ${\cal P}(\omega)/(\text{fin})$
On any poset $(P, \leq)$ we can consider two different topologies that arise directly from the ordering relation.
1) Order convergence topolog $\tau_o(P)$ : By a set filter $\mathcal{F}$ on $P$ we ...
- 48.9k
5
votes
1
answer
96
views
Preimage of a sublocale by a morphism of locales: description by nucleus?
For completeness of MathOverflow, and to avoid any possible misunderstanding, let me recall the following terminology and facts, which should be standard (experts skip the following 2–3 paragraphs ...
- 32.5k
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
-1
votes
0
answers
73
views
Why is there in theory no morphism/isogenies when enlarging a prime field sharing a common suborder/subgroup? [closed]
Simple question : I have a prime field having modulus $p$ where $p−1$ contains $O$ as prime factor, and I have a larger prime field $q$ also having $O$ as its suborder/subgroup. Why are there no ...
- 87
0
votes
0
answers
42
views
Topologizing quasi orders with regards to products
This morning I was asked by a colleague for the "right" way to construct a topology on a quasi-order (aka preorder, a reflexive and transitive relation) such that the topology on a product ...
- 1,322
3
votes
0
answers
114
views
Has this property of well-founded posets appeared in the literature?
Let $(P,\leq)$ be a partially ordered set. Assume that $(P,\leq)$ is well-founded. Then the levels of the poset are well-defined: $L_{0}$ is the set of minimal elements in $P$, and whenever $\mu$ is ...
- 500
4
votes
1
answer
189
views
Do idempotents in an abelian category constitute a lattice?
Consider an object $X$ in an abelian category $\mathcal{C}$. We define $\text{Idem}_{\mathcal{C}}(X)$ as the set of idempotent endomorphisms $a$ in $\text{End}_{\mathcal{C}}(X)$, meaning that $a \circ ...
3
votes
1
answer
130
views
Left shift of transfinite sequences
Background: Let $(D,\, {\leq})$ be a partial order. We consider sequences $a = (a_n)_{n \in \mathbb{N}}$ of elements of $D$. For two sequences $a$ and $b$, we lift $\leq$ (point-wise) to sequences by
...
- 351
3
votes
1
answer
136
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
79
views
Are finitely discriminable groups the compact elements of the poset of marked groups?
A finite discriminating family in a group $G$ is a finite set of non-identity elements such that every non-trivial normal subgroup of $G$ contains one of these elements.
A $k$-marked group is a group ...
- 543
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
2
votes
0
answers
71
views
Lexicographically largest incidence matrix
I have simple algorithmic question, but I can't find any source where this algorithm is explained in details.
Let's assume that we have incidence (with 0 and 1 values) matrix of size $m\times n$. Let ...
- 501
0
votes
1
answer
234
views
Minimum number of elements needed to represent a lattice with a union-closed family of sets
I know that it is possible to represent every finite lattice $L$ with a union-closed family $\mathcal{F}$ containing the empty set: for every $x\in L$, let $S_x=\{y\in L\, :\, y\not\geq x\}$ and $\...
- 1,000
2
votes
0
answers
109
views
Sublattice isomorphisms
Let $L$ be a non-distributive complete (bounded) lattice with the greatest element $1$ and the smallest element $0$.
Definitions: For a given $x,y\in L$, let's use the notation $[x,y] := \{z\in L: x\...
- 2,605
2
votes
1
answer
285
views
Size of antichains in powerset of $\mathbb N$
Take a countably infinite set $S$, say $\mathbb N$. Is it possible for there to be an antichain in $\mathcal P(S)$ (with the inclusion ordering) of continuum cardinality?
- 33
3
votes
1
answer
119
views
Non-isomorphic $T_0$-spaces with order-isomorphic topologies
Are there non-isomorphic $T_0$-spaces $(X_i, \tau_i)$ for $i = 1,2$ such that $\tau_1 \cong \tau_2$ when considered as partially ordered sets?
- 48.9k
1
vote
0
answers
78
views
Set-theoretic trees with ordering between siblings
In set-theoretic trees, we have the binary relation $<_T$ (which defines the "ancestor-descendant" ordering). This relation is partial, as children are incomparable in that ordering.
...
6
votes
3
answers
236
views
Refinement-minimal intersecting covers
Motivation. Yesterday I was sitting idly in the train, contemplating the train network. I noticed that a lot of lines (not all) intersected, and some pairs of lines intersected in quite a few stations....
- 48.9k
2
votes
2
answers
271
views
Is every finite lattice isomorphic to a union-closed family of sets containing $\emptyset$?
If a family of sets $\mathcal{F} \subseteq 2^E$ is union-closed and contains $\emptyset$, then $\mathcal{F}$ forms a lattice under the set-inclusion order. To see this, note that unions give the join ...
- 145
5
votes
0
answers
107
views
Structure of well-ordered commutative monoids
Let $(M,+)$ be a commutative monoid. Let $<$ be a well-ordering on $M$, where
$\forall a\in M,\ 0\leq a$
$\forall a,b,c\in M,\ a<b\Rightarrow a+c<b+c$
The first condition means $M$ will be ...
- 18.7k
0
votes
1
answer
211
views
Permutations which respect a partial order
I have been studying the following situation, and I have a claim I believe to be true, but am unsure on how to approach it. I would appreciate any references I could look into where others have ...
2
votes
1
answer
233
views
Order on Euclidean space in which a finite poset embeds
Fix positive integers $k$ and $n$.
For which finite posets $(X,\lesssim)$ with $\#X=k$ does there exist an order embedding $\phi\colon(X,\lesssim)\to (\mathbb{R}^n,\le)$, where $\le$ is the standard ...
- 5,405
29
votes
0
answers
665
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 ...
- 391
6
votes
1
answer
254
views
Fixed points for finitary distributive lattices bijection
Birkhoff's Fundamental Theorem of Finite Distributive Lattices says that there is a bijection
$$ \{ \textrm{finite posets}\} \to \{ \textrm{finite distributive lattices}\} $$
$$ P \mapsto J(P), $$
...
- 24.2k
3
votes
1
answer
222
views
Embedding of a poset with "desirable" characteristics
Let $(P, \succeq)$ be a poset (you can assume $\succeq$ is not empty). I am interested in finding a poset $(X, \succeq^*)$ that embeds $(P, \succeq)$, and $\forall x,y \in X$ both of the following ...
- 97
5
votes
1
answer
376
views
Kuratowski's 14 theorem and universal algebra
For a tuple of functions $\overline{p}$ on a set $Y$, let $cl_{\overline{p}}$ be the associated closure operation: $cl_{\overline{p}}(Z)$ is the smallest subset of $Y$ containing $Z$ and closed under ...
- 21.2k
4
votes
1
answer
216
views
Lattice description of matroid duality
Apologies for this very basic question in matroid theory, but I could not find anything about it online after a bit of searching.
There is a well-known bijective correspondence ("cryptomorphism&...
- 24.2k
0
votes
0
answers
117
views
"Infima" and "suprema" in the homomorphism preorder on hypergraphs on $\omega$
$\newcommand{Po}{{\cal P}(\omega)}$
$\newcommand{lh}{\leq_{\text{hom}}}$
If $H_i = (V_i, E_i)$ are hypergraphs for $i = 1,2$, then a map $f:V_1 \to V_2$ is said to be a (hypergraph) homomorphism if $f(...
- 48.9k
1
vote
0
answers
73
views
Ordered combinatorial classes and partitions
Let $\mathcal{C}$ be a combinatorial class and let $\leq$ be a partial order on $\mathcal{C}$. We say that $(\mathcal{C},\leq)$ is an ordered combinatorial class if for all $x,y\in\mathcal{C}$, $$x&...
- 11
4
votes
0
answers
125
views
Can we extend "every finite lattice is a sublattice of partitions of a finite set" to linear and/or finitary lattices?
Pudlák and Tůma https://link.springer.com/article/10.1007/BF02482893 proved that every finite lattice can be
embedded as a sublattice of the partition lattice of a finite set.
Can this be generalized ...
- 429
9
votes
1
answer
364
views
Are the Boolean algebras ${\cal P}(\omega)/(\text{fin})$ and ${\cal P}(\omega)/(\text{thin})$ isomorphic?
A set $A\subseteq \omega$ is said to be thin if $$\lim\sup_{n\to\infty}\frac{|A\cap \{0,\ldots, n\}|}{n+1} = 0.$$
We say for $A, B\subseteq \omega$ that $A\simeq_\text{fin} B$ if the symmetric ...
- 48.9k
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
12
votes
1
answer
525
views
Is the Tukey order well-founded
Consider the Tukey order restricted to directed orders of the form $(U,\supseteq)$, where $U$ is an ultrafilter on $\omega$. It is defined as follows:
For two ultrafilters $U,W$ on $\omega$, we say ...
- 123
3
votes
0
answers
176
views
Can the set of parafinite congruences be descriptive-set-theoretically complicated?
Fix an algebra $\mathfrak{A}$ with underlying set $\mathbb{N}$ and finite language $\Sigma$. The set of congruences on $\mathfrak{A}$ is a closed subset $C_\mathfrak{A}$ of $2^\mathbb{N}$ (with the ...
- 21.2k
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
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
3
votes
1
answer
152
views
Posets of equational theories of "bad quotients"
This is a follow-up to an older question of mine:
Suppose $\mathfrak{A}=(A;...)$ is an algebra (in the sense of universal algebra) and $E$ is an equivalence relation - not necessarily a congruence - ...
- 21.2k
1
vote
1
answer
83
views
Sizes of linearly ordered subalgebras of powers
On the grounds that I'm currently teaching a linear algebra class and I enjoy making my students furious, let a linear algebra be an algebra $\mathcal{A}$ in the sense of universal algebra equipped ...
- 21.2k
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.6k
4
votes
2
answers
274
views
Does strong stochastic ordering exist?
For two probability measure $\mu$ and $\nu$ on $\mathbb{R}$, we call $\mu$ is stochastically smaller than $\nu$ (i.e., $\mu\leq\nu$) , if $\int f \, d\mu\leq\int f \, d\nu$ for any nonnegative bounded ...
- 43
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
3
votes
1
answer
213
views
Reference Request for "Finite Semilattice with Top and Bottom is a Lattice"
Let $\mathcal{O}(P)$ be a finite, completely distributive lattice of all lower sets ordered by set inclusion.
Moreover, let $K =\; \mathrel{\{} h(x) \mathrel{|} x \in \mathcal{O}(P) \mathrel{\}}$ be ...
- 33
1
vote
1
answer
344
views
Is there anyway to formulate the Alexandrov topology algebraically?
One knows that the Alexandrov topology on a preordered set is the finest topology that induces the same [specialization] preorder on the set.
Given this, one finds a one-to-one correspondence between ...
- 612
5
votes
2
answers
478
views
Generalization of the concept of a measure
Consider the following generalization of the concept of a measure:
Let $L = (X, \lor, \land, \bot)$ be a semi-bounded lattice.
Let $M = (Y, \bullet, e)$ be a commutative monoid.
An $(L, M)$-measure is ...
- 2,203
4
votes
1
answer
182
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,644
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