ラッセルのパラドックス（）とは、素朴集合論において矛盾を導くパラドックスである。バートランド・ラッセルからゴットロープ・フレーゲへの1902年6月16日付けの書簡における、フレーゲの『算術の基本法則』における矛盾を指摘する記述に表れる。これは1903年に出版されたフレーゲの『算術の基本法則』第II巻（）の後書きに収録されている。同じパラドックスはツェルメロが1年先に発見していたが、彼はその発見を公開せず、ヒルベルトやフッサールなどのゲッティンゲン大学の同僚たちだけに知られているだけだった。ラッセルが型理論（階型理論）を生み出した目的にはこの種のパラドックスを解消するということも含まれていた。ラッセルのパラドックスとは、自分自身を要素として含まない集合全体の集合 formula_1 の存在から矛盾が導かれるという、素朴集合論におけるパラドックスである。いま formula_2 と仮定すると、formula_3 の定義より formula_4 となるから、これは不合理である。したがって（仮定無しで） formula_4 である。ところが formula_3 の定義より formula_2 となるから、やはり不合理である。集合論が形式化されていないことは矛盾の原因ではない。このパラドックスは古典述語論理上の理論として形式化された無制限な内包公理を持つ素朴集合論においても生ずる。上記の証明では排中律並びにそれと同等な論理法則を用いていないから、直観主義論理上の素朴集合論においても矛盾は生ずる。したがって論理を古典論理から直観主義論理に変更しても、ラッセルのパラドックスは回避できない。パラドックスの回避については、様々な方法が提案されている。詳細は矛盾の解消を参照。。ラッセルの時代には何をもって集合と呼ぶかがはっきりしていなかったので、上記の議論は集合論の矛盾を指摘するかに見えた。しかし公理的集合論によって何をもって集合とするかについての形式的な整備が進むとともに、上記の議論のはじめに考えたような素朴（だが超越的）なformula_3 の構成法は集合についての定義としては許容されないような体系が構築された。公理的集合論ではまず集合論を形式化する。次にいかなる形の集合が存在するかを公理によって規定する。これらの公理は通常の数学を集合論の上で展開するために十分なだけの集合の存在を保証しつつ、ラッセルのパラドックスののような集合は構成できないように慎重に選ばれている。例えば素朴集合論では、上のような集合の存在を保証するために次の内包公理を置く：例えば最もよく用いられる集合論の体系であるZFC集合論では次の分出公理が置かれる：ここでの性質とは形式化された集合論の論理式と解釈される。このように修正された公理からはラッセルのパラドックスで用いられるような集合の存在を証明することはできない。これによりラッセルのパラドックスの議論はZFC集合論からは排除される。ZFC集合論では formula_3 のような集合の存在を仮定すると矛盾が導かれる。したがって formula_3 の存在の否定が証明される。公理的集合論ではこのような集合の単なる集まりのことをクラスと呼ぶ。とくにその集合としての存在が否定されるようなクラスを真のクラスという。例えば全ての集合の集合が存在すれば、分出公理を適用することで、 formula_3 の存在が導かれる、ここに不合理を得る。したがって全ての集合の集合は存在せず、全ての集合のクラスは真のクラスである。ZFC集合論ではクラスそのものを体系の内部で扱うことができない。そこでクラスは形式的には変数を持つ論理式として扱われる。すなわちなるクラスは実体としては論理式 formula_10 であって、クラスを用いた議論はクラスを用いない形に書き換えて行う。例えば論理式 formula_10 と formula_26 で定まるクラス formula_15 と formula_28 について、それらが等しい formula_29 ということは、なる論理式のことと考える。このようにZFC集合論ではクラスを扱う際にメタ理論と対象理論とを行き来する必要がある。NBG集合論では、クラスを表す変数と集合を表す変数を導入し、体系内でクラスを扱えるようにしている。ラッセルのパラドックスでは論理式 formula_31 に内包性公理を適用することによってパラドキシカルな集合を構成している。これは論理式 formula_32 の否定である。ZFC集合論では formula_32 のように循環的な帰属関係を持つ集合の存在は正則性公理によって否定される。もっとも正則性公理がラッセルのパラドックスを排除しているわけではない。何故なら公理を追加しても証明できる論理式は減らないからである。さらに反基礎公理と呼ばれる循環的な集合の存在を積極的に保証する公理を置く集合論の体系も存在しており、この体系の無矛盾性はZFC集合論の無矛盾性から相対的に導かれる。ただしある種の循環性を制限することによって無矛盾性を確保しようという試みは存在しており、例えば後述する単純型理論はその典型的な例である。単純型理論では、項に型と呼ばれる自然数 0,1,2,… を割り当て、述語記号 ∈ を (n階の項)∈(n+1階の項) の形でのみ許容する（すなわち論理式の文法を制限する）ことで矛盾を回避する。単純型理論は階型毎に無制限の内包公理を持つが、無矛盾である。縮約規則を取り除いたグリシン論理やBCK論理などの弱い論理の上では、無制限な内包公理を認めた（ただし外延性公理を排除した）素朴集合論が矛盾無く展開できることが知られている。外延性公理が排除されるのは、外延性公理から縮約規則が導かれ、したがって矛盾するからである。例えばBCKβでは次のようにして外延性公理から矛盾が導かれる。次の集合 formula_15 を考える。ここで formula_36 は空集合であり、で定義される。集合 formula_15 の定義には自己参照が含まれるが、不動点コンビネータによってこれは可能である。この集合論において外延性公理が成立すると仮定する。すると次のようにして矛盾が導かれる。等号 formula_39 の形の仮定に対しては縮約規則が使用できることに注意。まず formula_40 を仮定する。集合 formula_12 を何でもいいのでひとつ取る。すると仮定および formula_15 の定義より formula_43 が成り立つ。再び仮定を使用すれば formula_44 が成り立つ。したがって空集合の定義より formula_45 が導かれる。これは不合理であるから formula_46 である。いま formula_47 を一度だけ仮定する。すると仮定および formula_15 の定義より formula_40 が成り立つ。ところが formula_46 であったはずだから矛盾 formula_45 が導かれる。ゆえに空集合の定義より formula_52 が成り立つ。逆に formula_52 を一度だけ仮定する。すると仮定および空集合の定義より矛盾 formula_45 が導かれる。ゆえに爆発原理より formula_47 が成り立つ。したがって formula_15 と空集合は外延的に等価である。外延性公理より formula_40 が成り立つ。これは formula_46 と矛盾する。ウカシェヴィッチの3値論理上の素朴集合論では、 formula_2 の真理値を不定値と解釈すればラッセルのパラドックスは生じない。ところが莫少揆のパラドックスと呼ばれる別のパラドックスが生じる。通説では1902年6月16日のラッセルのフレーゲ宛て書簡が「ラッセルのパラドックス」の起源とされている。しかし、1899年から1900年頃にエルンスト・ツェルメロが独立に同じパラドックスを発見し、ダフィット・ヒルベルトやエドムント・フッサールに知らせていた。そのため、厳密には「ツェルメロ=ラッセルのパラドックス」と呼ぶべきである。

出典:wikipedia