[proofplan] We proceed by induction on $n$. The base case $n = 1$ uses the single symmetric chain $\{\varnothing, \{1\}\}$. For the inductive step, given a symmetric chain decomposition of $\mathcal{P}([n-1])$, we split each chain $\mathcal{C}$ into two chains in $\mathcal{P}([n])$: the chain $\mathcal{C}^{(0)}$ extends $\mathcal{C}$ by appending $n$ to the top element, and $\mathcal{C}^{(1)}$ consists of the remaining elements of $\mathcal{C}$ (all but the top) with $n$ adjoined. Both resulting chains are symmetric, every element of $\mathcal{P}([n])$ appears exactly once, and the construction preserves the partition property. [/proofplan] [step:Verify the base case $n = 1$] For $n = 1$, the power set $\mathcal{P}([1]) = \{\varnothing, \{1\}\}$ is decomposed into the single chain $\varnothing \subsetneq \{1\}$. This chain starts at level $0$ and ends at level $1 = n$, so it spans levels $0$ through $1$, which is symmetric about $n/2 = 1/2$: the starting level $0$ and ending level $1$ satisfy $0 + 1 = n$. This is a valid symmetric chain decomposition. [/step] [step:State the inductive hypothesis and define the splitting construction] Suppose $\mathcal{P}([n-1])$ has a symmetric chain decomposition $\mathcal{C}_1, \mathcal{C}_2, \ldots, \mathcal{C}_t$, where each $\mathcal{C}_j$ is a chain $\{C_{a_j}, C_{a_j+1}, \ldots, C_{n-1-a_j}\}$ with $|C_k| = k$ for each $k$. (Here $a_j$ is the starting level of $\mathcal{C}_j$, and the chain ends at level $n - 1 - a_j$ by symmetry.) From each chain $\mathcal{C}_j$, construct two families in $\mathcal{P}([n])$: \begin{align*} \mathcal{C}_j^{(0)} &= \{C_{a_j},\, C_{a_j+1},\, \ldots,\, C_{n-1-a_j},\, C_{n-1-a_j} \cup \{n\}\}, \\ \mathcal{C}_j^{(1)} &= \{C_{a_j} \cup \{n\},\, C_{a_j+1} \cup \{n\},\, \ldots,\, C_{n-2-a_j} \cup \{n\}\}. \end{align*} The chain $\mathcal{C}_j^{(0)}$ is formed by keeping the original chain and appending the set $C_{n-1-a_j} \cup \{n\}$ (the top element of $\mathcal{C}_j$ with $n$ adjoined) at the end. The chain $\mathcal{C}_j^{(1)}$ is formed by taking all elements of $\mathcal{C}_j$ except the top element $C_{n-1-a_j}$ and adjoining $n$ to each. When $|\mathcal{C}_j| = 1$ (i.e., $a_j = (n-1)/2$ so the chain consists of a single element at the middle level), the chain $\mathcal{C}_j^{(1)}$ would be empty and is dropped. [guided] The construction doubles each chain (minus one for the top-element overlap), which accounts for the factor-of-$2$ growth from $|\mathcal{P}([n-1])| = 2^{n-1}$ to $|\mathcal{P}([n])| = 2^n$. Why do we split at the top element? The set $C_{n-1-a_j}$ is the unique element of $\mathcal{C}_j$ at the highest level. In $\mathcal{C}_j^{(0)}$, we keep $C_{n-1-a_j}$ as is and also include $C_{n-1-a_j} \cup \{n\}$ — these two are adjacent in the inclusion order, extending the chain upward by one level. In $\mathcal{C}_j^{(1)}$, we take all the elements below the top and adjoin $n$ — these form a chain because the originals form a chain and $n \notin C_k$ for any $C_k \in \mathcal{C}_j$ (since $\mathcal{C}_j \subseteq \mathcal{P}([n-1])$), so adjoining $n$ to a nested sequence preserves nesting. The top element $C_{n-1-a_j}$ is excluded from $\mathcal{C}_j^{(1)}$ because $C_{n-1-a_j} \cup \{n\}$ already appears in $\mathcal{C}_j^{(0)}$ — including it in both would create a duplicate. [/guided] [/step] [step:Verify that both $\mathcal{C}_j^{(0)}$ and $\mathcal{C}_j^{(1)}$ are symmetric chains in $\mathcal{P}([n])$] **Chain $\mathcal{C}_j^{(0)}$:** The elements are $C_{a_j} \subsetneq C_{a_j+1} \subsetneq \cdots \subsetneq C_{n-1-a_j} \subsetneq C_{n-1-a_j} \cup \{n\}$, where $|C_k| = k$ for each $k$ and $|C_{n-1-a_j} \cup \{n\}| = (n - 1 - a_j) + 1 = n - a_j$. This is a chain starting at level $a_j$ and ending at level $n - a_j$, with $a_j + (n - a_j) = n$. So $\mathcal{C}_j^{(0)}$ is a symmetric chain in $\mathcal{P}([n])$. **Chain $\mathcal{C}_j^{(1)}$:** The elements are $C_{a_j} \cup \{n\} \subsetneq C_{a_j+1} \cup \{n\} \subsetneq \cdots \subsetneq C_{n-2-a_j} \cup \{n\}$. Each set $C_k \cup \{n\}$ has size $k + 1$, so this chain passes through levels $a_j + 1, a_j + 2, \ldots, n - 1 - a_j$. The starting level is $a_j + 1$ and the ending level is $n - 1 - a_j$, with $(a_j + 1) + (n - 1 - a_j) = n$. So $\mathcal{C}_j^{(1)}$ is a symmetric chain in $\mathcal{P}([n])$. In the degenerate case $a_j = (n-1)/2$, the chain $\mathcal{C}_j$ has a single element at level $(n-1)/2$, so $\mathcal{C}_j^{(1)}$ is empty (no elements below the top) and is dropped. The chain $\mathcal{C}_j^{(0)} = \{C_{(n-1)/2},\, C_{(n-1)/2} \cup \{n\}\}$ starts at level $(n-1)/2$ and ends at level $(n+1)/2$, which is symmetric. [/step] [step:Show every element of $\mathcal{P}([n])$ appears in exactly one chain] Every $A \in \mathcal{P}([n])$ falls into exactly one of two cases. **Case 1: $n \notin A$.** Then $A \in \mathcal{P}([n-1])$, so $A$ belongs to a unique chain $\mathcal{C}_j$ by the inductive hypothesis. Since $A \in \mathcal{C}_j \subseteq \mathcal{C}_j^{(0)}$, the set $A$ appears in $\mathcal{C}_j^{(0)}$. It does not appear in any $\mathcal{C}_k^{(1)}$ because every element of $\mathcal{C}_k^{(1)}$ contains $n$. **Case 2: $n \in A$.** Then $A \setminus \{n\} \in \mathcal{P}([n-1])$, so $A \setminus \{n\}$ belongs to a unique chain $\mathcal{C}_j$, say $A \setminus \{n\} = C_k$ for some $a_j \leq k \leq n - 1 - a_j$. - If $k = n - 1 - a_j$ (i.e., $A \setminus \{n\}$ is the top element of $\mathcal{C}_j$), then $A = C_{n-1-a_j} \cup \{n\}$, which is the last element of $\mathcal{C}_j^{(0)}$. - If $k < n - 1 - a_j$ (i.e., $A \setminus \{n\}$ is not the top element of $\mathcal{C}_j$), then $A = C_k \cup \{n\}$, which appears in $\mathcal{C}_j^{(1)}$. In each sub-case, $A$ appears in exactly one of the chains $\mathcal{C}_j^{(0)}$ or $\mathcal{C}_j^{(1)}$, and this chain is uniquely determined by $j$ and the case. No element appears in two different chains. [guided] The partition argument has two key points to verify: (1) every element is accounted for, and (2) no element is double-counted. **Completeness.** Any $A \in \mathcal{P}([n])$ either contains $n$ or does not. If not, it lives in $\mathcal{P}([n-1])$ and is covered by exactly one $\mathcal{C}_j^{(0)}$. If it does contain $n$, then $A \setminus \{n\} \in \mathcal{P}([n-1])$ sits in some unique $\mathcal{C}_j$. The set $A$ is either the "capped" top element $C_{n-1-a_j} \cup \{n\}$ (appearing in $\mathcal{C}_j^{(0)}$) or a non-top element with $n$ adjoined (appearing in $\mathcal{C}_j^{(1)}$). **Disjointness.** Could the same set $A$ appear in both $\mathcal{C}_j^{(0)}$ and some $\mathcal{C}_k^{(1)}$? If $A$ is in $\mathcal{C}_j^{(0)}$ and $n \notin A$, then $A$ cannot be in any $\mathcal{C}_k^{(1)}$ (since all elements of $\mathcal{C}_k^{(1)}$ contain $n$). If $A$ is in $\mathcal{C}_j^{(0)}$ and $n \in A$, then $A = C_{n-1-a_j} \cup \{n\}$, so $A \setminus \{n\} = C_{n-1-a_j}$ is the top of $\mathcal{C}_j$. For $A$ to also be in $\mathcal{C}_k^{(1)}$, we would need $A \setminus \{n\} = C_{n-1-a_j}$ to be a non-top element of $\mathcal{C}_k$. But $A \setminus \{n\}$ belongs to a unique chain in $\mathcal{P}([n-1])$, so $k = j$, and $C_{n-1-a_j}$ is the top of $\mathcal{C}_j$, so it does not appear as a non-top element — contradiction. Similarly, elements of $\mathcal{C}_j^{(1)}$ and $\mathcal{C}_k^{(1)}$ for $j \neq k$ cannot coincide because their underlying sets $A \setminus \{n\}$ lie in distinct chains of $\mathcal{P}([n-1])$. This establishes that the chains $\{\mathcal{C}_j^{(0)}\}_j \cup \{\mathcal{C}_j^{(1)} : \mathcal{C}_j^{(1)} \neq \varnothing\}_j$ partition $\mathcal{P}([n])$ into symmetric chains. [/guided] [/step]