PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very high Entry average rating: Very high
[parent] algebraic definition of a lattice (Definition)

The parent entry defines a lattice as a relational structure (a poset) satisfying the condition that every pair of elements has a supremum and an infimum. Alternatively and equivalently, a lattice $L$ can be a defined directly as an algebraic structure with two binary operations called meet $\wedge$ and join $\vee$ satisfying the following conditions:

  • (idempotency of $\vee$ and $\wedge$ ): for each $a\in L$ , $a\vee a=a\wedge a=a$ ;
  • (commutativity of $\vee$ and $\wedge$ ): for every $a,b\in L$ , $a\vee b=b\vee a$ and $a\wedge b=b\wedge a$ ;
  • (associativity of $\vee$ and $\wedge$ ): for every $a,b,c\in L$ , $a\vee(b\vee c)=(a\vee b)\vee c$ and $a\wedge (b\wedge c)=(a\wedge b)\wedge c$ ; and
  • (absorption): for every $a,b\in L$ , $a\wedge (a\vee b)=a$ and $a\vee (a\wedge b)=a$ .

It is easy to see that this definition is equivalent to the one given in the parent, as follows: define a binary relation $\le$ on $L$ such that $$a\le b\quad\mbox{ iff }\quad a\vee b=b.$$ Then $\le$ is reflexive by the idempotency of $\vee$ . Next, if $a\le b$ and $b\le a$ , then $a=a\vee b=b$ , so $\le$ is anti-symmetric. Finally, if $a\le b$ and $b\le c$ , then $a\vee c= a\vee (b\vee c)=(a\vee b)\vee c=b\vee c=c$ , and therefore $a\le c$ . So $\le$ is transitive. This shows that $\le$ is a partial order on $L$ . For any $a,b\in L$ , $a\vee (a\vee b)=(a\vee a)\vee b=a\vee b$ so that $a\le a\vee b$ . Similarly, $b\le a\vee b$ . If $a\le c$ and $b\le c$ , then $(a\vee b)\vee c = a\vee (b\vee c)=a\vee c=c$ . This shows that $a\vee b$ is the supremum of $a$ and $b$ . Similarly, $a\wedge b$ is the infimum of $a$ and $b$ .

Conversely, if $(L,\le)$ is defined as in the parent entry, then by defining $$a\vee b = \sup\lbrace a,b\rbrace \quad \mbox{ and } \quad a\wedge b=\inf\lbrace a,b\rbrace,$$ the four conditions above are satisfied. For example, let us show one of the absorption laws: $a\vee (a\wedge b)=a$ . Let $c=\inf\lbrace a,b\rbrace \le a=a\wedge b$ . Then $c\le a$ so that $\sup\lbrace a,c\rbrace=a$ , which precisely translates to $a=a\vee c=a\vee(a\wedge b)$ . The remainder of the proof is left for the reader to try.




"algebraic definition of a lattice" is owned by CWoo.
(view preamble | get metadata)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: proof, remainder, translates, conversely, partial order, transitive, anti-symmetric, Reflexive, binary relation, equivalent, easy to see, absorption, associativity, commutativity, idempotency, join, meet, binary operations, algebraic structure, infimum, supremum, elements, poset, relational structure

This is version 9 of algebraic definition of a lattice, born on 2007-12-04, modified 2007-12-12.
Object id is 10091, canonical name is AlternativeDefinitionOfALattice.
Accessed 795 times total.

Classification:
AMS MSC06B99 (Order, lattices, ordered algebraic structures :: Lattices :: Miscellaneous)
 03G10 (Mathematical logic and foundations :: Algebraic logic :: Lattices and related structures)

Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)