Monday, September 19, 2011

Properties of lattices

1Lattices continued¶

A lattice $(L; \leq)$ is a partially ordered set with a top element $\top$ ($x \leq \top$ for all $x \in L$), a bottom element $\bot$ ($\bot \leq x$ for all $x \in L$), and for any $a, b \in L$ there are $a \lor b$ (the "join") and $a \land b$ (the "meet") in $L$ such that $a, b \leq a \lor b$ and whenever $a, b, \leq c$, $a \lor b \leq c$, and $a \land b \leq a, b$ and whenever $d \leq a, b$ then $d \leq a \land b$.

In the case of the power set ($L=P(X)$): $\bot = \varnothing$, $\top = X$, $A \lor B = A \cup B$, and $A \land B = A \cap B$.

1.1Representative sets¶

Fix a set of propositional variables: $\{p_1, ... p_n\}$ and let $\mathcal{F}$¹ be a representative set of formulas in these variables. $\mathcal{F}$ has $2^{2^n}$ elements².

How do we order this? It turns out there is a natural partial ordering where the bottom is $\bot$, the top is $\top$, and the variables are in the middle. The number of elements in each row thing follows the pattern in Pascal's triangle. For $n = 1$, the Hasse diagram would appear as follows:

For $n=2$, it's significantly more complicated. I kind of messed up the placement of the elements (it's supposed to look like a hypercube) but all the connections should be correct:

To do: explain this? Is it necessary?

1.2Distributivity¶

A lattice is distributive if it satisfies both distributive laws, for all $a, b, c \in L$:
1. $a \land (b \lor c) = (a\land b) \lor (a \land c)$
2. $a \lor (b \land c) = (a\lor b) \land (a \lor c)$

(The above is not really equality, but rather propositional equivalence.)

All of the example lattices were distributive. Incidentally, any lattice with 4 or fewer elements is always distributive.

1.2.1A simple non-distributive lattice¶

Here is an example of a lattice (called "three" or $M_3$) that is not distributive:

To check that it fails the first distributive law, we evaluate $a \land (b \lor c)$ and $(a \land b) \lor (b \land c)$:

$a \land (b \lor c)$

$a \land \top = a$

$(a \land b) \lor (b \land c)$

$(\bot) \lor (\bot) = \bot$

So yeah obviously the two are not equal.

1.3Modularity¶

A lattice is called modular if, whenever $x \leq y$, $y \land (x \lor z) = (y \land x) \lor (y \land z)$ and $x \lor (y \land z) = (x \lor y) \land (x \lor z)$ for all $z$. A weaker property than distributivity (as all distributive lattices are modular, but not all modular lattices are distributive).

1.3.1A simple non-modular lattice¶

An example of a a lattice (called "five" or $N_5$) that is not modular (and thus also not distributive):

Proof: $b \land (a \lor c) = b \land \top = b$, but $(b \land a) \lor (b \land c) = a \lor \bot = a$.

Fact: if a lattice $(L; \leq)$ is not modular, there are $\alpha, \beta, \gamma$ in $L$ with $\alpha < \beta$, $\alpha \land \gamma = \beta \land \gamma$, and $\alpha \lor \gamma = \beta \lor \gamma$ (so a copy of $N_5$, somehow). Conversely, if there is a copy of $N_5$, then the lattice is not modular.

1.4Complements¶

If $(L; \leq)$ is a lattice and $a \in L$, a complement of $a$ is an element $b$ such that $a \land b = \bot$ and $a \lor b = \top$.

In any lattice, $\top$ and $\bot$ are always complements. In a totally ordered set, only $\top$ and $\bot$ are complements.

N.B. Complements are not necessarily unique, although they are in certain cases.

In the lattice of the power set $P(X)$, every element $A$ has a unique complement, which is $X / \{A \}$ (so like the actual complement lol). The join (union) of $A$ and its complement is $X$, while the meet (intersection) is the empty set.

In the case of the non-distributive lattice $N_3$, any two of $(a, b, c)$ are complements.

Going back to the representative set $\mathcal{F}$, every formula $\Phi$ has a unique complete, which is just the negative of the formula ($\neg \Phi)$. The join is $\Phi \lor \neg \Phi$ which always comes out $\top$ and the meet is $\Phi \land \neg \Phi$ which always comes out $\bot$.

1.4.1Boolean algebras¶

A boolean algebra is a complemented³, distributive⁴ lattice.

An example of a boolean algebra can be found in assignment 4, question 1. The relation is the divisibility relation, and any number that is square-free (i.e. not divisible by any perfect squares except one) on the right side of the $\mid$ will result in a lattice in which each element has a unique complement.