利用者:Sillycrown/sandbox1

数理論理学におけるラッセルのパラドックスとは、カントールの素朴集合論のパラドックスである。1901年、論理学者バートランド・ラッセルにより発見された。

包括原理（内包公理）によれば、任意の性質 φ(x) に対して、φ(x) を満たす全ての x から成る集合 {x | φ(x)} が存在する。いま R を自分自身を要素として持たない全ての集合から成る集合とする。もし R が自分自身を要素として持つならば、定義により R は自分自身を要素として持たず、これは不合理。ゆえに R は自分自身を要素として持たない。ところが定義より R は自分自身を要素として持つことになり、やはり不合理。

このパラドックスが指摘された後、パラドックスを回避する2つの方法が提案された。ひとつはラッセルの型理論であり、ひとつはツェルメロの公理的集合論である。

形式的な記述

カントールの集合論における包括原理に現れる性質という概念は、現代的には述語論理式として扱われる。これに合せて、素朴集合論を一階述語論理の理論として形式化する。すなわち、二項述語記号として $\in$ を持ち、公理型として次に示す無制限の包括原理（それに外延性公理）を持つ、等号付き述語論理上の理論を考えるのである：

$\exists y\forall x(x\in y\iff P(x))$　ただし P(x) は変数 y の自由な現れを持たない任意の論理式である。

いま $P(x)$ として $\neg x\in x$ を代入せよ。ここで存在例化と普遍例化により

$y\in y\iff \neg y\in y$

を得る。これは不合理。したがって素朴集合論は矛盾している。矛盾の導出には直観主義論理で十分である。ゆえに論理公理を直観主義論理に制限しても矛盾は解消されない。

集合論の反応

1908年、エルンスト・ツェルメロは、無制限の包括原理を弱い集合の存在公理（分出公理）に置き換え矛盾を排除した集合論の公理化を提案した。この体系は公理化されてはいたが形式化されてはいない。1920年、この公理系はアドルフ・フレンケルとトアルフ・スコーレムにより改良され、1925年、フォン・ノイマンにより正則性公理が追加された。このようにして出来た公理系は現在ZFと呼ばれる。ZFに選択公理を加えたものはZFCと呼ばれる。

パラドックスの解消

包括原理の制限

ツェルメロ集合論（Z）やツェルメロ-フレンケル集合論（ZF）では、任意に与えられた集合 X に対して、「ある性質を満たす全ての X の元からなる集合」の存在が証明できる。このように包括原理を制限したことで、「X の元からなる」という条件がある為に R の存在が言えず、ラッセルのパラドックスの議論がZFの枠内では行えなくなる。

公理的集合論では単なる集合の集まりはクラスと呼ばれ、そのうち何が集合であるのかを公理によって決める。R や後述する V のようなクラスは集合ではないので真のクラスと呼ばれる。ZFでは真のクラスを直接扱うことはできず、クラスを扱う議論はクラスを扱わない（合法な）議論の略記と見做す。NBG集合論はクラスを直接扱えるようにZFを拡大したものである。

集合 A が与えられたとき、集合 B を、自分自身を要素として含まない A の全ての要素からなる集合と定める。B はラッセルのパラドックスと同様の議論により A の要素として含まれないことが分かる。このことより、集合全体から成る集合の存在がZFCにおいて否定されることが分かる。というのも、もし集合全体 V が集合とすれば、 $A=V$ として同様の議論を行うと、 $\neg B\in V$ かつ $B\in V$ となって矛盾するからである。

正則性公理は帰属関係 $\in$ の無限下降列が存在しないことを保証する公理である。帰属関係が整礎であると言い換えられるから整礎性公理とも呼ばれる。この公理は自分自身を要素とする集合の存在を否定するが、このことがパラドックスを解消しているわけではない。（なぜなら公理を追加しても証明できる命題は減らないからである。）

自分自身を要素とする集合の存在を思惟することがパラドックスを引き起こしているわけではない。例えばアクツェルの反基礎集合論（ZFC/AFA）と呼ばれる集合論の公理系では、ある種の基点付き有向グラフに対して、帰属関係のハッセ図がそのグラフと一致する集合（基点がその集合を表す）の存在を保証する公理（反基礎公理）を持つ。これによれば、例えば $\Omega =\{\Omega \}$ を満たす集合の存在が導ける。この公理系はZFCから相対的に無矛盾である。

文法の制限

ラッセルとホワイトヘッドのプリンキピア・マテマティカ（PM）はこの方向によるパラドックスの解決を提供したものである。ここではPMを単純化した単純階型理論（ST）について述べる。STでは、型と呼ばれる自然数 0, 1, 2, … 毎に項が定義される。そして $t\in u$ という表現は、(uのtype)=(tのtype)+1 である場合にのみ許容する。STは各階毎に無制限の包括原理を持つが、 $x\in x$ という表現は文法違反であるから、ラッセルのパラドックスの議論はSTの枠内では行えない。

この方向性での研究は型理論を生み出した。

論理の制限

グリシン論理やBCK論理などの縮約規則を持たない論理上では、無制限の包括原理を持ち（ただし外延性公理を持たない）素朴集合論が矛盾なく展開できる。縮約規則が制限されたことでラッセルのパラドックスの議論が通じなくなっている。外延性公理から縮約規則が導けるので、これらの集合論では外延性公理の否定が証明できる。いくつかの集合論では包括原理よりも強い次の形の主張が成立つ：

$\exists x\forall y\left(y\in x\leftrightarrow \varphi \left(x,y\right)\right)$

すなわち集合の定義に自分自身を用いることができる。

別な例としてラムダ計算に論理記号 $\Xi$ と定数記号 $i$ を加えた体系が考えられる。この体系は次の推論規則からなる：

${\frac {\Gamma \vdash \Xi MN\qquad \Gamma \vdash MR}{\Gamma \vdash NR}}$

${\frac {Mx,\Gamma \vdash Nx}{\Gamma \vdash \Xi MN}}$ ただし $x$ は下式に自由に現れない

${\frac {\Gamma \vdash M}{\Gamma \vdash N}}$ ただし $M=_{\beta }N$

$\Xi MN$ は意味的には $\forall x(Mx\to Nx)$ である。集合を対象から論理式への関数と見做すことにすれば、関数抽象 $\lambda x.M$ は集合 $\{x\mid M\}$、関数適用 $MN$ は論理式 $N\in M$ と同一視できる。このアナロジーにより、通常の論理記号を全て定義により導入することができる：

${\begin{aligned}M\in N&:=MN\\\{x\mid M\}&:=\lambda x.M\\\top &:=\Xi ii\\\forall x.M&:=\Xi (\lambda x.\top )(\lambda x.M)\\M\to N&:=\Xi (KM)(KN)\\\bot &:=\forall x.x\\\exists x.M&:=\forall y.(\forall x.(M\to y)\to y)\\M=N&:=\forall x.(xM\to xN)\end{aligned}}$

ただし $K=\lambda xy.x$ である。

いま $\neg M$ を通常通り $M\to \bot$ の省略形と見做せば、

$R:=\{x\mid \neg x\in x\}$

として R を構成できる。上に定義した論理記号はすべて通常の直観主義論理の法則を満たすから、この体系ではラッセルのパラドックスが生じる。もっと直接的に不動点コンビネータを用いて否定の不動点を構成すれば嘘つきのパラドックスが得られる。その他の再帰的パラドックスも同様に再現できる。

上の体系の論理を縮約を持たないBCK論理に変更することで得られる体系をBCKβという。BCK論理上の素朴集合論と同様に、BCKβは無矛盾である。BCKβでも次の強い主張が成り立つ：

$\exists x\forall y(y\in x\leftrightarrow \varphi (x,y))$

この x は不動点コンビネータ Y を用いて次のように記述できる：

$x:=Y(\lambda x.\{y\mid \varphi (x,y)\})$

歴史

ラッセルは1901年の5月か6月にこのパラドックスを発見した 彼自身の言によれば（彼の1919年の著作 Introduction to Mathematical Philosophy）「最大の濃度が存在しないというカントールの証明の不備を見つけようと試みた」。1902年の手紙において、彼はゴットロープ・フレーゲに対して、フレーゲの1879年の『概念記法』におけるパラドックスの発見を伝え、この問題を論理と集合論の両方の言葉でまとめた。とくに次のフレーゲによる関数定義の言葉が用いられている：以下において、"p. 17" はオリジナルの概念記法を指し、"page 23" は van Heijenoort 1967 における同じページを指す：

There is just one point where I have encountered a difficulty. You state (p. 17 [p. 23 above]) that a function too, can act as the indeterminate element. This I formerly believed, but now this view seems doubtful to me because of the following contradiction. Let w be the predicate: to be a predicate that cannot be predicated of itself. Can w be predicated of itself? From each answer its opposite follows. Therefore we must conclude that w is not a predicate. Likewise there is no class (as a totality) of those classes which, each taken as a totality, do not belong to themselves. From this I conclude that under certain circumstances a definable collection [Menge] does not form a totality.

Russell would go on to cover it at length in his 1903 The Principles of Mathematics, where he repeated his first encounter with the paradox:

Before taking leave of fundamental questions, it is necessary to examine more in detail the singular contradiction, already mentioned, with regard to predicates not predicable of themselves. ... I may mention that I was led to it in the endeavour to reconcile Cantor's proof...."

Russell wrote to Frege about the paradox just as Frege was preparing the second volume of his Grundgesetze der Arithmetik. Frege responded to Russell very quickly; his letter dated 22 June 1902 appeared, with van Heijenoort's commentary in Heijenoort 1967:126–127. Frege then wrote an appendix admitting to the paradox, and proposed a solution that Russell would endorse in his Principles of Mathematics, but was later considered by some to be unsatisfactory. For his part, Russell had his work at the printers and he added an appendix on the doctrine of types.

Ernst Zermelo in his (1908) A new proof of the possibility of a well-ordering (published at the same time he published "the first axiomatic set theory") laid claim to prior discovery of the antinomy in Cantor's naive set theory. He states: "And yet, even the elementary form that Russell⁹ gave to the set-theoretic antinomies could have persuaded them [J. König, Jourdain, F. Bernstein] that the solution of these difficulties is not to be sought in the surrender of well-ordering but only in a suitable restriction of the notion of set". Footnote 9 is where he stakes his claim:

⁹1903, pp. 366–368. I had, however, discovered this antinomy myself, independently of Russell, and had communicated it prior to 1903 to Professor Hilbert among others.

A written account of Zermelo's actual argument was discovered in the Nachlass of Edmund Husserl.

It is also known that unpublished discussions of set theoretical paradoxes took place in the mathematical community at the turn of the century. van Heijenoort in his commentary before Russell's 1902 Letter to Frege states that Zermelo "had discovered the paradox independently of Russell and communicated it to Hilbert, among others, prior to its publication by Russell".

In 1923, Ludwig Wittgenstein proposed to "dispose" of Russell's paradox as follows:

The reason why a function cannot be its own argument is that the sign for a function already contains the prototype of its argument, and it cannot contain itself. For let us suppose that the function F(fx) could be its own argument: in that case there would be a proposition 'F(F(fx))', in which the outer function F and the inner function F must have different meanings, since the inner one has the form O(f(x)) and the outer one has the form Y(O(fx)). Only the letter 'F' is common to the two functions, but the letter by itself signifies nothing. This immediately becomes clear if instead of 'F(Fu)' we write '(do) : F(Ou) . Ou = Fu'. That disposes of Russell's paradox. (Tractatus Logico-Philosophicus, 3.333)

Russell and Alfred North Whitehead wrote their three-volume Principia Mathematica hoping to achieve what Frege had been unable to do. They sought to banish the paradoxes of naive set theory by employing a theory of types they devised for this purpose. While they succeeded in grounding arithmetic in a fashion, it is not at all evident that they did so by purely logical means. While Principia Mathematica avoided the known paradoxes and allows the derivation of a great deal of mathematics, its system gave rise to new problems.

In any event, Kurt Gödel in 1930–31 proved that while the logic of much of Principia Mathematica, now known as first-order logic, is complete, Peano arithmetic is necessarily incomplete if it is consistent. This is very widely – though not universally – regarded as having shown the logicist program of Frege to be impossible to complete.

パラドックスの変種

床屋のパラドックス

このパラドックスには現実的な状況に即したいくつかの変種がある。これらは論理学に親しくない場合にも理解が容易である。例えば、床屋のパラドックスは、自分自身の髭を剃らない男の髭を剃り、自分自身の髭を剃る男の髭を剃らない床屋を考える。すると、床屋が自分自身の髭を剃るとしても、剃らないとしても矛盾する。

一覧表のパラドックス

別の例として、百科事典のなかにある、その百科事典の記事が書かれた5つの一覧を考える。

人物に関する記事の一覧: プトレマイオス7世 ヘルマン・ヘッセ ドン・ニックス ドン・ノッツ ニコラ・テスラ シャーロック・ホームズ 光仁天皇

漢字を含む記事の一覧: 漢字 記号学 土佐日記 ... 漢字を含む記事の一覧 ひらがなを含む記事の一覧 カタカナを含む記事の一覧 ...

場所に関する記事の一覧: レイヴォンマキ 境川 江ノ島

日本に関する記事の一覧: 昭和天皇 境川 江ノ島

自分自身を含まない一覧の一覧: 日本に関する記事の一覧 場所に関する記事の一覧 人物に関する記事の一覧 ... ひらがなを含む記事の一覧 カタカナを含む記事の一覧 ... 自分自身を含まない一覧の一覧?

もし "自分自身を含まない一覧の一覧" が自分自身を含むとすると、自分自身に含まれないことになり、一覧から削除しなければならない。ところが、もしこれが自分自身に含まれないとすると、一覧に追加しなければならない。

While appealing, these layman's versions of the paradox share a drawback: an easy refutation of the barber paradox seems to be that such a barber does not exist, or at least does not shave (a variant of which is that the barber is a woman). The whole point of Russell's paradox is that the answer "such a set does not exist" means the definition of the notion of set within a given theory is unsatisfactory. Note the difference between the statements "such a set does not exist" and "it is an empty set". It is like the difference between saying, "There is no bucket", and saying, "The bucket is empty".

A notable exception to the above may be the Grelling–Nelson paradox, in which words and meaning are the elements of the scenario rather than people and hair-cutting. Though it is easy to refute the barber's paradox by saying that such a barber does not (and cannot) exist, it is impossible to say something similar about a meaningfully defined word.

One way that the paradox has been dramatised is as follows:

Suppose that every public library has to compile a catalog of all its books. Since the catalog is itself one of the library's books, some librarians include it in the catalog for completeness; while others leave it out as it being one of the library's books is self-evident.

Now imagine that all these catalogs are sent to the national library. Some of them include themselves in their listings, others do not. The national librarian compiles two master catalogs – one of all the catalogs that list themselves, and one of all those that don't.

The question is: should these catalogs list themselves? The 'Catalog of all catalogs that list themselves' is no problem. If the librarian doesn't include it in its own listing, it is still a true catalog of those catalogs that do include themselves. If he does include it, it remains a true catalog of those that list themselves.

However, just as the librarian cannot go wrong with the first master catalog, he is doomed to fail with the second. When it comes to the 'Catalog of all catalogs that don't list themselves', the librarian cannot include it in its own listing, because then it would include itself. But in that case, it should belong to the other catalog, that of catalogs that do include themselves. However, if the librarian leaves it out, the catalog is incomplete. Either way, it can never be a true catalog of catalogs that do not list themselves.

類似のパラドックス

上記の床屋のパラドックスを説明する為に、ラッセルのパラドックスを一般化するのは容易である。いま他動詞 <V> を用意して、次の文を考える：

「自分自身を<V>しない全ての人を、かつそれのみを<V>する人」

しばしば「人」を「<V>er」など別のものに置き換える。

「描く」を取れば：「自分自身を描かない全ての人を、かつそれのみを描く画家」

「投票する」を取れば：「自分自身に投票しない全ての有権者に投票する有権者」

いくつかのパラドックスはこの図式に当てはめることができる：

• 床屋のパラドックス「剃る」：自分自身の髭を剃らない全ての人の髭をかつそれのみを剃る床屋を B とする。すると、B が自分自身の髭を剃ることと、剃らないこととが同値となり、矛盾する。
• ラッセルのパラドックス「属する」；自分自身を要素として含まない全ての集合を要素とする集合を R とする。すると、R が自分自身を要素として含むことと、要素として含まないこととが同値となり、矛盾する。
• グレリングのパラドックス「形容する」：自分自身を形容しない形容詞はheterologicalであるということにする。"heterological"は「自分自身を形容しない全ての形容詞を形容する」形容詞である。すると、"heterological"が自分自身を形容することと、形容しないこととが同値となり、矛盾する。

関連するパラドックス

• 嘘つきのパラドックス
• エピメニデスのパラドックス
• クリーネ＝ロッサーのパラドックス
• カリーのパラドックス
• 興味深い数字のパラドックス

関連項目

• 自己言及
• 対角線論法
• 素朴集合論

参考文献

• Potter, Michael (15 January 2004), Set Theory and its Philosophy, Clarendon Press (Oxford University Press), ISBN 978-0-19-926973-0 
• van Heijenoort, Jean (1967, third printing 1976), From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931, Cambridge, Massachusetts: Harvard University Press, ISBN 0-674-32449-8 
• Livio, Mario (6 January 2009), Is God a Mathematician?, New York: Simon & Schuster, ISBN 978-0-7432-9405-8 
• Barwise, Jon; Etchemendy, John (6 April 1989), The Liar: An Essay on Truth and Circularity, Oxford University Press, ISBN 978-0-19-505944-1 

外部リンク

• Weisstein, Eric W. "Russell's Antinomy". mathworld.wolfram.com (英語).
• Russell's Paradox at Cut-the-Knot
• Stanford Encyclopedia of Philosophy: "Russell's Paradox" – by A. D. Irvine.