# 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
=> <=> = =
top T true universe empty meet /\Ø
bottom _|_ false Ø empty join \/Ø
/\ meet conjunction,and 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:

• We can define them using the concept of 'order', that is, as a partially ordered set (poset).
• We can define them using algebraic identities. 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    If a lattice represents a completely ordered set (a>b or a

### 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:

• the join operation represents the least upper bound of an arbitrary set of elements.
• the meet operation represents greatest lower bound of an arbitrary set of elements.

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

• A partially ordered set where the join of any two elements always exists is a join-semilattice.
• A partially ordered set where the meet of any two elements always exists is a meet-semilattice.
For n-ary relations:
• An n-ary relation on a set A is a subset of An
• The inverse r¬ of a binary relation on A is specified by <a,b> r iff <b,a> r
• The relational product r o s of two binary relations r,s on A is given by <a,b> r o s iif for some c: <a,c> r <c,b> s.

### 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:

• meet /\
• join \/

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 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 /\ join: where two branches meet beneath we have a 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 /\ intersection greatest lower bound (infimum) and

examples:

• the Boolean lattice defined from the family of all subsets of a finite set has this property.
• any finite topological space has a lattice of sets as its family of open sets.

### 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:

• Complement law: a¬ \/ a = 1 and a¬ \/ a = 0.
• Involution law: a¬¬ = a.
• Order-reversing: if a ? b then b¬ ? a¬.

Boolean algebras are a special case of orthocomplemented lattices