Lattices are partially ordered sets such that a least upper bound and a greatest lower bound can be found for any subset consisting two elements. Lattice theory is an important subfield of order theory.
1
vote
1answer
53 views
When is “mod $n$” a congruence relation on the lattice $(\Bbb N,\gcd,\text{lcm})$?
For which $n\in \Bbb N$,
$$a\equiv b,a'\equiv b'\quad \text{implies} \quad \gcd(a,a')\equiv \gcd(b,b'),
\text{lcm}(a,a')\equiv \text{lcm}(b,b')$$
all mod $n$.
For $n=2$ it is true.
6
votes
0answers
60 views
The right way to motivate lattice theory in a combinatorics class
I am attending a course on combinatorics. I was asked to present Möbius functions on lattices for this course. I was trying to look for a simple non-trivial problem that illustrates the need for ...
2
votes
3answers
34 views
How to show that $C(\bigcup _{i \in I} A_i)$ is a supremum of a subset $\{C(A_i): i \in I \}$ of the lattice $L_C$ of closed subsets?
According to Brris & Sankappanavar's "A course in universal algebra," the set $L_C$ of closed subsets of a set $A$ forms a complete lattice under $\subseteq$. Here, a subset $X$ of $A$ is said to ...
4
votes
1answer
71 views
A Question on the Young Lattice and Young Tableaux
Let:
$\lambda \vdash n$ be a partition of $n$
$f^\lambda$ - number of standard Young Tableaux of shape $\lambda$
$\succ$ - be the covering in the Young Lattice (that is, $\mu \succ \lambda$ iff ...
0
votes
1answer
19 views
order preserving function over Poset
I have a DAG (Directed Acyclic Graph) $G$ represents the dominance relation between solutions. A path from $x$ to $y$ means $y\succ x$ ($y$ dominates or better than $x$) where the absence of such a ...
1
vote
0answers
27 views
Monotonicity in DFA analysis
I am studying program analysis and synthesis, I was reading a presentation
about some DFA analysis.
I can't seem to understand why $$\bigcap_{s'\in\text{pred (s)}}\text{Out}(s')$$
and ...
-2
votes
0answers
146 views
Lattice Paths & Principle of Exclusion-Inclusion
How many lattice paths are there from $(0,0)$ to $(m, n)$ which pass through the point $(x, y)$ for
integers $x, y, m, n$ such that $0 \leq x \leq m$ and $0 \leq y \leq n$?
i figured the answer is ...
5
votes
2answers
141 views
Example of non-abelian partially ordered group
What is a simple example of a non-abelian partially ordered group?
1
vote
1answer
30 views
does this property of a lattice have a commonly used name?
Given any $x$, $x' \in L$ with $x\geq x'$, there exists a $x^* \in L$ s.t. $x^* \vee x' = x$. This is a property that a given lattice $L$ may or may not satisfy. Is there a commonly used name for ...
0
votes
2answers
39 views
$\operatorname{lcm}(\operatorname{gcd}(a,b),c)=\operatorname{gcd}(\operatorname{lcm}(a,c),\operatorname{lcm}(b,c))$ for any $a,b,c \in \mathbb{Z}$
I tried to show that the lattice of subgroups of the group $\mathbb{Z}$ is distributive. The question reduced showing that for any $a,b,c \in \mathbb{Z}$ we have that
$$
...
0
votes
1answer
26 views
Birkhoff Lattice theory notation question- probably easy to answer
In Lattice Theory p. 30 3rd edition:
Lemma 3. In any distributive lattice, every polynomial is equivalent to a join of meets, and dually:
$p(x_1,...,x_r)=\lor_{\alpha \in A}\{ \land_{S_\alpha} x_i ...
1
vote
1answer
64 views
Drawing lattices
I would like to be able to draw the lattices of subgroups of certain groups. I thought it would be easy when I already know the structure, but I've never done it before, and it turns out it's harder ...
0
votes
0answers
24 views
Property lattice - sign of variables
I am doing program analysis and am interested in the sign of variables. That is, whether we can guarantee that for a given program point and a variable x (at least) one of the following properties ...
1
vote
2answers
28 views
Partition of lattice into symmetric chains
Let $C_1 \subsetneq C_2 \subsetneq C_3 \subsetneq \cdots \subsetneq C_k$ be a chain in the subset lattice $(2^{[n]},\subseteq)$. A chain is considered symmetric if $|C_1| + |C_k| = n$ and ...
0
votes
1answer
28 views
Tell if $S = (X, \Sigma)$ is a distributive complemented lattice
Let $\Sigma$ be a partial order defined over $\mathbb N^* = \mathbb N \setminus \{0\}$ such that $$n\;\Sigma\;m \Leftrightarrow n=m \text{ or } \text{r}(8,n) \text { is a non-trivial divisor of } ...
4
votes
3answers
93 views
Why are ordered spaces normal? [collecting proofs]
Greets
This is a problem I wanted to solve for a long time, and finally did some days ago. So I want to ask people here at MSE to show as many different answers to this problem as possible. I will ...
2
votes
1answer
34 views
Can infinite joins/meets be viewed as special cases of a limit with respect to some topology?
Let $L$ denote a lattice. Is there a topology on $L$ such that infinite joins and meets can be viewed as a special kind of "limit"? And if so, is this topology unique?
2
votes
1answer
54 views
Sub-lattices and lattices.
I have read in a textbook that $ \mathcal{P}(X) $, the power-set of $ X $ under the relation ‘contained in’ is a lattice. They also said that $ S := \{ \varnothing,\{ 1,2 \},\{ 2,3 \},\{ 1,2,3 \} \} $ ...
6
votes
1answer
34 views
What are ideals in a complete lattice?
If I have a complete lattice $L$, what conditions do I need for $I\subseteq L$ to be an ideal?
In a general lattice the conditions are:
$I$ is a lower set;
$I$ is closed under (finite) joins.
For ...
0
votes
0answers
40 views
Calculating the size of a property space
Within the context of program analysis, I understand the the property space for Reaching Definition solutions is given as the powerset of the cartesian product between the labels in the program and ...
2
votes
1answer
85 views
Why is this not a Lattice?
I am having some trouble understanding lattices. The following is defined as not being a lattice:
$$S = \{ \{\}, \{y\}, \{x\}, \{x,y,z\}, \{a,x,y,z\}, \{b,x,y,z\} \}$$
I understand that a lattice is ...
1
vote
1answer
47 views
Atomic Boolean lattice is weakly atomic
The book "Introduction to Lattices and Order" says at Exercise 10.12 that an atomic Boolean lattice is weakly atomic.
Could you tell me why it holds?
0
votes
1answer
36 views
an infinite queue preserving equality.
Is there any well-ordered set $(A,\leq)$ such that:
$(A,\leq^{-1})$ is well-ordered.
$A$ is infinite.
there's exactly one function $\theta:A\rightarrow \{0,1\}$ such that
1) for each $a < M$,
...
5
votes
1answer
78 views
classical topology but with lattices
I'm looking for a reference, if such a references exists.
So there are currently at least two approaches to topology.
The point-set or "classical" approach to topology, which concerns itself with ...
0
votes
1answer
33 views
Represent the three element chain as a subdirect product of subdirectly irreducible lattices.
Represent the three element chain as a subdirect product of subdirectly irreducible lattices.
I know the two element chain as either a Boolean algebra or a semilattice,is subdirectly irreducible.In ...
0
votes
0answers
32 views
$\ell$-group character
Let $G$ be an $\ell$-group and $H$ be a subgroup of $G$ such that $[G: H]$ is finite. Let $x$ and $y$ in G and not in $H$. Is there any example of an $\ell$-group $G$ and subgroup $H$ such that $x\leq ...
0
votes
0answers
24 views
Question about a property of lattice-morphism
I would like to know if there is a name for the class of commutative (i.e., $\phi(x,y)=\phi(y,x)$) lattice-morphisms $\phi : L_1\times L_{1} \rightarrow L_2$ with the following property:
$\phi(x ...
4
votes
1answer
144 views
Help me get hyped about lattices
I own a small book on Lattice theory published by Dover. Unfortunately, since I bought it almost a year ago, I have gotten nowhere in its study.
What I am asking for are freely available papers that ...
2
votes
1answer
228 views
Problem about Hasse diagrams
Can someone help me to solve this problem.
Are these Hasse diagrams lattices?
2
votes
1answer
36 views
breadth of join-semilattice
On page 16, Lattice Theory: Foundation, George Grätze(2011),
1.19 Show that a join-semilattice $(L; \lor)$ has breadth at most $n$, for a
positive integer n, iff for every nonempty finite subset ...
7
votes
1answer
92 views
Least common fixed-point
I have been reading a book, "Introduction to Lattices and Order", and I'm trying to solve exercise 8.29 as the following in it:
Suppose that $P$ is a complete lattice and let $F$ and $G$ be ...
0
votes
0answers
45 views
Is there a name for a lattice that is isomorphic to its dual?
If we have a lattice and we invert the order, we again obtain a lattice, called the dual lattice. Is there a name for a lattice that is isomorphic to its dual lattice?
6
votes
1answer
88 views
Order embedding from a poset into a complete lattice
Let $\mathfrak{A}$ is an arbitrary poset.
Does it necessarily exist an order embedding from $\mathfrak{A}$ into some complete lattice $\mathfrak{B}$, which preserves all suprema and infima defined in ...
0
votes
0answers
38 views
Distribution of natural numbers' divisor lattices - via zeta function?
The attchd graphics are some sample divisor lattices of natural numbers programmed with Mathematica.
Excuse that due to cropping (to fit the Math.SE format), there are fewer columns than the number ...
5
votes
4answers
69 views
Complete lattices on $\mathbb{Q}$ and $\mathbb{R}$ ordered by $\leq$
To quote from my lecture notes:
When every subset of A has a lub and glb, we say that the order is a complete lattice, but this takes us beyond the syllabus. It is notable that $\mathbb{Q}$, ...
2
votes
1answer
42 views
Continuity of the operation: Infimum of two projections.
The question actually is limited to a very specific case.
The following takes place in a fixed Hilbert space.
Let $(p_i)_i, (q_i)_i, p, q$ projections (resp. nets of projections) so that ...
1
vote
0answers
32 views
How to characterize the partial order on the k-combinations of a totally ordered set?
Consider a finite set $X = \{x_1,\ldots,x_n\}$ whose elements are totally ordered. In fact, for concreteness, assume that $X$ is a set of reals, and without loss of generality assume that $x_i$ is ...
2
votes
1answer
42 views
Proving that idempotence follows from other lattice axioms
I am supposed to prove that $x\wedge x = x$ and $x\vee x = x$ follow from the other lattice axioms (associativity, commutativity and absorption).
So far I have $$x = x\vee(x\wedge x) = ...
1
vote
1answer
56 views
The cardinality of finite Boolean lattice
A book (Introduction to Lattices and Order) says that we can prove that the cardinality of any finite Boolean lattice $B$ is a power of 2 by induction on $|B|$ with the following lemma:
If a lattice ...
2
votes
1answer
51 views
Composition length of surjective inverse limits
Let $M$ be a left module over some ring $R$ and suppose that $M$ is an inverse limit of a family of modules $M_i$ with $i\in I$. We suppose also that the maps of the inverse limit $\pi_i:M\to M_i$ are ...
3
votes
1answer
262 views
Given the Hasse diagram tell if the structure is a lattice
Let's consider the following Hasse diagram:
I need to tell whether this is a lattice. By lattice definition I can prove the above shown structure $M_5$ to be a lattice if and only if $\forall x,y ...
0
votes
0answers
39 views
Given an outcome, how to assess its goodness in the partial/total order?
I am looking for different ways to assess an outcome goodness in the given order. By goodness I mean how good this outcome is compared to the other outcomes in the order.
For instance, assume I have ...
2
votes
2answers
40 views
How to spot a lattice
Let $A=\{1,2,3,4,5,6\}$ and let's consider the usual order relation given by $\leq$. My textbook includes an image representing this structure:
Given the definition of lattice, I don't understand ...
1
vote
1answer
43 views
Prime filters in $(\mathbb{N}, \text{lcm}, \text{gcd})$
I'm trying to determine all the prime filters in the lattice $N = (\mathbb{N}, \text{lcm}, \text{gcd})$, where the order is given by divisibility.
I know that this lattice is distributive and that ...
0
votes
2answers
42 views
Weak Partial Complete Lattice and Homomorphisms
What is the proper nomenclature for a generalization of a lattice $L$ such that not all subsets of $L$ may have a join/meet, sometimes not even for finite subsets? This paper calls it a "weak partial ...
5
votes
1answer
102 views
Foundations of measure theory
In measure theory one usually starts with a $\sigma$-algebra $A$ of sets and considers a measure $\mu:A\to [0,\infty]$. I'm interested in abstracting this definition to allow more general domains and ...
-1
votes
1answer
91 views
Error at PlanetMath? (lattice theory: pseudocomplement)
Let $L$ is a lattice.
At http://planetmath.org/encyclopedia/Benzene.html it's written:
It is easy to see that given an element $a\in L$, the pseudocomplement of $a$, if it exists, is unique.
Is ...
3
votes
1answer
76 views
What is a complete lattice?
In a lecture of real analysis (this course is about Lebesgue measure)
the lecture said:
For a set $X$ - $P(X)$ (the power set) is a compele lattice: For every
$S\subseteq P(X)$ there exist $\cup ...
0
votes
2answers
137 views
Orders on the Cartesian product of partially ordered sets
The wikipedia article about partially ordered set describes three of the possible partial orders on the Cartesian product of two partially ordered sets, and mentions that similar constructions can be ...
1
vote
1answer
32 views
Join-Irreducibles and Direct Products
I'm trying to characterize the join-irreducible elements of the direct product of two lattices $L$ and $K$.
If we denote by $\mathscr{J}(L)$ the set of all join-irreducible elements of $L$, then my ...
