Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Free lattice
Summary
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.
Because the concept of a lattice can be axiomatised in terms of two operations and satisfying certain identities, the 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 from sets to lattices, assigning to each set the free lattice equipped with a set map assigning to each the corresponding element . The universal property of these is that there for any map from to some arbitrary lattice exists a unique lattice homomorphism satisfying , or as a commutative diagram:
The functor is left adjoint to the forgetful functor from lattices to their underlying sets.
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.
In the case of semilattices, an explicit construction of the free semilattice is straightforward to give; this helps illustrate several features of the definition by way of universal property. Concretely, the free semilattice may be realised as the set of all finite nonempty subsets of , with ordinary set union as the join operation . The map maps elements of to singleton sets, i.e., for all . For any semilattice and any set map , the corresponding universal morphism is given by
where denotes the semilattice operation in .
This form of is forced by the universal property: any can be written as a finite union of elements on the form for some , the equality in the universal property says , and finally the homomorphism status of implies for all .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.