# 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.