All Questions
Tagged with order-theory lattice-theory
137 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
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 ...
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
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
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
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
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
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
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
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
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
13
votes
1
answer
283
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 ...
- 48.9k
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
1
vote
0
answers
75
views
When can we separate two pairs in ${\mathbb H}_n$, although it is not a lattice?
Recall that a lattice is a partially ordered set $E$ for which any pair $a,b\in E$ admits a least upper bound and a greatest lower bound. Remark that given four elements $a_i,b_j$ ($j=1,2$), in order ...
- 52.3k
6
votes
1
answer
356
views
Is every homogeneous poset a lattice?
A poset $(P,\leq)$ is homogeneous if $P\cong [a,b]$ for all $a,b\in P$ with $a<b$ (where $[a,b] := \{x\in P: a\leq x\leq b\}$).
Examples of homogeneous posets include $[0,1]$, $[0,1]\cap \mathbb{Q}$...
- 48.9k
2
votes
0
answers
105
views
What is known about sublocales defined by regular nuclei?
(For basic terminology, which is supposed to be standard anyway, see this other question, which inspired this one.)
I am interested in nuclei $j\colon L\to L$ on a frame $L$ which are regular elements ...
- 32.5k
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
5
votes
2
answers
496
views
Do germs of open sets around a point form a frame?
Let $X$ be a topological space and $x \in X$ a point. Let $\Omega$ be the set of open sets (viꝫ. the topology) of $X$, and $\Omega_x$ the set of germs around $x$ of open sets, that is, $\Omega_x = \...
- 32.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
2
votes
0
answers
114
views
Product-decomposition of ${\cal P}(\omega)/\rm{fin}$ [closed]
For $A,B\in {\cal P}(\omega)$ let us say that $A\simeq_{\rm{fin}} B$ if both $A\setminus B$ and $B\setminus A$ are finite. It is easy to see that this establishes an equivalence relation on ${\cal P}(\...
- 48.9k
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
2
votes
0
answers
52
views
Can we decompose an increasing net of functions into two increasing nets with prescribed supports?
Let $K$ be a compact Hausdorff space and let $U,V\subset K$ be open. Let $\left(f_{i}\right)_{i\in I}$ be an increasing net of continuous non-negative functions such that $f_{i}\le 1$ and $f_{i}$ ...
- 5,529
10
votes
4
answers
928
views
Are arbitrary nonempty intersections of principal filters principal?
Suppose $\langle L,\leq\rangle$ is a lattice with join $\sqcup$. Let $F_1$ and $F_2$ be principal filters on $L$. Thus, for $i\in I=\{1,2\}$ there are $x_i\in L$ so that $F_i=\{y\in L:x_i\leq y\}$.
In ...
- 345
6
votes
0
answers
188
views
Natural bijection between join- and meet-irreducibles in modular lattices?
A well known property of finite modular lattices is that they have the same number of join-irreducible and meet-irreducible elements. I was wondering if there exists a natural bijection between these ...
- 3,513
14
votes
5
answers
881
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 ...
- 3,513
5
votes
1
answer
218
views
Classification of multiplicative lattices
Question 1:Is there a classification of finite lattices which admit a multiplication making them into a finite multiplicative lattices? (see https://encyclopediaofmath.org/wiki/Multiplicative_lattice ...
- 26.5k
7
votes
0
answers
139
views
poset of lattice properties
Is there a good overview of the dependencies between properties that a (finite) lattice poset can have?
To give a practical example, I was looking for a property weaker than congruence uniform and ...
- 5,822
5
votes
0
answers
197
views
Weak compactness is to trees as [?] is to lattices?
Let $\kappa$ be an inaccessible cardinal. Recall that $\kappa$ is weakly compact if every tree of height $\kappa$ has either a level of size $\kappa$ or a branch of size $\kappa$.
So if $\kappa$ is a ...
- 63.9k
2
votes
1
answer
119
views
Dedekind-MacNeille completion of ${\cal P}(\omega)/({\rm fin})$
Let ${\cal P}(\omega)/({\rm fin})$ be the quotient of the Boolean algebra ${\cal P}(\omega)$ where two sets are considered to be equivalent if they differ by a finite number of elements.
It turns out ...
- 48.9k
3
votes
2
answers
504
views
"Pseudo-Boolean" lattice (almost every element has several complements)
If $(L,\leq)$ is a lattice with bottom element $0$ and top element $1$ and $x\in L$ we say that $y$ is a complement of $x$ if $x\vee y = 1$ and $x\wedge y = 0$.
Is there a lattice $(L,\leq)$ with more ...
- 48.9k
2
votes
0
answers
150
views
In a constructive order/lattice theory are the arbitrary join and the weak suprema the same?
For a poset $X$ we define an upperbound $w \in X$ of a subset $S \subseteq X$ to be a weak-supremum if
$(\forall a \in S (a \leq b)) \implies w \leq b$.
While a supremum is defined more carefully (in ...
- 411
3
votes
0
answers
214
views
Does every finite lattice embed into a finite Eulerian lattice?
A finite Boolean lattice is a lattice isomorphic to the subset lattice of a finite set. Every Boolean lattice is Eulerian, namely, a graded lattice $L$ such that $\mu(a,b) = (-1)^{|b|-|a|}$ for all $a,...
2
votes
1
answer
249
views
closure operator on a complete lattice arising from adjunction on lattice itself
Define a closure operator on a complete lattice $L$ as a function $f:L \to L$ which is order preserving and idempotent and satisfies $x \leq fx$.
Every closure operator arises from an adjunction ...
- 121
8
votes
1
answer
551
views
Can one characterize maximal antichains in terms of distributive lattices?
This is inspired by the recent question Verification of a maximal antichain
The celebrated duality between finite posets and finite distributive lattices has several nice formulations. One of them ...
- 18.4k
0
votes
1
answer
129
views
Ordering preserved by an inverse frame homomorphism
Recall that a frame homomorphism $h:L\to M$ is called ($L$ and $M$ are frames):
Dense if, for any $x ∈ L$, $h(x) = 0$ implies $x = 0$.
Codense if, for any $x ∈ L$, $h(x) = 1$ implies $x = 1$.
...
8
votes
2
answers
294
views
Euler characteristic of the simplicial complex of sets of elements in a semilattice with non-zero meet
In a combinatorial computation, I came across the following quantity:
Consider a finite meet semilattice $L$, that is, a finite poset which is closed under $\min$. Denote the least element of $L$ by $...
- 305
3
votes
1
answer
177
views
How to construct a lattice having a subset of a given relations?
I am given a (smallish, say $n=14$ element) set $X$, and a set $R$ of (a few hundred) quadruples of elements $(a, b, c, d)$ with $a,b,c, d\in X$.
I want to construct lattices on $X$, such that for all ...
- 5,822
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
10
votes
2
answers
445
views
Class of lattices that excludes $M_3$?
It is well known that a lattice is distributive iff it excludes as a sublattice $N_5$ (the pentagon) and $M_3$ (three unordered elements with a top and bottom). Further, a lattice that only excludes $...
- 123
0
votes
2
answers
526
views
The union of two cuts is a cut?
Every poset $\langle P, \leq \rangle$ has a Dedekind-MacNeille completion, a complete lattice that embeds $\langle P, \leq \rangle$.
For $A \subseteq P$, the upset $U(A) = \{p \in P\ |\ \forall a \in ...
3
votes
2
answers
124
views
Explicit lifting characterization of complete lattices among posets?
It's well-known that the complete lattices are characterized among all posets as the regular-injectives. That is, a poset $L$ is a complete lattice if and only if $L$ has the right lifting property ...
- 63.9k
0
votes
2
answers
103
views
Is this ordering on the set of all covers of $\omega$ a (complete) lattice?
Let ${\frak C} \subseteq {\cal P}({\cal P}(\omega))$ be the collection of all covers of $\omega$ (that is, ${\cal C} \in {\frak C}$ iff $\bigcup {\cal C} = \omega$.)
We define the following binary ...
- 48.9k
4
votes
1
answer
289
views
Does the lattice of partitions map onto the lattice of subsets?
Let $X\neq \emptyset$ be a set and let $X^X$ denote the collection of all functions $f:X\to X$. We put a binary relation (reflexive and transitive), the composition preorder on $X^X$ by setting for $f,...
- 48.9k
1
vote
1
answer
102
views
Are non-trivial interval-isomorphic posets lattices?
We say that a partially ordered set $(P,\leq)$ is interval-isomorphic if for all $a<b \in P$ we have $P \cong [a,b]$, where $[a,b]=\{x\in P:a\leq x\leq b\}$.
Suppose $(P,\leq)$ is interval-...
- 48.9k