Knuth classes are the fibers of the insertion tableau

First row calculation for $cab\leftrightarrow acb$. Let $a<b<c$ be absent from an increasing row $R$ of a tableau. Write a missing bumped letter as $\mathrm{\infty }$, meaning that insertion appends and does nothing in lower rows. Compare inserting $cab$ with inserting $acb$. If inserting $a$ after $c$ does not bump that newly inserted $c$, let $d$ be the old entry bumped by $a$, $z$ the entry bumped by $c$, and $q$ the last entry bumped by $b$; the row ends the same in both orders, the carried words are $zdq$ and $dzq$, and whenever these are all finite their order is $d<q<z$. If $a$ does bump the inserted $c$, let $d,e$ be the first two old entries greater than $c$ (possibly $\mathrm{\infty }$): the carried words are $dce$ and $dec$, the final row is the same, and when $d,e$ are finite $c<d<e$. Thus the carried words are equal after null insertions are removed or are related by one of the two Knuth moves.

First row calculation for $bac\leftrightarrow bca$. Let $a<b<c$ be absent from $R$ and let $y$ be the old entry first bumped by inserting $b$, or $\mathrm{\infty }$ if there is none. Compare $bac$ with $bca$. If inserting $a$ does not bump the newly inserted $b$, let $d\in (a,b)$ be the old entry bumped by $a$ and let $z$ be the entry bumped by $c$ (or $\mathrm{\infty }$); the row ends the same, the carried words are $ydz$ and $yzd$, and when finite $d<y<z$. If $a$ bumps $b$, the carried words are $ybz$ and $yzb$, with the same final row and, when finite, $b<y<z$. Deleting null insertions makes the two carried words equal or leaves a Knuth move.

A local move preserves insertion into any tableau. Induct on the number of rows of the starting tableau $T$. Steps 1.1 and 1.2 show that after either local move the first row is identical and the words carried to the remaining rows are equal or differ by a Knuth move; those carried letters are absent from the old lower tableau because all entries and inputs are distinct. By [F5], the intermediate lower tableaux remain standard, so the induction hypothesis applies; if the carried words differ by a move, it makes their insertions into the lower tableau identical, and if they agree, determinism does so. The base case has no lower rows. Therefore inserting either side of either Knuth move into $T$ gives the same resulting tableau. A common suffix of a word then preserves equality because subsequent row insertions are deterministic, so every finite Knuth chain preserves $P$.

One insertion changes the row-reading word by Knuth moves. For a standard tableau $T$, let $u(T)$ read each row left to right, starting with the bottom row and moving upward. If $x$ appends to the top row, then $u(T)x=u(T\leftarrow x)$. Otherwise the top row is $y_1<\cdots <y_m$ and $y_j$ is the first entry greater than $x$, so $y_{j-1}<x<y_j$ when $j>1$. Starting with $y_1\cdots y_{m}x$, move $x$ left across $y_{j+1},\dots ,y_m$ using $bca\leftrightarrow bac$, then move $y_j$ left across $y_{j-1},\dots ,y_1$ using $cab\leftrightarrow acb$. This gives $y_j{y}_1\cdots y_{j-1}x{y}_{j+1}\cdots y_m$, the bumped letter followed by the updated top row. By [F5], the lower tableau remains standard after insertion of the bumped letter; induction on its height transforms the lower-row word with that letter into the row-reading word after insertion. Hence $u(T)x{\sim }_{K}u(T\leftarrow x)$.

Every word is equivalent to its tableau’s row word. Induct on the length of a permutation word $w=w^{\mathrm{\prime }}x$. The empty prefix has the empty tableau and empty row word. If $P(w^{\mathrm{\prime }})=T$, the induction hypothesis gives $w^{\mathrm{\prime }}{\sim }_{K}u(T)$; appending the same final letter preserves a chain of local moves, so $w{\sim }_{K}u(T)x$. Step 2.2 gives $u(T)x{\sim }_{K}u(T\leftarrow x)=u(P(w))$.

Knuth equivalence iff insertion tableaux agree. If $x{\sim }_{K}y$, step 2.1 shows each move in a witnessing finite chain preserves the insertion tableau, so $P(x)=P(y)$. Conversely, if $P(x)=P(y)=T$, step 3.1 gives $x{\sim }_{K}u(T)$ and $y{\sim }_{K}u(T)$; symmetry and transitivity of ${\sim }_K$ give $x{\sim }_{K}y$. This proves the first equivalence.

Dual Knuth equivalence iff recording tableaux agree. By definition and step 4.1, $x{\sim }_{dK}y$ iff $P(x^{-1})=P(y^{-1})$. By [F4] this is equivalent to $Q(x)=Q(y)$, proving the second equivalence.

The induced maps on classes are bijections. Steps 4.1 and 5.1 identify Knuth and dual Knuth classes exactly with fibers of $P$ and $Q$, respectively, so the induced maps are injective. Given any standard tableau $T$ of size $n$, the pair $(T,T)$ has common shape; by [F3] it is the RSK pair of some permutation, so every such $T$ occurs as both an insertion and a recording tableau. The induced maps are therefore surjective as well. All inductions are on finite words or finite tableaux, and no choice principle is used.