Maths - Lattice

In this context a lattice is a mathematical structure with two binary operators: \/ and /\.

The lattice structure arises in algebras associated with various branches of mathematics including logic, sets and orders. These branches of mathematics tend to use different names and notations for corresponding concepts as follows:

Lattice Logic Set Order
  => contains
  <=> = =
top T true universe empty meet /\Ø
bottom _|_ false Ø empty join \/Ø
/\ meet conjunction,and M intersection greatest lower bound glb
infimum inf
\/ join disjunction,or U union least upper bound lub
supremum sup

So we can approach lattices in different ways:

divisors This lattice structure can be visualised as a diagram with nodes and lines between them, this diagram is called a Hasse diagram. This has some similarities to a graph structure however the lines in a lattice structure have a notion of 'ordering' and there will be a highest node at the top and a lowest node at the bottom.

A big application of mathematical lattices is when factoring is involved somehow.

Categorisation of Lattices

lattice complete If a lattice represents a completely ordered set (a>b or a<b is valid for any two elements) then the lattice is just a vertical line.
lattice N5 lattice m5 lattice o6
N5 M5 O6
lattice L7 lattice 23 lattice p6
L7 23 P6

Lattice and Partially Ordered Sets

A lattice is a partially ordered set in which any two elements have a least upper bound and a greatest lower bound.

For partially ordered sets:

A partially ordered set where both the join and the meet of any two elements always exist is a lattice

For n-ary relations:

Completeness

If a poset/lattice has completeness properties then it can be described as an algebraic structure.

The presence of certain completeness conditions allows us to regard the formation of certain suprema and infima as total operations of an ordered set. It turns out that in many cases it is possible to characterize completeness solely by considering appropriate algebraic structures in the sense of universal algebra, which are equipped with operations like \/ or /\. By imposing additional conditions (in form of suitable identities) on these operations, one can then derive the underlying partial order exclusively from such algebraic structures.

  completeness requires negation operation
lattice    
semilattice    
Heyting algebra   'pseudo complement'
Boolean algebra   'not' operation

Algebra of Lattice

An important algebra is a lattice, it has two operations:

identities:

identity meet join
commutativity x /\ y = y /\ x x \/ y = y \/ x
associativity (x /\ y) /\ z = x /\ (y /\ z) (x \/ y) \/ z = x \/ (y \/ z)
idempotency x /\ x = x x \/ x = x
absorption laws x \/ (x /\ y) = x x /\ (x \/ y) = x

there are also distributive laws which may, or may not, apply for a particular lattice.

identity  
distributive /\ over \/ x /\ (y \/ z) = (x /\ y) \/ z
distributive \/ over /\ x \/ (y /\ z) = (x \/ y) /\ z

Example - Factorising integer

As an example of a lattice we will look at factorising an integer, in this case 120. The following table the columns represents an integer we are trying to factorise and the row represents the the integer we are trying to factorise by. The entry in the table is a boolean value where '' represents true and blank represents false depending on whether row is a factor of column:

Is-a-factor-of 1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120
1
2        
3                
4                
5                
6                    
8                        
10                    
12                        
15                        
20                        
24                            
30                          
40                            
60                            
120                              

So the function 'is-a-factor-of' has a type signature of (int,int) -> boolean

We can convert the above 'is-a-factor-of' table into an 'is-direct-factor-of' table, So since 4 is a factor of 8 we don't need to include the factors of 4 as direct factors of 8:

Is-direct-factor-of 1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120
1                          
2                          
3                            
4                          
5                            
6                            
8                            
10                            
12                            
15                              
20                            
24                              
30                              
40                              
60                              
120                                

We can put this in terms of a diagram:

divisors divisors
prime powers prime powers

From this diagram we can create two operations [type signature of (int,int) -> int] called meet and join. In meet we go upwards in the diagram, from each of the nodes representing the operands, to find the first common node where they first meet. In join we go downwards in the diagram, from each of the nodes representing the operands, to find the first common node where they first join.

Meet /\

least common factor

\/ 1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120
1 1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120
2 2 2 6 4 10 6 8 10 12 30 20 24 30 40 60 120
3 3 6 3 12 15 6 24 30 12 15 60 24 30 120 60 120
4 4 4 12 4 20 12 8 40 12 60 20 24 60 40 60 120
5 5 10 15 20 5 30 40 10 60 15 20 120 30 40 60 120
6 6 6 6 12 30 6 24 30 12 30 60 24 30 120 60 120
8 8 8 24 8 40 24 8 40 24 120 40 24 120 40 120 120
10 10 10 30 40 10 30 40 10 60 30 20 120 30 40 60 120
12 12 12 12 12 60 12 24 60 12 60 60 24 60 120 60 120
15 15 30 15 60 15 30 120 30 60 15 60 120 30 120 60 120
20 20 20 60 20 20 60 40 20 60 60 20 120 60 40 60 120
24 24 24 24 24 120 24 24 120 24 120 120 24 120 120 120 120
30 30 30 30 60 30 30 120 30 60 30 60 120 30 120 60 120
40 40 40 120 40 40 120 40 40 120 120 40 120 120 40 120 120
60 60 60 60 60 60 60 120 60 60 60 60 120 60 120 60 120
120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120

Join \/

greatest common denominator

/\ 1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 2 1 2 1 2 2 2 2 1 2 2 2 2 2 2
3 1 1 3 1 1 3 1 1 3 3 1 3 3 1 3 3
4 1 2 1 4 1 2 4 2 4 1 4 4 2 4 4 4
5 1 1 1 1 5 1 1 5 1 5 5 1 5 5 5 5
6 1 2 3 2 1 6 2 2 6 3 2 6 6 2 6 6
8 1 2 1 4 1 2 8 2 4 1 4 8 2 8 4 8
10 1 2 1 2 5 2 2 10 2 1 10 2 10 10 10 10
12 1 2 3 4 1 6 4 2 12 3 2 12 6 4 12 12
15 1 1 3 1 5 3 1 1 3 15 5 3 15 5 15 15
20 1 2 1 4 5 2 4 10 2 5 20 4 5 20 20 20
24 1 2 3 4 1 6 8 2 12 3 4 24 6 8 12 24
30 1 2 3 2 5 6 2 10 6 15 5 6 30 10 30 30
40 1 2 1 4 5 2 8 10 4 5 20 8 10 40 20 40
60 1 2 3 4 5 6 4 10 12 15 20 12 30 20 60 60
120 1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120

Diagrams

see Hasse diagram.

Relationship Between Poset and Algebra

We can represent a poset as a diagram:

meet: where two branches meet above we have a meet /\ meet
join: where two branches meet beneath we have a join \/ join

Warning: different sources somtimes reverese the way that /\ and \/ are used so I am not sure which is the best standard to use?

Birkhoff's theorem

All distributive lattices can be represented by sets as follows:

distributive lattice set poset boolean
join operation \/ union U least upper bound (supremum) or
meet operation /\ intersectionM greatest lower bound (infimum) and

examples:

 

Complemented lattice

In the mathematical discipline of order theory, a complemented lattice is a bounded lattice in which every element a has a complement, i.e. an element b satisfying a \/ b = 1 and a \/ b = 0.

An orthocomplementation on a bounded lattice is a function that maps each element a to an "orthocomplement" a¬ in such a way that the following axioms are satisfied:

Boolean algebras are a special case of orthocomplemented lattices


metadata block
see also:

Examples and Applications

Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

cover Modern Graph Theory (Graduate Texts in Mathematics, 184)

Terminology and Notation

Specific to this page here:

 

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2017 Martin John Baker - All rights reserved - privacy policy.