一意可読性

条件 2 を $C_m(w)$ と書く。$C_0(w)$ は $w=\varepsilon$ と同値である。$w=\varepsilon$ なら真の接頭辞がなく $K(\varepsilon)=0$ なので $C_0(\varepsilon)$ が成り立ち、$w\ne\varepsilon$ なら空列 $\varepsilon$ が真の接頭辞で $K(\varepsilon)=0\not< 0$ だからである。$P^{0}=\{\varepsilon\}$ なので、$m=0$ では主張が成り立つ。以下、$w$ の長さについての帰納法で、すべての $m\ge1$ について同時に示す。
（1 から 2）$w=t_1t_2\cdots t_m$（$t_j\in P$）とし、$t_1=fs_1\cdots s_n$（$\mathrm{ar}(f)=n$、$s_i\in P$）と書く。$w=fw'$、$w':=s_1\cdots s_nt_2\cdots t_m\in P^{n+m-1}$ であり、$w'$ は $w$ より短いので、帰納法の仮定（$n+m-1=0$ の場合は上の $m=0$ の場合）により $C_{n+m-1}(w')$ が成り立つ。すると $K(w)=(1-n)+(n+m-1)=m$ である。$w$ の真の接頭辞は、$\varepsilon$（重み $0< m$）か、$w'$ の真の接頭辞 $v'$ による $fv'$ であり、後者の重みは $(1-n)+K(v')<(1-n)+(n+m-1)=m$ である。よって $C_m(w)$ が成り立つ。
（2 から 1）$C_m(w)$、$m\ge1$ とする。$K(w)=m\ne0$ なので $w\ne\varepsilon$ であり、$w=fw'$（$\mathrm{ar}(f)=n$）と書ける。$K(w')=m-(1-n)=m+n-1\ge0$ であり、$w'$ の真の接頭辞 $v'$ について $fv'$ は $w$ の真の接頭辞なので $(1-n)+K(v')< m$、すなわち $K(v')< m+n-1$ である。よって $C_{m+n-1}(w')$ が成り立ち、帰納法の仮定（または $m=0$ の場合）により $w'=s_1s_2\cdots s_{m+n-1}$（$s_i\in P$）と書ける。$m\ge1$ より $m+n-1\ge n$ なので、$t_1:=fs_1\cdots s_n\in P$ とおくと $w=t_1s_{n+1}\cdots s_{m+n-1}$ は $m$ 個の項をつないだ記号列である。$\square$

1：項 $t$ の真の接頭辞 $v$ は lem-ur-weight-criterion により $K(v)\le0$ を満たすが、項の重みは $1$ である。
2：重みを比べて $m=K(t_1\cdots t_m)=K(s_1\cdots s_{m'})=m'$ である。$m$ についての帰納法で成分の一致を示す。$m=0$ なら示すことはない。$m\ge1$ なら、$t_1$ と $s_1$ はどちらも同じ記号列の先頭から始まるので、一方が他方の接頭辞である。$t_1\ne s_1$ なら短いほうが長いほうの真の接頭辞で、しかも項になり、1 に反する。よって $t_1=s_1$ であり、それを取り除いた $t_2\cdots t_m=s_2\cdots s_m$ に帰納法の仮定を使う。
3：$t=ft_1\cdots t_n=gs_1\cdots s_k$ とすると、先頭の記号を比べて $f=g$、したがって $n=k$ であり、残りの $t_1\cdots t_n=s_1\cdots s_n$ に 2 を使えば $t_i=s_i$ である。$\square$

記号列 $x_1\cdots x_\ell$ を逆順の $x_\ell\cdots x_1$ に写す写像を $\rho$ と書く。$\rho(t_1\cdots t_nf)=f\rho(t_n)\cdots\rho(t_1)$ なので、構造的帰納法により $\rho(P')\subset P$ であり、同様に $\rho(P)\subset P'$ である。$\rho$ は対合なので $\rho(P')=P$ である。$t=t_1\cdots t_nf=s_1\cdots s_kg$ なら、$\rho$ で写して $f\rho(t_n)\cdots\rho(t_1)=g\rho(s_k)\cdots\rho(s_1)$ となり、thm-ur-polish の 3 から $f=g$、$\rho(t_i)=\rho(s_i)$、したがって $t_i=s_i$ である。$\square$

論理式の定義により、命題変数でない $\varphi$ は $(\lnot\psi)$ か $(\psi\ast\chi)$ のどちらかの形をもつ（どちらの形か、また $\psi,\chi$ が何かはまだ一通りとは限らない）。論理式の最初の記号は命題変数か左括弧なので、$(\psi\ast\chi)$ の 2 番目の記号（$\psi$ の最初の記号）は $\lnot$ でない。よって $x_2=\lnot$ なら前者の形で 1 が成り立つ。
$x_2\ne\lnot$ なら $\varphi=(\psi\ast\chi)$ の形の表し方が少なくとも 1 つある。そのどれについても以下が成り立つ。記号列 $\sigma$ の左括弧の個数から右括弧の個数を引いた数を $b(\sigma)$ と書くと、数理論理学 の命題「論理式の括弧の均衡」により、論理式では $b=0$、論理式の空でない真の接頭辞では $b\ge1$ である。表示した $\ast$ の前は $(\psi$ なので、その深さは $1+b(\psi)=1$ である。ほかの 2 項の結合子の出現を考える。それが $\psi$ の中にあれば、その前の記号列は $(\sigma$（$\sigma$ は $\psi$ の真の接頭辞で、$\psi$ は結合子で始まらないので空でない）であり、深さは $1+b(\sigma)\ge2$ である。$\chi$ の中にあれば、同様に前の記号列は $(\psi\ast\sigma'$（$\sigma'$ は $\chi$ の空でない真の接頭辞）であり、深さは $1+0+b(\sigma')\ge2$ である。よって深さ $1$ の 2 項の結合子は表示した $\ast$ だけであり、その位置は表し方によらず決まるので、$\psi,\chi$ も一通りに決まり、2 が成り立つ。$\square$