• Images
• Videos
• Documents
• Books
• Articles

Formal definition

As a partially ordered set, the flat lattice on a multielement set X {\displaystyle X} is given by⁴ ( X ∪ { ⊤ , ⊥ } , ⪯ ) {\displaystyle (X\cup \{\top ,\bot \},\preceq )} where ∀ a , b . a ⪯ b ↔ a = ⊥ ∨ a = b ∨ b = ⊤ . {\displaystyle \forall a,b.a\preceq b\leftrightarrow a=\bot \lor a=b\lor b=\top .}

As an algebraic structure, the flat lattice is equivalently given by⁵ ( X ∪ { ⊤ , ⊥ } , ⊓ , ⊔ ) {\displaystyle (X\cup \{\top ,\bot \},\sqcap ,\sqcup )} where ∀ a , b . a ⊓ b = { ⊥ if  a = ⊥ ∨ b = ⊥ ⊥ if  a ∈ X ∧ b ∈ X ∧ a ≠ b a if  a = b a if  b = ⊤ b if  a = ⊤ {\displaystyle \forall a,b.a\sqcap b={\begin{cases}\bot &{\text{if }}a=\bot \lor b=\bot \\\bot &{\text{if }}a\in X\land b\in X\land a\neq b\\a&{\text{if }}a=b\\a&{\text{if }}b=\top \\b&{\text{if }}a=\top \\\end{cases}}} and symmetrically for join: ∀ a , b . a ⊔ b = { ⊤ if  a = ⊤ ∨ b = ⊤ ⊤ if  a ∈ X ∧ b ∈ X ∧ a ≠ b a if  a = b a if  b = ⊥ b if  a = ⊥ {\displaystyle \forall a,b.a\sqcup b={\begin{cases}\top &{\text{if }}a=\top \lor b=\top \\\top &{\text{if }}a\in X\land b\in X\land a\neq b\\a&{\text{if }}a=b\\a&{\text{if }}b=\bot \\b&{\text{if }}a=\bot \\\end{cases}}}

All of the cases in the algebraic definition follow from the general lattice axioms except for the a ∈ X ∧ b ∈ X ∧ a ≠ b {\displaystyle a\in X\land b\in X\land a\neq b} cases; the poset definition implies them because elements of X {\displaystyle X} are incomparable, so ⊥ {\displaystyle \bot } (respectively ⊤ {\displaystyle \top } ) is the only remaining possibility for the value of the meet (respectively join).

Similarly, the algebraic definition implies the poset definition because no two distinct elements have a nontrivial meet or join, so the only relations that are possible are those that are mandatory from the lattice axioms—exactly the three disjuncts listed.

Finally, the flat lattice on X {\displaystyle X} may be defined implicitly, as the least lattice in which the elements of X {\displaystyle X} are incomparable. This too is equivalent: Consider any lattice on X {\displaystyle X} where the set's elements are pairwise incomparable. Because they are multiple and incomparable, none of them can be the lattice top or bottom, and since X {\displaystyle X} is nonempty, ⊤ {\displaystyle \top } and ⊥ {\displaystyle \bot } must be distinct. Therefore, X ∪ { ⊤ , ⊥ } {\displaystyle X\cup \{\top ,\bot \}} is the smallest possible set such a lattice could be defined on, and incomparability and the lattice axioms wholly determine the element relations to match the definitions above.

The flat lattice of an empty set or of a singleton

The three definitions above, however, do not agree when X {\displaystyle X} is the empty set or a singleton, as the implicit definition would then collapse lattice elements. Possible resolutions are to exclude these cases (as above), to define the flat lattice of such a set to be the one-element lattice (in agreement with the implicit definition) or to define it as the two- or three-element lattice (in agreement with the explicit constructions).

References

1. Brink, Chris; Kahl, Wolfram; Schmidt, Gunther (23 April 1997). Relational Methods in Computer Science. Vienna, Austria: Springer Vienna. p. 127. ISBN 978-3-211-82971-4. 978-3-211-82971-4 ↩

2. Berghammer, Rudolf; von Karger, Burghard (12 September 1990). "Relational Semantics of Functional Programs". Expert Systems in Engineering: Principles and Applications. the International Workshop on Expert Systems in Engineering. Springer. p. 105. ISBN 978-3-540-53104-3. 978-3-540-53104-3 ↩

3. Knoop, Jens (August 19, 1998). "Parallel Constant Propagation". Euro-Par'98 Parallel Processing. 4th International Euro-Par Conference. Vol. Workshop 4: Automatic Parallelisation and High-Performance Compilers. Southampton, UK: Springer Berlin Heidelberg. pp. 449–450. ISBN 978-3-540-64952-6. 978-3-540-64952-6 ↩

4. Berghammer, Rudolf; von Karger, Burghard (12 September 1990). "Relational Semantics of Functional Programs". Expert Systems in Engineering: Principles and Applications. the International Workshop on Expert Systems in Engineering. Springer. p. 105. ISBN 978-3-540-53104-3. 978-3-540-53104-3 ↩

5. Knoop, Jens (August 19, 1998). "Parallel Constant Propagation". Euro-Par'98 Parallel Processing. 4th International Euro-Par Conference. Vol. Workshop 4: Automatic Parallelisation and High-Performance Compilers. Southampton, UK: Springer Berlin Heidelberg. pp. 449–450. ISBN 978-3-540-64952-6. 978-3-540-64952-6 ↩