|
|
|
|
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)
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 MSC: | 06B99 (Order, lattices, ordered algebraic structures :: Lattices :: Miscellaneous) | | | 03G10 (Mathematical logic and foundations :: Algebraic logic :: Lattices and related structures) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|