Loading article…
ベリーのパラドックスは、「60文字未満で定義できない最小の正の整数」（57文字のフレーズ）のような表現から生じる自己言及的なパラドックスである。
このパラドックスを初めて活字で論じたバートランド・ラッセルは、それをオックスフォード大学ボドリアン図書館の若手司書、GG・ベリー（1867-1928） [ 1 ]に帰属させた。ラッセルはベリーを「数学的論理を理解していたオックスフォードで唯一の人物」と呼んだ[ 2 ] 。このパラドックスはジャン＝イヴ・ジラールによって「リチャードのパラドックス」と呼ばれた[ 3 ]。
次の表現を考えてみましょう。
英語のアルファベットは26文字しかないので、60文字未満のフレーズは有限個しか存在せず、したがって60文字未満のフレーズで定義できる正の整数も有限個しか存在しません。正の整数は無限に存在するので、60文字未満のフレーズで定義できない正の整数も存在します。ある性質を満たす正の整数が存在する場合、その性質を満たす最小の正の整数が存在します。したがって、「60文字未満で定義できない」という性質を満たす最小の正の整数が存在します。これが上記の式が指す整数です。しかし、上記の式は57文字しかないので、 60文字未満で定義できますが、60文字未満で定義できない最小の正の整数ではなく、この式によって定義される整数でもありません。これはパラドックスである。この式で定義される整数が存在するはずだが、この式は自己矛盾している（この式で定義される整数は60文字未満で定義できる）ため、この式で定義される整数は存在しない。
数学者でコンピュータ科学者のグレゴリー・チャイティンは著書『The Unknowable 』（1999年）の中で、次のように述べている。「メキシコの数学史家アレハンドロ・ガルシディエゴは、ラッセルが発言の根拠としたベリーの手紙を探し出すという手間をかけたが、それはむしろ別のパラドックスだった。ベリーの手紙は、有限語では表現できない最初の順序数について述べている。カントールの理論によれば、そのような順序数は必ず存在するはずだが、我々はそれを有限語で表現してしまった。これは矛盾である。」
上記のように定式化されたベリーのパラドックスは、「定義可能」という言葉の体系的な曖昧さから生じます。ベリーのパラドックスの他の定式化、例えば「…より少ない…で名付けられない」という定式化では、「名付けられる」という用語もこの体系的な曖昧さを持っています。このような用語は、悪循環の誤謬を引き起こします。この種の曖昧さを持つ他の用語には、充足可能、真、偽、関数、性質、クラス、関係、基数、順序などがあります。[ 4 ]これらのパラドックスのいずれかを解決するには、言語の使用がどこで間違っていたかを正確に特定し、それらを回避できるような言語の使用に関する制限を設ける必要があります。
こうしたパラドックスは、言語に意味の階層構造を取り入れることで解決できる。体系的な曖昧さを持つ用語は、解釈においてある意味レベルが別の意味レベルよりも優先順位が高いことを示す添え字を付けて表記することができる。「 11語未満で0と命名できない数」は、この方式では11語未満で1と命名できる。 [ 5 ]
しかし、アルフレッド・タルスキの嘘つきパラドックスに関する考察を読めば、言語によるこの解決策がいかに不十分であるかが分かる。タルスキは、このパラドックスは「意味的に閉じた」言語でのみ生じると診断した。ここで言う「意味的に閉じた」とは、ある文が同じ言語内の別の文（あるいは自分自身の文）の真偽を述語できる言語のことである。自己矛盾を避けるためには、真理値を議論する際には、言語のレベルを想定する必要がある。各レベルは、より低いレベルの言語の真偽のみを述語できる。したがって、ある文が別の文の真理値を参照する場合、それは意味的に高いレベルにある。参照される文は「対象言語」の一部であり、参照する文は対象言語に関して「メタ言語」の一部であると考えられる。意味階層の上位にある「言語」の文が、下位にある「言語」の文を参照することは正当であるが、その逆は正当ではない。これにより、システムが自己参照的になるのを防ぐことができる。
しかし、このシステムは不完全です。例えば、「階層のレベルαにあるすべての命題に対して、最初の命題が偽であると主張するレベルα + 1 の命題が存在する」といった命題を述べられるようにしたいものです。これはタルスキが定義する階層に関する真で意味のある命題ですが、階層のすべてのレベルの命題を参照するため、階層のすべてのレベルより上に位置づけられなければならず、したがって階層内では不可能です (ただし、限定されたバージョンの命題は可能です)。[ 6 ] [ 7 ]ソール・クリプキは、引用数の多い論文「真理の理論の概要」 [ 7 ]でタルスキの階層におけるこの不完全性を指摘したことで知られており、これは階層言語における一般的な問題として認識されています。[ 8 ] [ 7 ]
グレゴリー・チャイティンが行ったように、プログラムや長さが制限された証明を用いることで、形式的な数学言語でベリー表現の類似物を構築することが可能です。形式的な類似物は論理的な矛盾にはつながりませんが、ある種の不可能性の結果は証明されます。[ 9 ]
ジョージ・ブーロス（1989）は、ベリーのパラドックスの形式化されたバージョンに基づいて、ゲーデルの不完全性定理を新しい、はるかに単純な方法で証明した。[ 10 ]彼の証明の基本的な考え方は、ある自然数nに対してx = nである場合に限りxについて成り立つ命題をnの定義と呼ぶことができ、集合 {( n , k ): nはk個の記号からなる定義を持つ} は表現可能であることが示される（ゲーデル数を使用）。すると、「 mはk個未満の記号で定義できない最初の数である」という命題を形式化し、前述の意味で定義であることが示される。[ 10 ]
一般的に、自然言語で与えられた文字列を記述するために必要な最小記号数を曖昧さなく定義することは不可能です。この文脈では、文字列と数値という用語は互換的に使用できます。なぜなら、数値は実際には記号の列であり、例えば英語の単語（パラドックスで使用されている「eleven」という単語など）である一方、任意の単語を数値で参照することも可能であり、例えば、特定の辞書における位置番号や適切なエンコーディングによって参照できます。長い文字列の中には、完全な表現に必要な記号数よりも少ない記号数で正確に記述できるものもあり、これはデータ圧縮によってよく実現されます。与えられた文字列の複雑さは、その文字列の完全な表現を（曖昧さなく）参照するために記述に必要な最小長として定義されます。
コルモゴロフ複雑性は、与えられた記述からどの文字列が生成されるかについての曖昧さを回避する形式言語、すなわちチューリングマシンを用いて定義されます。コルモゴロフ複雑性は計算不可能であることが証明されています。背理法による証明によれば、コルモゴロフ複雑性を計算できるとすれば、このパラドックスと同様のパラドックス、つまり記述された文字列の複雑性が示唆するよりも短い記述を体系的に生成することも可能になります。言い換えれば、ベリー数の定義はパラドックス的です。なぜなら、数を定義するのに必要な単語数を実際に計算することは不可能であり、パラドックスのためにそのような計算が不可能であることは周知の事実だからです。