Introduction to Computer Security

Chapter 27. Lattices

A lattice is a mathematical construction built on the notion of a group. First, we review some basic terms. Then we discuss lattices.

Basics

For a set S, a relation R is any subset of S × S. For convenience, if (a, b) ∊ R, we write aRb.

EXAMPLE: Let S = { 1, 2, 3 }. Then the relation less than or equal to (written ≤) is defined by the set R = { (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3) }. We write 1 ≤ 1 and 2 ≤ 3 for convenience, because (1, 2) ∊ R and (2, 3) ∊ R, but not 3 ≤ 2, because (3, 2) ∉ R.

The following definitions describe properties of relations.

• Definition 27–1. A relation R defined over a set S is reflexive if aRa for all a ∊ S.

• Definition 27–2. A relation R defined over a set S is antisymmetric if aRb and bRa ...