Posets and Lattices

Definition 1.
A lattice is a nonempty poset with a maximum and a minimum, and such that any nonempty finite subset has a supremum (or join) and an infimum (or meet).

One could just as well simply say that a lattice is a poset $\mathcal L$ where any finite subset has a supremum and an infimum, using the (natural) convention that the supremum of the empty set is the minimum of $\mathcal L$ , and its infimum is the maximum of $\mathcal L$ .

The requirement that a lattice $\mathcal L$ has a minimum and a maximum is not universally followed, and lattices with this additional property are sometimes called bounded.

Examples 2.
Any linearly ordered set with a minimum and a maximum is a lattice. In this case, all infima and suprema of nonempty finite sets are just minima and maxima.

For a more interesting example, consider $\mathbb N$ , partially ordered by divisibility. This is a lattice, with minimum $1$ and maximum $0$ . The infimum of a nonempty set $X\ne\{0\}$ is the greatest common divisor of the elements of $X$ , and its supremum is their least common multiple.

Given a set $X$ , its power set $\mathcal P(X)$ is a lattice under containment, $\subseteq.$ In fact, in this case any nonempty subcollection of $\mathcal P(X)$ (whether finite or not) has an infinimum (its intersection) and a supremum (its union). This is an example of a complete lattice, as in Definition 3.

Given a set $X$ , let $\mathrm{Fin}(X)$ denote the collection of finite subsets of $X$ , partially ordered under containment. If $X$ is infinite, $\mathrm{Fin}(X)$ is not a lattice (it lacks a maximum), but $\{X\}\cup\mathrm{Fin}(X)$ is.

The partition lattice $\Pi_n$ has as elements the partitions of $\{1,\dots,n\}$ where, as usual, a partition of a set $A$ is a collection $\mathcal A$ of pairwise disjoint nonempty subsets of $A$ whose union is $A$ . The set $\Pi_n$ is ordered by refinement: If $x,y$ are partitions in $\Pi_n$ , we say that $x\le y$ iff every set in $x$ is a subset of a set in $y$ .

Definition 3.
A lattice $\mathbb P=(P,\le)$ is complete iff any nonempty subset of $P$ has a supremum and an infimum.

With the same convention as above, we could as well say that any subset of $P$ admits a supremum and an infimum.

Examples 4.
By the completeness of the real line, any compact interval ${}[a,b]\subseteq\mathbb R$ is a complete lattice under the usual order.

$(\mathbb N,|)$ is actually a complete lattice. The supremum of any infinite set is $0$ .

The collection of convex subsets of $\mathbb R^2$ is a complete lattice under containment. The infimum of a nonempty family $\mathcal F$ of convex sets is just their intersection. Its supremum is their convex hull, that is, the intersection of all the convex subsets of $\mathbb R^2$ that contain all sets in $\mathcal F$ .

Given a group $G$ , the collection $\mathrm{Sub}(G)$ of subgroups of $G$ , partially ordered by containment, is a complete lattice.

If $X$ is a linearly ordered set with a supremum and an infimum, then $X$ is a complete lattice iff it is Dedekind complete, meaning that any cut admits a supremum. Cuts are defined as a natural generalization of the usual concept for $\mathbb Q$ : A cut of $X$ is a pair $(A,B)$ of subsets of $X$ such that $B$ is the collection of upper bounds of $A$ , and $A$ is the collection of lower bounds of $B$ . Note that this notion makes sense even if $X$ is just a partially ordered set. Given a cut $(A,B)$ in $X$ , we say that it admits a supremum iff $\sup(A)$ exists.

Given any partially ordered set $P$ , there is always a complete lattice that contains $P$ , for example, the collection of downward closed subsets of $P$ , under containment, where $p\in P$ is identified with $\{x\in P\mid x\le p\}$ .

Exercise 5 (MacNeille).
In fact, any poset $\mathbb P=(P,\le)$ admits a minimal completion $\mathcal L$ , in the sense that $\mathcal L$ is a complete lattice containing $\mathbb P$ , and $\mathcal L$ embeds (as a poset) into any complete lattice that contains $\mathbb P$ (with the embedding fixing $P$ pointwise).

As with the rationals and the reals, a natural way of defining this minimal completion $\mathcal L$ of $\mathbb P$ is simply to take as $\mathcal L$ the collection of all cuts in $\mathbb P$ , partially ordered by saying that $(A,B)\le(C,D)$ iff $A\subseteq C$ . This construction is called the Dedekind-MacNeille (or normal) completion, first introduced in MacNeille [Mac37]. Verify that it indeed results in the minimal completion of $\mathbb P$ .

Suppose that $(A,B)$ is a cut of $\mathbb P$ . Show that either $A$ and $B$ are disjoint, or else they meet at exactly one point.

Suppose that $a\in P$ , $A\subseteq\mathbb P$ , and $a=\max(A)=\sup(A\setminus\{a\})$ . Let $\hat A$ be the downward closure of $A$ , and let $B$ be the set of upper bounds of $A$ . Show that $(\hat A,B)$ is a cut but $(\hat A\setminus\{a\},B)$ is not. This is slightly different from the situation with $\mathbb Q$ and its completion $\mathbb R$ , where commonly we require the two sets in a cut to have no elements in common. Does the Dedekind-MacNeille completion of $\mathbb Q$ actually coincide with $\mathbb R$ ?

Exercise 6 (Birkhoff).
Say that a lattice $\mathcal L$ is distributive iff $p \land (q \lor r) = (p \land q) \lor (p \land r)$ for any $p,q,r\in\mathcal L$ , where $a \land b$ denotes the meet of $a$ and $b$ , and $a\lor b$ denotes their join.

For example, $\mathcal P(X)$ is a distributive lattice. Give an example of a lattice that is not distributive.

Prove Birkhoff’s representation theorem, also called the fundamental theorem for finite distributive lattices, stating that any such lattice is isomorphic to a lattice of finite sets, where the lattice operations are just given by union and intersection.

References

[Mac37]
Holbrook M. MacNeille.
Partially ordered sets.
Trans. Amer. Math. Soc. 42 (3), (1937), 416–460.
MR1501929.

This entry was posted on Tuesday, February 4th, 2014 at 7:11 pm and is filed under 580: Topics in set theory. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

	ปั่นสล็อต on 414/514 The theorems of Rieman…
	Richard Kimberly Hec… on Woodin’s proof of the se…
	Is there a Borel-mea… on 414/514 Examples of Baire clas…
	Simple bijectiveness… on 580 -Some choiceless results…
	Schur’s theore… on 580 -III. Partition calcu…
	Uncountable linearly… on 403/503 – Homework …
	What is a non-constr… on On strong measure zero se…
	function from Nmathb… on Hindsight
	Cauchy Schwarz Inequ… on 275 -Positive polynomials
	What is a Cantor-sty… on 580 -Some choiceless results…
	Question about Gener… on 580 -Some choiceless results…
	Set has Measure Zero… on On strong measure zero se…
	Non-measurable subse… on 580 -Cardinal arithmetic …
	hmeng1 on 414/514 The theorems of Rieman…
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …

M	T	W	T	F	S	S
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28

A kind of library