# Formal Definition of a Lattice

I am new to lattices, having some difficulty understanding the main definition. First, here are my main questions.

1. What it means for every pair in a lattice to have a lub/glb. For example, what can $\{x,y,z\}$ be paired with in the diagram to give it a lub/glb.
2. How to formalize the definition: $\forall \{a, b\} \in P, \{a,b\}\ has\ lub\ and\ glb$

Second, here is my understanding so far if that's helpful...

A partial order is a binary relation $\prec$ over a set $X$, creating a poset, written as $P = (X, \prec)$, satisfying:

1. $a \prec a$ (reflexivity)
2. $a \prec b \land b \prec a \Rightarrow a = b$ (anti-symmetry)
3. $a \prec b \land b \prec c \Rightarrow a \prec c$ (transitivity)

Posets can be drawn graphically as Hasse diagrams.

A maximal element of $p_{max} \in P$ satisfies:

$$\neg (\exists x \in P : p_{max}\prec x)$$

A minimal element of $p_{min} \in P$ satisfies:

$$\neg (\exists x \in P : x \prec p_{min})$$

An upper bound of $S \subset P$ is an element $p_{(+)} \in P$ such that:

$$p_{(+)} \succeq x, \forall x \in S$$

A least upper bound of $S \subset P$ is an element $p_{(<)} \in P$ satisfying:

$$\forall p_{(+)} \in S,\ p_{(<)} \preceq p_{(+)}$$

A lower bound of $S \subset P$ is an element $p_{(-)} \in P$ such that:

$$p_{(-)} \preceq x, \forall x \in S$$

A greatest lower bound of $S \subset P$ is an element $p_{(>)} \in P$ satisfying:

$$\forall p_{(-)} \in S,\ p_{(>)} \succeq p_{(-)}$$

A join semi-lattice is a poset $P$ where every pair of elements has a least upper bound (join).

A meet semi-lattice is a poset $P$ where every pair of elements has a greatest lower bound (meet).

A lattice arises when every pair of elements in $P$ has a least upper bound and greatest lower bound.

$$\forall \{a, b\} \in P, \{a,b\}\ has\ lub\ and\ glb$$

Not sure how to write that formally.

• Your question isn't clear. You don't "convert a poset into a lattice". A poset either is or isn't one. The two examples at the end show this. Both are posets. In the first, $a$ and $b$ do not have a greatest lower bound. In the poset of subsets the intersection of two sets is their greatest lower bound. I can't imagine where "cross product" comes in. – Ethan Bolker May 3 '18 at 0:21
• I am new to lattices, sorry about that. By converting into a lattice I guess I meant from a programming perspective, what you said makes sense. I am confused about which "pairs" are considered, are they the things touching each other, or any two elements in the lattice. And what is the lub/glb for a "pair", since there's only two elements in a pair that would make one lub and the other glb. – Lance Pollard May 3 '18 at 1:21
• The lub of two elements, if it exists, is generally - though not necessarily - a different element from the two. For instance, in your lattice picture, $\{x,y\}$ is the lub of $\{x\}$ and $\{y\}.$ When we say "all" pairs of elements must have a lub in order for the poset to be a lattice, we literally mean all pairs of elements in the poset, regardless of their relationship to one another. Same goes for glb. – spaceisdarkgreen May 3 '18 at 1:48
• @spaceisdarkgreen sort of following you, wondering about $\{x, y, z\}$, it doesn't have a lub (there's nothing above it). Same with the empty set, no glb. – Lance Pollard May 3 '18 at 1:54
• Your definition of maximal element is wrong because, since < js reflexive, pmax < pmax. – William Elliot May 3 '18 at 3:45

Assuming that $\prec$ is reflexive, the sentence $$\forall a\forall b\exists p\forall x(p\prec x\leftrightarrow(a\prec x\land b\prec x))$$ says that every pair of elements has a least upper bound, while the sentence $$\forall a\forall b\exists q\forall x(x\prec q\leftrightarrow(x\prec a\land x\prec b))$$ says that every pair of elements has a greatest lower bound.
An upper bound of a set $S$ is an element $u$ such that it fulfils the following condition: “If an element $b$ is in $S$ then it is equal or below $u$.” Given $S=∅$ this means the precondition is always false so this implication is always true. That means every element is an upper bound of the empty set. The same is true for the lower bound. As an intuition: In the Order diagrams you provided an upper bound of a set is a point, that can be reached from every element of the set by following the arrows. Dually, a lower bound is a starting point that has paths to all nodes representing the Set elements.