Proof of Substitution is the Unique Unital Homomorphism with Prescribed Values on the Variables: Monomials, Products, Adjoints and Composition

This proof uses the definitions Words over a Finite Alphabet: the Empty Word, Concatenation and Reversal, The Algebra of Noncommutative Polynomials in Finitely Many Self-Adjoint Variables and Substitution of Noncommutative Polynomials into the Variables; the word identities Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §monoid, Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §last-letter and Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §reversal; the clauses Noncommutative Polynomials Form a Unital Complex Algebra with Involution: Linear Extension from Monomials, Products, Adjoints and Self-Adjoint Parts §vector-space, Noncommutative Polynomials Form a Unital Complex Algebra with Involution: Linear Extension from Monomials, Products, Adjoints and Self-Adjoint Parts §linear-extension, Noncommutative Polynomials Form a Unital Complex Algebra with Involution: Linear Extension from Monomials, Products, Adjoints and Self-Adjoint Parts §monomials, Noncommutative Polynomials Form a Unital Complex Algebra with Involution: Linear Extension from Monomials, Products, Adjoints and Self-Adjoint Parts §algebra and Noncommutative Polynomials Form a Unital Complex Algebra with Involution: Linear Extension from Monomials, Products, Adjoints and Self-Adjoint Parts §adjoint, which are applied with $m$ or $l$ in place of $n$ whenever they concern $\mathcal{P}_{m}$ or $\mathcal{P}_{l}$; the uniqueness of iterates Existence and Uniqueness of Iterates of a Binary Operation; claims 1 and 3 of Basic Properties of Initial Segments of the Natural Numbers; claim 1 of Properties of Complex Conjugation and Modulus; the definitions Natural Numbers and Linear Map; and the principle of induction. By the definition of words, every $w\in W_{n}$ is either $\varnothing$ or a word of some length $k\in\mathbb{N}$.

Step 1 (letters, and the last-letter recursion). Let $j\in[n]$. The letter $(j)$ has length $1$, so by Substitution of Noncommutative Polynomials into the Variables §word-products $a_{(j)}=\pi(1)=a_{(j)_{1}}=a_{j}$, where $\pi:[1]\to\mathcal{P}_{m}$ is the map of that clause. We claim that

If $z=\varnothing$, then $z(j)=(j)$ by the definition of concatenation, and $a_{(j)}=a_{j}=1\,a_{j}=a_{\varnothing}a_{j}$ by Noncommutative Polynomials Form a Unital Complex Algebra with Involution: Linear Extension from Monomials, Products, Adjoints and Self-Adjoint Parts §monomials. Let $z$ have length $k$ and put $w=z(j)$. By Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §monoid, $w$ has length $k+1$, which is $S(k)$ by claim 1 of Natural Numbers; by the definition of concatenation, $w_{i}=z_{i}$ for $i\in[k]$ and $w_{S(k)}=(j)_{1}=j$. Let $\pi:[S(k)]\to\mathcal{P}_{m}$ be the map of Substitution of Noncommutative Polynomials into the Variables §word-products for $w$, so that $a_{w}=\pi(S(k))$. By claim 3 of Basic Properties of Initial Segments of the Natural Numbers, $[k]\subseteq[S(k)]$; let $\rho$ be the restriction of $\pi$ to $[k]$. Then $\rho(1)=a_{w_{1}}=a_{z_{1}}$ (note $1\in[k]$ by claim 1 of Basic Properties of Initial Segments of the Natural Numbers), and whenever $S(i)\in[k]$ we have $S(i)\in[S(k)]$, so $\rho(S(i))=\pi(i)\,a_{w_{S(i)}}=\rho(i)\,a_{z_{S(i)}}$. By the uniqueness in Existence and Uniqueness of Iterates of a Binary Operation (for the product of $\mathcal{P}_{m}$ and the map $i\mapsto a_{z_{i}}$ on $[k]$), $\rho$ is the map defining $a_{z}$, so $\pi(k)=\rho(k)=a_{z}$, using $k\in[k]$ (claim 1 of Basic Properties of Initial Segments of the Natural Numbers). Since $S(k)\in[S(k)]$, the recursion of $\pi$ gives $a_{w}=\pi(S(k))=\pi(k)\,a_{w_{S(k)}}=a_{z}a_{j}$. This proves $(\ast)$.

Step 2 (claim 1, products along concatenations). Let $u\in W_{n}$. If $v=\varnothing$, then $uv=u$ by the definition of concatenation and $a_{u}a_{\varnothing}=a_{u}1=a_{u}$ by Noncommutative Polynomials Form a Unital Complex Algebra with Involution: Linear Extension from Monomials, Products, Adjoints and Self-Adjoint Parts §monomials. Let $A$ be the set of $l\in\mathbb{N}$ such that $a_{uv}=a_{u}a_{v}$ for every $u\in W_{n}$ and every word $v$ of length $l$. We have $1\in A$: a word of length $1$ is a letter $(j)$ by Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §last-letter, and $a_{u(j)}=a_{u}a_{j}=a_{u}a_{(j)}$ by $(\ast)$ and Step 1. Let $l\in A$ and let $v$ have length $S(l)$. By Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §last-letter, $v=v'(j)$ with $v'$ of length $l$ and $j\in[n]$, and $uv=u(v'(j))=(uv')(j)$ by Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §monoid. Hence, by $(\ast)$, $l\in A$, associativity in Noncommutative Polynomials Form a Unital Complex Algebra with Involution: Linear Extension from Monomials, Products, Adjoints and Self-Adjoint Parts §algebra, and $(\ast)$ again,

So $S(l)\in A$, and $A=\mathbb{N}$ by Principle of Induction for the Natural Numbers. Together with the case $v=\varnothing$ this gives $a_{uv}=a_{u}a_{v}$ for all $u,v\in W_{n}$.

Step 3 (claim 1, values of $\sigma_{a}$). By Substitution of Noncommutative Polynomials into the Variables §substitution, $\sigma_{a}(x_{w})=a_{w}$ for every $w\in W_{n}$. Since $1=x_{\varnothing}$ (The Algebra of Noncommutative Polynomials in Finitely Many Self-Adjoint Variables §monomials), $\sigma_{a}(1)=a_{\varnothing}=1$ by Substitution of Noncommutative Polynomials into the Variables §word-products. For $j\in[n]$, $x_{j}=x_{(j)}$ by The Algebra of Noncommutative Polynomials in Finitely Many Self-Adjoint Variables §monomials, so $\sigma_{a}(x_{j})=a_{(j)}=a_{j}$ by Step 1.

Step 4 (two linearity facts). (i) If $T_{1}:X\to Y$ and $T_{2}:Y\to Z$ are linear maps of complex vector spaces, then $T_{2}\circ T_{1}$ is linear: $T_{2}(T_{1}(p+q))=T_{2}(T_{1}p+T_{1}q)=T_{2}T_{1}p+T_{2}T_{1}q$ and $T_{2}(T_{1}(cp))=T_{2}(c\,T_{1}p)=c\,T_{2}T_{1}p$ by the two conditions of Linear Map. (ii) For $r\in\mathcal{P}_{m}$, the maps $p\mapsto pr$ and $p\mapsto rp$ of $\mathcal{P}_{m}$ into itself are linear, by the distributive laws and the identity $(cp)q=c(pq)=p(cq)$ of Noncommutative Polynomials Form a Unital Complex Algebra with Involution: Linear Extension from Monomials, Products, Adjoints and Self-Adjoint Parts §algebra; the same holds in $\mathcal{P}_{n}$ and $\mathcal{P}_{l}$. All these spaces are complex vector spaces by Noncommutative Polynomials Form a Unital Complex Algebra with Involution: Linear Extension from Monomials, Products, Adjoints and Self-Adjoint Parts §vector-space.

Step 5 (claim 2). Fix $v\in W_{n}$ and define $L,R:\mathcal{P}_{n}\to\mathcal{P}_{m}$ by $L(p)=\sigma_{a}(p\,x_{v})$ and $R(p)=\sigma_{a}(p)\,a_{v}$. Both are linear by Step 4 and the linearity of $\sigma_{a}$. For $u\in W_{n}$, Noncommutative Polynomials Form a Unital Complex Algebra with Involution: Linear Extension from Monomials, Products, Adjoints and Self-Adjoint Parts §monomials and Steps 2 and 3 give $L(x_{u})=\sigma_{a}(x_{uv})=a_{uv}=a_{u}a_{v}=R(x_{u})$. By the uniqueness in part (b) of Noncommutative Polynomials Form a Unital Complex Algebra with Involution: Linear Extension from Monomials, Products, Adjoints and Self-Adjoint Parts §linear-extension (with $c(u)=a_{uv}$), $L=R$; that is, $\sigma_{a}(p\,x_{v})=\sigma_{a}(p)\,\sigma_{a}(x_{v})$ for all $p\in\mathcal{P}_{n}$ and $v\in W_{n}$. Now fix $p\in\mathcal{P}_{n}$ and define $L'(q)=\sigma_{a}(pq)$ and $R'(q)=\sigma_{a}(p)\,\sigma_{a}(q)$. Both are linear by Step 4, and $L'(x_{v})=R'(x_{v})$ for every $v\in W_{n}$ by what was just shown; by the same uniqueness, $L'=R'$, which is claim 2.

Step 6 (claim 3). Let $T$ be as in claim 3. We show $T(x_{w})=a_{w}$ for all $w\in W_{n}$. For $w=\varnothing$: $T(x_{\varnothing})=T(1)=1=a_{\varnothing}$. Let $B$ be the set of $k\in\mathbb{N}$ such that $T(x_{w})=a_{w}$ for every word $w$ of length $k$. A word of length $1$ is a letter $(j)$ (Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §last-letter), and $T(x_{(j)})=T(x_{j})=a_{j}=a_{(j)}$ by Step 1; so $1\in B$. If $k\in B$ and $w$ has length $S(k)$, write $w=w'(j)$ with $w'$ of length $k$ (Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §last-letter); then $x_{w}=x_{w'}x_{(j)}$ by Noncommutative Polynomials Form a Unital Complex Algebra with Involution: Linear Extension from Monomials, Products, Adjoints and Self-Adjoint Parts §monomials, and by multiplicativity of $T$, $k\in B$ and $(\ast)$,

So $S(k)\in B$ and $B=\mathbb{N}$ by Principle of Induction for the Natural Numbers. Thus the linear maps $T$ and $\sigma_{a}$ agree on every monomial, and $T=\sigma_{a}$ by the uniqueness in part (b) of Noncommutative Polynomials Form a Unital Complex Algebra with Involution: Linear Extension from Monomials, Products, Adjoints and Self-Adjoint Parts §linear-extension.

Step 7 (claim 4). Assume $a_{j}^{*}=a_{j}$ for every $j\in[n]$. First, $(a_{w^{\mathrm{rev}}})^{*}=a_{w}$ for every $w\in W_{n}$. For $w=\varnothing$: $\varnothing^{\mathrm{rev}}=\varnothing$ (Words over a Finite Alphabet: the Empty Word, Concatenation and Reversal §reversal) and $a_{\varnothing}^{*}=1^{*}=1$ by Noncommutative Polynomials Form a Unital Complex Algebra with Involution: Linear Extension from Monomials, Products, Adjoints and Self-Adjoint Parts §adjoint. Let $D$ be the set of $k\in\mathbb{N}$ such that $(a_{w^{\mathrm{rev}}})^{*}=a_{w}$ for every word $w$ of length $k$. If $w=(j)$ is a letter, $(j)^{\mathrm{rev}}=(j)$ by Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §reversal and $(a_{(j)})^{*}=a_{j}^{*}=a_{j}=a_{(j)}$ by Step 1; with Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §last-letter this gives $1\in D$. If $k\in D$ and $w$ has length $S(k)$, write $w=w'(j)$ with $w'$ of length $k$; then $w^{\mathrm{rev}}=(j)^{\mathrm{rev}}w'^{\mathrm{rev}}=(j)\,w'^{\mathrm{rev}}$ by Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §reversal, so $a_{w^{\mathrm{rev}}}=a_{j}\,a_{w'^{\mathrm{rev}}}$ by Steps 1 and 2, and by the product rule for adjoints in Noncommutative Polynomials Form a Unital Complex Algebra with Involution: Linear Extension from Monomials, Products, Adjoints and Self-Adjoint Parts §adjoint, $k\in D$, the hypothesis and $(\ast)$,

So $S(k)\in D$ and $D=\mathbb{N}$ by Principle of Induction for the Natural Numbers.

Define $\tau:\mathcal{P}_{n}\to\mathcal{P}_{m}$ by $\tau(p)=\bigl(\sigma_{a}(p^{*})\bigr)^{*}$. By Noncommutative Polynomials Form a Unital Complex Algebra with Involution: Linear Extension from Monomials, Products, Adjoints and Self-Adjoint Parts §adjoint (applied in $\mathcal{P}_{n}$ and in $\mathcal{P}_{m}$), the linearity of $\sigma_{a}$, and $\overline{\overline{c}}=c$ (claim 1 of Properties of Complex Conjugation and Modulus),

so $\tau$ is linear. For $w\in W_{n}$, $(x_{w})^{*}=x_{w^{\mathrm{rev}}}$ by Noncommutative Polynomials Form a Unital Complex Algebra with Involution: Linear Extension from Monomials, Products, Adjoints and Self-Adjoint Parts §adjoint, so $\tau(x_{w})=(a_{w^{\mathrm{rev}}})^{*}=a_{w}=\sigma_{a}(x_{w})$. By the uniqueness in part (b) of Noncommutative Polynomials Form a Unital Complex Algebra with Involution: Linear Extension from Monomials, Products, Adjoints and Self-Adjoint Parts §linear-extension, $\tau=\sigma_{a}$. Applying the adjoint and $(r^{*})^{*}=r$ (Noncommutative Polynomials Form a Unital Complex Algebra with Involution: Linear Extension from Monomials, Products, Adjoints and Self-Adjoint Parts §adjoint) to $\bigl(\sigma_{a}(p^{*})\bigr)^{*}=\sigma_{a}(p)$ gives $\sigma_{a}(p^{*})=\sigma_{a}(p)^{*}$ for every $p\in\mathcal{P}_{n}$. If $p\in\mathcal{P}_{n,\mathrm{sa}}$, then $\sigma_{a}(p)^{*}=\sigma_{a}(p^{*})=\sigma_{a}(p)$, so $\sigma_{a}(p)\in\mathcal{P}_{m,\mathrm{sa}}$ by The Algebra of Noncommutative Polynomials in Finitely Many Self-Adjoint Variables §self-adjoint.

Step 8 (claim 5). Claims 1 and 2, applied to $b$ (with $(m,l)$ in place of $(n,m)$), show that $\sigma_{b}:\mathcal{P}_{m}\to\mathcal{P}_{l}$ is linear, multiplicative and satisfies $\sigma_{b}(1)=1$. Let $T=\sigma_{b}\circ\sigma_{a}:\mathcal{P}_{n}\to\mathcal{P}_{l}$. It is linear by Step 4, and by claim 2 for $a$ and for $b$, $T(pq)=\sigma_{b}\bigl(\sigma_{a}(p)\sigma_{a}(q)\bigr)=T(p)\,T(q)$; by claim 1, $T(1)=\sigma_{b}(1)=1$ and $T(x_{j})=\sigma_{b}(a_{j})=c_{j}$ for $j\in[n]$. By claim 3 (Step 6), applied to the $n$-tuple $c$ in $\mathcal{P}_{l}$, $T=\sigma_{c}$.

Step 9 (claim 6). The identity map of $\mathcal{P}_{n}$ is linear, satisfies $\mathrm{id}(pq)=pq=\mathrm{id}(p)\,\mathrm{id}(q)$ and $\mathrm{id}(1)=1$, and sends $x_{j}$ to $x_{j}$ for $j\in[n]$. By claim 3 (Step 6), applied with $m=n$ and the $n$-tuple $x$, it equals $\sigma_{x}$, that is, $\sigma_{x}(p)=p$ for every $p\in\mathcal{P}_{n}$.