ラッセルのパラドックス
古典論理を(グリシン論理やBCK論理などの)縮約規則を取り除いた部分構造論理に置き換え、無制限な内包公理を認める代わりに外延性公理を排除した素朴集合論が矛盾無く展開できることが知られている。外延性公理が排除されるのは、外延性公理から縮約規則が導かれ、したがって矛盾するからである。例えばBCKβでは次のようにして外延性公理から矛盾が導かれる。次の集合 A {\displaystyle A} を考える。 A = { x | A = ∅ } {\displaystyle A=\{x|A=\varnothing \}}
ここで ∅ {\displaystyle \varnothing } は空集合であり、 ∅ = { x | ⊥ } {\displaystyle \varnothing =\{x|\bot \}}
で定義される。集合 A {\displaystyle A} の定義には自己参照が含まれるが、不動点コンビネータによってこれは可能である。この集合論において外延性公理が成立すると仮定する。すると次のようにして矛盾が導かれる。等号 x = y {\displaystyle x=y} の形の仮定に対しては縮約規則が使用できることに注意。
ラッセルのパラドックス(英: Russell's paradox)とは、素朴集合論において、自身を要素として持たない集合全体からなる集合の存在を認めると矛盾が導かれるというパラドックス。バートランド・ラッセルからゴットロープ・フレーゲへの1902年6月16日付けの書簡においてフレーゲの『算術の基本法則』における矛盾を指摘する記述に現れ、1903年出版のフレーゲの『算術の基本法則』第II巻(独: Grundgesetze der Arithmetik II)の後書きに収録された。なお、ラッセルに先立ってツェルメロも同じパラドックスを発見しており、ヒルベルトやフッサールなどゲッティンゲン大学の同僚に伝えた記録が残っている。
ラッセルの型理論(階型理論)の目的のひとつは、このパラドックスを解消することにあった。