4
$\begingroup$

NOTE: There is another question asking "What is a Lattice?" but when reading the question, it has to do with programming, and that is not what my question has to do with. The answer provided to that question didn't answer MY question either, so please don't list this as a duplicate.

I have been researching set theory and I've come across "lattices". Looking at the wikipedia article and some other articles, it makes it so confusing and I can't understand anything. I tried looking for videos or articles or anything explaining lattices, but to no avail. Help? Can anyone explain to me in detail the basics of lattices, or, provide an article that explains them?

$\endgroup$
  • 1
    $\begingroup$ There are at least two completely unrelated meanings of lattice in mathematics. A lattice can be a free abelian group, or a special kind of partially ordered set. $\endgroup$ – Matt Samuel Feb 9 '16 at 0:11
  • $\begingroup$ @MattSamuel That just makes it even more confusing... I THINK I'm talking about the partially ordered set. The one I'm talking about includes the symbols $\vee$ and $\wedge$, unless they BOTH include those symbols. $\endgroup$ – Sam Feb 9 '16 at 0:16
  • $\begingroup$ Only the partially ordered set uses those symbols, so that's probably the one you mean. $\endgroup$ – Matt Samuel Feb 9 '16 at 0:17
  • 1
    $\begingroup$ The relevant wikipedia article is this one. It would help if you were more specific about what you find confusing. $\endgroup$ – Alex Kruckman Feb 9 '16 at 0:26
  • 2
    $\begingroup$ Sprinkling question marks through a post does not create a Question that can be concisely answered by reasoned mathematical argument. In particular not understanding a topic is perhaps the occasion for asking a question but not the total package. Start with where your understanding ends and ask a simple "next step" to build on that secure foundation. $\endgroup$ – hardmath Feb 9 '16 at 2:41
6
$\begingroup$

To understand lattices first you need to understand partially ordered sets. A partially ordered set is a set with an ordering operation $ \leq $ that sometimes works.

For example the set of all people ordered by ancestry is a partially ordered set (poset). If your mother is your ancestor and your mother's mother is your ancestor then your grandmother is your ancestor. However you are neither your siblings ancestor nor is your sibling your ancestor.

A lattice is a poset with two additional restrictions:

For any two members $x,y$ of the set there is a member of the set which is larger than or equal to both $x$ and $y$, and is the smallest member that has this property. This is called their join, and is denoted $x \vee y$.

The other restriction is that for any two members $x,y$ of the set there is a member of the set which is smaller than or equal to both $x$ and $y$, and is the largest member that has this property. This is called their meet, and is denoted $ x\wedge y $.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The additional restriction is that meet and join are required for any two elements, $\endgroup$ – Berci Feb 9 '16 at 0:55
  • $\begingroup$ Sorry I'll make that clearer $\endgroup$ – Q the Platypus Feb 9 '16 at 0:57
  • $\begingroup$ given the restrictions, how is it possible that either x or y are not the memebers of the set which is largest/smallest and therefore cant meet the requirement? $\endgroup$ – Joaquin Brandan May 4 '17 at 19:37
  • 2
    $\begingroup$ I did mean "larger or equal" however the condition isn't the way you stated exactly. The join condition is defined as $ x \bigwedge y = a \Leftrightarrow a \geq x \wedge a \geq y \wedge (\forall b . (b \geq x \wedge b \geq y) \Rightarrow (b \geq a)) $ and the requirement for a join semi-lattice is $ \forall x,y \in A. \exists a \in A . x \bigwedge y = a $. With the equivalent for a meet semi-lattice with the values flipped. A lattice is both a join and a meet semi-lattice. $\endgroup$ – Q the Platypus May 5 '17 at 4:22
  • 2
    $\begingroup$ Q the Platypus - I think the symbols for join and meet are interchanged! $\endgroup$ – KGhatak Sep 6 '19 at 7:02
5
$\begingroup$

A lattice is an algebraic structure, generalizing each of the following pairs of (binary) operations: $$\min,\ \max$$ $$\inf,\ \sup$$ $$\bigcap,\ \bigcup$$ $$\mathtt{and},\ \mathtt{or}$$ $$\gcd,\ \mathrm{lcm}$$

A partially ordered set can be naturally equipped with an algebraic lattice structure whenever every pair of elements $a,b$ has a greatest lower bound $a\land b$, and a least upper bound $a\lor b$.

(Conversely, every lattice determines a partial order by $a\le b\ :\iff\ a\lor b=b \ (\iff a=a\land b)$.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The brackets in your last formula look like they are placed wrong $\endgroup$ – Q the Platypus Feb 9 '16 at 2:19
5
$\begingroup$

Consider a partially ordered set $(A,\leq)$, and a non-empty subset $B$. A lower bound is an element $l$ such that for every $b \in B, l \leq b$. A greatest lower bound is an element $l_0$ such that for every lower bound $l$, $l \leq l_0$.

An example would be $A = \mathbb{R}$ with the standard order, $B$ the subset $(0,1) \cup (2,3)$. Any element less than or equal to $0$ is a lower bound, and the greatest lower bound is $0$.

An example of a subset without a greatest lower bound would be $A = \mathbb{R}, B = (\infty, 1]$. In fact $B$ has no lower bound at all.

Similar definitions apply for upper bounds and greatest upper bounds.

A lattice is a partially ordered $(A, \leq)$ with the property that for every $a,b \in A$, the set ${a,b}$ has a greatest lower bound and a least upper bound.

An example of a lattice would be $A = [0,1]$ with the standard ordering. An example of something that is not a lattice would $A = \{\{1\},\{2\},\{1,2,3\},\{1,2,10\}\}$ with set theoretic inclusion as the ordering. Taking $a = \{1\}, b = \{2\}$ the set $B = \{a,b\}$ has two upper bounds $\{1,2,3\}$ and $\{1,2,10\}$ but does not have a greatest upper bound, since $\{1,2,3\}$ and $\{1,2,10\}$ are not comparable. (Note that they are not comparable because neither is a superset of the other)

Another example of a lattice would be the powers of a set with set theoretic inclusion.

A way to think of lattices would be as a sort of structure where every pair of elements has one element above it that is smaller than every other element above it, and one bigger then every below it. Visualized this means that every pair of elements forms either has one element above and one below, or forms a diamond with some pair of elements, one above and one below.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.