ありとあらゆる文字列が15文字以内で表現できることの証明。
n文字以内で定義できない文字列を Sn とする。
任意の Sn からなる集合を Xn とすると、Xn の要素は必ず Xn-1 の要素である(n 文字で定義できなければ n-1 文字でも定義できない)。
すなわち
Xn ⊂ Xn-1
が任意のn( > 1) について成り立つ。
よって、n 以下の正の整数 k (0 < k ≦ n) について、
Xn ⊆ Xk …①
も成立する。
ここで、k = 15 文字からなる文字列 T = "n文字以内で定義できない文字列" を考えたとき、これは書き下しによって15文字で定義できるので
T ∈ X15 …②
である。
ところが、Snの定義より、
T = Sn
であるので、
T ∈ Xn …③
となり、15 ≦ n の下で②および③は①に反する。
このような矛盾が導かれたのは、n文字以内で定義できない文字列 Sn が存在すると仮定したことが誤りであったからである。
したがって、n文字以内で定義できない文字列は存在しない。
つまり、任意の文字列はn文字以内で定義できる。
(ただし n ≧ 15)
ここで n = 15 を代入すると、「任意の文字列は15文字以内で定義できる。」が導かれる。
おわり。
n文字以内で定義できない文字列を Sn とする。
任意の Sn からなる集合を Xn とすると、Xn の要素は必ず Xn-1 の要素である(n 文字で定義できなければ n-1 文字でも定義できない)。
すなわち
Xn ⊂ Xn-1
が任意のn( > 1) について成り立つ。
よって、n 以下の正の整数 k (0 < k ≦ n) について、
Xn ⊆ Xk …①
も成立する。
ここで、k = 15 文字からなる文字列 T = "n文字以内で定義できない文字列" を考えたとき、これは書き下しによって15文字で定義できるので
T ∈ X15 …②
である。
ところが、Snの定義より、
T = Sn
であるので、
T ∈ Xn …③
となり、15 ≦ n の下で②および③は①に反する。
このような矛盾が導かれたのは、n文字以内で定義できない文字列 Sn が存在すると仮定したことが誤りであったからである。
したがって、n文字以内で定義できない文字列は存在しない。
つまり、任意の文字列はn文字以内で定義できる。
(ただし n ≧ 15)
ここで n = 15 を代入すると、「任意の文字列は15文字以内で定義できる。」が導かれる。
おわり。
※コメント投稿者のブログIDはブログ作成者のみに通知されます