ラッセルのパラドックス

ラッセルのパラドックス（英: Russell's paradox）とは、素朴集合論において、自身を要素として持たない集合全体からなる集合の存在を認めると矛盾が導かれるというパラドックス。バートランド・ラッセルからゴットロープ・フレーゲへの1902年6月16日付けの書簡においてフレーゲの『算術の基本法則』における矛盾を指摘する記述に現れ^[1]、1903年出版のフレーゲの『算術の基本法則』第II巻（独: Grundgesetze der Arithmetik II）の後書きに収録された^[2]。なお、ラッセルに先立ってツェルメロも同じパラドックスを発見しており、ヒルベルトやフッサールなどゲッティンゲン大学の同僚に伝えた記録が残っている^[3][4]。

ラッセルの型理論（階型理論）の目的のひとつは、このパラドックスを解消することにあった^[5]。

概要

「それ自身を要素として含まない集合」を「M 集合」とし、「すべての M 集合を要素として含む集合 R」を作ってみる。そうすると、「任意の集合 X」に関しては、「X は R に含まれる」↔︎「X は X に含まれない」という定式が成り立つ。そして特に X = R とすれば、「R は R に含まれる」↔︎「R は R に含まれない」となり、パラドックスが明示される。

集合は事物とは違った存在の仕方をしており、世界を構成する存在者ではなく、論理的虚構にすぎず、そこには階型の違いがある。よって「集合がそれ自身の要素であるかどうかの問いの全体」が、「真でも偽でもなく」むしろ「無意味」「意味のない雑音」であった。集合とは、後の「記述の理論」があきらかにする意味で不完全記号である。「集合」「数」の指示するものが「スコラ的プラトン的な意味」で「無時間的に存在」すると考えてはならないとラッセルは気付いた。事物の存在の次元と集合の語られる次元とは混同されてはならず、或る階型の対象に真偽を言えても、異階型の対象には有意味には言えない。我々は何らかの性質を有意味には命題一般には帰属させ得ず、ただ特定の次元の命題に有意味に帰属させうるのみである(ラッセルの階型理論)。

集合論が形式化されていないことが矛盾の原因なのではなく、このパラドックスは、古典述語論理上の理論として形式化された無制限の内包公理を持つ素朴集合論や、直観主義論理上の素朴集合論においても生じる。したがって論理を古典論理から直観主義論理に変更してもラッセルのパラドックスは回避できない。パラドックスの回避については、様々な方法が提案されている。詳細は矛盾の解消を参照。

矛盾の解消

公理的集合論によって何をもって集合とするかについての形式的な整備が進められ、素朴（だが超越的）な${\displaystyle R}$ の構成を許容しない体系が構築された。

公理的集合論ではまず集合論を形式化する。次にいかなる形の集合が存在するかを公理によって規定する。 例えば素朴集合論では、上のような集合の存在を保証するために次の内包公理を置いた：

任意の性質 ${\displaystyle P(x)}$ に対して、 ${\displaystyle P(x)}$ を満たす元 ${\displaystyle x}$ の集合 ${\displaystyle \{x|P(x)\}}$ が存在する

しかしながら、内包公理からは、上述のとおり、

${\displaystyle R=\{x|x\notin x\}}$

が構成でき、パラドックスが発生する。 したがって、集合論の公理は通常の数学を集合論の上で展開するために十分なだけの集合の存在を保証しつつ、パラドックスを発生させる集合は構成できないように慎重に設定する必要がある。

1.公理的集合論による解消^{[注 1]}

具体的には内包公理を次の分出公理に弱める（ツェルメロによる版）。

任意の性質 ${\displaystyle P(x)}$ と集合 ${\displaystyle A}$ に対して、 ${\displaystyle P(x)}$ を満たす ${\displaystyle A}$ の元 ${\displaystyle x}$ の集合 ${\displaystyle \{x\in A|P(x)\}}$ が存在する

この場合、

${\displaystyle R_{A}=\{x\in A|x\notin x\}}$

は、${\displaystyle A}$ の要素でないため、それ自身を要素としなくても矛盾は発生しない。

また ${\displaystyle R}$ のような集合は構成できないのでやはり矛盾は発生しない。

（なお現在のZFC集合論では、フレンケルが設定した置換公理から分出公理が導けるため、分出公理自体は公理としていない。）

なお、ラッセルのパラドックスでは論理式 ${\displaystyle x\notin x}$ に内包性公理を適用することによってパラドキシカルな集合を構成している。これは論理式 ${\displaystyle x\in x}$ の否定である。ZFC集合論では ${\displaystyle x\in x}$ のように循環的な帰属関係を持つ集合の存在は正則性公理によって否定される。もっとも正則性公理がラッセルのパラドックスを排除しているわけではない。何故なら公理を追加しても証明できる論理式は減らないからである。さらに反基礎公理と呼ばれる循環的な集合の存在を積極的に保証する公理を置く集合論の体系も存在しており、この体系の無矛盾性はZFC集合論の無矛盾性から相対的に導かれる。ただしある種の循環性を制限することによって無矛盾性を確保しようという試みは存在しており、例えば後述する単純型理論はその典型的な例である。

2.単純型理論による解消^{[注 2]}

項に型と呼ばれる自然数 0, 1, 2,… を割り当て、述語記号 ∈ を (n階の項)∈(n+1階の項) の形でのみ許容する（すなわち論理式の文法を制限する）ことで矛盾を回避する。単純型理論は階型毎に無制限の内包公理を持つが、無矛盾である。

3.部分構造論理による解消^{[注 3]}

古典論理を（グリシン論理やBCK論理などの）縮約規則を取り除いた部分構造論理に置き換え、無制限な内包公理を認める代わりに外延性公理を排除した素朴集合論が矛盾無く展開できることが知られている^{[注 4]}。外延性公理が排除されるのは、外延性公理から縮約規則が導かれ、したがって矛盾するからである。例えばBCKβでは次のようにして外延性公理から矛盾が導かれる。次の集合 ${\displaystyle A}$ を考える。

${\displaystyle A=\{x|A=\varnothing \}}$

ここで ${\displaystyle \varnothing }$ は空集合であり、

${\displaystyle \varnothing =\{x|\bot \}}$

で定義される。集合 ${\displaystyle A}$ の定義には自己参照が含まれるが、不動点コンビネータによってこれは可能である。この集合論において外延性公理が成立すると仮定する。すると次のようにして矛盾が導かれる。等号 ${\displaystyle x=y}$ の形の仮定に対しては縮約規則が使用できることに注意。まず ${\displaystyle A=\varnothing }$ を仮定する。集合 ${\displaystyle x}$ を何でもいいのでひとつ取る。すると仮定および ${\displaystyle A}$ の定義より ${\displaystyle x\in A}$ が成り立つ。再び仮定を使用すれば ${\displaystyle x\in \varnothing }$ が成り立つ。したがって空集合の定義より ${\displaystyle \bot }$ が導かれる。これは不合理であるから ${\displaystyle A\neq \varnothing }$ である。いま ${\displaystyle y\in A}$ を一度だけ仮定する。すると仮定および ${\displaystyle A}$ の定義より ${\displaystyle A=\varnothing }$ が成り立つ。ところが ${\displaystyle A\neq \varnothing }$ であったはずだから矛盾 ${\displaystyle \bot }$ が導かれる。ゆえに空集合の定義より ${\displaystyle y\in \varnothing }$ が成り立つ。逆に ${\displaystyle y\in \varnothing }$ を一度だけ仮定する。すると仮定および空集合の定義より矛盾 ${\displaystyle \bot }$ が導かれる。ゆえに爆発原理より ${\displaystyle y\in A}$ が成り立つ。したがって ${\displaystyle A}$ と空集合は外延的に等価である。外延性公理より ${\displaystyle A=\varnothing }$ が成り立つ。これは ${\displaystyle A\neq \varnothing }$ と矛盾する。

ウカシェヴィッチの3値論理上の素朴集合論では、 ${\displaystyle R\in R}$ の真理値を不定値と解釈すればラッセルのパラドックスは生じない。ところが莫少揆のパラドックスと呼ばれる別のパラドックスが生じる^{[注 5]}。パラドックスを回避するには無限ウカシェヴィッチ論理を用いる必要がある^{[注 6]}。

歴史

起源

通説では、1902年6月16日付のラッセルからフレーゲへの書簡がこのパラドックスの起源とされている。しかし、1899年から1900年にかけてエルンスト・ツェルメロが独立に同じパラドックスを発見し、ダフィット・ヒルベルトやエドムント・フッサールに伝えていた。そのため、「ツェルメロ=ラッセルのパラドックス」と呼ぶべきという意見もある^[3][4]。

年表

1872年 - 1878年

• デーデキントが『数とは何かそして何であるべきか』のスケッチを作成して閲覧させる^[27]。

1879年

• フレーゲ『概念記法』出版。数理論理学の始まり。

1884年

• フレーゲ『算術の基礎』出版。自然数論の始まり。

1888年

• デーデキント『数とは何かそして何であるべきか』出版^[28]。

1893年

• フレーゲ『算術の基本法則』出版。

1902年6月16日

• ラッセルからフレーゲ宛てにパラドックスを知らせる書簡が投函^[1]。

1902年6月22日

• フレーゲからラッセル宛てに返信が投函。

1903年

• フレーゲ『算術の基本法則』第II巻出版。後書きでラッセルのパラドックスを公開^[2]。

1903年

• ラッセル『数学の原理』出版。型理論の始まり。

1903年11月7日

• ヒルベルトからフレーゲ宛に返信が投函。ラッセルのパラドックスが3年前から4年前にツェルメロによって発見されていたことを記載^[3]。

1908年

• ツェルメロ「集合論の基礎に関する研究」発表^[29][30]。公理的集合論の始まり。