[proofplan] We prove existence by a potential function argument. Among all families $\mathcal{B}$ with $|\mathcal{B}| = |\mathcal{A}|$ and $|\partial \mathcal{B}| \leq |\partial \mathcal{A}|$, choose one minimising the weight $\Sigma(\mathcal{B}) = \sum_{B \in \mathcal{B}} \sum_{i \in B} 2^i$. We show that any nontrivial valid compression $C_{UV}$ would strictly decrease $\Sigma$, contradicting minimality. The key ingredient is the [General Compression Reduces Shadow Under Inductive Hypothesis](/theorems/2593) theorem, which guarantees that the compression does not increase the shadow provided all smaller sub-compressions are already applied --- a condition ensured by the minimality of $|U|$ among violating pairs. [/proofplan] [step:Define the potential function and select a minimiser] Define the potential function \begin{align*} \Sigma: \mathcal{P}(X^{(r)}) &\to \mathbb{Z}_{\geq 0} \\ \mathcal{B} &\mapsto \sum_{B \in \mathcal{B}} \sum_{i \in B} 2^i. \end{align*} The collection $\{\mathcal{B} \subseteq X^{(r)} : |\mathcal{B}| = |\mathcal{A}|, \; |\partial \mathcal{B}| \leq |\partial \mathcal{A}|\}$ is nonempty (it contains $\mathcal{A}$ itself) and finite (since $X$ is finite). Choose $\mathcal{B}$ in this collection that minimises $\Sigma(\mathcal{B})$. [guided] We need to construct a family $\mathcal{B}$ with the same size as $\mathcal{A}$, shadow no larger than $\mathcal{A}$'s shadow, and the property of being fully compressed (i.e., $(U,V)$-compressed for all valid pairs). Rather than building $\mathcal{B}$ by iteratively applying compressions (which would require a convergence argument), we use a cleaner approach: choose $\mathcal{B}$ to minimise a potential function and show that the minimiser must already be fully compressed. Define \begin{align*} \Sigma(\mathcal{B}) = \sum_{B \in \mathcal{B}} \sum_{i \in B} 2^i. \end{align*} This assigns weight $2^i$ to the element $i$ and sums over all elements in all sets of $\mathcal{B}$. Larger elements contribute exponentially more weight. The use of powers of $2$ is essential: it ensures that replacing even the largest element of $V$ with all elements of $U$ still results in a strict decrease, because $2^{\max V} > \sum_{u \in U} 2^u$ when $\max V > \max U$ and $|U| = |V|$. (In fact, any base $> 1$ would work, but $2$ makes the argument cleanest.) The feasible set $\{\mathcal{B} \subseteq X^{(r)} : |\mathcal{B}| = |\mathcal{A}|, \; |\partial \mathcal{B}| \leq |\partial \mathcal{A}|\}$ is nonempty (it contains $\mathcal{A}$) and finite (since $X$ is finite, there are finitely many subfamilies of $X^{(r)}$). So a minimiser exists. [/guided] [/step] [step:Assume for contradiction that $\mathcal{B}$ is not fully compressed and choose a violating pair with $|U|$ minimal] Suppose for contradiction that there exists a pair $(U, V)$ with $|U| = |V|$, $U \cap V = \varnothing$, $\max V > \max U$, and $C_{UV}(\mathcal{B}) \neq \mathcal{B}$. Among all such pairs, choose one with $|U|$ minimal. Write $s = |U| = |V|$. [guided] Suppose $\mathcal{B}$ is not fully compressed. Then there exists at least one valid pair $(U, V)$ for which $C_{UV}(\mathcal{B}) \neq \mathcal{B}$. Among all such violating pairs, pick one with $|U| = |V| = s$ as small as possible. Why do we choose $|U|$ minimal? Because the [General Compression Reduces Shadow Under Inductive Hypothesis](/theorems/2593) theorem requires that for each $u \in U$, there exists $v \in V$ such that $\mathcal{B}$ is $(U \setminus \{u\}, V \setminus \{v\})$-compressed. These are compressions of size $s - 1$. By our minimality choice of $s$, the family $\mathcal{B}$ is already $(U', V')$-compressed for every valid pair with $|U'| < s$. This is the step where the minimality of $s$ converts into the hypothesis of the inductive shadow lemma. [/guided] [/step] [step:Verify the hypotheses of the general shadow lemma for the pair $(U, V)$] For any $u \in U$, we need to find $v \in V$ such that $\mathcal{B}$ is $(U \setminus \{u\}, V \setminus \{v\})$-compressed. Take any $v \in V$ with $v \neq \max V$ (such a $v$ exists since $|V| = s \geq 1$; if $s = 1$ the condition is vacuous). Then $|U \setminus \{u\}| = |V \setminus \{v\}| = s - 1$, the two sets are disjoint, and $\max(V \setminus \{v\}) \geq \max V > \max U \geq \max(U \setminus \{u\})$ if $v \neq \max V$, or if $s - 1 = 0$ the compression is trivial. In either case, $(U \setminus \{u\}, V \setminus \{v\})$ is a valid pair of size $s - 1 < s$. By the minimality of $s$, the family $\mathcal{B}$ is $(U \setminus \{u\}, V \setminus \{v\})$-compressed. Since this holds for every $u \in U$, the hypotheses of the [General Compression Reduces Shadow Under Inductive Hypothesis](/theorems/2593) theorem are satisfied. [guided] We must check that the inductive hypothesis of the [General Compression Reduces Shadow Under Inductive Hypothesis](/theorems/2593) theorem holds: for every $u \in U$, there exists $v \in V$ such that $\mathcal{B}$ is $(U \setminus \{u\}, V \setminus \{v\})$-compressed. Fix $u \in U$. Choose any $v \in V \setminus \{\max V\}$ (if $|V| \geq 2$). We verify that $(U \setminus \{u\}, V \setminus \{v\})$ is a valid compression pair: - **Size**: $|U \setminus \{u\}| = s - 1 = |V \setminus \{v\}|$. - **Disjointness**: $U \setminus \{u\}$ and $V \setminus \{v\}$ remain disjoint, since $U$ and $V$ were disjoint. - **Directional condition**: $\max(V \setminus \{v\}) = \max V$ (since we removed a non-maximal element), and $\max(U \setminus \{u\}) \leq \max U < \max V$. So $\max(V \setminus \{v\}) > \max(U \setminus \{u\})$. Since $|U \setminus \{u\}| = s - 1 < s$ and $(U, V)$ was chosen with $|U|$ minimal among violating pairs, the pair $(U \setminus \{u\}, V \setminus \{v\})$ cannot be a violating pair. Therefore $\mathcal{B}$ is $(U \setminus \{u\}, V \setminus \{v\})$-compressed. If $|V| = 1$ (i.e., $s = 1$), then $U \setminus \{u\} = V \setminus \{v\} = \varnothing$, and the $(\varnothing, \varnothing)$-compression is the identity, so $\mathcal{B}$ is $(\varnothing, \varnothing)$-compressed (the identity fixes every family). The hypothesis is satisfied in this case as well. [/guided] [/step] [step:Apply the general shadow lemma and show $C_{UV}(\mathcal{B})$ is feasible] By the [General Compression Reduces Shadow Under Inductive Hypothesis](/theorems/2593) theorem, \begin{align*} \partial C_{UV}(\mathcal{B}) \subseteq C_{UV}(\partial \mathcal{B}). \end{align*} Since $C_{UV}$ is an injection on $X^{(r-1)}$, we have $|C_{UV}(\partial \mathcal{B})| = |\partial \mathcal{B}|$, and therefore \begin{align*} |\partial C_{UV}(\mathcal{B})| \leq |C_{UV}(\partial \mathcal{B})| = |\partial \mathcal{B}| \leq |\partial \mathcal{A}|. \end{align*} Moreover, $|C_{UV}(\mathcal{B})| = |\mathcal{B}| = |\mathcal{A}|$ by the size-preserving property of general compressions. So $C_{UV}(\mathcal{B})$ belongs to the feasible set. [/step] [step:Show $\Sigma(C_{UV}(\mathcal{B})) < \Sigma(\mathcal{B})$, contradicting minimality] Since $C_{UV}(\mathcal{B}) \neq \mathcal{B}$, there exists at least one $B \in \mathcal{B}$ with $B \cap (U \cup V) = V$ and $C_{UV}(B) = (B \setminus V) \cup U \notin \mathcal{B}$. For this set, the compression replaces the elements of $V$ with the elements of $U$. The change in potential contributed by this set is \begin{align*} \sum_{u \in U} 2^u - \sum_{v \in V} 2^v. \end{align*} Since $\max V > \max U$ and both $U$ and $V$ have the same cardinality $s$, we have \begin{align*} \sum_{v \in V} 2^v \geq 2^{\max V} > 2^{\max U + 1} - 1 \geq \sum_{u \in U} 2^u, \end{align*} where the middle inequality uses $\max V > \max U$ (so $\max V \geq \max U + 1$, giving $2^{\max V} \geq 2^{\max U + 1}$), and the final inequality uses $U \subseteq \{1, \ldots, \max U\}$ with $|U| = s$ (so $\sum_{u \in U} 2^u \leq \sum_{k=1}^{\max U} 2^k = 2^{\max U + 1} - 2 < 2^{\max U + 1} - 1$). Therefore the potential strictly decreases: $\Sigma(C_{UV}(\mathcal{B})) < \Sigma(\mathcal{B})$. But $C_{UV}(\mathcal{B})$ is feasible (same size, shadow no larger), so this contradicts the choice of $\mathcal{B}$ as the minimiser of $\Sigma$. [guided] Since $C_{UV}(\mathcal{B}) \neq \mathcal{B}$, the compression acts nontrivially on at least one set. For any $B \in \mathcal{B}$ on which $C_{UV}$ acts nontrivially (i.e., $B \cap (U \cup V) = V$, so $B$ contains all of $V$ and none of $U$), the set $B$ is replaced by $C_{UV}(B) = (B \setminus V) \cup U$. The contribution of $B$ to $\Sigma$ changes from $\sum_{i \in B} 2^i$ to $\sum_{i \in C_{UV}(B)} 2^i$. Since $C_{UV}(B)$ and $B$ agree on $B \setminus V = B \cap (X \setminus (U \cup V))$, the difference in contribution is \begin{align*} \sum_{u \in U} 2^u - \sum_{v \in V} 2^v. \end{align*} We claim this is strictly negative. Since $\max V > \max U$, we have $\max V \geq \max U + 1$, so $2^{\max V} \geq 2 \cdot 2^{\max U}$. Even if $U$ contained the $s$ largest possible elements below $\max V$, the geometric sum $\sum_{u \in U} 2^u$ is bounded by $\sum_{k=\max U - s + 1}^{\max U} 2^k < 2^{\max U + 1} \leq 2^{\max V}$. Meanwhile $\sum_{v \in V} 2^v \geq 2^{\max V}$. So $\sum_{u \in U} 2^u < \sum_{v \in V} 2^v$, and the potential strictly decreases for each nontrivially compressed set. Sets in $\mathcal{B}$ on which $C_{UV}$ acts as the identity contribute the same amount to $\Sigma(\mathcal{B})$ and $\Sigma(C_{UV}(\mathcal{B}))$. Sets that are retained because their image was already present also do not increase $\Sigma$. Therefore $\Sigma(C_{UV}(\mathcal{B})) < \Sigma(\mathcal{B})$. Since $C_{UV}(\mathcal{B})$ has the same size as $\mathcal{B}$ and shadow no larger than $\mathcal{B}$'s (by the previous step), it belongs to the feasible set. But $\Sigma(C_{UV}(\mathcal{B})) < \Sigma(\mathcal{B})$ contradicts the minimality of $\mathcal{B}$. This contradiction shows that no violating pair $(U, V)$ exists, i.e., $\mathcal{B}$ is $(U,V)$-compressed for all valid pairs. [/guided] [/step] [step:Conclude that $\mathcal{B}$ is fully compressed with the required properties] Since the assumption that $\mathcal{B}$ is not fully compressed leads to a contradiction, $\mathcal{B}$ is $(U,V)$-compressed for every pair of disjoint sets $U, V \subseteq X$ with $|U| = |V|$ and $\max V > \max U$. By construction, $|\mathcal{B}| = |\mathcal{A}|$ and $|\partial \mathcal{B}| \leq |\partial \mathcal{A}|$. This completes the proof. [/step]