【徹底解説】サーディナス・パターソンの定理

本記事は情報理論の徹底解説シリーズに含まれます。

初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。

お気持ち

本記事では，一意復号可能な符号の必要十分条件を扱うSardinasPatterson（サーディナスパターソン）の定理を解説します。情報符号理論の中でも「一意復号可能」という性質は，避けては通れない重要なトピックです。学部レベルの授業では「瞬時符号は一意復号可能であることの十分条件」であることは習いますが， Sardinas-Pattersonの定理を証明することはまずないと思います。しかし，一意復号可能な符号を俯瞰するためには， Sardinas-Pattersonの定理を扱うことは非常に有益だと管理人は考えております。

Sardinas-Pattersonの定理は，符号が一意に復号可能かどうかを判定する際に利用します。復号の一意性を確認する単純な方法は，語頭条件から瞬時符号かどうかを判定するというものです。一方で，ある符号語が他の符号語の語頭となっている場合でも，一意に復号可能な符号は存在します。Sardinas-Pattersonの定理では，下図のように，瞬時符号でない符号で一意に復号可能な符号も対象とします。

定理

まず最初に，Sardinas-Pattersonの定理を示します。

意味不明な式ですよね。自分も最初に見たときは，身体が拒否反応を示すくらいゾっとした定理です。この定理の証明は，学部レベルを遥かに超えているため，完全に理解する必要はないでしょう。しかし，この定理の証明を通して「一意復号可能な符号」と戯れることで，より俯瞰して情報符号理論を理解することができるようになります。

本記事では，Sardinas-Pattersonの定理の証明を初学者の方に向けて出来る限り噛み砕いて説明していきます。少し長くなりますが，一緒に手を動かして証明を追ってみれば，必ず理解できるはずです。数学の難しい概念は登場しません。出てくるのは，少しだけ注意が必要な数学の記法と，ある種の算数のようなパズル性のある論理展開です。ぜひ楽しみながら証明していきましょう。

証明の流れ

さて，Sardinas-Pattersonの定理の証明ですが，以下のような流れで行っていきます。

最初に行うのは記号（ノーテーション）の確認です。本書では情報符号理論の解説で統一的な記号を用いている訳ではないため，改めて定義を見直すことで，その後の証明を見通しよく行うことができます。続いて，定理を具体的に使ってみることで，なんとなく全体を把握します。このステップが意外と重要で，後々のステップで必ず効いてきます。Sardinas-Pattersonの定理には無限回の操作が含まれていますが，有限の操作に絞って定理を裏付ける議論を行うことで，無限回の操作を行う際のイメージを確認します。最終的には，無限回の操作に対して証明を行います。　

ノーテーションの確認

早速記号の確認をしていきます。符号$\calC$というのは，関数$S\rightarrow T$のことです。ただし，$S$は情報源であり，固定された有限集合$S=\left\{ s_1, \ldots, s_q \right\}$を用いて定義されます。$T$は有限符号アルファベットであり，基数$r$を用いた有限集合$T=\left\{ t_1, \ldots, t_q \right\}$を用いて定義されます。なお，基数というのは$t_i$として使えるシンボルの種類で，例えば二進数だと基数$r=2$になります。$T$の符号語$w$は$T$のシンボルからなる有限列です。

さて，$w$を関数$S$とシンボルの集合$T$で表すため，$T$の要素の有限個の列から成る符号語全体の集合を以下のように定義します。

このとき，情報源$S$の各シンボル$s_i$に対して符号語$w_i$が定義され，$w_i=\calC (s_i)\in T^{\ast}$と表されます。$T^{\ast}$には$n=0$，すなわち空語$\varepsilon$も含まれることに注意しましょう。

さて，より一般には$s_i$と$w_i$はそれぞれ複数のシンボルから構成されます。ですので，インデックスをもう一階層深くしてみましょう。すると，$\vs_i=s_{i1}\ldots s_{in}$となり，$w_{ij}=\calC (s_{ij})\in T$となります。$T^{\ast}$と同様に$S$を$S^{\ast}$に拡張すれば，$\vw_i=\calC^{\ast}(\vs_i)\in T^{\ast}$となります。

例えば，$S={1,2,3,4,5,6}$とすれば，情報源$S$から生成されるシンボル$\vs_1$としては$314$が考えられます。このとき，$\vs_1=314=s_{11}s_{12}s_{13}$となります。符号アルファベットを二進数$T={0,1}$とすれば，符号$C$は各シンボル$s_i$を有限の二進数で表す対応を表すことになります。符号$C$として純粋な二進数表記を用いれば，

という対応関係になります。すると，

と変形して分かる通り，$w_{11}=11,w_{12}=1,w_{13}=100$となります。ただし，ピリオド「$.$」は符号語の区切れ目を表します。

ここで疑問に思う人も多いのではないでしょうか。そもそも，符号とは関数のことだったのかと。でも心配はいりません。符号の多くの性質は，符号語$\vw_i$に依存するため，符号$C$は多くの場合で関数ではなく符号語$w_1,\ldots, w_q$の有限集合とみなされます。本書でも，符号は符号語の有限集合とみなします。このとき，符号$\calC$を拡張した符号$\calC^{\ast}$も，符号語の集合として改めて以下のように表すことができます。

先ほどの例で言えば，$w_{11}=11,w_{12}=1,w_{13}=100$はそれぞれ$T$を構成する要素である${0,1}$で表されているため，$w_{11}\in T^{\ast}$になります。このような符号語$\vw_i$を全て集めた集合が$\calC^{\ast}$になります。

使ってみる

さて，ここからSardinas-Pattersonの定理を使ってみることで具体的なイメージを確認しましょう。今回は，題材として符号$\calC=\{0,01,011\}$が一意復号可能かどうかを考えます。Sardinas-Pattersonの定理を利用して符号$\calC$が一意復号可能かどうかを判断するためには，$\calC_{\infty}$を計算する必要があります。$\calC_{\infty}$は$\calC_0=\calC$から帰納的に定義されるため，改めて$\calC_n$の定義を確認します。

この定義の意味を粘って理解できるかどうかが勝負の分かれ目です。

日本語で噛み砕きましょう。先に説明した通り，符号は符号語の集合と捉えられたので，$\calC_n$は符号アルファベット$T^+$の要素で表される符号語$w$の集合です。ただし，$w$は$uw=v$を満たすことが前提です。この$u$と$v$はそれぞれ，「$u$が$\calC$の符号で$v$が$\calC_{n-1}$の符号」のパターンか，「$u$が$\calC_{n-1}$の符号で$v$が$\calC$の符号」のパターンのいずれかになります。これが，$\calC_n$の定義です。そこで，早速$\calC_1$を計算してみましょう。$\calC_0=\calC$となりますので，$\calC_n$のうち$\calC_1$だけは特別で，

と簡略化できます。今回の例でいえば，$u$と$v$は$\calC$の要素ですので，$\{0,01,011\}$のいずれかになります。$w$は$T^+$の要素であることから，空語$\varepsilon$ではありません。このことに注目すれば，$u=0$または$u=01$であることがわかります。

$u=0$のときは$w=1$または$w=11$，$u=01$のときは$w=1$とすれば，$v$が$\{0,01,011\}$のいずれかになり，$v\in\calC$となります。したがって，$\calC_1=\{1, 11\}$となります。続いて$\calC_2$ですが，以下の式を満たすような$u$と$v$を見つけることはできません。

なぜなら，$u\in\calC$のとき，$u=\{0,01,011\}$いずれの場合でも$v\in\calC_1$を満たすような$v$は見つからず，$u\in\calC_1$のとき，$u=\{1,11\}$いずれの場合でも$v\in\calC$を満たすような$v$は見つからないからです。したがって，$C_2=\emptyset$となります。

すると，$2\leq n$に対して$\calC_n=\emptyset$となります。したがって，$\calC_{\infty}=\calC_1=\{1, 11\}$となります。このとき，$\calC\cap \calC_1=\emptyset$ですので，Sardinas-Pattersonの定理より，符号$\calC$は一意復号可能であることが分かります。

この符号$\calC$は語頭条件を満たさないため，瞬時符号でない場合に一意復号可能な符号の例を表しています。

ここまでがSardinas-Pattersonの定理の具体的な使い方でした。「なぜ$\calC\cap\calC_{\infty}=\emptyset$のときに$\calC$は一意復号可能なのか」という疑問を持たれると思います。これは現時点では分からなくて当然です。証明を追っていく中で徐々に理解していけばOKです。

示したい命題

証明したい命題を改めて示します。

以下では，十分性（$\Rightarrow$）と必要性 （$\Leftarrow$） のそれぞれについて順番に説明していきます。

十分性の証明

有限の場合

命題の仮定は，符号$\calC$が一意復号可能でないことでした。そこで，一意復号可能でないあいまいな符号語の列$\vt=u_1u_2=v_1v_2$となる$u_1, u_2, v_1, v_2\in\calC$が存在するとします。このとき，$|u_1|\neq |v_1|$になります。なぜなら，$|u_1|=|v_1|$とすると，$u_1$と$v_1$は$\vt$の最初のシンボルを表すため，$u_1=v_1$となり，このことから$u_2=v_2$となり，$\vt$が一意復号可能でない仮定に矛盾します。したがって，$|u_1|\neq |v_1|$となります。

さて，$u$と$v$の対称性から$|u_1|>|v_1|$としても一般性を失わず，ある$|w|>0$に対して$u_1=wv_1$となっているとしてよいです。よって，$\calC_n$の定義から，$w\in\calC_1$になります。同様に，$u_1=wv_1$を$u_1u_2=v_1v_2$に代入すれば$wu_2=v_2$となり，$\calC_n$の定義から，$u_2\in\calC_2\in\calC_{\infty}$となります。したがって，$\calC\cap\calC_{\infty}=u_2\neq\emptyset$となります。

こちらの場合を少しだけ拡張してみましょう。一意復号可能でない符号$\calC$で，$\vt=u_1u_2u_3=v_1v_2v_3v_4v_5$となる$u_1, u_2, u_3, v_1, v_2, v_3, v_4, v_5\in\calC$が存在するとします。このとき，以下のように$\vt$を2通りの符号語で表すことができます。

上の図のような「符号語を線分で表現する方法」に慣れましょう。線分の長さは符号語の長さを表します。

ここで，非常に重要な記号$x_n$を導入します。$x_n$は「左端が$x_{n-1}$，右端が$u$か$v$の端点と一致している線分のうち最小」の線分（符号語）を表します。ただし，対称性から$u_1 > v_1$としてよく，このとき$x_0=v_1$と定義されることに注意しましょう。$x_n$の定義はとても大切ですので，改めてまとめておきます。

全く意味が分からないと思いますので，順を追って見ていきます。$x_1$は左端が$v_1=x_0$，右端が$u$か$v$の端点と一致している線分のうち最小の線分ですので，以下のような線分になります。

次に，$x_2$を作ります。$x_2$は左端が$x_1$，右端が$u$か$v$の端点と一致している線分のうち最小の線分ですので，以下のような線分になります。

これを繰り返していけば，以下のように$x_6$まで作ることができます。

さて，このような$x$を考えることで，なぜ嬉しいのでしょうか。それは，

$x_n\in \calC_n$になっている

からなのです。大事すぎることなので，もう一度言います。

$x_n\in \calC_n$になっている

のです。なぜ$x_n\in \calC_n$になるかというと，$\calC$の定義を見れば分かります。

大切なのは，対称性から$u$と$v$には本質的な違いはないということです。それを踏まえれば，$\calC$の定義は

「ある符号語$w$の集まりですよ。ただし，$w$の左に$\calC$の符号語を繋げたものは$\calC_{n-1}$の符号語になり，$w$の左に$\calC_{n-1}$の符号語を繋げたものは$\calC$の符号語になるという条件付きですよ。」

ということになります。気付きましたでしょうか。$x$は$\calC_n$における$w$の条件を満たすように逐次的に作られる符号語なのです。ここをおさえられるかどうかが，この証明のカギです。以下，$w$を$x$に読み変えます。改めて，「$x$の左に$\calC$の符号語を繋げたものは$\calC_{n-1}$の符号語になる」という条件を$\alpha$，「$x$の左に$\calC_{n-1}$の符号語を繋げたものは$\calC$の符号語になる」という条件を$\beta$とおきます。

実際に見ていきましょう。改めて「$x_n$の作り方」の図をお見せします。

この図から，$v_1 x_1 = u_1$が成り立つことが確認できます。これは条件$\alpha$を満たすパターンです。同様に，$x_1 x_2 = v_2$が成り立ちます。これは条件$\beta$を満たすパターンです。以下同様に，$x_2 x_3 = u_2$は条件$\beta$，$v_3 x_4 = x_3$は条件$\alpha$，$x_4 x_5 = v_4$は条件$\beta$，$x_5 x_6 = u_3$は条件$\beta$を満たすパターンです。

この逐次操作が最後に到達したとき，つまり$\vt$の右端に到達したときに注目します。最後の$x$は，必ず両端が$u$か$v$に一致しています。最後の$x$のインデックスを$i$とすると，最後の$x_i$は$x_i \in \calC_i$となります。実際に，先ほどの例でも$x_6 \in \calC_6$になります。したがって，

となりますので，右矢印（$\Rightarrow$）の有限の場合の証明は完了しました。

無限の場合

次に，十分性（$\Rightarrow$）の無限の場合を証明します。方針は有限の場合と同様に，一意復号可能でない符号$\calC$を用いて，あいまいな符号語列を2通りに表せる立場から出発します。ゴールも有限の場合と同様で，$\calC\cap\calC_{\infty}=u_l\neq\emptyset$となる$u_l$（または$v_m$）が存在することを示すことです。早速始めましょう。有限の場合と同様に，一意復号可能でない符号$\calC$で，

となる$u_1, \ldots, u_l, v_1, \ldots, v_m\in\calC$が存在するとします。このとき，目指すゴールは両端が$u$と$v$のいずれにも属している$x$が存在することを示すことです。大丈夫です。やることは先ほどの有限の場合と同じです。まず，新しい記号を導入しましょう。$u \leq v$は$u$が$v$の語頭であることを意味します。また，$w = u^{-1}v$は，$v$の語頭から$u$を取り除いて$w$が得られることを意味します。

最小性を考慮すると，$u_1 \neq v_1$になります。なぜなら，$u_1 = v_1$とすると，$u_2\ldots u_l = v_2\ldots v_m$となり，$u_1^{-1}\vt = v_1^{-1}\vt = u_2\cdots u_l = v_2\cdots v_m$に対して同じ議論が展開できるからです。すると，$u_1 > v_1$または$u_1 < v_1$ということになりますが，ここは$u$と$v$の対称性から片方のパターンを扱うだけで十分ですので，今回は$u_1 > v_1$の場合を扱いたいと思います。早速，符号語を線分で表した図から見ていきましょう。

これから行う証明は，一番左側のブロックA，真ん中のブロックB・C，一番右側のブロックDに分かれます。ブロックAはあいまいな符号語$\vt$の一番左から$u_1$に関する$x$を抽出し終わるまでの区間です。ブロックBとCは$x$の両端が曖昧な符号語$\vt$の両端とならない区間です。最後のブロックDは，$x$の右端があいまいな符号語$\vt$の右端と一致する区間です。

ここでは最後のブロックDで「右端と一致する」と表現しましたが，今回の証明の目的はこのブロックDにおける$x$が存在することを示すことなので（つまり一致することが最初から保証されている訳ではないので）注意してください。

さて，有限場合と同じようにブロックAにおける$x$を抽出していきましょう。なお，図中では$u$の右端に対する$x$を抽出していく場合は下から上に，$v$の右端に対する$x$を抽出していく場合は上から下に$x$を書いていきます。すると，右端が$u_1$の右端と一致する$x$の中で最小の$x_{i_1}$まで到達します。このとき，$x_{i_1}$のインデックス$i_1$に注目すると，$i_1$回目で$x_{i_1}$まで到達していますので，$x_{i_1}$の左端は$u_{i_1}$の右端と一致しています。

次はブロックBに入ります。有限の場合と同じように，ブロックBにおける$x$を抽出していきましょう。すると，右端が$v_{i+1}$の右端と一致する$x$の中で最小の$x_{i_1 + j_1}$まで到達します。このとき，$x_{i_1 + j_1}$のインデックス$i_1 + j_1$に注目すると，$j_1$回目で$x_{i_1 + j_1} $まで到達していますので，$x_{i_1 + j_1} $の左端は$u_{j_1}$の右端と一致しています。

次はブロックCに入ります。ブロックCはブロックDとは真逆のパターンを表しています。つまり，ブロックBでは$x$の両端が$\vt$の両端と一致しないパターンのうち$v$の右端に対する$x$を抽出していくパターン，ブロックCでは$x$の両端が$\vt$の両端と一致しないパターンのうち$u$の右端に対する$x$を抽出していくパターンを表しています。

ですので，パターンBとは基本的には同じ作業になります。ただし，インデックスだけ新しいものを使う必要がありますので注意してください。右端が$u_{j_1+1}$と一致する$x$のうち最小の$x$に到達するまでの回数を$i_2$とすると，$x$のインデックスは$i_1 + j_1 + i_2$となります。ここでは，分かりやすさのため$i_1 + i_2 = i_2$と置き直します。すると，インデックスは$i_2 + j_1$ときれいな形になります。

ブロックDとブロックB・Cの間にはブロックB・Cが交互に現れています。なぜ交互に現れるかというと，それぞれのブロックでは最小の$x$は見つけるまで$x$の抽出作業を繰り返すからです。もし同じブロックが続けて現れたとすると，それは$x$の最小性に矛盾します。

最後のブロックDに到達したときには，$|u_l|$と$|v_m|$のどちらが大きいかは保証できません。一方，$|u_l| \neq |v_m|$は保証できます。なぜなら，$|u_l| = |v_m|$とすると$u_l = v_m$となるため，先ほど$u_1 \neq v_1$を示したときと同様に，最小性に矛盾するからです。

図中では$|u_l| > |v_m|$となっていますので，まずは$|u_l| > |v_m|$の場合を考えましょう。この場合は，ブロックDの直前にはブロックCがあります。このとき，ブロックBとブロックCは同じ回数だけこなされていますので，$(p-1)$回のブロックBと$(p-1)$回のブロックCが終わったとします。すると，$x$のインデックスは$i_p + j_{p-1}$とります。

このとき，$v_m=x_{i_p + j_{p-1}}$となります。$v_m \in \calC$であることと，$x_{i_p + j_{p-1}} \in \calC_{i_p + j_{p-1}}$であることから，「$x_{i_p + j_{p-1}} \in \calC$」かつ「$x_{i_p + j_{p-1}} \in \calC_{i_p + j_{p-1}}$」ですので，以下が成り立ちます。

やりました。$\calC \cap \calC_{\infty} \neq \emptyset$が示せました。

$|u_l| < |v_m|$の場合も同様です。この場合，ブロックDの直前にはブロックBがあります。このとき，ブロックBはブロックCより1回多くこなされていますので，$p$回のブロックBと$(p-1)$回のブロックCが終わったとします。すると，$x$のインデックスは$i_p + j_p$とります。

このとき，$u_l=x_{i_p + j_p}$となります。$u_l \in \calC$であることと，$x_{i_p + j_p} \in \calC_{i_p + j_p}$であることから，「$x_{i_p + j_p} \in \calC$」かつ「$x_{i_p + j_p} \in \calC_{i_p + j_p}$」ですので，以下が成り立ちます。

以上で，$|u_l| > |v_m|$ ，$|u_l| < |v_m|$両方の場合で$\calC \cap \calC_{\infty} \neq \emptyset$が示せたため，十分性（$\Rightarrow$）の無限の場合の証明が終了しました。

必要性の証明

必要性 （$\Leftarrow$） の証明も，有限の場合を証明してから無限の場合に応用するという流れで証明していきます。

有限の場合

必要性（$\Leftarrow$）の有限の場合を確認します。つまり，$\calC \cap \calC_{\infty} \neq \emptyset$のとき$\calC$が一意復号可能でないことを示します。この証明のゴールは，あいまいな符号語が存在することを示すことです。具体的には，$w_1,w_3 \in \calC$，$ w_1 \neq w_3 $，$w_2, w_4 \in \calC^{+}$に対して以下のような形を導くことが目標です。

$w_1 \neq w_3$より，$w_2 \neq w_4$となり，この式はある符号語を2つの異なる分解で表すことができることを示しています。例えば，$\calC = \{ 100, 10, 010 \}$という符号に対し，$10010$という符号語には$100.10$という分解と$10.010$という分解が存在するといった具合です。

なぜ$w_2$と$w_4$は$\calC$ではなく$\calC^{+}$の符号語なのかというと，$w_2$と$w_4$は$w_1$と$w_3$を語頭と考えたときのそれ以外の部分を表すため，和集合で定義する必要があるからです。この式の形を「方程式$(\ast)$」と呼ぶことにします。

さて，ここからは$\calC = \{ 01, 1, 2, 210 \}$を考えます。$\calC_n$の定義から，逐次的に$\calC \cap \calC_n \neq \emptyset$となる$n$が見つかるまで探します。なお，今回は一意復号不可能な符号$\calC$を具体例として用意したので，必ずそのような$n$が見つかるのですが，一般には必ず見つかるとは限らないことに注意しましょう。

今回はインデックス$n$を用いるため，$\calC$の定義中に現れる符号語の分解式$uw=v$を$v_{n-1} v_n = u_{n-1}$というようにインデックスを用いて表すことにします。さらに，今回は$v_n \in \calC_n$を固定して考えます。このとき，分解式が可変になり，$u_{n-1} v_n = v_{n-1}$も条件として考える必要が出てきます。

今までの定義では「分解式が固定で符号語$u$，$v$が可変」であったところを，「分解式が可変で符号語$u$，$v$が固定」として考えるということですね。改めて，$\calC_n$の定義を見直してみましょう。

必要性の証明はこの「定義の読み変え」がポイントです。

まず最初は，$u_0\in\calC$かつ$v_0\in\calC$の状況下で$v_0v_1 = u_0$となる$v_1$を探します。すると，$v_1 = 10$のとき，$v_0 = 2 \in \calC$かつ$u_0 = 210 \in \calC$となり，$\calC_1 = { 10 }$となることが分かります。

同様に，$u_1\in\calC$かつ$v_1\in\calC_1$の状況下で$v_1v_2 = u_1$または$u_1v_2 = v_1$となる$v_2$を探します。すると，$v_2=0$のとき$v_1 = 10 \in \calC_1$かつ$u_1 = 1 \in\calC$となり，$\calC_2 = { 0 }$となることが分かります。

同様に，$u_2\in\calC$かつ$v_2\in\calC_2$の状況下で$v_2v_3 = u_2$または$u_2v_3 = v_2$となる$v_3$を探します。すると，$v_3=1$のとき$u_2 = 01 \in \calC_2$かつ$v_2 = 0 \in\calC_2$となり，$\calC_3 = { 1 }$となることが分かります。

ここまできて，${1} = \calC \cap \calC_3 \neq \emptyset$となるので，今回の証明の仮定まで辿り着くことができました。逆に言えば，今回の証明の仮定に基づけば，以下のように符号語が分解できることが分かります。ただし，ピリオド「$.$」は符号語と符号語の区切り目を表しています。

さて，我々の目標は$w_1, w_2, w_3, w_4 \in \calC$に対し，$w_1\neq w_3$の状況下で$w_1w_2 = w_3w_4$となる方程式$(\ast)$を導くことでした。ここで，一番下の$v_0 v_1 = u_0\;(2.10 = 210)$に注目すると，$v_0, u_0 \in \calC$に対し$v_0, v_1 = u_0$が成り立っていることが分かります。さらに，$u_0 = v_0 $とすると，$v_1 = \varepsilon$となるため，$v_1 \in \calC$に矛盾します。したがって，$u_0 \neq v_0$となります。

この「$u_0, v_0 \in \calC$かつ$u_0 \neq v_0$」という条件が，一番最後の式に注目する最大の理由です。ほぼ目標の方程式$(\ast)$には近づいてはいるものの，あと一歩及ばないですね。そこで，目標の方程式$(\ast)$に近づけるため，両辺の右側に$y_1 \in \calC^{+}$をくっつけてみます。

このとき，$v_1 y_1 = z_1 \in \calC$となる$y_1 \in \calC^{+}$が存在することを示すことができれば，目標の方程式$(\ast)$を示すことができます。そこで，今回は$v_1 y_1 = z_1 \in \calC$となる$y_1 \in \calC^{+}$が存在すればそいつを選びます。実際，$y_1 = 1$とすれば，

となることが分かります。結局，まとめると以下のようにあいまいな符号語を見つけることができました。

したがって，ある符号語の列を2つの異なる分解で表すことができるため，符号$\calC$は一意復号不可能な符号です。

無限の場合

最後に，左矢印（$\Leftarrow$）の無限の場合を証明します。とは言っても，今回は有限の場合の証明の大部分を有効活用できるため，そこまで難しくはありません。先ほど同様，$\calC \cap \calC_{\infty} \neq \emptyset$と仮定すると，$\calC \cap \calC_n \neq \emptyset$となる$n$が存在します。この$n$から$\calC_n$の定義に従い，徐々にインデックスを下げていき，$n=1$となるまで繰り返します。そして，$y_1$を右から付け加えることで，2つの異なる分解で表すことができあいまいな符号語列を構成するという流れです。見通しを良くするため，$1\leq k \leq n$，$1\leq l \leq n-1$に対して以下の2つの命題を考えます。

ただし，命題$S_k$において，$k=1$の場合は$u_0, v_0 \in \calC_0=\calC$となることに注意してください。命題$S_k$は$n$から$\calC_n$の定義に従い徐々にインデックスを下げていくために利用される命題で，これは$\calC_n$の定義そのものです。命題$T_l$は，$n=1$までインデックスを下げることで得られる式を，目標の方程式$(\ast)$に近づけるために利用される命題です。これは別途証明が必要です。そこで，先に命題$(T_l)$を示してしまいましょう。

数学的帰納法を利用します。まず，命題$T_{n-1}$が成り立つことを示します。$y_{n-1} = v_n$とすれば，$z_{n-1}=u_{n-1}$を選ぶことによって命題$(S_k)$から等式が成り立つことが分かります。続いて，命題$T_k$が成り立つと仮定します。このとき，命題$T_{k-1}$が成り立つことを示します。

インデックスを落としていく方向の数学的帰納法です。

まずは，仮定の式を確認します。$y_k, v_k\in \calC^{+}$，$v_k\in \calC_k$に対して以下が成り立ちます。

次に，命題$S_k$から以下のいずれかが成り立ちます。

どちらの式も，右から$y_k$を付け加えて両辺を入れ替えることで，以下のように変形できます。

このいずれの式も，以下の形になっています。

なぜなら，$y_{k-1} = y_k$，$z_{k-1} = u_{k-1}z_k$と置けば式($\ref{eq:vy=uz}$)に，$y_{k-1} = z_k$，$z_{k-1} = u_{k-1}y_k$と置けば式($\ref{eq:uy=vz}$) になるからです。命題$T_{k-1}$が成り立つことを示すためには，いずれの場合でも$y_{k-1}，z_{k-1} \in \calC^{+}$になることを示さなくてはなりません。

実際， 式($\ref{eq:vy=uz}$) のパターンでは，$y_k, z_k \in \calC^{+}$と$u_{k-1} \in \calC$に注意すると，$y_{k-1} = y_k \in \calC^{+}$，$z_{k-1} = u_{k-1}z_k \in \calC{+}$であることが分かります。同様に， 式($\ref{eq:uy=vz}$) のパターンでも，$y_{k-1} = z_k \in \calC^{+}$，$z_{k-1} = u_{k-1}y_k \in \calC{+}$であることが分かります。

したがって，$1\leq l \leq n-1$に対して命題$T_l$が正しいことになります。ということは，$l=1$の場合の命題$T_1$も成り立ちます。

これでようやく左矢印（$\Leftarrow$）全体を証明する準備が整いました。まず，$\calC \cap \calC_n \neq \emptyset$となる$n$が存在します。この要素を$v_n$とおいて，逐次命題$S_k$を適用していくと，$S_1$により以下が得られます。

ただし，有限の場合でも示した通り，$v_0 = u_0$とすると最小性に矛盾するため，$v_0 \neq u_0$です。ここで目標の方程式$(\ast)$に近づけるため，命題$(S_1)$の両辺の右側に$y_1$を付け加えます。すると，

となります。ここで，$y_1, z_1 \in \calC^{+}$であることと，$v_0, u_0 \in \calC$かつ$v_0 \neq u_0$であることから，この式は目標の方程式$(\ast)$と等価であることが分かります。したがって，符号$\calC$では2つの異なる分解で表すことができるあいまいな符号語の列が存在するため，符号$\calC$は一意復号可能ではありません。これで， 必要性 （$\Leftarrow$） の無限の場合の証明も完了です。