The Robinson-Schensted correspondence

Each $P_k$ is standard on the alphabet $\{w_1,\dots ,w_k\}$ by [F1], obtained by applying the insertion lemma once per letter. In particular $P_n$ has entries $1,\dots ,n$ and is standard in the published convention.

Each $Q_k$ is standard with entries $1,\dots ,k$ and $\mathrm{shape}(Q_k)=\mathrm{shape}(P_k)$: this is [F2].

In a standard tableau of size $k\ge 1$ the box of the largest entry $k$ is removable: this is [F3].

If $U$ is standard with distinct real entries and $b$ is a removable box, then reverse deletion gives $(V,x)=U-b$ with $V$ standard, its entries those of $U$ except $x$, and $V\leftarrow x=U$ with new box $b$: this is [F4].

Reinsertion restores any pair: start with standard tableaux $(U_n,R_n)$ of a common shape with $n$ boxes. Recursively, let $b_k$ be the box of label $k$ in $R_k$, set $(U_{k-1},v_k):=U_k-b_k$, and remove $b_k$ from $R_k$ to obtain $R_{k-1}$. Step 1.3 makes $b_k$ removable in both shapes, and step 1.4 preserves increasing rows and columns of $U_{k-1}$ on its remaining alphabet; $R_{k-1}$ remains standard with entries $1,\dots ,k-1$. Thus every deletion is defined. Each reinsertion $U_{k-1}\leftarrow v_k$ returns $U_k$ with new box $b_k$, so writing recording label $k$ returns $R_k$. Induction from the empty pair therefore gives the RSK pair of $(v_1,\dots ,v_n)$ as $(U_n,R_n)$.

Deletion recovers the original word: the procedure is well defined by step 2.1, and in $(P_k,Q_k)$ the box of label $k$ is precisely the new box of $P_k=P_{k-1}\leftarrow w_k$. The converse identity in [F4] therefore deletes this box to give $(P_{k-1},w_k)$; removing its recording label leaves $Q_{k-1}$. Induction for $k=n,n-1,\dots ,1$ recovers all original letters. Hence, if $P(w)=P(w^{\mathrm{\prime }})$ and $Q(w)=Q(w^{\mathrm{\prime }})$, the deterministic deletion procedure recovers both words from the same pair, so $w=w^{\mathrm{\prime }}$.

Surjectivity: let $(P,Q)$ be any pair of standard tableaux of a common shape $\lambda ⊢n$. Running the procedure of step 2.1 from $(P,Q)$ is well defined at every step by step 1.3, and produces a word $w=(w_1,\dots ,w_n)$ whose letters are the entries of $P$, each expelled exactly once (the entries of $P_{k-1}$ are those of $P_k$ with $w_k$ deleted by step 1.4), hence precisely $1,\dots ,n$; by the induction of step 2.1 the RSK pair of $w$ is $(P,Q)$.

The map $w\mapsto (P(w),Q(w))$ is therefore a bijection from $X_n$ onto the set of pairs of standard tableaux of the same shape $\lambda ⊢n$: steps 2.1 and 3.1 establish both inverse identities, and step 3.2 gives surjectivity onto the stated set. For $n=0$ both procedures have no steps and exchange the unique empty word and empty pair.