section-boolean-lattices.ipynb

Kernel:

%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

Section19.1Lattices

¶

SubsectionPartially Ordered Sets

¶

We begin the study of lattices and Boolean algebras by generalizing the idea of inequality. Recall that a on a set $X$ is a subset of $X \times X\text{.}$ A relation $P$ on $X$ is called a of $X$ if it satisfies the following axioms.

1. The relation is : $(a, a) \in P$ for all $a \in X\text{.}$

2. The relation is : if $(a,b) \in P$ and $(b,a) \in P\text{,}$ then $a = b\text{.}$

3. The relation is : if $(a, b) \in P$ and $(b, c) \in P\text{,}$ then $(a, c) \in P\text{.}$

We will usually write $a \preceq b$ to mean $(a, b) \in P$ unless some symbol is naturally associated with a particular partial order, such as $a \leq b$ with integers $a$ and $b\text{,}$ or $A \subset B$ with sets $A$ and $B\text{.}$ A set $X$ together with a partial order $\preceq$ is called a , or .

Example19.1

The set of integers (or rationals or reals) is a poset where $a \leq b$ has the usual meaning for two integers $a$ and $b$ in ${\mathbb Z}\text{.}$

Example19.2

Let $X$ be any set. We will define the of $X$ to be the set of all subsets of $X\text{.}$ We denote the power set of $X$ by ${\mathcal P}(X)\text{.}$ For example, let $X = \{ a, b, c \}\text{.}$ Then ${\mathcal P}(X)$ is the set of all subsets of the set $\{ a, b, c \}\text{:}$

$$\begin{align*} & \emptyset & & \{ a \} & & \{ b \} & & \{ c \} &\\ & \{ a, b \} & & \{ a, c\} & &\{ b, c\} & & \{ a, b, c \}. & \end{align*}$$

On any power set of a set $X\text{,}$ set inclusion, $\subset\text{,}$ is a partial order. We can represent the order on $\{ a, b, c \}$ schematically by a diagram such as the one in Figure 19.3.

Figure19.3Partial order on $\mathcal P( \{ a, b, c \})$

Example19.4

Let $G$ be a group. The set of subgroups of $G$ is a poset, where the partial order is set inclusion.

Example19.5

There can be more than one partial order on a particular set. We can form a partial order on ${\mathbb N}$ by $a \preceq b$ if $a \mid b\text{.}$ The relation is certainly reflexive since $a \mid a$ for all $a \in {\mathbb N}\text{.}$ If $m \mid n$ and $n \mid m\text{,}$ then $m = n\text{;}$ hence, the relation is also antisymmetric. The relation is transitive, because if $m \mid n$ and $n \mid p\text{,}$ then $m \mid p\text{.}$

Example19.6

Let $X = \{ 1, 2, 3, 4, 6, 8, 12, 24 \}$ be the set of divisors of 24 with the partial order defined in Example 19.5. Figure 19.7 shows the partial order on $X\text{.}$

Figure19.7A partial order on the divisors of 24

Let $Y$ be a subset of a poset $X\text{.}$ An element $u$ in $X$ is an of $Y$ if $a \preceq u$ for every element $a \in Y\text{.}$ If $u$ is an upper bound of $Y$ such that $u \preceq v$ for every other upper bound $v$ of $Y\text{,}$ then $u$ is called a or of $Y\text{.}$ An element $l$ in $X$ is said to be a of $Y$ if $l \preceq a$ for all $a \in Y\text{.}$ If $l$ is a lower bound of $Y$ such that $k \preceq l$ for every other lower bound $k$ of $Y\text{,}$ then $l$ is called a or of $Y\text{.}$

Example19.8

Let $Y = \{ 2, 3, 4, 6 \}$ be contained in the set $X$ of Example 19.6. Then $Y$ has upper bounds 12 and 24, with 12 as a least upper bound. The only lower bound is 1; hence, it must be a greatest lower bound.

As it turns out, least upper bounds and greatest lower bounds are unique if they exist.

Theorem19.9

Let $Y$ be a nonempty subset of a poset $X\text{.}$ If $Y$ has a least upper bound, then $Y$ has a unique least upper bound. If $Y$ has a greatest lower bound, then $Y$ has a unique greatest lower bound.

Proof

Let $u_1$ and $u_2$ be least upper bounds for $Y\text{.}$ By the definition of the least upper bound, $u_1 \preceq u$ for all upper bounds $u$ of $Y\text{.}$ In particular, $u_1 \preceq u_2\text{.}$ Similarly, $u_2 \preceq u_1\text{.}$ Therefore, $u_1 = u_2$ by antisymmetry. A similar argument show that the greatest lower bound is unique.

On many posets it is possible to define binary operations by using the greatest lower bound and the least upper bound of two elements. A is a poset $L$ such that every pair of elements in $L$ has a least upper bound and a greatest lower bound. The least upper bound of $a, b \in L$ is called the of $a$ and $b$ and is denoted by $a \vee b\text{.}$ The greatest lower bound of $a, b \in L$ is called the of $a$ and $b$ and is denoted by $a \wedge b\text{.}$

Example19.10

Let $X$ be a set. Then the power set of $X\text{,}$ ${\mathcal P}(X)\text{,}$ is a lattice. For two sets $A$ and $B$ in ${\mathcal P}(X)\text{,}$ the least upper bound of $A$ and $B$ is $A \cup B\text{.}$ Certainly $A \cup B$ is an upper bound of $A$ and $B\text{,}$ since $A \subset A \cup B$ and $B \subset A \cup B\text{.}$ If $C$ is some other set containing both $A$ and $B\text{,}$ then $C$ must contain $A \cup B\text{;}$ hence, $A \cup B$ is the least upper bound of $A$ and $B\text{.}$ Similarly, the greatest lower bound of $A$ and $B$ is $A \cap B\text{.}$

Example19.11

Let $G$ be a group and suppose that $X$ is the set of subgroups of $G\text{.}$ Then $X$ is a poset ordered by set-theoretic inclusion, $\subset\text{.}$ The set of subgroups of $G$ is also a lattice. If $H$ and $K$ are subgroups of $G\text{,}$ the greatest lower bound of $H$ and $K$ is $H \cap K\text{.}$ The set $H \cup K$ may not be a subgroup of $G\text{.}$ We leave it as an exercise to show that the least upper bound of $H$ and $K$ is the subgroup generated by $H \cup K\text{.}$

In set theory we have certain duality conditions. For example, by De Morgan's laws, any statement about sets that is true about $(A \cup B)'$ must also be true about $A' \cap B'\text{.}$ We also have a duality principle for lattices.

Axiom19.12Principle of Duality

Any statement that is true for all lattices remains true when $\preceq$ is replaced by $\succeq$ and $\vee$ and $\wedge$ are interchanged throughout the statement.

The following theorem tells us that a lattice is an algebraic structure with two binary operations that satisfy certain axioms.

Theorem19.13

If $L$ is a lattice, then the binary operations $\vee$ and $\wedge$ satisfy the following properties for $a, b, c \in L\text{.}$

1. Commutative laws: $a \vee b = b \vee a$ and $a \wedge b = b \wedge a\text{.}$

2. Associative laws: $a \vee ( b \vee c) = (a \vee b) \vee c$ and $a \wedge (b \wedge c) = (a \wedge b) \wedge c\text{.}$

3. Idempotent laws: $a \vee a = a$ and $a \wedge a = a\text{.}$

4. Absorption laws: $a \vee (a \wedge b) = a$ and $a \wedge ( a \vee b ) =a\text{.}$

Proof

By the Principle of Duality, we need only prove the first statement in each part.

(1) By definition $a \vee b$ is the least upper bound of $\{ a, b\}\text{,}$ and $b \vee a$ is the least upper bound of $\{ b, a \}\text{;}$ however, $\{ a, b\} = \{ b, a \}\text{.}$

(2) We will show that $a \vee ( b \vee c)$ and $(a \vee b) \vee c$ are both least upper bounds of $\{ a, b, c \}\text{.}$ Let $d = a \vee b\text{.}$ Then $c \preceq d \vee c = (a \vee b) \vee c\text{.}$ We also know that

$$\begin{equation*} a \preceq a \vee b =d \preceq d \vee c = (a \vee b) \vee c. \end{equation*}$$

A similar argument demonstrates that $b \preceq (a \vee b) \vee c\text{.}$ Therefore, $(a \vee b) \vee c$ is an upper bound of $\{ a, b, c \}\text{.}$ We now need to show that $(a \vee b) \vee c$ is the least upper bound of $\{ a, b, c\}\text{.}$ Let $u$ be some other upper bound of $\{ a, b, c \}\text{.}$ Then $a \preceq u$ and $b \preceq u\text{;}$ hence, $d = a \vee b \preceq u\text{.}$ Since $c \preceq u\text{,}$ it follows that $(a \vee b) \vee c = d \vee c \preceq u\text{.}$ Therefore, $(a \vee b) \vee c$ must be the least upper bound of $\{ a, b, c\}\text{.}$ The argument that shows $a \vee ( b \vee c)$ is the least upper bound of $\{ a, b, c \}$ is the same. Consequently, $a \vee ( b \vee c) = (a \vee b) \vee c\text{.}$

(3) The join of $a$ and $a$ is the least upper bound of $\{ a \}\text{;}$ hence, $a \vee a = a\text{.}$

(4) Let $d = a \wedge b\text{.}$ Then $a \preceq a \vee d\text{.}$ On the other hand, $d = a \wedge b \preceq a\text{,}$ and so $a \vee d \preceq a\text{.}$ Therefore, $a \vee ( a \wedge b) = a\text{.}$

Given any arbitrary set $L$ with operations $\vee$ and $\wedge\text{,}$ satisfying the conditions of the previous theorem, it is natural to ask whether or not this set comes from some lattice. The following theorem says that this is always the case.

Theorem19.14

Let $L$ be a nonempty set with two binary operations $\vee$ and $\wedge$ satisfying the commutative, associative, idempotent, and absorption laws. We can define a partial order on $L$ by $a \preceq b$ if $a \vee b = b\text{.}$ Furthermore, $L$ is a lattice with respect to $\preceq$ if for all $a, b \in L\text{,}$ we define the least upper bound and greatest lower bound of $a$ and $b$ by $a \vee b$ and $a \wedge b\text{,}$ respectively.

Proof

We first show that $L$ is a poset under $\preceq\text{.}$ Since $a \vee a = a\text{,}$ $a \preceq a$ and $\preceq$ is reflexive. To show that $\preceq$ is antisymmetric, let $a \preceq b$ and $b \preceq a\text{.}$ Then $a \vee b = b$ and $b \vee a = a\text{.}$By the commutative law, $b = a \vee b = b \vee a = a\text{.}$ Finally, we must show that $\preceq$ is transitive. Let $a \preceq b$ and $b \preceq c\text{.}$ Then $a \vee b = b$ and $b \vee c = c\text{.}$ Thus,

$$\begin{equation*} a \vee c = a \vee (b \vee c ) = ( a \vee b) \vee c = b \vee c = c, \end{equation*}$$

or $a \preceq c\text{.}$

To show that $L$ is a lattice, we must prove that $a \vee b$ and $a \wedge b$ are, respectively, the least upper and greatest lower bounds of $a$ and $b\text{.}$ Since $a=(a \vee b) \wedge a = a \wedge (a \vee b)\text{,}$ it follows that $a \preceq a \vee b\text{.}$ Similarly, $b \preceq a \vee b\text{.}$ Therefore, $a \vee b$ is an upper bound for $a$ and $b\text{.}$ Let $u$ be any other upper bound of both $a$ and $b\text{.}$ Then $a \preceq u$ and $b \preceq u\text{.}$ But $a \vee b \preceq u$ since

$$\begin{equation*} (a \vee b) \vee u = a \vee (b \vee u) = a \vee u = u. \end{equation*}$$

The proof that $a \wedge b$ is the greatest lower bound of $a$ and $b$ is left as an exercise.