Friday, September 16, 2011

Orders and lattices

1Partial orders¶

A nonstrict partial order on $A$ is (r), (as), and (t). Example: $\leq$.
A strict partial order is (ir), (as), and (t). Example: $<$.

The idea of a partial order is to have things happening in a certain order, but with some freedom. For instance, $a$ and $b$ might have to be before $c$, but $a$ can be before or after $b$, etc.

If $R$ is a strict partial order, then $R \cup \Delta_A$ is a nonstrict partial order. (From $< to \leq$, etc.) If $R$ is a nonstrict partial order, then $R \backslash \Delta_A$ is strict.

1.1Total orders¶

A partial order is also a total order if the property of totality is satisfies, i.e., if $aRb$ or $bRa$ or $a = b$ for all $a, b \in A$.

1.2Power sets¶

If $X$ is any set, $P(X)$ (the power set of $X$) is a collection of subsets in $X$ ($\{ Y: Y \subseteq X\}$), i.e., the elements are sets.

For example, if $X = \{a, b, c\}$, $P(X) = \{\varnothing, \{a\}, \{b\}, \{c\}, \{a, b\}, \{b, c\}, \{a, b, c\}\}$ which is pretty cool. The empty set is always in a power set, as is $X$ itself.

N.B. $P(X) = \{ \varnothing, X\} \iff |x| \leq 1\}$ (i.e. $X$ is a singleton or the empty set)

There is natural partial order on this set (and this works for any set of sets I think): If $R$ is $\subseteq$, then $R$ is a partial order of $P(X)$. This partial ordering is: (r), as $Y$ is always $\subseteq$¹; (as), because if $Y \subseteq Z$ and $Z \subseteq Y$ then $Y = Z$; (t) because if $Y \subseteq W$ and $W \subseteq Z$ then $Y \subseteq Z$.

Diagrammatically, this is a cube (or rather the Hasse diagram of a lattice - more on that later):

Note that this is not a total order. For instance, $\{a\}$ and $\{b\}$ are not related, and are not the same. For the power set to be a total order, $X$ would have to be a singleton (or the empty set?).

1.3More partial orders¶

Another example of a partial order is the "divides" relation. (Recall: $A = \mathbb{N}$, $R = \mid$, $a \mid b$ if $a$ divides $b$). This is not a total order.

1.4Hasse diagrams¶

Given a small partial order on a set $A$, we can draw a Hasse diagram. Just write down all the elements in the poset² and draw a non-horizontal line between two elements if the bottom element, $a$, is related to the top element $b$ (as in, $aRb$).

For example: $A = \{x \in \mathbb{N}: x \mid 24\} = \{1, 2, 3, 4, 6, 8, 12, 24\}$ (so all the factors of 24). This is a partial but not a total order (for example, 2 does not divide 3). The Hasse diagram would look as follows:

Another example: the factors of 30, with the "divides" relation. The Hasse diagram would look like:

Similarly, we can define $A_n$ for any $n$ as the number to find the factors of (not standard notation). For which values of $n$ is it true that the set is totally ordered? Well, when $n$ is 1, when $n$ is a prime, and $n$ is a power of a prime. Wow

1.5Lattices¶

Not all Hasse diagrams are lattices. For example, a sort of straightened figure eight would not be. Here's the definition of a lattice:

Lattice: a partially ordered set such that
1. There is a bottom element called $\bot$ such that $\bot \leq a$ for all $a$ (so related to everything else, in an underneath sort of way)
2. There is a top element called $\top$ such that $a \leq \top$ for all $a$
3. Given any $a, b \in A$, there is an element $c$ (the smallest thing "above" both $a$ and $b$ - i.e. for any $d \in A$ with $a \leq d$, $b \leq d$, we have $c \leq d$) that is called the "join" of the two elements. The notation is $a \lor b$. So, the least upper bound of $(a, b)$.
4. There is also a greatest upper bound - the meet of the two elements - which is represented by $a \land b$.

For example, with divisibility and $\mathbb{N}$, $a \lor b$ is the least common multiple, and $a \land b$ is the great common divisor.

The join and meet of any two elements are unique. Proof: since $a \leq c$, $b \leq c$, we have $c \leq c'$. Also, $a \leq c'$, $b \leq c'$, so $c' \leq c$. By antisymmetry, $c = c'$.

Triviality: if $a \leq b$ in a lattice then $a \lor b = b$, $a \land b = a$.