free lattice
   HOME

TheInfoList



In
mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It has no generally ...
, in the area of
order theory Order theory is a branch of mathematics which 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 intro ...
, a free lattice is the
free objectIn mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ha ...
corresponding to a lattice. As free objects, they have the
universal property In category theory Category theory formalizes mathematical structure and its concepts in terms of a Graph labeling, labeled directed graph called a ''Category (mathematics), category'', whose nodes are called ''objects'', and whose labelled d ...
.


Formal definition

Any set ''X'' may be used to generate the free
semilatticeIn mathematics, a join-semilattice (or upper semilattice) is a partially ordered set that has a join (mathematics), join (a least upper bound) for any nonempty set, nonempty finite set, finite subset. Duality (order theory), Dually, a meet-semilattic ...
''FX''. The free semilattice is defined to consist of all of the finite
subsets In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are u ...

subsets
of ''X'', with the semilattice operation given by ordinary
set union In set theory illustrating the intersection (set theory), intersection of two set (mathematics), sets. Set theory is a branch of mathematical logic that studies Set (mathematics), sets, which informally are collections of objects. Although any ...
. The free semilattice has the
universal property In category theory Category theory formalizes mathematical structure and its concepts in terms of a Graph labeling, labeled directed graph called a ''Category (mathematics), category'', whose nodes are called ''objects'', and whose labelled d ...
. The
universal morphism In category theory Category theory formalizes mathematical structure and its concepts in terms of a Graph labeling, labeled directed graph called a ''Category (mathematics), category'', whose nodes are called ''objects'', and whose labelled d ...
is , where η is the unit map η: ''X'' → ''FX'' which takes ''x'' ∈ ''X'' to the
singleton set In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
. 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 Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

functor
from the
category of setsIn the mathematical Mathematics (from Greek Greek may refer to: Greece Anything of, from, or related to Greece Greece ( el, Ελλάδα, , ), officially the Hellenic Republic, is a country located in Southeast Europe. Its population is ...
to the category of lattices. The functor ''F'' is
left adjoint In mathematics, specifically category theory, adjunction is a relationship that two functors may have. Two functors that stand in this relationship are known as adjoint functors, one being the left adjoint and the other the right adjoint. Pairs of ...
to the
forgetful functorIn 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 signat ...
from lattices to their underlying sets. The free lattice is a
free objectIn mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ha ...
.


Word problem

The word problem for free lattices has some interesting aspects. Consider the case of bounded lattices, i.e. algebraic structures with the two binary operations ∨ and ∧ and the two constants (
nullary operation Arity () is the number of arguments In logic and philosophy, an argument is a series of statements (in a natural language), called the premises or premisses (both spellings are acceptable), intended to determine the degree of truth of another st ...
s) 0 and 1. The set of all well-formed
expressions Expression may refer to: Linguistics * Expression (linguistics), a word, phrase, or sentence * Fixed expression, a form of words with a specific meaning * Idiom, a type of fixed expression * Metaphor#Common types, Metaphorical expression, a parti ...
that can be formulated using these operations on elements from a given set of generators ''X'' will be called W(''X''). This set of words contains many expressions that turn out to denote equal values in every lattice. For example, if ''a'' is some element of ''X'', then ''a'' ∨ 1 = 1 and ''a'' ∧ 1 =''a''. The word problem for free bounded lattices is the problem of determining which of these elements of W(''X'') denote the same element in the free bounded lattice ''FX'', and hence in every bounded lattice. The word problem may be resolved as follows. A relation ≤~ on W(''X'') may be defined inductively by setting ''w'' ≤~ ''v''
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicondit ...
one of the following holds: #   ''w'' = ''v'' (this can be restricted to the case where ''w'' and ''v'' are elements of ''X''), #   ''w'' = 0, #   ''v'' = 1, #   ''w'' = ''w''1 ∨ ''w''2 and both ''w''1~ ''v'' and ''w''2~ ''v'' hold, #   ''w'' = ''w''1 ∧ ''w''2 and either ''w''1~ ''v'' or ''w''2~ ''v'' holds, #   ''v'' = ''v''1 ∨ ''v''2 and either ''w'' ≤~ ''v''1 or ''w'' ≤~ ''v''2 holds, #   ''v'' = ''v''1 ∧ ''v''2 and both ''w'' ≤~ ''v''1 and ''w'' ≤~ ''v''2 hold. This defines a
preorder In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive relation, reflexive and Transitive relation, transitive. Preorders are more general than equivalence relations and (non-strict) partial ...
~ on W(''X''), so an
equivalence relation In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
can be defined by ''w'' ~ ''v'' when ''w'' ≤~ ''v'' and ''v'' ≤~ ''w''. One may then show that the
partially ordered 250px, The set of all subsets of a three-element set , ordered by inclusion. Distinct sets on the same horizontal level are incomparable with each other. Some other pairs, such as and , are also incomparable. In mathematics, especially order the ...
quotient space W(''X'')/~ is the free bounded lattice ''FX''. The
equivalence class In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
es of W(''X'')/~ are the sets of all words ''w'' and ''v'' with ''w'' ≤~ ''v'' and ''v'' ≤~ ''w''. Two well-formed words ''v'' and ''w'' in W(''X'') denote the same value in every bounded lattice if and only if ''w'' ≤~ ''v'' and ''v'' ≤~ ''w''; the latter conditions can be effectively decided using the above inductive definition. The table shows an example computation to show that the words ''x''∧''z'' and ''x''∧''z''∧(''x''∨''y'') denote the same value in every bounded lattice. The case of lattices that are not bounded is treated similarly, omitting rules 2. and 3. in the above construction. The solution of the word problem on free lattices 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 A lattice is an abstract structure studied in the mathematics, mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every two elements have a unique supremum (also called a least up ...
which is free for a set of four generators. By mathematical induction, induction, this eventually yields a sublattice free on countable, countably many generators. This property is reminiscent of SQ-universality in group (mathematics), groups. 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 relations of meet and join; 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 number, 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 ordinal number, ordinally indexed p_\alpha given by :p_\alpha = \operatorname\ when \alpha is a limit ordinal. 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