In mathematics, in the area of order theory, a free lattice is the free object corresponding to a lattice. As free objects, they have the universal property.

Formal definition

Because the concept of a lattice can be axiomatised in terms of two operations ${\displaystyle \wedge }$ and ${\displaystyle \vee }$ satisfying certain identities, the category of all lattices constitute a variety (universal algebra), and thus there exist (by general principles of universal algebra) free objects within this category: lattices where only those relations hold which follow from the general axioms.

These free lattices may be characterised using the relevant universal property. Concretely, free lattice is a functor ${\displaystyle F}$ from sets to lattices, assigning to each set ${\displaystyle X}$ the free lattice ${\displaystyle F(X)}$ equipped with a set map ${\displaystyle \eta \colon X\longrightarrow F(X)}$ assigning to each ${\displaystyle x\in X}$ the corresponding element ${\displaystyle \eta (x)\in F(X)}$. The universal property of these is that there for any map ${\displaystyle f\colon X\longrightarrow L}$ from ${\displaystyle X}$ to some arbitrary lattice ${\displaystyle L}$ exists a unique lattice homomorphism ${\displaystyle {\tilde {f}}\colon F(X)\longrightarrow L}$ satisfying ${\displaystyle f={\tilde {f}}\circ \eta }$, or as a commutative diagram:

$${\displaystyle {\begin{array}{cccc}X&{\stackrel {\eta }{\longrightarrow }}&F(X)\\&\!\forall f\searrow &{\Bigg \downarrow }\exists _{1}{\tilde {f}}\!\!\!\!\!\!\!\!\!\!&\quad \\&&L\end{array}}}$$

${\displaystyle F}$

It is frequently possible to prove things about the free lattice directly using the universal property, but such arguments tend to be rather abstract, so a concrete construction provides a valuable alternative presentation.

Semilattices

In the case of semilattices, an explicit construction of the free semilattice ${\displaystyle F_{\vee }(X)}$ is straightforward to give; this helps illustrate several features of the definition by way of universal property. Concretely, the free semilattice ${\displaystyle F_{\vee }(X)}$ may be realised as the set of all finite nonempty subsets of ${\displaystyle X}$, with ordinary set union as the join operation ${\displaystyle \vee }$. The map ${\displaystyle \eta \colon X\longrightarrow F_{\vee }(X)}$ maps elements of ${\displaystyle X}$ to singleton sets, i.e., ${\displaystyle \eta (x)=\{x\}}$ for all ${\displaystyle x\in X}$. For any semilattice ${\displaystyle L}$ and any set map ${\displaystyle f\colon X\longrightarrow L}$, the corresponding universal morphism ${\displaystyle {\tilde {f}}\colon F_{\vee }(X)\longrightarrow L}$ is given by

$${\displaystyle {\tilde {f}}(S)=\bigvee _{x\in S}f(x)\qquad {\text{for all }}S\in F_{\vee }(X)}$$

${\displaystyle \bigvee }$

${\displaystyle L}$

This form of ${\displaystyle {\tilde {f}}}$ is forced by the universal property: any ${\displaystyle S\in F_{\vee }(X)}$ can be written as a finite union of elements on the form ${\displaystyle \eta (x)}$ for some ${\displaystyle x\in X}$, the equality in the universal property says ${\displaystyle {\tilde {f}}{\bigl (}\eta (x){\bigr )}=f(x)}$, and finally the homomorphism status of ${\displaystyle {\tilde {f}}}$ implies ${\displaystyle {\tilde {f}}(S_{1}\cup S_{2})={\tilde {f}}(S_{1})\vee {\tilde {f}}(S_{2})}$ for all ${\displaystyle S_{1},S_{2}\in F_{\vee }(X)}$. Any extension of ${\displaystyle {\tilde {f}}}$ to infinite subsets of ${\displaystyle X}$ (if there even is one) need however not be uniquely determined by these conditions, so there cannot in ${\displaystyle F_{\vee }(X)}$ be any elements corresponding to infinite subsets of ${\displaystyle X}$.

Lower semilattices

It is similarly possible to define a free functor ${\displaystyle F_{\wedge }}$ for lower semilattices, but the combination ${\displaystyle F_{\wedge }(F_{\vee }(X))}$Zdroj:https://en.wikipedia.org?pojem=Free_lattice
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.