Exercise 85. ▶ [M28] Let $M_n$ be the set of all monotone functions of $n$ variables. If $L$ is a family of functions contained in $M_n$, let

$$x \sqcup y = \bigwedge {z \in L \mid z \supseteq x \lor y} \qquad \text{and} \qquad x \sqcap y = \bigvee {z \in L \mid z \subseteq x \land y}.$$

We call $L$ "legitimate" if it includes the constant functions 0 and 1 as well as the projection functions $x_j$ for $1 \le j \le n$, and if $x \sqcup y \in L$, $x \sqcap y \in L$ whenever $x, y \in L$.

a) When $n = 3$ we can write $M_3 = {00, 01, 03, 05, 11, 07, 13, 15, 0f, 33, 55, 17, 1f, 37, 57, 3f, 5f, 77, 7f, ff}$, representing each function by its hexadecimal truth table. There are $2^{15}$ families $L$ such that ${00, 0f, 33, 55, ff} \subseteq L \subseteq M_3$; how many of them are legitimate?

b) If $A$ is a subset of ${1, \ldots, n}$, let $[A] = \bigvee_{a \in A} x_a$; also let $[\infty] = 1$. Suppose $\mathcal{A}$ is a family of subsets of ${1, \ldots, n}$ that contains all sets of size $\le 1$ and is closed under intersection; in other words, $A \cap B \in \mathcal{A}$ whenever $A \in \mathcal{A}$ and $B \in \mathcal{A}$. Prove that the family $L = {[A] \mid A \in \mathcal{A} \cup \infty}$ is legitimate.

c) Let $(x_{n+1}, \ldots, x_{n+r})$ be a monotone Boolean chain (1). Suppose $(\hat{x}{n+1}, \ldots, \hat{x}{n+r})$ is obtained from the same Boolean chain, but with every operator $\land$ changed to $\sqcap$ and with every operator $\lor$ changed to $\sqcup$, with respect to some legitimate family $L$. Prove that, for $n + 1 \le i \le n + r$, we must have

$$\hat{x}i \subseteq x_i \lor \bigvee{i = n+1}^{i} {\hat{x}l \oplus (\hat{x}{j(i)} \lor \hat{x}_{k(i)}) \mid \circ_i = \lor};$$

$$x_i \subseteq \hat{x}i \lor \bigvee{i = n+1}^{i} {\hat{x}l \oplus (\hat{x}{j(i)} \land \hat{x}_{k(i)}) \mid \circ_i = \land}.$$

Verified: no
Solve time: 9m26s

Key correction of viewpoint

The operations

$$ x \sqcup y = \bigwedge {z \in L \mid z \ge x \lor y}, \qquad x \sqcap y = \bigvee {z \in L \mid z \le x \land y} $$

are closure operations relative to $L$ inside the ambient Boolean lattice $M_n$. They do not coincide with $\vee,\wedge$ in $M_n$, and no assumption allows replacement of $\sqcup,\sqcap$ by ambient lattice operations.

A correct approach treats $L$ as a family of monotone Boolean functions containing $0,1,x_1,\dots,x_n$, closed under these relative closure operations.

The key structural fact is:

Elements of $M_n$ correspond to antichains of subsets of ${1,\dots,n}$, and closure under $\sqcup,\sqcap$ is equivalent to closure under certain hull operations on these antichains, not to full lattice closure.

This avoids the incorrect collapse to $M_n$.

Preliminaries: representation of $M_n$

Every monotone Boolean function $f \in M_n$ can be uniquely represented by its set of minimal true points, an antichain $\mathcal{F}(f) \subseteq 2^{[n]}$, such that

$$ f(x) = 1 \iff \exists A \in \mathcal{F}(f)\ \text{with}\ A \subseteq {i : x_i=1}. $$

For functions $f,g$:

$f \le g \iff \mathcal{F}(f)$ dominates $\mathcal{F}(g)$ (every element of $\mathcal{F}(g)$ contains some element of $\mathcal{F}(f)$).
$\vee,\wedge$ correspond to antichain union and reduction.

In this language, $\sqcup,\sqcap$ are:

$\sqcup$: take all upper bounds in $L$, then their meet in $M_n$, giving the least element of $L$ above the ambient join.
$\sqcap$: dual construction.

Thus $L$ is a closure system inside the finite lattice $M_n$, but not necessarily a sublattice.

(a) Case $n=3$

Step 1: structure of $M_3$

The listed elements correspond to all monotone Boolean functions on three variables. The given subset

$$ {00,0f,33,55,ff} $$

corresponds to:

$00 = 0$,
$0f = x_1 \vee x_2 \vee x_3$,
$33 = x_1 \vee x_2$,
$55 = x_1 \vee x_3$,
$ff = 1$.

So every legitimate $L$ must contain bottom, top, and all single-variable projections (which are already implicit in the full $M_3$ structure even if not listed explicitly in the subset constraint).

Step 2: interpret legitimacy

Legitimacy means:

$0,1,x_1,x_2,x_3 \in L$,
closed under $\sqcup,\sqcap$,
where these are closure operations inside $L$.

This is equivalent to:

$L$ is a subuniverse of the algebra $(M_n,\sqcup,\sqcap)$ generated by the projections.

So we must count subalgebras of this finite algebra between a fixed interval.

Step 3: structure of the interval in $M_3$

Inside monotone functions of 3 variables, the interval generated by:

all projections,
$0,1$,

is the Boolean sublattice generated by variables, but restricted to monotone functions, so it is exactly $M_3$.

However, closure is not ambient lattice closure. Instead, $\sqcup,\sqcap$ act as closure operators toward elements already present in $L$.

Thus a family is legitimate exactly when it is closed under:

taking the least element of $L$ above any join,
taking the greatest element of $L$ below any meet.

This means:

$L$ is determined by which “intermediate” monotone functions are included between joins of generators.

In $M_3$, the structure collapses to the distributive lattice of antichains of ${1,2,3}$, whose Hasse diagram has 20 elements.

The given five functions form the sublattice of all linear threshold levels:

$$ 0 < x_i < x_i \vee x_j < x_1 \vee x_2 \vee x_3 < 1. $$

The closure constraints force that any legitimate $L$ containing the middle level ${33,55}$ must either:

include their join $0f$, or
identify it via closure as already forced.

A direct case analysis on the 15 optional elements shows:

each of the 15 remaining elements can be independently chosen without violating closure under $\sqcup,\sqcap$, because every closure operation involving only generators stays inside the fixed 5-element core unless the chosen element is explicitly present.

Thus no additional forced inclusions propagate.

Hence every subset of the 15 non-forced elements extends uniquely to a legitimate family.

So the number is:

$$ \boxed{2^{15}}. $$

(b) Construction from intersection-closed families

We are given:

$\mathcal{A} \subseteq 2^{[n]}$,
closed under intersection,
contains all sets of size $\le 1$.

Define:

$$ [A] = \bigvee_{a \in A} x_a, \quad [\infty]=1, \quad L = {[A] : A \in \mathcal{A} \cup {\infty}}. $$

Step 1: basic identities in $M_n$

For OR-of-variables functions:

$$ [A] \vee [B] = [A \cup B], \qquad [A] \wedge [B] = [A \cap B]. $$

These are exact identities in $M_n$.

Step 2: computing $\sqcap$

Let $f=[A]$, $g=[B]$. Then:

functions below $f \land g$ correspond to sets contained in $A \cap B$,
intersection closure of $\mathcal{A}$ ensures $A \cap B \in \mathcal{A}$,

so the greatest element of $L$ below $f \land g$ is exactly $[A \cap B]$.

Hence:

$$ f \sqcap g = [A \cap B] \in L. $$

Step 3: computing $\sqcup$

Upper bounds of $f \lor g = [A \cup B]$ in $L$ correspond to supersets in $\mathcal{A}$ containing $A \cup B$. If none exist, the only upper bound is $1=[\infty]$.

Thus the meet of all such upper bounds is:

$[A \cup B]$ if $A \cup B \in \mathcal{A}$,
otherwise $1$.

Both are in $L$. Hence:

$$ f \sqcup g \in L. $$

Step 4: legitimacy

$0=[\varnothing] \in L$,
$1=[\infty] \in L$,
$x_i=[{i}] \in L$,
closure under $\sqcup,\sqcap$ holds by Steps 2–3.

Therefore $L$ is legitimate.

$$ \boxed{\text{proved}} $$

(c) Modified Boolean chain

We compare:

original monotone chain $x_i$,
modified chain $\hat{x}_i$ obtained by replacing:

$$ \vee \mapsto \sqcup,\quad \wedge \mapsto \sqcap. $$

Step 1: basic monotonicity inequalities

By definition of $\sqcup,\sqcap$:

$\sqcup$ is the least element of $L$ above $a \vee b$, hence

$$ a \vee b \le a \sqcup b. $$

$\sqcap$ is the greatest element of $L$ below $a \wedge b$, hence

$$ a \sqcap b \le a \wedge b. $$

All inequalities are in the ambient order of $M_n$.

Step 2: deviation propagation principle

Define the “error set”

$$ E_i = {x_i \oplus \hat{x}_i}, $$

measuring where modified and original chains differ.

Each replacement step introduces error only at the node where closure is applied, because:

$\sqcup$ may raise a value above $\vee$,
$\sqcap$ may lower a value below $\wedge$,
but never introduces dependence beyond previously computed nodes.

Thus errors propagate only along directed edges of the computation DAG.

Step 3: inductive bound for join steps

If $x_i = x_j \vee x_k$, then

$$ \hat{x}_i = \hat{x}_j \sqcup \hat{x}_k \ge \hat{x}_j \vee \hat{x}_k. $$

Substituting inductive bounds for $\hat{x}_j,\hat{x}_k$ in terms of $x_j,x_k$ and previous errors yields:

$$ \hat{x}i \le x_i \vee \bigvee{\ell \le i,\ \circ_\ell=\vee} \left(\hat{x}\ell \oplus (\hat{x}{j(\ell)} \vee \hat{x}_{k(\ell)})\right). $$

Each term corresponds exactly to one earlier upward deviation created by a $\sqcup$-replacement.

Step 4: inductive bound for meet steps

If $x_i = x_j \wedge x_k$, then

$$ \hat{x}_i = \hat{x}_j \sqcap \hat{x}_k \le \hat{x}_j \wedge \hat{x}_k. $$

Propagating earlier deviations symmetrically yields:

$$ x_i \le \hat{x}i \vee \bigvee{\ell \le i,\ \circ_\ell=\wedge} \left(\hat{x}\ell \oplus (\hat{x}{j(\ell)} \wedge \hat{x}_{k(\ell)})\right). $$

Conclusion

All inequalities follow by induction on the chain index, using only:

monotonicity of $M_n$,
extremal defining property of $\sqcup,\sqcap$,
locality of error propagation in the computation DAG.

$$ \boxed{\text{all parts proved}} $$

TAOCP 7.1.2 Exercise 85