[proofplan] We first record the universal lower bound: any chain cover must contain at least one chain for each element of a largest antichain. To prove the reverse inequality, we encode comparable pairs in a bipartite graph with two copies of $P$ and use matchings to build chain partitions. [König's theorem](/theorems/4832) for bipartite graphs identifies the largest possible matching with a smallest vertex cover, and the complement of such a cover gives an antichain of the required size. [/proofplan] [step:Reduce chain covers to chain partitions] A chain cover of $P$ means a finite family of chains whose union is $P$. We may assume, when minimizing the number of chains, that the chains are pairwise disjoint. Indeed, let $\mathcal C=\{C_1,\dots,C_k\}$ be a chain cover of $P$. For each $x\in P$, choose one index $i(x)\in\{1,\dots,k\}$ with $x\in C_{i(x)}$. Define $D_i=\{x\in P:i(x)=i\}$ for each $i\in\{1,\dots,k\}$. Since $D_i\subseteq C_i$, each nonempty $D_i$ is a chain. The nonempty sets among $D_1,\dots,D_k$ are pairwise disjoint and cover $P$, and there are at most $k$ of them. Therefore the minimum number of chains in a cover is the same as the minimum number of chains in a partition of $P$. [/step] [step:Every antichain gives a lower bound for every chain cover] Let $A\subseteq P$ be an antichain, and let $\mathcal C=\{C_1,\dots,C_k\}$ be a chain cover of $P$. Since each $C_i$ is a chain, it contains at most one element of $A$; otherwise two distinct elements of $A$ would be comparable. Since $\mathcal C$ covers $P$, every element of $A$ lies in at least one chain $C_i$. Hence $|A|\leq k$. Taking $A$ to be an antichain of maximum cardinality gives $w(P)\leq k$. Since this holds for every chain cover with $k$ chains, we obtain $w(P)\leq c(P)$, where $c(P)$ denotes the minimum number of chains whose union is $P$. [/step] [step:Build the bipartite graph from strict comparability] Let $P_L=\{x_L:x\in P\}$ and $P_R=\{x_R:x\in P\}$ be two disjoint copies of $P$. Recall that $x<y$ means $x\leq y$ and $x\neq y$. Define a bipartite graph $G$ with left vertex set $P_L$, right vertex set $P_R$, and edge set \begin{align*} E(G)=\{\{x_L,y_R\}:x,y\in P \text{ and } x<y\}. \end{align*} The strict relation $x<y$ is used, so no edge joins the two copies of the same element. Let $\nu(G)$ denote the maximum size of a matching in $G$. A matching $M\subseteq E(G)$ determines a directed relation on $P$ by putting $x\to y$ whenever $\{x_L,y_R\}\in M$. Because $M$ is a matching, each $x\in P$ has at most one outgoing arrow and at most one incoming arrow. There is no directed cycle. If \begin{align*} x_0\to x_1\to \cdots \to x_m=x_0 \end{align*} were a directed cycle with $m\geq 1$, then each arrow would give \begin{align*} x_0<x_1<\cdots <x_m=x_0, \end{align*} contradicting antisymmetry of the partial order. Thus the directed graph on $P$ defined by $M$ is a disjoint union of directed paths and isolated vertices, and each path is a chain in $P$. If $|P|=n$ and $|M|=m$, then these paths and isolated vertices form a chain partition of $P$ with $n-m$ parts, because starting with $n$ singleton chains and adding each matched arrow merges two current chains into one. Therefore \begin{align*} c(P)\leq |P|-\nu(G). \end{align*} [guided] The reason for introducing two copies of $P$ is that a matched edge is meant to say: place $x$ immediately before $y$ inside one of the chains. We define \begin{align*} P_L=\{x_L:x\in P\},\qquad P_R=\{x_R:x\in P\}, \end{align*} where $x<y$ means $x\leq y$ and $x\neq y$. We put an edge from $x_L$ to $y_R$ precisely when $x<y$ in $P$. Now let $M$ be a matching in this bipartite graph. For each edge $\{x_L,y_R\}\in M$, draw a directed arrow $x\to y$ in $P$. The matching condition is exactly what prevents branching: no left vertex is used twice, so each $x\in P$ has at most one outgoing arrow; no right vertex is used twice, so each $y\in P$ has at most one incoming arrow. We also need to check that these arrows cannot form a cycle. If there were a directed cycle \begin{align*} x_0\to x_1\to \cdots \to x_m=x_0 \end{align*} with $m\geq 1$, then the definition of the edges would give strict inequalities \begin{align*} x_0<x_1<\cdots <x_m=x_0. \end{align*} This is impossible in a poset, since transitivity gives $x_0<x_0$, contradicting irreflexivity of the strict order $<$, equivalently contradicting the definition that $x<y$ means $x\leq y$ and $x\neq y$. Hence the arrows decompose $P$ into directed paths and isolated vertices. Each directed path is a chain, because along the path the elements strictly increase in the partial order. If $|P|=n$ and the matching has $m$ edges, then adding these $m$ arrows merges singleton chains $m$ times and never creates a cycle or branching. Thus the resulting chain partition has exactly $n-m$ chains. In particular, for a maximum matching of size $\nu(G)$, we get \begin{align*} c(P)\leq |P|-\nu(G). \end{align*} [/guided] [/step] [step:Recover a matching from any chain partition] Conversely, let $P$ be partitioned into $k$ chains \begin{align*}C_1,\dots,C_k.\end{align*} For each $i$, list the elements of $C_i$ in increasing order: \begin{align*}C_i=\{x_{i,1}<x_{i,2}<\cdots <x_{i,r_i}\}.\end{align*} For every $j\in\{1,\dots,r_i-1\}$, include the edge \begin{align*}\{(x_{i,j})_L,(x_{i,j+1})_R\}\end{align*} in a set $M$. Since the chains $C_i$ are disjoint, no element of $P$ appears in two different chains. Inside a fixed chain, each element appears in at most one edge as a left endpoint and in at most one edge as a right endpoint. Hence $M$ is a matching in $G$. Its size is \begin{align*}|M|=\sum_{i=1}^k(r_i-1)=\left(\sum_{i=1}^k r_i\right)-k=|P|-k.\end{align*} Thus every chain partition with $k$ chains gives a matching of size $|P|-k$, so \begin{align*}\nu(G)\geq |P|-c(P).\end{align*} Equivalently, \begin{align*}c(P)\geq |P|-\nu(G).\end{align*} Together with the previous step, \begin{align*}c(P)=|P|-\nu(G).\end{align*} [/step] [step:Use a minimum vertex cover to construct a large antichain] We invoke König's theorem for bipartite graphs: in a finite bipartite graph, the maximum size of a matching is equal to the minimum size of a vertex cover. The graph $G$ is finite because $P$ is finite, and it is bipartite by construction with vertex classes $P_L$ and $P_R$. Let $C\subseteq P_L\cup P_R$ be a vertex cover of $G$ with minimum cardinality. By König's theorem, \begin{align*}|C|=\nu(G).\end{align*} Define \begin{align*}A=\{x\in P:x_L\notin C \text{ and } x_R\notin C\}.\end{align*} We claim that $A$ is an antichain. Suppose $x,y\in A$ and $x<y$. Then $\{x_L,y_R\}$ is an edge of $G$. Since $x\in A$, we have $x_L\notin C$; since $y\in A$, we have $y_R\notin C$. Thus the edge $\{x_L,y_R\}$ is not covered by $C$, contradicting that $C$ is a vertex cover. Hence no two distinct elements of $A$ are comparable, so $A$ is an antichain. Let \begin{align*}S=\{x\in P:x_L\in C \text{ or } x_R\in C\}.\end{align*} Then $P\setminus A=S$. The map from $C$ to $S$ that sends $x_L$ and $x_R$ to $x$ is surjective, so \begin{align*}|S|\leq |C|.\end{align*} Therefore \begin{align*}|A|=|P|-|S|\geq |P|-|C|=|P|-\nu(G).\end{align*} Since $A$ is an antichain, \begin{align*}w(P)\geq |A|\geq |P|-\nu(G)=c(P).\end{align*} [/step] [step:Combine the two inequalities] From the lower-bound step, every chain cover has at least $w(P)$ chains, so \begin{align*}w(P)\leq c(P).\end{align*} From the vertex-cover construction, there exists an antichain of cardinality at least $c(P)$, so \begin{align*}w(P)\geq c(P).\end{align*} Hence \begin{align*}w(P)=c(P).\end{align*} This is exactly the assertion that the maximum size of an antichain in $P$ equals the minimum number of chains whose union is $P$. [/step]