**Proof.**
Let $\sigma $ be a nondegenerate $q$-simplex of the product $\Delta ^{m} \times \Delta ^{n}$, given by a chain

\[ (i_0, j_0) < (i_1, j_1) < \cdots < (i_ q, j_ q). \]

We will say that $\sigma $ is *free* if the composite maps

\[ \Delta ^{q} \xrightarrow {\sigma } \Delta ^{m} \times \Delta ^{n} \twoheadrightarrow \Delta ^{m} \quad \quad \Delta ^{q} \xrightarrow {\sigma } \Delta ^{m} \times \Delta ^{n} \twoheadrightarrow \Delta ^{n} \]

are surjective and there exists an integer $0 \leq p < q$ such that $(i_ p, j_ p) = (p,0)$ and $(i_{p+1}, j_{p+1} ) = (p, 1)$. If this condition is satisfied, then the integer $p$ is uniquely determined; we will refer to $p$ as the *index* of $\sigma $ and denote it by $p(\sigma )$. We also denote the dimension $q$ of $\sigma $ by $q(\sigma )$.

Let $\{ \sigma _1, \sigma _{2}, \cdots , \sigma _{t} \} $ be an enumeration of the collection of all free simplices of the product $\Delta ^{m} \times \Delta ^{n}$. Without loss of generality, we may assume that that this enumeration satisfies the following pair of conditions:

For $1 \leq s \leq s' \leq t$, we have $q( \sigma _ s ) \leq q( \sigma _{s'} )$.

If $1 \leq s \leq s' \leq t$ are integers satisfying $q( \sigma _ s ) = q( \sigma _{s'} )$, then $p( \sigma _ s ) \geq p( \sigma _{s'} )$.

Let $X(0)$ denote the union $(\Delta ^{m} \times \Lambda ^{n}_{0}) \cup (\operatorname{\partial \Delta }^{m} \times \Delta ^{n}) \subseteq \Delta ^{m} \times \Delta ^{n}$. For $0 < s \leq t$, we let $X(s)$ denote the smallest simplicial subset of $\Delta ^{m} \times \Delta ^{n}$ which contains $X(0)$ together with the simplices $\{ \sigma _1, \sigma _2, \ldots , \sigma _{s} \} $. We will show that the sequence

\[ X(0) \subset X(1) \subset \cdots \subset X(t) \]

satisfies the requirements of Lemma 4.4.4.7.

We first claim that $X(t) = \Delta ^{m} \times \Delta ^{n}$. Let $\sigma $ be an arbitrary nondegenerate $q$-simplex of $\Delta ^{m} \times \Delta ^{n}$, which we will identify with a sequence

\[ (i_0, j_0) < (i_1, j_1) < \cdots < (i_ q, j_ q) \]

of elements of the partially ordered set $[m] \times [n]$. We wish to show that $\sigma $ is contained in $X(t)$. Without loss of generality, we may assume that the sequence $(i_0, i_1, \ldots , i_ q)$ contains every element of the set $[m] = \{ 0 < 1 < \cdots < m \} $. (otherwise, $\sigma $ is contained in the simplicial subset $\operatorname{\partial \Delta }^ m \times \Delta ^ n \subseteq X(0) \subseteq X(t)$). Similarly, we may assume that that the sequence $(j_0, j_1, \ldots , j_ q)$ contains every element of the set $\{ 1 < 2 < \cdots < n \} $ (otherwise, $\sigma $ is is contained in the simplicial subset $\Delta ^ m \times \Lambda ^{n}_{0} \subseteq X(0) \subseteq X(t)$). In particular, the sequence $\sigma $ contains $(p,1)$, for some integer $0 \leq p \leq n$. Let us assume that $p$ is chosen as small as possible. In this case, there are two possibilities:

The sequence $\sigma $ also contains the pair $(p,0)$. In this case, $\sigma $ is a free simplex of $\Delta ^{m} \times \Delta ^{n}$, and therefore belongs to $X(t)$.

The sequence $\sigma $ does not contain $(p,0)$, and therefore has the form

\[ (0,0) < (1,0) < \cdots < (p-1, 0) < (p,1) < (i_{p+1}, j_{p+1} ) < \cdots < (i_ q, j_ q). \]

We can then identify $\sigma $ with the $p$th face of the $(q+1)$-simplex $\sigma '$ given by the sequence

\[ (0,0) < (1,0) < \cdots < (p-1, 0) < (p,0) < (p,1) < (i_{p+1}, j_{p+1} ) < \cdots < (i_ q, j_ q). \]

The simplex $\sigma '$ is free and therefore belongs to $X(t)$, so that $\sigma $ belongs to $X(t)$ as well.

We now complete the proof by verifying requirement $(2)$ of Lemma 4.4.4.7. Fix an integer $0 < s \leq t$ and let $\sigma = \sigma _{s}$ be the corresponding free simplex of $\Delta ^{m} \times \Delta ^{n}$. Let $q = q(\sigma )$ be the dimension of $\sigma $ and let $p = p(\sigma )$ be the index of $\sigma $, so that $0 \leq p < q$ and $\sigma $ has the form

\[ (0,0) < (1,0) < \cdots < (p,0) < (p,1) < (i_{p+2}, j_{p+2} ) < \cdots < (i_ q, j_ q). \]

By construction, the simplicial subset $X(s) \subseteq \Delta ^{m} \times \Delta ^{n}$ is the union of $X(s-1)$ with the image of $\sigma $. Let $K \subseteq \Delta ^1$ denote the inverse image $\sigma ^{-1} X(s-1)$. We will show that $K$ is equal to the horn $\Lambda ^{q}_{p} \subseteq \Delta ^{q}$, so that the pullback diagram of simplicial sets

\[ \xymatrix@R =50pt@C=50pt{ K \ar [r] \ar [d] & X(s-1) \ar [d] \\ \Delta ^{q} \ar [r]^-{\sigma } & X(s) } \]

is also a pushout square (Lemma 3.1.2.10).

We first show that the horn $\Lambda ^{q}_{p}$ is contained in $K$. For this, it will suffice to show that for every integer $0 \leq p' \leq q$ satisfying $p' \neq p$, the face $\tau = d_{p'}( \sigma )$ is contained in $X(s-1)$. We consider three cases:

For $p' < p$, the simplex $\tau $ is given by the sequence

\[ (0,0) < \cdots < (p'-1,0) < (p'+1,0) < \cdots < (p,0) < (p,1) < \cdots < (i_ q, j_ q), \]

which is contained in the simplicial subset $\operatorname{\partial \Delta }^{m} \times \Delta ^{n} \subseteq X(0) \subseteq X(s-1)$.

For $p' = p+1$, the simplex $\tau $ is given by the sequence

\[ (0,0) < (1,0) < \cdots < (p,0) < (i_{p+2}, j_{p+2} ) < \cdots < (i_ q, j_ q). \]

If $j_{p+2} \geq 2$, then $\tau $ belongs to the simplicial subset $\Delta ^ m \times \Lambda ^{n}_{0} \subseteq X(0) \subseteq X(s-1)$. Otherwise, we must have $(i_{p+2}, j_{p+2} ) = (p+1, 1)$, so that $\tau $ occurs as a face of the free simplex $\sigma '$ given by the sequence

\[ (0,0) < (1,0) < \cdots < (p,0) < (p+1,0) < (p+1, 1) < \cdots < (i_ q, j_ q), \]

which has dimension $q$ and index $p+1$. By construction, $\sigma '$ belongs to the set $\{ \sigma _1, \sigma _2, \ldots , \sigma _{s-1} \} $, and is therefore contained in the simplicial subset $X(s-1) \subseteq \Delta ^{m} \times \Delta ^ n$.

For $p' > p+1$, the simplex $\tau $ is given by the sequence

\[ (0,0) < \cdots < (p,0) < (p,1) < \cdots < (i_{p'-1}, j_{p'-1} ) < (i_{p'+1}, j_{p'+1} ) < \cdots < (i_ q, j_ q). \]

It follows that $\tau $ is either contained in the simplicial subset $X(0) = (\Delta ^{m} \times \Lambda ^{n}_{0}) \cup (\operatorname{\partial \Delta }^{m} \times \Delta ^{n})$ or that it is a free simplex of $\Delta ^{m} \times \Delta ^{n}$ having dimension $q-1$. In the latter case, $\tau $ must belong to the set $\{ \sigma _1, \ldots , \sigma _{s-1} \} $, and is therefore contained in the simplicial subset $X(s-1) \subseteq \Delta ^{m} \times \Delta ^{n}$.

To show that the inclusion $\Lambda ^{q}_{p} \subseteq K$ is an equality, it will suffice to show that $K$ does not contain the $p$th face of $\Delta ^{q}$. Let $\tau = d_{p}(\sigma )$ be the $p$th face of $\sigma $, given by the sequence

\[ (0,0) < (1,0) < \cdots < (p-1, 0) < (p,1) < (i_{p+1}, j_{p+1} ) < \cdots < (i_ q, j_ q). \]

We wish to show that $\tau $ is not contained in $X(s-1)$. Assume otherwise. Since $\tau $ is not contained in $X(0)$, we conclude that $\tau $ is contained in some free simplex $\sigma ' \in \{ \sigma _1, \sigma _2, \ldots , \sigma _{s-1} \} $. Note that $\tau \neq \sigma '$ (since $\tau $ is not free), so we have inequalities

\[ q-1 = q(\tau ) < q(\sigma ') \leq q(\sigma ) = q. \]

It follows that $\sigma '$ is a free $q$-simplex of $\Delta ^{m} \times \Delta ^{n}$ which contains $\tau $ and is not equal to $\sigma $, and is therefore necessarily given by the sequence

\[ (0,0) < (1,0) < \cdots < (p-1, 0) < (p-1,1) < (p,1) < (i_{p+1}, j_{p+1} ) < \cdots < (i_ q, j_ q). \]

We therefore have $p(\sigma ') = p-1 < p = p(\sigma )$, which contradicts our assumption regarding the choice of enumeration $\{ \sigma _1, \sigma _2, \ldots , \sigma _ t \} $.
$\square$