Free Lattice
   HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, in the area of
order theory Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article int ...
, a free lattice is the
free object In mathematics, the idea of a free object is one of the basic concepts of abstract algebra. Informally, a free object over a set ''A'' can be thought of as being a "generic" algebraic structure over ''A'': the only equations that hold between eleme ...
corresponding to a
lattice Lattice may refer to: Arts and design * Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material * Lattice (music), an organized grid model of pitch ratios * Lattice (pastry), an orna ...
. As free objects, they have the
universal property In mathematics, more specifically in category theory, a universal property is a property that characterizes up to an isomorphism the result of some constructions. Thus, universal properties can be used for defining some objects independently fr ...
.


Formal definition

Any
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
''X'' may be used to generate the free
semilattice In mathematics, a join-semilattice (or upper semilattice) is a partially ordered set that has a join (a least upper bound) for any nonempty finite subset. Dually, a meet-semilattice (or lower semilattice) is a partially ordered set which has a ...
''FX''. The free semilattice is defined to consist of all of the finite subsets of ''X'', with the semilattice operation given by ordinary
set union In set theory, the union (denoted by ∪) of a collection of sets is the set of all elements in the collection. It is one of the fundamental operations through which sets can be combined and related to each other. A refers to a union of ze ...
. The free semilattice has the
universal property In mathematics, more specifically in category theory, a universal property is a property that characterizes up to an isomorphism the result of some constructions. Thus, universal properties can be used for defining some objects independently fr ...
. The
universal morphism In mathematics, more specifically in category theory, a universal property is a property that characterizes up to an isomorphism the result of some constructions. Thus, universal properties can be used for defining some objects independently ...
is , where η is the unit map η: ''X'' → ''FX'' which takes ''x'' ∈ ''X'' to the
singleton set In mathematics, a singleton, also known as a unit set or one-point set, is a set with exactly one element. For example, the set \ is a singleton whose single element is 0. Properties Within the framework of Zermelo–Fraenkel set theory, the ...
. The universal property is then as follows: given any map ''f'': ''X'' → ''L'' from ''X'' to some arbitrary semilattice ''L'', there exists a unique semilattice homomorphism \tilde:FX \to L such that f = \tilde\circ\eta. The map \tilde may be explicitly written down; it is given by :S \in FX \mapsto \bigvee\left\ where \bigvee denotes the semilattice operation in ''L''. This construction may be promoted from semilattices to lattices; by construction the map \tilde will have the same properties as the lattice. The construction ''X'' ↦ ''FX'' is then a
functor In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) are associated to topological spaces, and m ...
from the
category of sets In the mathematical field of category theory, the category of sets, denoted as Set, is the category whose objects are sets. The arrows or morphisms between sets ''A'' and ''B'' are the total functions from ''A'' to ''B'', and the composition o ...
to the category of lattices. The functor ''F'' is
left adjoint In mathematics, specifically category theory, adjunction is a relationship that two functors may exhibit, intuitively corresponding to a weak form of equivalence between two related categories. Two functors that stand in this relationship are kno ...
to the
forgetful functor In mathematics, in the area of category theory, a forgetful functor (also known as a stripping functor) 'forgets' or drops some or all of the input's structure or properties 'before' mapping to the output. For an algebraic structure of a given sign ...
from lattices to their underlying sets. The free lattice is a
free object In mathematics, the idea of a free object is one of the basic concepts of abstract algebra. Informally, a free object over a set ''A'' can be thought of as being a "generic" algebraic structure over ''A'': the only equations that hold between eleme ...
.


Word problem

The word problem for free lattices and free bounded lattices is decidable using an inductive relation. The solution has several interesting corollaries. One is that the free lattice of a three-element set of generators is infinite. In fact, one can even show that every free lattice on three generators contains a sublattice which is free for a set of four generators. By
induction Induction, Inducible or Inductive may refer to: Biology and medicine * Labor induction (birth/pregnancy) * Induction chemotherapy, in medicine * Induced stem cells, stem cells derived from somatic, reproductive, pluripotent or other cell t ...
, this eventually yields a sublattice free on
countably In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...
many generators. This property is reminiscent of
SQ-universality In mathematics, in the realm of group theory, a countable group (mathematics), group is said to be SQ-universal if every countable group can be embedded in one of its quotient groups. SQ-universality can be thought of as a measure of largeness or c ...
in
groups A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic ide ...
. The proof that the free lattice in three generators is infinite proceeds by inductively defining :''p''''n''+1 = ''x'' ∨ (''y'' ∧ (''z'' ∨ (''x'' ∧ (''y'' ∨ (''z'' ∧ ''p''''n''))))) where ''x'', ''y'', and ''z'' are the three generators, and ''p''0 = ''x''. One then shows, using the inductive relations of the word problem, that ''p''''n''+1 is strictly greaterthat is, ''p''''n''~ ''p''''n''+1, but not ''p''''n''+1~ ''p''''n'' than ''p''''n'', and therefore all infinitely many words ''p''''n'' evaluate to different values in the free lattice ''FX''.


The complete free lattice

Another corollary is that the complete free lattice (on three or more generators) "does not exist", in the sense that it is a proper class. The proof of this follows from the word problem as well. To define a complete lattice in terms of relations, it does not suffice to use the
finitary relation In mathematics, a finitary relation over sets is a subset of the Cartesian product ; that is, it is a set of ''n''-tuples consisting of elements ''x'i'' in ''X'i''. Typically, the relation describes a possible connection between the elemen ...
s of
meet and join In mathematics, specifically order theory, the join of a subset S of a partially ordered set P is the supremum (least upper bound) of S, denoted \bigvee S, and similarly, the meet of S is the infimum (greatest lower bound), denoted \bigwedge S ...
; one must also have infinitary relations defining the meet and join of infinite subsets. For example, the infinitary relation corresponding to "join" may be defined as :\operatorname_N:(f:N\to FX) Here, ''f'' is a map from the elements of a cardinal ''N'' to ''FX''; the operator \operatorname_N denotes the supremum, in that it takes the image of ''f'' to its join. This is, of course, identical to "join" when ''N'' is a finite number; the point of this definition is to define join as a relation, even when ''N'' is an infinite cardinal. The axioms of the pre-ordering of the word problem may be adjoined by the two infinitary operators corresponding to meet and join. After doing so, one then extends the definition of p_n to an ordinally indexed p_\alpha given by :p_\alpha = \operatorname\ when \alpha is a
limit ordinal In set theory, a limit ordinal is an ordinal number that is neither zero nor a successor ordinal. Alternatively, an ordinal λ is a limit ordinal if there is an ordinal less than λ, and whenever β is an ordinal less than λ, then there exists a ...
. Then, as before, one may show that p_ is strictly greater than p_\alpha. Thus, there are at least as many elements in the complete free lattice as there are ordinals, and thus, the complete free lattice cannot exist as a set, and must therefore be a proper class.


References

* Peter T. Johnstone, ''Stone Spaces'', Cambridge Studies in Advanced Mathematics 3, Cambridge University Press, Cambridge, 1982. ({{ISBN, 0-521-23893-5) ''(See chapter 1)'' Lattice theory Free algebraic structures Combinatorics on words