FACTOID # 12: It's not the government they hate: Washington DC has the highest number of hate crimes per capita in the US.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
RELATED ARTICLES
People who viewed "Semilattice" also viewed:
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Semilattice

A semilattice is a mathematical concept with two definitions, one as a type of ordered set, the other as an algebraic structure. In mathematical order theory, a semilattice is a partially ordered set (poset) closed under one of two binary operations, either supremum (join) or infimum (meet). Hence one speaks of either a join-semilattice or a meet-semilattice. If an ordered set is both a meet- and join-semilattice, it is also a lattice, a more familiar concept. ... In universal algebra, a branch of pure mathematics, an algebraic structure consists of one or more sets closed under one or more operations. ... Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. ... In mathematics, especially order theory, a partially ordered set (or poset for short) is a set equipped with a partial order relation. ... In mathematics, a binary operation, or binary operator, is a calculation involving two input quantities and one kind of a specific operation. ... In mathematics, the supremum of an ordered set S is the least element that is greater than or equal to each element of S. Consequently, it is also referred to as the least upper bound (also lub and LUB). ... In mathematics the infimum of a subset of some set is the greatest element, not necessarily in the subset, that is smaller than all other elements of the subset. ... The name lattice is suggested by the form of the Hasse diagram depicting it. ...

Contents


Semilattices as posets

Let S be a set partially ordered by the binary relation ≤. lang S,leq rang is a meet-semilattice if In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... In mathematics, especially order theory, a partially ordered set (or poset for short) is a set equipped with a partial order relation. ... In mathematics, the concept of binary relation, sometimes called dyadic relation, is exemplified by such ideas as is greater than and is equal to in arithmetic, or is congruent to in geometry, or is an element of or is a subset of in set theory. ...

For all elements x and y of S, the greatest lower bound of the set {x, y} exists.

The greatest lower bound of the set {x,y} is called the meet of x and y, denoted xwedgey. In mathematics the infimum of a subset of some set is the greatest element, not necessarily in the subset, that is smaller than all other elements of the subset. ...


Replacing "greatest lower bound" with "least upper bound" results in the dual concept of a join-semilattice. The least upper bound of {x, y} is called the join of x and y, denoted xveey. Meet and join are binary operations on S. A simple induction argument shows that the existence of all possible pairwise suprema (infima), as per the definition, implies the existence of all non-empty finite suprema (infima). In mathematics, the supremum of an ordered set S is the least element that is greater than or equal to each element of S. Consequently, it is also referred to as the least upper bound (also lub and LUB). ... In mathematics, a binary operation, or binary operator, is a calculation involving two input quantities and one kind of a specific operation. ... Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers, or otherwise is true of all members of an infinite sequence. ...


A join-semilattice may have a least element, the join of the empty set. Dually, a meet-semilattice may include a greatest element. In either case, we say that the semilattice is bounded. Wikipedia does not require that a semilattice be bounded; when a bound is required, it will be explicitly assumed. In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually. ... In the mathematical area of order theory, every partially ordered set P gives rise to a dual (or opposite) partially ordered set which is often denoted by Pop. ...


Other properties may be assumed; see the article on completeness in order theory for more discussion on this subject. That article also discusses how one may rephrase the above definition in terms of the existence of suitable Galois connections between related posets — an approach of special interest for category theoretic investigations of the concept. In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set. ... In mathematics, especially in order theory, a Galois connection is a particular correspondence between two partially ordered sets (posets). Galois connections generalize the correspondence between subgroups and subfields investigated in Galois theory. ... Category theory is a mathematical theory that deals in an abstract way with mathematical structures and relationships between them. ...


Semilattices as algebraic structures

A "meet-semilattice" is an algebraic structure lang S,wedge rang consisting of a set S with the binary operation wedge, called meet, such that for all members x, y, and z of S, the following identities hold: In universal algebra, a branch of pure mathematics, an algebraic structure consists of one or more sets closed under one or more operations. ... In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... In mathematics, a binary operation, or binary operator, is a calculation involving two input quantities and one kind of a specific operation. ... // Computer programming In object-oriented programming, object identity is a mechanism for distinguishing different objects from each other. ...

If vee, denoting join, replaces wedge in the definition just given, a join-semilattice results. Meet and join form a dual pair of binary operations, and meet-semilattice and join-semilattice are dual algebraic structures. In mathematics, associativity is a property that a binary operation can have. ... In mathematics, especially abstract algebra, a binary operation * on a set S is commutative if x * y = y * x for all x and y in S. Otherwise * is noncommutative. ... In mathematics, an idempotent element is an element which, intuitively, leaves something unchanged. ... In the mathematical area of order theory, every partially ordered set P gives rise to a dual (or opposite) partially ordered set which is often denoted by Pop. ... In mathematics, a binary operation, or binary operator, is a calculation involving two input quantities and one kind of a specific operation. ... In universal algebra, a branch of pure mathematics, an algebraic structure consists of one or more sets closed under one or more operations. ...


A meet-semilattice lang S,wedge rang is bounded if S includes the distinguished element 1 such that for all x in S,

x wedge 1 = x.

1 is the greatest element of S. Dually, lang S,vee,0 rang is a join-semilattice with least element 0 if vee and 0 replace wedge and 1, respectively, in the definition just given.


A semilattice is an idempotent, commutative semigroup, and a bounded semilattice is an idempotent commutative monoid. Alternatively, a semilattice is a commutative band. Hence semilattices are groupoids. In mathematics, an idempotent element is an element which, intuitively, leaves something unchanged. ... In mathematics, especially abstract algebra, a binary operation * on a set S is commutative if x * y = y * x for all x and y in S. Otherwise * is noncommutative. ... In mathematics, a semigroup is an algebraic structure consisting of a set S closed under an associative binary operation. ... In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single, associative binary operation and an identity element. ... In mathematics, a semigroup is an algebraic structure consisting of a set S closed under an associative binary operation. ... In abstract algebra, a magma (also called a groupoid) is a particularly basic kind of algebraic structure. ...


Connection between both definitions

An order theoretic meet-semilattice lang S,leq rang gives rise to a binary operation wedge such that lang S,wedge rang is an algebraic meet-semilattice. Conversely, the meet-semilattice lang S,wedge rang gives rise to a binary relation ≤ that partially orders S in the following way. For all elements x and y in S, In mathematics, a binary operation, or binary operator, is a calculation involving two input quantities and one kind of a specific operation. ... In mathematics, the concept of binary relation, sometimes called dyadic relation, is exemplified by such ideas as is greater than and is equal to in arithmetic, or is congruent to in geometry, or is an element of or is a subset of in set theory. ...

x leq y harr x = x wedge y.

The relation ≤ introduced in this way defines a partial ordering from which the binary operation wedge may be recovered. Conversely, the order induced by the algebraically defined semilattice lang S,wedge rang coincides with that induced by ≤.


Hence both definitions may be used interchangeably, depending on which one is more convenient for a particular purpose. A similar conclusion holds for join-semilattices and the dual ordering ≥.


Examples

Semilattices are employed to construct other order structures, or in conjunction with other completeness properties.

  • A lattice is both a join- and a meet-semilattice. The interaction of these two semilattices via the absorption law is what truly distinguishes a lattice from a semilattice.
  • The compact elements of an algebraic lattice, under the induced partial ordering, form a bounded join-semilattice.
  • Any tree structure (with the root as the least element) is a meet-semilattice. Consider for example the set of finite words over some alphabet, ordered by the prefix ordering. It has a least but no greatest element: the root is the meet of all other elements.
  • A Scott domain is a meet-semilattice.
  • Membership in any set L can be taken as a model of a semilattice with base set L, because a semilattice captures the essence of set extensionality. Let ab denote aL & bL. Two sets differing only in one or both of the:
  1. Order in which their members are listed;
  2. Multiplicity of one or more members,
are in fact the same set. Commutativity and associativity of ∧ assure (1), idempotence, (2). This semilattice is not bounded by L, because a set is not a member of itself.
  • Classical extensional mereology defines a join semilattice, with join read as binary fusion. This semilattice is bounded from above by the world individual.

The name lattice is suggested by the form of the Hasse diagram depicting it. ... In algebra, the absorption law is an identity linking a pair of binary operations. ... In the mathematical area of order theory, the compact or finite elements of a partially ordered set are those elements that cannot be subsumed by a supremum of any directed set that does not already contain members above the compact element. ... The ordinary meaning of lattice is the basis for several technical usages A cherry lattice pastry A mathematical lattice that is a type of partially ordered set. ... A tree structure is a way of representing the hierarchical nature of a structure in a graphical form. ... In the mathematical fields of order and domain theory, a Scott domain is an algebraic, bounded complete cpo. ... In mathematics, model theory is the study of the representation of mathematical concepts in terms of set theory, or the study of the models which underlie mathematical systems. ... In mathematics, this usually refers to some form of the principle, going back to Leibniz, that two mathematical objects are equal if there is no test to distinguish them. ... There are two main definitions of idempotence (IPA , like eye-dem-potent-s) in mathematics. ... Mereology is a collection of axiomatic formal systems dealing with parts and their respective wholes. ...

Semilattice morphisms

The above algebraic definition of a semilattice suggests a notion of morphism between two semilattices. Given two join-semilattices (S,vee) and (T,vee), a homomorphism of (join-) semilattices is a function f: ST such that In mathematics, a morphism is an abstraction of a structure-preserving process between two mathematical structures. ... In abstract algebra, a homomorphism is a structure-preserving map. ...

f(x vee y) = f(x) vee f(y).

Hence f is just a homomorphism of the two semigroups associated with each semilattice. If S and 'T both include a least element 0, then f should also be a monoid homomorphism, i.e. one additionally requires that A closed system S(#) with an associative operation (#) is called a semigroup , where: . . . for all a, b, c in S holds (a#b)#c = a#(b#c) Normal string concatenation is associative, and it is the standard for notation, hence : (ab)c = a(bc) = abc (unique, independent of bracketing, also... In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single, associative binary operation and an identity element. ...

f(0) = 0.

In the order-theoretic formulation, these conditions just state that a homomorphism of join-semilattices is a function that preserves binary joins and least elements, if such there be. The obvious dual--replacing wedge with vee and 0 with 1--transforms this definition of a join-semilattice homomorphism into its meet-semilattice equivalent. In the mathematical area of order theory, one often speaks about functions that preserve certain limits, i. ...


Note that any semilattice homomorphism is necessarily monotone with respect to the associated ordering relation. For an explanation see the entry preservation of limits. In mathematics, functions between ordered sets are monotonic (or monotone) if they preserve the given order. ... In the mathematical area of order theory, one often speaks about functions that preserve certain limits, i. ...


Distributive semilattices

Surprisingly, there is a notion of "distributivity" applicable to semilattices, even though distributivity conventionally requires the interaction of two binary operations. This notion requires but a single operation, and generalizes the distributivity condition for lattices. See the entry distributivity (order theory). In the mathematical area of order theory, there are various notions of the common concept of distributivity, applied to the formation of suprema and infima. ...


Complete semilattices

Nowadays, the term "complete semilattice" has no generally accepted meaning, and various inconsistent definitions exist. If completeness is taken to require the existence of all infinite joins and meets, whichever the case may be, as well as finite ones, this immediately leads to partial orders that are in fact complete lattices. For why the existence of all possible infinite joins entails the existence of all possible infinite meets (and vice versa), see the entry completeness (order theory). In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum (join) and an infimum (meet). ... In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set. ...


Nevertheless, the literature on occasion still takes complete join- or meet-semilattices to be complete lattices. In this case, "completeness" denotes a restriction on the scope of the homomorphisms. Specifically, a complete join-semilattice requires that the homomorphisms preserve all joins, but contrary to the situation one finds for completeness properties, this does not require that homomorphisms preserve all meets. On the other hand, one can conclude that every such mapping is the lower adjoint of some Galois connection. The corresponding (unique) upper adjoint will then be a homomorphism of complete meet-semilattices. This gives rise to a number of useful categorical dualities between the categories of all complete semilattices with morphisms preserving all meets or joins, respectively. In abstract algebra, a homomorphism is a structure-preserving map. ... In mathematics, especially in order theory, a Galois connection is a particular correspondence between two partially ordered sets (posets). Galois connections generalize the correspondence between subgroups and subfields investigated in Galois theory. ... In category theory, an abstract branch of mathematics, an equivalence of categories is a relation between two categories that establishes that these categories are essentially the same. There are numerous examples of categorical equivalences from many areas of mathematics. ...


Another usage of "complete meet-semilattice" refers to a bounded complete cpo. A complete meet-semilattice in this sense is arguably the "most complete" meet-semilattice that is not necessarily a complete lattice. Indeed, a complete meet-semilattice has all non-empty meets (which is equivalent to being bounded complete) and all directed joins. If such a structure has also a greatest element (the meet of the empty set), it is also a complete lattice. Thus a complete semilattice turns out to be "a complete lattice possibly lacking a top". This definition is of interest specifically in domain theory, where bounded complete algebraic cpos are studied as Scott domains. Hence Scott domains have been called algebraic semilattices. In the mathematical field of order theory, a partially ordered set is bounded complete if all of its subsets which have some upper bound also have a least upper bound. ... In mathematics, directed complete partial orders and complete partial orders are special classes of partially ordered sets. ... Domain theory is a branch of mathematics that studies special kinds of partially ordered sets commonly called domains. ... In the mathematical fields of order and domain theory, a Scott domain is an algebraic, bounded complete cpo. ...


Free semilattices

This section presupposes some knowledge of category theory. In various situations, free semilattices exist. For example, the forgetful functor from the category of join-semilattices (and their homomorphisms) to the category of sets (and functions) admits a left adjoint. Therefore, the free join-semilattice F(S) over a set S is constructed by taking the collection of all non-empty finite subsets of S, ordered by subset inclusion. Clearly, S can be embedded into F(S) by a mapping e that takes any element s in S to the singleton set {s}. Then any function f from a S to a join-semilattice T (more formally, to the underlying set of T) induces a unique homomorphism f' between the join-semilattices F(S) and T, such that f = f' o e. Explicitly, f' is given by f' (A) = vee{f(s) | s in S}. Now the obvious uniqueness of f' suffices to obtain the required adjunction -- the morphism-part of the functor F can be derived from general considerations (see adjoint functors). The case of free meet-semilattices is dual, using the opposite subset inclusion as an ordering. For join-semilattices with bottom, one just adds the empty set to the above collection of subsets. Category theory is a mathematical theory that deals in an abstract way with mathematical structures and relationships between them. ... The idea of a free object in mathematics is one of the basics of abstract algebra. ... A forgetful functor is a type of functor in mathematics. ... Category theory is a mathematical theory that deals in an abstract way with mathematical structures and relationships between them. ... The existence of many pairs of adjoint functors is a major observation of the branch of mathematics known as category theory. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, a set A is a subset of a set B, if A is contained inside B. The relationship of one set being a subset of another is called inclusion. ... The existence of many pairs of adjoint functors is a major observation of the branch of mathematics known as category theory. ...


In addition, semilattices often serve as generators for free objects within other categories. Notably, both the forgetful functors from the category of frames and frame-homomorphisms, and from the category of distributive lattices and lattice-homomorphisms, have a left adjoint. In mathematics, especially in order theory, a complete Heyting algebra is a Heyting algebra which is complete as a lattice. ...


References

Regrettably, it is often the case that standard treatments of lattice theory define a semilattice, if that, and then say no more. See the references in the entries order theory and lattice theory. Moreover, there is no literature on semilattices of comparable magnitude to that on semigroups. Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. ... See lattice for other mathematical as well as non-mathematical meanings of the term. ... In mathematics, a semigroup is an algebraic structure consisting of a set S closed under an associative binary operation. ...


See also

Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. ... This is a list of order topics, by Wikipedia page. ... See lattice for other mathematical as well as non-mathematical meanings of the term. ...

External links

  • Jipsen's algebra structures page: Semilattices.

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m