Complete lattice

A com­plete lat­tice is a poset that is closed un­der ar­bi­trary joins and meets. A com­plete lat­tice, be­ing closed un­der ar­bi­trary joins and meets, is closed in par­tic­u­lar un­der bi­nary joins and meets; a com­plete lat­tice is thus a spe­cific type of lat­tice, and hence satis­fies as­so­ci­a­tivity, com­mu­ta­tivity, idem­po­tence, and ab­sorp­tion of joins and meets.

Com­plete lat­tices can be equiv­a­lently for­mu­lated as posets which are closed un­der ar­bi­trary joins; it then fol­lows that com­plete lat­tices are closed un­der ar­bi­trary meets as well.

Sup­pose that \(P\) is a poset which is closed un­der ar­bi­trary joins. Let \(A \subseteq P\). Let \(A^L\) be the set of lower bounds of \(A\), i.e. the set \(\{ p \in P \mid \forall a \in A. p \leq a \}\). Since \(P\) is closed un­der joins, we have the ex­is­tence of \(\bigvee A^L\) in \(P\). We will now show that \(\bigvee A^L\) is the meet of \(A\).

First, we show that \(\bigvee A^L\) is a lower bound of \(A\). Let \(a \in A\). By the defi­ni­tion of \(A^L\), \(a\) is an up­per bound of \(A^L\). Be­cause \(\bigvee A^L\) is less than or equal to any up­per bound of \(A^L\), we have \(\bigvee A^L \leq a\). \(\bigvee A^L\) is there­fore a lower bound of \(A\).

Now we will show that \(\bigvee A^L\) is greater than or equal to any lower bound of \(A\). Let \(p \in P\) be a lower bound of \(A\). Then \(p \in A^L\). Be­cause \(\bigvee A^L\) is an up­per bound of \(A^L\), we have \(p \leq \bigvee A^L\). <div><div>

Com­plete lat­tices are bounded

As a con­se­quence of clo­sure un­der ar­bi­trary joins, a com­plete at­tice \(L\) con­tains both \(\bigvee \emptyset\) and \(\bigvee L\). The former is the least el­e­ment of \(L\) satis­fy­ing a vac­u­ous set of con­straints; ev­ery el­e­ment of \(L\) satis­fies a vac­u­ous set of con­straints, so this is re­ally the min­i­mum el­e­ment of \(L\). The lat­ter is an up­per bound of all el­e­ments of \(L\), and so it is a max­i­mum. A lat­tice with both min­i­mum and max­i­mum el­e­ments is called bounded, and as this dis­cus­sion has shown, all com­plete lat­tices are bounded.

Ba­sic examples

Finite Lattices

The col­lec­tion of all sub­sets of a finite lat­tice co­in­cides with its col­lec­tion of finite sub­sets. A finite lat­tice, be­ing a finite poset that is closed un­der finite joins, is then nec­es­sar­ily closed un­der ar­bi­trary joins. All finite lat­tices are there­fore com­plete lat­tices.

Powersets

For any set \(X\), con­sider the poset \(\langle \mathcal P(X), \subseteq \rangle\) of \(X\)’s pow­er­set or­dered by in­clu­sion. This poset is a com­plete lat­tice in which for all \(Y \subset \mathcal P(X)\), \(\bigvee Y = \bigcup Y\).

To see that \(\bigvee Y = \bigcup Y\), first note that be­cause union con­tains all of its con­stituent sets, for all \(A \in Y\), \(A \subseteq \bigcup Y\). This makes \(\bigcup Y\) an up­per bound of \(Y\). Now sup­pose that \(B \in \mathcal P(X)\) is an up­per bound of \(Y\); i.e., for all \(A \in Y\), \(A \subseteq B\). Let \(x \in \bigcup Y\). Then \(x \in A\) for some \(A \in Y\). Since \(A \subseteq B\), \(x \in B\). Hence, \(\bigcup Y \subseteq B\), and so \(\bigcup Y\) is the least up­per bound of \(Y\).

The Knaster-Tarski fix­point theorem

Sup­pose that we have a poset \(X\) and a mono­tone func­tion \(F : X \to X\). An el­e­ment \(x \in X\) is called \(F\)-con­sis­tent if \(x \leq F(x)\) and is called \(F\)-closed if \(F(x) \leq x\). A fix­point of \(F\) is then an el­e­ment of \(X\) which is both \(F\)-con­sis­tent and \(F\)-closed.

Let \(A \subseteq X\) be the set of all fix­points of \(F\). We are of­ten in­ter­ested in the max­i­mum and min­i­mum el­e­ments of \(A\), if in­deed it has such el­e­ments. Most of­ten it is the min­i­mum el­e­ment of \(A\), de­noted \(\mu F\) and called the least fix­point of \(F\), that holds our in­ter­est. In the de­duc­tion sys­tem ex­am­ple from Mono­tone func­tion: ex­am­ples, the least fix­point of the de­duc­tion sys­tem \(F\) is equal to the set of all judg­ments which can be proven with­out as­sump­tions. Know­ing \(\mu F\) may be first step to­ward test­ing a judg­ment’s mem­ber­ship in \(\mu F\), thus de­ter­min­ing whether or not it is prov­able. In less pedes­trian sce­nar­ios, we may be in­ter­ested in the set of all judg­ments which can be proven with­out as­sump­tion us­ing pos­si­bly in­finite proof trees; in these cases, it is the great­est fix­point of \(F\), de­noted \(\nu F\), that we are in­ter­ested in.

Now that we’ve es­tab­lished the no­tions of the least and great­est fix­points, let’s try an ex­er­cise. Namely, I’d like you to think of a lat­tice \(L\) and a mono­tone func­tion \(F : L \to L\) such that nei­ther \(\mu F\) nor \(\nu F\) ex­ists.

Let \(L = \langle \mathbb R, \leq \rangle\) and let \(F\) be the iden­tity func­tion \(F(x) = x\). \(x \leq y \implies F(x) = x \leq y = F(y)\), and so \(F\) is mono­tone. The fix­points of \(F\) are all el­e­ments of \(\mathbb R\). Be­cause \(\mathbb R\) does not have a max­i­mum or min­i­mum el­e­ment, nei­ther \(\mu F\) nor \(\nu F\) ex­ist.

If that was too easy, here is a harder ex­er­cise: think of a com­plete lat­tice \(L\) and mono­tone func­tion \(F : L \to L\) for which nei­ther \(\mu F\) nor \(\nu F\) ex­ist.

There are none. :p

In fact, ev­ery mono­tone func­tion on a com­plete lat­tice has both least and great­est fix­points. This is a con­se­quence of the Knaster-Tarski fix­point the­o­rem.

The­o­rem (The Knaster-Tarski fix­point the­o­rem): Let \(L\) be a com­plete lat­tice and \(F : L \to L\) a mono­tone func­tion on \(L\). Then \(\mu F\) ex­ists and is equal to \(\bigwedge \{x \in L \mid F(x) \leq x\}\). Dually, \(\nu F\) ex­ists and is equal to \(\bigvee \{x \in L \mid x \leq F(x) \}\).

We know that both \(\bigwedge \{x \in L \mid F(x) \leq x\}\) and \(\bigvee \{x \in L \mid F(x) \leq x \}\) ex­ist due to the clo­sure of com­plete lat­tices un­der meets and joins. We there­fore only need to prove that \(\bigwedge \{x \in L \mid F(x) \leq x\}\) is a fix­point of \(F\) that is less or equal to all other fix­points of \(F\). The rest fol­lows from du­al­ity.

Let \(U = \{x \in L \mid F(x) \leq x\}\) and \(y = \bigwedge U\). We seek to show that \(F(y) = y\). Let \(V\) be the set of fix­points of \(F\). Clearly, \(V \subseteq U\). Be­cause \(y \leq u\) for all \(u \in U\), \(y \leq v\) for all \(v \in V\). In other words, \(y\) is less than or equal to all fix­points of \(F\).

For \(u \in U\), \(y \leq u\), and so \(F(y) \leq F(u) \leq u\). Since \(F(y)\) is a lower bound of \(U\), the defi­ni­tion of \(y\) gives \(F(y) \leq y\). Hence, \(y \in U\). Us­ing the mono­ton­ic­ity of \(F\) on the in­equal­ity \(F(y) \leq y\) gives \(F(F(y)) \leq F(y)\), and so \(F(y) \in U\). By the defi­ni­tion of \(y\), we then have \(y \leq F(y)\). Since we have es­tab­lished \(y \leq F(y)\) and \(F(y) \leq y\), we can con­clude that \(F(y) = y\). <div><div>

TODO: Prove the knaster tarski the­o­rem and ex­plain these images

add !’s in front of the fol­low­ing two lines A Knaster-Tarski-style view of com­plete lat­ticess More Knaster-Tarski-style view of com­plete latticess

Parents:

  • Order theory

    The study of bi­nary re­la­tions that are re­flex­ive, tran­si­tive, and an­ti­sym­metic.