[proofplan] We show $\partial C_{ij}(\mathcal{A}) \subseteq C_{ij}(\partial \mathcal{A})$ by taking an arbitrary $B \in \partial C_{ij}(\mathcal{A})$ and producing a witness in $\partial \mathcal{A}$ whose $C_{ij}$-image accounts for $B$. The argument splits into cases based on whether $B$ contains $i$, $j$, both, or neither. In each case, we trace back through the definition of $C_{ij}$ on families to locate a set in $\mathcal{A}$ that witnesses membership of the appropriate set in $\partial \mathcal{A}$. The size bound then follows because $C_{ij}$ preserves the cardinality of any uniform family. [/proofplan] [step:Recall the structure of $C_{ij}(\mathcal{A})$ and set up the goal] Write $\mathcal{A}' = C_{ij}(\mathcal{A})$. By the definition of the compression on families, $\mathcal{A}'$ is obtained from $\mathcal{A}$ by partitioning $\mathcal{A}$ into three parts: - **Unmoved sets:** $A \in \mathcal{A}$ with $C_{ij}(A) = A$ (either $j \notin A$, or both $i, j \in A$). These stay in $\mathcal{A}'$. - **Paired sets:** $A \in \mathcal{A}$ with $C_{ij}(A) \neq A$ and $C_{ij}(A) \in \mathcal{A}$. Both $A$ and $C_{ij}(A)$ remain in $\mathcal{A}'$. - **Shifted sets:** $A \in \mathcal{A}$ with $C_{ij}(A) \neq A$ and $C_{ij}(A) \notin \mathcal{A}$. The set $A$ is replaced by $C_{ij}(A)$ in $\mathcal{A}'$. In all cases, $|\mathcal{A}'| = |\mathcal{A}|$. Now let $B \in \partial \mathcal{A}'$, so $B \in X^{(r-1)}$ and $B \subset A'$ for some $A' \in \mathcal{A}'$. We must show $B \in C_{ij}(\partial \mathcal{A})$. [/step] [step:Handle the case $i \in B$] Suppose $i \in B$. Then $C_{ij}(B) = B$ (the swap condition "$j \in B$ and $i \notin B$" fails because $i \in B$). Since $i \in B \subset A'$, the element $i \in A'$. This means $C_{ij}(A') = A'$ (the swap condition for $A'$ fails because $i \in A'$). By the definition of $\mathcal{A}'$, the set $A'$ being fixed by $C_{ij}$ and belonging to $\mathcal{A}'$ implies $A' \in \mathcal{A}$. Since $B \subset A'$ and $A' \in \mathcal{A}$, we have $B \in \partial \mathcal{A}$. Since $C_{ij}(B) = B$, the set $B$ belongs to $C_{ij}(\partial \mathcal{A})$ (it is either mapped to itself or retained as an original). [/step] [step:Handle the case $j \notin B$ and $i \notin B$] Suppose $i \notin B$ and $j \notin B$. Then $C_{ij}(B) = B$ (since $j \notin B$, the swap condition fails). **Sub-case (a): $A' \in \mathcal{A}$.** Then $B \subset A' \in \mathcal{A}$ gives $B \in \partial \mathcal{A}$, and $C_{ij}(B) = B$ gives $B \in C_{ij}(\partial \mathcal{A})$. **Sub-case (b): $A' = C_{ij}(A)$ for some $A \in \mathcal{A}$ with $A' \neq A$.** Then $j \in A$, $i \notin A$, and $A' = (A \setminus \{j\}) \cup \{i\}$. Since $j \notin A'$ (as $j$ was removed) and $B \subset A'$, and also $i \in A'$ but $i \notin B$, the unique element of $A' \setminus B$ must be some element $a$. Now consider $B \subset A$: we have $B \subset A' = (A \setminus \{j\}) \cup \{i\}$, so every element of $B$ is in $(A \setminus \{j\}) \cup \{i\}$. Since $i \notin B$, every element of $B$ is in $A \setminus \{j\} \subset A$. Therefore $B \subset A$ and $A \in \mathcal{A}$, giving $B \in \partial \mathcal{A}$. Since $C_{ij}(B) = B$, we have $B \in C_{ij}(\partial \mathcal{A})$. [guided] In Sub-case (b), the parent $A'$ was produced by shifting some $A \in \mathcal{A}$: the element $j \in A$ was replaced by $i$ to form $A'$. Since $B$ avoids both $i$ and $j$, the set $B$ lies entirely in the "stable part" $A \setminus \{j\} = A' \setminus \{i\}$, which is common to both $A$ and $A'$. So $B$ is a subset of the original $A \in \mathcal{A}$, and $B \in \partial \mathcal{A}$ follows. [/guided] [/step] [step:Handle the case $j \in B$ and $i \notin B$] Suppose $j \in B$ and $i \notin B$. Then $C_{ij}(B) = (B \setminus \{j\}) \cup \{i\} \neq B$. We must show $B \in C_{ij}(\partial \mathcal{A})$. By the family-level definition, this holds if either (i) $B \in \partial \mathcal{A}$ and $C_{ij}(B) \in \partial \mathcal{A}$, or (ii) $B \in \partial \mathcal{A}$ and $C_{ij}(B) \notin \partial \mathcal{A}$ (in which case $C_{ij}(B)$ replaces $B$, not $B$ itself), or (iii) $C_{ij}(B) \in \partial \mathcal{A}$ (so $B$ is retained as the original when its image is also present). More precisely, $B \in C_{ij}(\partial \mathcal{A})$ if and only if at least one of the following holds: $B \in \partial \mathcal{A}$, or $C_{ij}(B) \in \partial \mathcal{A}$. We verify that $B \in \partial \mathcal{A}$. Since $j \in B \subset A'$, the element $j \in A'$. If $A' = C_{ij}(A)$ for some $A \neq A'$, then $A' = (A \setminus \{j\}) \cup \{i\}$, so $j \notin A'$, contradicting $j \in A'$. Therefore $A' \in \mathcal{A}$ (it was not produced by shifting some other set). Since $B \subset A'$ and $A' \in \mathcal{A}$, we have $B \in \partial \mathcal{A}$. We also verify that $C_{ij}(B) \in \partial \mathcal{A}$. Set $B' = C_{ij}(B) = (B \setminus \{j\}) \cup \{i\}$. If $i \in A'$: then $B' = (B \setminus \{j\}) \cup \{i\} \subset A'$ (since $B \setminus \{j\} \subset A' \setminus \{j\}$ and $i \in A'$, and $|B'| = r - 1 < r = |A'|$). Since $A' \in \mathcal{A}$, this gives $B' \in \partial \mathcal{A}$. If $i \notin A'$: then $j \in A'$ and $i \notin A'$, so $C_{ij}(A') = (A' \setminus \{j\}) \cup \{i\}$. Since $A' \in \mathcal{A}'$ and $A' \in \mathcal{A}$, the definition of $\mathcal{A}'$ guarantees that $C_{ij}(A') \in \mathcal{A}$ (otherwise $A'$ would have been shifted out of $\mathcal{A}'$ and replaced by $C_{ij}(A')$, but since $A'$ remains in $\mathcal{A}'$, the only possibility under the paired-set rule is that $C_{ij}(A') \in \mathcal{A}$). Now $B' = (B \setminus \{j\}) \cup \{i\} \subset (A' \setminus \{j\}) \cup \{i\} = C_{ij}(A') \in \mathcal{A}$, so $B' \in \partial \mathcal{A}$. In both sub-cases, $B' = C_{ij}(B) \in \partial \mathcal{A}$, so $B \in C_{ij}(\partial \mathcal{A})$. [guided] This is the key case: $C_{ij}$ acts non-trivially on $B$, swapping $j$ for $i$. The difficulty is ensuring that $B$ ends up in $C_{ij}(\partial \mathcal{A})$, which requires showing that *both* $B$ and its image $C_{ij}(B)$ belong to $\partial \mathcal{A}$ (so that $B$ is retained as the "original" in the compressed family). The first claim ($B \in \partial \mathcal{A}$) follows from a simple observation: $j \in B \subset A'$ forces $j \in A'$, which means $A'$ could not have been produced by a $C_{ij}$-shift (since shifting removes $j$). So $A' \in \mathcal{A}$, and $B \subset A'$ gives $B \in \partial \mathcal{A}$. The second claim ($C_{ij}(B) \in \partial \mathcal{A}$) requires finding a set in $\mathcal{A}$ that contains $(B \setminus \{j\}) \cup \{i\}$. If $i$ is already in $A'$, then $A'$ itself works. If $i \notin A'$, we use the compressed set $C_{ij}(A') \in \mathcal{A}$: since $A'$ is in the compressed family $\mathcal{A}'$ and is not a shifted set (it is genuinely in $\mathcal{A}$), the only reason $A'$ survives in $\mathcal{A}'$ despite having $j \in A'$ and $i \notin A'$ is that $C_{ij}(A')$ is *also* in $\mathcal{A}$ (the paired-set case). This companion set $C_{ij}(A') = (A' \setminus \{j\}) \cup \{i\} \in \mathcal{A}$ contains $C_{ij}(B)$. [/guided] [/step] [step:Conclude the inclusion and derive the size bound] The four cases ($i \in B$ with $j \in B$ or $j \notin B$; $i \notin B$ with $j \notin B$; $i \notin B$ with $j \in B$) are exhaustive. In every case, $B \in C_{ij}(\partial \mathcal{A})$. Therefore: \begin{align*} \partial C_{ij}(\mathcal{A}) \subseteq C_{ij}(\partial \mathcal{A}). \end{align*} For the size bound: the map $C_{ij}$ on individual sets is an injection from $X^{(k)}$ to $X^{(k)}$ for any $k$, and the family-level operation $C_{ij}$ satisfies $|C_{ij}(\mathcal{F})| = |\mathcal{F}|$ for any $\mathcal{F} \subseteq X^{(k)}$ (each set is either fixed or swapped with its image, with no duplicates created). Applying this to $\mathcal{F} = \partial \mathcal{A} \subseteq X^{(r-1)}$: \begin{align*} |\partial C_{ij}(\mathcal{A})| \leq |C_{ij}(\partial \mathcal{A})| = |\partial \mathcal{A}|. \end{align*} [/step]