---
tag: MA20X7JCET
kind: object
name: Post's lattice
msc: [08A40, "06E30", 03B50]
instance_of: [EX9NCDFYC7]
uses: [PTKR703G6A, 0X05GS525E]
sources:
  - url: https://en.wikipedia.org/wiki/Post%27s_lattice
same_as:
  wikidata: Q11837622
  wikipedia: Post's lattice
---

## Description

*Post's lattice* is the [[lattice of clones|EX9NCDFYC7]] on the two-element set $\set{0, 1}$, that is, the set of all [[clones|PTKR703G6A]] of [[Boolean functions|0X05GS525E]] ordered by inclusion.
Emil Post gave a complete description of it, published in 1941.
Its main features are these.

1. It is countably infinite.
2. Every clone on $\set{0, 1}$ is generated by finitely many Boolean functions.
3. It has exactly five maximal clones, that is, coatoms below the clone of all Boolean functions.
   They consist of the operations that preserve $0$, that preserve $1$, that are monotone, that are self-dual, and that are affine.
4. Its least element is the clone of projections.

Check of one maximal clone: the monotone operations form a clone, since projections are monotone and a composition of monotone operations is monotone.
It is a proper clone, since negation $\neg$ is not monotone.

## Explanations

### L1 human

Post's lattice is a complete map of all the ways to pick a family of logic gates and see what circuits they can build.
Each point in the map is a closed family of Boolean functions, and lines go from smaller families to larger ones.
The map is infinite but countable, and every family in it is generated by finitely many gates.
Reading off the five families just below the top gives [[Post's functional completeness theorem|WGBR7JHBV4]].