本日は、Frege の基本法則 V が Cantor's Theorem と矛盾することの証明を与えます。
Cantor's Theorem の証明は、しばしば全射の写像を使い矛盾を導くことでなされますが、基本法則 V が Cantor's Theorem と矛盾することの証明には、単射の写像を使い矛盾を導くことで証明する方が適当です。しかし単射を使った Cantor's Theorem の証明はあまり見かけないので、ここで単射による Cantor's Theorem の証明を与え、その証明を Frege の言葉に翻訳することによって、基本法則 V が Cantor's Theorem と確かに矛盾することを見てみます。これがどなたかの参考になれば幸いです。なお、Frege の基本法則 V が Cantor's Theorem と矛盾するという話は昔から言われていることですので、本日の日記に original な主張は何もございません。前もってお伝えしておきます。
目次
1. Frege の基本法則 V と Cantor's Theorem が矛盾するという従来からの話
2. Cantor's Theorem 証明への準備: 濃度の大小と、単射の写像との関係
3. Cantor's Theorem とその証明
4. Frege の基本法則 V が Cantor's Theorem と矛盾するという証明の詳細
補足 Cantorian Predicate F の具体例: 対角化による図表
1. Frege の基本法則 V と Cantor's Theorem が矛盾するという従来からの話
Gottlob Frege の Grundgesetze der Arithmetik における基本法則 V が、Russell Paradox により、矛盾をもたらすことはよく知られています。そもそも基本法則 V は Cantor's Theorem (Cantor's Power Set Theorem) と整合しないので、基本法則 V に問題が含まれていることは、Frege にとって、場合によっては予知できたはずであると言われています*1。基本法則 V を現代の記法で書けば、一つには、次のようになります*2。
(V) 'εFε = 'εGε ⇔ ∀x( Fx ⇔ Gx ).
この式は次の二つの式の連言と同値です。
(Va) ∀x( Fx ⇔ Gx ) → 'εFε = 'εGε,
(Vb) 'εFε = 'εGε → ∀x( Fx ⇔ Gx ).
これら二つの式のうち、(Va) は、集合論で言えば外延性の公理に相当しますので、問題ないものと考えられています*3。問題があるのは (Vb) の方で、Frege も Grundgesetze の第2巻あとがきで述べているように*4、こちらから矛盾が生じます。(Vb) 左辺の ε という記号の左肩にある Abstraction Operator ( ' ) を、概念から概念の外延への写像と考えると、この写像は単射であり、このことは Cantor's Theorem と矛盾するので、(Vb) は問題を抱えているのであると、主として海外の研究者たちによってしばしば指摘されてきました*5。では実際どのように (Vb) は Cantor's Theorem と不整合なのでしょうか。(Vb) の Abstraction Operator が単射の写像を表している場合、Cantor's Theorem と矛盾する様を具体的に見てみたいと思います。
ところで Cantor's Theorem の証明についてですが、素朴集合論の日本語で書かれている教科書で、昔から定番の本を開いてみると、その定理の証明では「任意の集合からその巾集合へ、全射の写像があるとすると矛盾が生じる」という事実から、その定理がしばしば証明されています。たとえば以下の書籍がそうです。
- 赤攝也 『集合論入門』、新数学シリーズ 1、培風館、初版1957年、増補版1959年、61-62ページ、同書文庫版、ちくま学芸文庫、筑摩書房、2014年、95-97ページ、
- 松坂和夫 『集合・位相入門』、岩波書店、1968年、76-77ページ*6。
また、これらのような定番の教科書とまでは言えないものの啓発的な副読本であって、図を多用し、わかりやすく丁寧な解説を心掛けることにより読者の多いと思われる次の本でも、全射を使った証明がなされています。
- 志賀浩二 『集合への30講』、数学30講シリーズ 3、朝倉書店、1988年、107-109ページ。
他方、前に述べたように、海外の研究者たちは「(Vb) と Cantor's Theorem が矛盾するのは、Abstraction Operator が単射を表すからだ」と指摘してきました。つまり、日本で評価の高い定番の教科書では、集合間に全射の写像があると仮定し矛盾を導くことで Cantor's Theorem を証明しているのに対し、海外の研究者の指摘では、Abstraction Operator に関し、集合間に単射があるとすると矛盾が生じるので (Vb) と Cantor's Theorem は不整合なのだと言っています。前者の教科書では Cantor's Theorem を全射を仮定し証明するのに対し、後者はその定理を単射を使い証明しているのです。そして国内の定番の教科書にある全射を仮定した証明を Frege の言葉で言い直すことによって、(Vb) が Cantor's Theorem と矛盾することを実際に私自身確かめようとしたことがあるのですが、どうもうまくいきません。私のやり方がまずかったのかもしれませんが、全射による証明を、できるだけ Frege の言葉に沿って翻訳し直そうとしても齟齬が出てきてうまくはまらないのです*7。
そこで国内の教科書ではたぶんあまり目にしない、単射を仮定することで Cantor's Theorem を証明する証明法を以下に記してみます。そしてそのあとに、それを Frege の言葉に言い直してみます。そうしますと、すんなりとうまくいきます。
2. Cantor's Theorem 証明への準備: 濃度の大小と、単射の写像との関係
Cantor's Theorem を証明する前に準備をします。下に出てくる濃度の大小と、単射の写像との関係を述べた (i) - (v) がそれです。これら (i) - (v) のあとに Cantor's Theorem が記され、その下にその定理の証明を提示します。
以降、記号 | | を、集合の濃度を表すものとします*8。また、このあとの (i) - (v) に見られる論証は、常識と直観に訴えてなされています*9。厳密にやろうとすると話が大規模になってくるので (選択公理が絡んでくるので)、素朴な論証に留めています。これらは粗描の一つとお考えください。
(i) B を一つの集合、B1 をその部分集合とします。このとき、B1 の濃度は B の濃度以下であるということを、|B1| ≦ |B| と定めます。
ただし B1 が B の部分集合ならば、特に B1 が B の真部分集合ならば、B1 の方が B よりも、いわば「小さい」ので、|B1| ≦ |B| と定めるのではなく、|B1| < |B| と定めるべきであると一見思われるかもしれません。しかし真部分集合である B1 が、それを含んでいる集合 B と濃度が等しくなること (|B1| = |B|) があり得ます。たとえば、偶数の集合は自然数の集合の真部分集合ですが、両者の数を一つずつ組みにしてみると余りが出ることはないので、それら二つの集合は対等であり、よって濃度は等しくなります。このように無限集合を考慮すれば、部分集合とそれを含む集合の濃度が等しくなることがあるので、両者の間では濃度の大きさを |B1| < |B| と定めるのではなく、|B1| ≦ |B| と定めるのが適切です。
(ii) A と B を二つの集合とする時、A が B の部分集合 B1 と対等であるならば、A と B との濃度は |A| ≦ |B| と定めます。
なぜこのようにするのがよいのかというと、 A と B1 が対等ならば |A| = |B1| であり、上の (i) の |B1| ≦ |B| によって、|A| ≦ |B| だからです。
これは (ii) の前半「A が B の部分集合 B1 と対等であるならば」の部分を、(iii) の前半「A から B へ、単射の写像があるならば」に入れ換えたものです。ということは、これら (ii) の前半と (iii) の前半は同値だということです。同値であることの証明を略述します。
証明概略
(ii) 前半 → (iii) 前半
(ii) の前半「A が B の部分集合 B1 と対等である」としてみます。すると A と B1 は対等なので、 A から B1 へ、全単射の写像 f があります。この時、f の値域 B1 を B へと、いわば拡大してやると、一般には f は全射ではなくなります。しかし A から B への写像 f は単射であり続けます。よって (iii) の前半「A から B へ、単射の写像がある」と言うことができます。
(iii) 前半 → (ii) 前半
逆に (iii) の前半「A から B へ、単射の写像がある」としてみます。この写像を f とし、その値域を B1 ⊆ B とすると、この B を B1 へと、いわば縮小した写像 f は、A から B1 への全単射となります。すると、A は B1 と対等であるということですから、(ii) の前半「A は B の部分集合 B1 と対等である」と言うことができます。
(iv) |A| ≦ |B|、かつ |B| ≦ |A| でないならば、|A| < |B|。記号で書くと [|A| ≦ |B| ∧ ¬(|B| ≦ |A|)] → |A| < |B|。
背理法で証明します。
| A | < | B | でないとしてみます。ならば、 | B | < | A | または | A | = | B | だ、ということです。ところで | B | ≦ | A | ではありません。ということは「 | B | < | A | または | A | = | B | 」ではない、ということです。これは矛盾です。故に、 | A | < | B | です。 |
これは (iv) の前半を、(iii) により、単射の言葉に言い換えたものです。
以下ではこの (v) を使って Cantor's Theorem を証明します。(v) における A を任意の集合 X、B を X の巾集合 𝔓(X) とし、X から 𝔓(X) への単射はあるが、𝔓(X) から X への単射はないことにより、|X| < |𝔓(X)| を結論します。これが Cantor's Theorem です。
3. Cantor's Theorem とその証明
Cantor's Theorem X を任意の集合とすると、X の濃度よりも、その巾集合 𝔓(X) の濃度の方が大きい。すなわち、|X| < |𝔓(X)|。
この定理を証明するために、上に掲げた (iv) により、|X| ≦ |𝔓(X)| ではあるものの、しかし |𝔓(X)| ≦ |X| ではないことを示して証明します。その際、(v) を使って、X から 𝔓(X) には単射があるものの、𝔓(X) から X には単射がないことを明らかにします。単射がないというこの結論は、背理法により、それがあるとすると矛盾が出ることで、示されます。
証明
| X | ≦ | 𝔓(X) | : |
X から 𝔓(X) へ単射があることを示せばよい。任意の集合 X の各元 a を、この a だけが属する集合 {a} に写す写像を考えることができて、この写像は明らかに単射です。
| 𝔓(X) | ≦ | X | ではない: |
𝔓(X) から X には単射がないことにより、|𝔓(X)| ≦ |X| ではないことを証明します。そこで、次の文献の記述を参考にします*10。
- Peter Milne ''Frege's Folly: Bearerless Names and Basic Law V,'' in M. Potter and T. Ricketts eds., The Cambridge Companion to Frege, Cambridge University Press, 2010, pp. 492-494,
- J. Barkley Rosser Logic for Mathematicians, 2nd ed., Dover Publications, 2008, p. 346. This book was first published in 1978.
以下ではこの Milne 先生の記述を参考にして当方で取捨、選択、追加などの arrange を大幅に行い、証明を記すことにします。その際、証明の流れの大枠については、この Milne 論文と上記 Rosser 先生の本の記述を参考にしています*11。なお、下記の証明は、よく言えば丁寧、悪く言えばかなりくどいものとなっております。証明の gap をある程度減らして、論証の推移をできるだけわかりやすくするために、わざとそのようにしております。どうかご了承ください。
さて、X を任意の集合、𝔓(X) をその巾集合とし、𝔓(X) から X への写像を g とします。そして X の元から成る部分集合の一つを、次のように定義します。
Cantorian Set: Y =def. { x ∈ X | ∃Z ⊆ X [ x = g(Z) ∧ x ∉ Z ] }.
この集合の内容を説明する前に、基本的なことを確認しておきますと、𝔓(X) に含まれている部分集合は、X の元 x から成りますので、𝔓(X) に含まれているある部分集合に X のある元は属しているか、属していないかのどちらかです。たとえば、 X = { a, b, c, ... } とし、𝔓(X) = { {a}, ..., { a, c }, ..., { b, c }, ... } とします。g は 𝔓(X) に含まれる部分集合を取って、X の元を返す写像ですので、仮に a = g({ b, c }) とすると、a ∉ { b, c } です。X の元 a は、𝔓(X) に含まれている部分集合 { b, c } に属しているか否かといえば、今見たように属していないということです。また仮に c = g({ a, c }) とすると、c ∈ { a, c } です。X の元 c は、𝔓(X) に含まれている部分集合 { a, c } に属しているか否かといえば、属しているということです。このように、𝔓(X) に含まれている部分集合各々に対して、X の元 x は属しているか、属していないか、どちらか一方に決まっているというわけです。
以上を理解した上で Cantorian Set Y の中身を見てみますと、これは X の元 x から成る集合です (x ∈ X)。この Y は、次のような条件を満たした x から成ります。まず、Z は X の元 x から成る部分集合なので (∃Z ⊆ X)、写像 g はこれを取って、その像として X の元 x を返しています (x = g(Z))。そして Z は X の元から成る部分集合ですから、x = g(Z) の x は Z に属するか否かのどちらかです。それがどちらなのかというと、x は Z に属していません (x ∉ Z)。こうして Y という集合は、写像 g が input として取る Z には属さないような、そのような output としての x をすべて集めてできている、ということになります。Cantorian Set Y についての説明はこれぐらいにしておきます。
そして、Y は X の元 x から成る部分集合なので、g はこれを取り、像 y を返すとします。つまり、
(*) y = g(Y)
とします。(もちろん y ∈ X です。)
以下、証明の本文に入って行きますが、ここで写像 g を単射であると仮定します。
さて、Y は X の元から成る部分集合であり、y は X の元なので、y は Y に属するか (y ∈ Y)、属さないか (y ∉ Y)、これらどちらか一方だけが必ず成り立つはずです。そこで y は Y に属するとしてみましょう。
y ∈ Y:
今、y ∈ Y と仮定します。すると y は Y に属しているので、y は Cantorian Set Y に属する条件を満たしており、∃Z ⊆ X [ y = g(Z) ∧ y ∉ Z ] です。つまりある部分集合 Z について、y = g(Z) かつ y ∉ Z である、ということです。そして (*) により y = g(Y) でした。こうして y = g(Z) でもあり、y = g(Y) でもある、ということです。ところで g は単射であると仮定しています。単射とは、たとえば写像 f を単射とすると、f が a を c に写し (f(a) = c)、f が b を同じ c に写すなら (f(b) = c)、a = b であるとする写像です。したがって、g が単射なら、y = g(Z) でもあり、y = g(Y) でもあるとすると、g は同じ y に Z と Y を写しているので、Z = Y です。ところで少し振り返ると y ∉ Z でした。よって Z = Y ですので、y ∉ Y です。こうして y ∈ Y と仮定して y ∉ Y が出ましたので、y ∈ Y かつ y ∉ Y です。これは矛盾です。故に背理法によって*12、最初の仮定 y ∈ Y は否定されねばならず、y ∉ Y が正しいと言えます。つまり y ∉ Y が証明されました。
今、y ∉ Y が証明されましたので、y ∉ Y は定理です。ところで (*) により y = g(Y) です。すると、y = g(Y) ∧ y ∉ Y ですので、∃Y ⊆ X [ y = g(Y) ∧ y ∉ Y ] と言うことができて、これは Cantorian Set Y に y が属する条件を満たしていますから、y ∈ Y ということになります。今、定理 y ∉ Y から y ∈ Y が出ましたので、y ∉ Y かつ y ∈ Y です。これは矛盾です。行き止まりに突き当りました。
振り出しに戻ります。y は Y に属するか (y ∈ Y)、または属さないか (y ∉ Y) のどちらか一方だけが必ず成り立つはずでした。このうち、前者の y ∈ Y からは矛盾に行き当たって y ∈ Y が成り立たないことが、すぐ上でわかりました。そこで今度は「y ∈ Y または y ∉ Y」のうち、後者の y は Y に属さないという選択肢を取ってみましょう。
y ∉ Y:
y は Y に属さないと仮定してみます (y ∉ Y)。そして (*) により y = g(Y) です。すると、先ほどの繰り返しですが、y = g(Y) ∧ y ∉ Y ですので、∃Y ⊆ X [ y = g(Y) ∧ y ∉ Y ] と言うことができて、これは Cantorian Set Y に y が属する条件を満たしていますから、y ∈ Y ということになります。今、y ∉ Y と仮定して y ∈ Y が出ましたので、y ∉ Y かつ y ∈ Y です。これは矛盾です。よって背理法により*13、仮定 y ∉ Y は否定されねばならず、¬(y ∉ Y), すなわち y ∈ Y が正しいと言えます。つまり y ∈ Y が証明されました。
さて今、 y ∈ Y が証明されましたから、y ∈ Y は定理です。ところで y ∈ Y ということは、やはり先ほどの繰り返しになりますが、y は Y に属しているということですので、y は Cantorian Set Y に属する条件を満たしており、∃Z ⊆ X [ y = g(Z) ∧ y ∉ Z ] です。つまりある部分集合 Z について、y = g(Z) かつ y ∉ Z である、ということです。そして (*) により y = g(Y) でした。こうして y = g(Z) でもあり、y = g(Y) でもある、ということです。ところで g は単射であると仮定しています。したがって g が単射なら、y = g(Z) でもあり、y = g(Y) でもあるとすると、Z = Y です。ところで振り返ると y ∉ Z でした。よって y ∉ Y です。こうして定理 y ∈ Y から y ∉ Y が出ましたので、y ∈ Y かつ y ∉ Y です。これは矛盾です。また行き止まりに突き当ってしまいました。本当の袋小路です。
こうして y ∈ Y としても y ∉ Y としても、いずれからも矛盾が生じます。故に、g は単射ではないと結論されます。以上により、𝔓(X) から X には単射はありません。
これで、上述の (v) により、|X| < |𝔓(X)| です。証明終わり。
4. Frege の基本法則 V が Cantor's Theorem と矛盾するという証明の詳細
今度は、上の証明を Frege の言葉でほとんどそのまま言い直すことにより、基本法則 V の Abstraction Operator が、その法則の難点になっていることを確認してみます。
(Vb) 'εFε = 'εGε → ∀x( Fx ⇔ Gx )
でした。記号 ε の左肩の点のような印 ' が Abstraction Operator です。これは概念を取って概念の外延を返す写像です*14。
概念とは、簡単には、日本人であることや、偶数であることや、自動車であることなどです。太郎が日本人であるならば、太郎は日本人であるという概念に当てはまる、と言われます。Mary が日本人でないならば、Mary は日本人であるという概念には当てはまらない、と言われます。
概念の外延とは何であるかについては、いささかややこしい問題がありますので説明を控えます (概念についても本当はあるのですが ... )。それが何であれ、他と区別ができて数えることのできるようなもののことと考えておいていただければ結構です。ということは、さしあたり集合に属する元のようなものと解しておいてくださいましたら構いません。そうしておくだけで、以下の論証には支障を来たしません。
(Vb) の Abstraction Operator ですが、これは単射の写像を表しています。(Vb) の対偶を取ってみますと、
(Vb-Cont. 1) ¬∀x( Fx ⇔ Gx ) → 'εFε ≠ 'εGε
であり、これを同値変形すると、
(Vb-Cont. 2) ∃¬x( Fx ⇔ Gx ) → 'εFε ≠ 'εGε
となります。この式の内容を簡単に言うと、「異なる概念同士 F ≠ G について、Abstraction Operator が F, G を取ると、各々異なった概念の外延 'εFε ≠ 'εGε を返す」となります。これは単射の定義に適っています。単射とは、異なる元を取れば、異なる像を返す写像だからです。
さて、概念の集合から概念の外延の集合へ、Abstraction Operator により、単射があるとし、ここから矛盾を引き出すという論証を、上の Cantor's Theorem の証明にならって記してみます*15。
| M | ≦ | N | ではない: |
M を概念の集合、N を概念の外延の集合とし、M から N への写像を g とします。そして M の概念の一つを、次のように定義します。
Cantorian Predicate: F =def. ( x ∈ N ∧ ∃G ∈ M [ x = g(G) ∧ ¬Gx ] ).
この概念の内容を説明する前に、基本的なことを確認しておきますと、私たちは概念というものを、何であれ何かが当てはまったり、当てはまらなかったりすることが、はっきりしているものだけに限ることにしますので、M に含まれている概念は、N に属する何らかのものが当てはまるか、当てはまらないかのどちらかです。たとえば、M = { H, I, J, ... } とし、N = { a, b, c, ... } とし、成り立つ式の集合を { Ha, Hc, Ib, Jc } とすると、a は H に当てはまりますが、I には当てはまりません。b は I には当てはまりますが、H には当てはまりません。c については、もうおわかりと思います。
ところで、g は M に含まれる概念を取って、N の元を返す写像ですので、たとえば、b = g(H) とすると、¬Hb です。N の元 b は、M に含まれている概念 H に当てはまるか否かといえば、今見たように当てはまらないということです。またたとえば、c = g(J) とすると、Jc です。N の元 c は、M に含まれている概念 J に当てはまるか否かといえば、当てはまるということです。このように、M に含まれている概念各々に対して、N の元は当てはまるか、当てはまらないか、どちらか一方に決まっているというわけです。
以上を理解した上で Cantorian Predicate F の中身を見てみますと、F は概念の外延の集合に属している (x ∈ N) もの x に関する概念です。この F には、次のような条件を満たした x が当てはまります。まず G は M に属する概念なので (∃G ∈ M)、写像 g はこれを取って、その像として N の元 x を返しています (x = g(G))。そして G は概念ですから、x = g(G) の x は G に当てはまるか否かのどちらかです。そしてそのどちらなのかというと、x は G に当てはまりません (¬Gx)。こうして F という概念は、写像 g が input として取る G には当てはまらないような、そのような output としての x すべてに当てはまる概念である、ということになります。Cantorian Predicate F についての説明はこれぐらいにしておきます。
そして、F は M に属する概念なので、g はこれを取り、像 d を返すとします。つまり、
(#) d = g(F)
とします。(もちろん d ∈ N です。)
以下、証明の本文に入って行きますが、ここで写像 g を、Abstraction Operator が表す単射であると仮定します。
さて、F は M に属する概念の一つであり、d は N の元なので、d は F に当てはまるか (Fd)、当てはまらないか (¬Fd)、これらどちらか一方だけが必ず成り立つはずです。そこで d は F に当てはまるとしてみましょう。
Fd:
今、Fd と仮定します。すると d は F に当てはまっているので、d は Cantorian Predecate F に当てはまる条件を満たしており、∃G ∈ M [ d = g(G) ∧ ¬Gd ] です。つまりある概念 G について、d = g(G) かつ ¬Gd である、ということです。そして (#) により d = g(F) でした。こうして d = g(G) でもあり、d = g(F) でもある、ということです。ところで g は単射であると仮定しています。単射とは、たとえば写像 f を単射とすると、f が a を c に写し (f(a) = c)、f が b を同じ c に写すなら (f(b) = c)、a = b であるとする写像です。したがって、g が単射なら、 d = g(G) でもあり、d = g(F) でもあるとすると、g は同じ d に G と F を写しているので、G = F です。ところで少し振り返ると ¬Gd でした。よって G = F ですので、¬Fd です。こうして Fd と仮定して ¬Fd が出ましたので、Fd かつ ¬Fd です。これは矛盾です。故に背理法によって*16、最初の仮定 Fd は否定されねばならず、¬Fd が正しいと言えます。つまり ¬Fd が証明されました。
今、¬Fd が証明されましたので、¬Fd は定理です。ところで (#) により d = g(F) です。すると、d = g(F) ∧ ¬Fd ですので、∃F ∈ M [ d = g(F) ∧ ¬Fd ] と言うことができて、これは Cantorian Predicate F に d が当てはまる条件を満たしていますから、Fd ということになります。今、定理 ¬Fd から Fd が出ましたので、¬Fd かつ Fd です。これは矛盾です。行き止まりに突き当りました。
振り出しに戻ります。d は F に当てはまるか (Fd)、当てはまらないか (¬Fd)、これらどちらか一方だけが必ず成り立つはずです。このうち、前者の Fd からは矛盾に行き当たって Fd が成り立たないことが、すぐ上でわかりました。そこで今度は「Fd または ¬Fd」のうち、後者の d は F に当てはまらないという選択肢を取ってみましょう。
¬Fd:
d は F に当てはまらないと仮定してみます (¬Fd)。そして (#) により d = g(F) です。すると、d = g(F) ∧ ¬Fd ですので、∃F ∈ M [ d = g(F) ∧ ¬Fd ] と言うことができて、これは Cantorian Predicate F に d が当てはまる条件を満たしていますから、Fd ということになります。今、¬Fd と仮定して Fd が出ましたので、¬Fd かつ Fd です。これは矛盾です。よって背理法により*17、仮定 ¬Fd は否定されねばならず、¬¬Fd, すなわち Fd が正しいと言えます。つまり Fd が証明されました。
さて今、 Fd が証明されましたから、Fd は定理です。ところで Fd ということは、やはり先ほどの繰り返しになりますが、d は F に当てはまるということですので、d は Cantorian Predicate F に当てはまる条件を満たしており、∃G ∈ M [ d = g(G) ∧ ¬Gd ] です。つまりある概念 G について、d = g(G) かつ ¬Gd である、ということです。そして (#) により d = g(F) でした。こうして d = g(G) でもあり、d = g(F) でもある、ということです。ところで g は単射であると仮定しています。したがって g が単射なら、d = g(G) でもあり、d = g(F) でもあるとすると、G = F です。ところで振り返ると ¬Gd でした。よって ¬Fd です。こうして定理 Fd から ¬Fd が出ましたので、Fd かつ ¬Fd です。これは矛盾です。また行き止まりに突き当ってしまいました。本当の袋小路です。
こうして Fd としても ¬Fd としても、いずれからも矛盾が生じます。故に、g は単射ではないと結論されます。以上により、M から N には単射はありません。証明終わり。
これで Frege の (Vb) が Cantor's Theorem と矛盾してしまうことが実際に確かめられました。全射を使った Cantor's Theorem の証明を Frege の言葉にできるだけ忠実に言い直して (Vb) が Cantor's Theorem と矛盾することを、かつて私は確かめようと試みたことがあったのですが、うまくいきませんでした。しかし今回のように、単射を使った Cantor's Theorem の証明なら Frege の言葉にあっさりと翻訳できて (Vb) と Cantor's Theorem が矛盾する様を簡単に見ることができました。これらに目新しい主張は何もございませんが、どなたかのお役に立てればと思います。
補足 Cantorian Predicate F の具体例: 対角化による図表
ここで、
Cantorian Predicate: F =def. ( x ∈ N ∧ ∃G ∈ M [ x = g(G) ∧ ¬Gx ] )
をより理解するために、この概念の内容をもう少し具体的に構成してみましょう。
概念の集合 M の元 Gn から ( n = 0, 1, 2, … )、概念の外延の集合 N の元 x = g(Gn) への、ある一つの写像を g とします。そこで次の表を見てください*18。
この表は写像 g に関して、どの概念 Gn に、どの概念の外延 g(Gn) が当てはまるのかを表したものです。
表の左端、縦の欄には概念が下に向かって G0, G1, G2, ..., と並んでおり、表の一番上、横の行には概念の外延が左から右へ g(G0), g(G1), g(G2), ..., と並んでいます。
そして g は単射であるとします。g が単射であるということは、異なる概念 Gi ≠ Gj それぞれが、同じ一つの概念の外延 g(Gn) に g によって写される (g(Gi) = g(Gj)) ことはない、ということです。Gi ≠ Gj ならば、いつでも g(Gi) ≠ g(Gj) になる、ということです。
また、この表の〇と×は random に配されています。たまたまこのように配しただけであって、別の並びに配置し直しても構いません。〇と×の並びが random でよいということは、g が任意の単射であることを意味しています。
表の中身を詳しく見てみましょう。たとえば G1 の g による像 g(G1) が G0 に当てはまる場合、そのことを G0 の横の行と g(G1) の縦の欄が交わるマス目において〇印で表しています。他方 G2 の g による像 g(G2) が G0 に当てはまらないことを G0 の横の行と g(G2) の縦の欄が交わるマス目において×印で表しています。
すると、たとえば表の g(G0) から下の縦の欄を見れば、g(G0) という概念の外延が当てはまる概念は、G0, G3, G5, …, であり、g(G1) が当てはまるのは、G0, G2, G3, …, であることがわかります。
また、たとえば表の G0 から横の行を見れば、G0 に当てはまる概念の外延は、g(G0), g(G1), g(G4) …, であり、G1 に当てはまるのは、g(G3), g(G5), …, であることがわかります。
さてここで、ある概念 F を考えてみます。 これは次のようにして作られます。表の対角線に沿って、斜めにマス目を見てみましょう。対角線の矢印に沿って進みながら○印に出会えば、そのマスの欄の g(Gn) が F には当てはまらず、×印に出会えば、そのマスの欄の g(Gn) が F に当てはまる、とします。注意すべきは、〇に出会えばその g(Gn) は F に「当てはまらない」、ということであり、×に出会えばその g(Gn) は F に「当てはまる」、ということです。
そこで改めて表を見てみると、対角線上、左斜め一番上のマスでは、G0 の行と g(G0) の欄が交わっており、そこには○印があるので、F には g(G0) は当てはまらない、ということです。次に対角線を右下へと一つ進むと、G1 の行と g(G1) の欄が交わっており、この対角線上のマス目には×印があるので、F には g(G1) が当てはまる、ということです。以下、右斜め下に対角線を進んで行けば、F に当てはまる概念の外延と当てはまらない概念の外延が明らかになります。
対角線 (diagonal) 上の〇×を拾い上げて表にすれば、次のようになります。
G0 の横の行を見ると○印がありますが、これは概念 G0 に、その横の行、右端に記された概念の外延 g(G0) が当てはまることを表しており、また G1 の横の行を見ると×印がありますが、これは G1 に、その右端に記された g(G1) が当てはまらないことを表しています。
今のことを別に言い換えれば、G0 の行の○印は、G0 に右端の自らの像 g(G0) が当てはまることを表しており、G1 の行の×印は、G1 に右端の自らの像 g(G1) が当てはまらないことを表しています。つまり対角線の○×は、Gn(g(Gn)) かまたは ¬Gn(g(Gn)) であることを表しています。
次にこの表に対して、F に当てはまる概念の外延と当てはまらない概念の外延を、○×で表した欄を追加してみるならば、以下のようになります。
Diagonal の縦欄で○とある行は、F の縦欄で×となっており、Diagonal の縦欄で×とある行は、F の縦欄で〇となっています。
たとえば G0 の横の行を見てみると、その端に g(G0) が記されていて、Diagonal の縦欄では〇であり、F の縦欄では×となっています。これは概念の外延 g(G0) が概念 G0 には当てはまっているが、F には当てはまっていないことを表しています。
ここからわかることの一つは、G0 は g(G0) が当てはまる点で、g(G0) が当てはまらない F と異なっている、ということです。もう一つの例でこのことを確認しておくと、表の G1 の横を見てみるならば、その端に g(G1) とあって、Diagonal では×となっており、F では〇となっています。これは g(G1) が G1 には当てはまらないが、F には当てはまっていることを表しており、G1 は g(G1) が当てはまらない点で、g(G1) が当てはまる F と異なっている、ということを意味しています。G2 以下もすべて同様に F と必ず異なっていることは、これでわかると思います。こうして F は、表に出てくるいかなる Gn とも異なっています。そして F は、Gn の像が Gn 自らに当てはまらないような、そのような像 (= 概念の外延) が、それらのみが当てはまる概念だ、ということです。
さてそこで、最初の表を再度掲げますので見てください。
この表の対角線、矢印の先の大きな丸印のところに注目してください。ここは対角線上のマス目で、g(F) の欄と F の行とが交差するところです。他のマス目と同様に、ここにも〇か×のどちらか一つだけがくるはずです。ではここには〇がくるでしょうか。それとも×がくるでしょうか。
〇がくると仮定してみましょう。するとここは対角線上なので、そこに〇があるということは、g(F) が F に当てはまらないということになりますから、g(F) の縦の欄と F の横の行が交差するマスには×と記されねばなりません。ですが、そのマスとは大きな丸印のマスで、そこには既に〇が記されています！ つまりそのマスには〇と同時に×が記されねばならないということです。しかしこれは矛盾です。
今、大きな丸印のマス目のところに〇がくるとした結果、矛盾が出てきました。それならば、そこに×がくると仮定したらどうでしょうか。しかし×がきても、〇がきた場合と同様に矛盾が生じることはすぐにわかります。
こうして、概念 F の像である概念の外延 g(F) が F に当てはまるのか否かといえば、それは今の結果からわかるように、当てはまるとすれば当てはまらず、当てはまらないとすれば当てはまる、ということになって矛盾が生じるということです。
写像 g が単射であり、今の表にあるように、概念 Gn と概念の外延 g(Gn) を順番に並べることができる場合、曖昧でもない概念 F を表に位置付けようとすると矛盾が出てくることがわかりました。この補足の section の前に、Cantor's Theorem にならって、概念から概念の外延へ、Frege の Abstraction Operator により単射があるとすると矛盾が出てくる様をみました。そこで矛盾が出てきた様子を図表で描いてみるならば、ここで見たように、図の対角線上のマス目の一つに○と×が同時にきて、かちあってしまうことで表されることになります*19。
以上で終ります。もしも間違いが含まれていましたらすみません。また、誤字や脱字、衍字や衍文、不明瞭、不正確な表現などがありましたら申し訳ございません。今後、精度を高めていく努力をすることに致します。
*1:John P. Burgess, ''Frege and Arbitrary Functions,'' in W. Demopoulos ed., Frege's Philosophy of Mathematics, Harvard University Press, 1995, 2nd printing 1997, pp. 101-102. This paper was first published in 1993.
*2:これは基本法則 V の正確な翻訳ではありません。そのため「一つには」と本文中で断っています。実際にはこの式の中央にある必要十分条件記号 ⇔ は、正しくは等号 = でなければならず、等号であることが本質的なのですが、この点については今回は置いておき、一般に行われているように、必要十分条件の記号で記しておきます。
*3:Michael D. Resnik, Frege and the Philosophy of Mathematics, Cornell University Press, 1980, p. 214.
*4:Gottlob Frege, Grundgesetze der Arithmetik I/II, mit Ergaenzungen zum Nachdruck von Christian Thiel, Georg Olms Verlag, 1998, Band II, SS. 256-257, 邦訳、G. フレーゲ、『算術の基本法則』、野本和幸編、フレーゲ著作集 3, 勁草書房、2000年、407-409ページ。
*5:Resnik, loc.cit. Also see, e.g., John P. Burgess, ''Introduction to Part II, Frege Studies,'' in George Boolos, Logic Logic, and Logic, Harvard University Press, 1998, pp. 137-138, Michael Potter, Reason's Nearest Kin, Oxford University Press, 2000, p. 114, Kevin C. Klement, ''Russell, His Paradoxes, and Cantor's Theorem: Part I,'' in: Philosophy Compass, vol. 5, no. 1, 2010, pp. 18-19, and Gregory Landini, Frege's Notations, Palgrave Macmillan, 2012, pp. 172-173.
*6:なお、松坂先生によるここでの Cantor's Theorem の証明と本質的に同じ証明は、次にもあります。松坂和夫、『現代数学序説 集合と代数』、ちくま学芸文庫、筑摩書房、2017年、176-178ページ。ちなみにこの文庫本は、先生の『数学序説 集合と代数』、実教出版、1978年刊行を改題、文庫化したものです。
*7:Abstraction Operator の表す写像が、「概念から概念の外延への」単射である、ということが neck となっていると思われます。
*8:以降の素朴集合論の言葉使いは、松坂和夫、『集合・位相入門』、岩波書店、1968年におおむね沿います。もしも自分に取って見慣れない言葉使いが出てきましたら、この松坂先生の本をご覧ください。
*9:ここでの (i) - (iv) にある論証は、松坂、『集合・位相入門』、67-69, 63-64ページにある記述にならったものです。(v) を含めた同種の記述は、藤田博司、『「集合と位相」をなぜ学ぶのか』、技術評論社、2018年、93-95ページにもあります。
*10:直前の註で言及した藤田先生の『「集合と位相」をなぜ学ぶのか』、100-101ページでも、日本語の書籍には珍しく、単射がないことで Cantor's Theorem を証明されています。私は個人的には次の Milne 論文がわかりやすかったので、この論文の証明を参考にします。簡潔な証明を望まれるかたは藤田先生の本をご覧ください。なお先生は、全射がないことによっても件の定理が証明できることを、その概略を通して説明されておられます。
*11:ちなみに Milne 論文では単射による Cantor's Theorem の証明が述べられていますが、Rosser 先生の本の該当ページでなされているその定理の証明は、単射ではなく、全射を使ってなされています。
*12:この背理法は直観主義者も許容する、いわば広義の背理法で、肯定文 p を仮定し、矛盾が出れば仮定 p を落として ¬p を結論するものです。
*13:この背理法は直観主義者が許容しない、いわば狭義の背理法で、肯定文 p を証明したい場合、p の否定文 ¬p を仮定し、矛盾が出れば仮定 ¬p を落としてその否定を引き出し ¬¬p、最後にこの二重否定を解いて p を結論するものです。
*14:なお、ここでの概念と概念の外延を、関数などに一般化して語ることも可能ですが、話が長くなるので概念および概念の外延に限定して話を進めます。
*15:概念の外延の集合 N から概念の集合 M へ、単射があるとする証明、すなわち |N| ≦ |M| の証明は省きます。というのも、この証明では、概念の外延が Frege にとって何であったのか、ということを明らかにせねばならず、その用意が私には今ないからです。概念の外延を差し当たり集合 (set) かクラス (class) と見なすのが妥当ですが、それは概念の外延を便宜的に集合またはクラスと同一視するだけであって、本当のところ、概念の外延が何であったのかという問いには答えたことになっていません。それが何であったのかを正確に突き止めなければなりません。しかしそのような探究は結構な仕事になりますので、今は脇に置いておかざるを得ません。いずれにしても、概念の外延の集合 N から概念の集合 M へ、単射があるとする証明の概略は、おそらく次のような感じるなるのではないかと、現在の私は推測しています。天下りにその概略を記します。まず、いかなる概念の外延も概念からできます。故にいかなる概念の外延にも概念が対応します。(Va) の対偶により概念の外延が異なれば、その概念も異なるのであって、概念の外延が異なるのに、その概念が等しくなるということはありません。つまり (Va) の対偶は、概念の外延から概念への写像が単射であることを表しています。よって N から M への単射があります。以上。ただし、この証明概略は間違っているかもしれません。この概略は、詰めて考えた結果ではありません。何となく思ったことを書き留めただけです。ですので、鵜呑みにしないでください。そもそも考え方によっては、概念の外延が何であるかということとは別に、概念の外延から概念へ、単射が存在することを証明することもできるかもしれません。これらの正確な究明は後日に期したいと思います。
*16:前の註でも述べましたが、この背理法は直観主義者も許容する広義の背理法で、p を仮定し、矛盾が出れば仮定 p を落として ¬p を結論するものです。
*17:前の註でも述べましたが、この背理法は直観主義者が許容しない狭義の背理法で、p を証明したい場合、その否定文 ¬p を仮定し、矛盾が出れば仮定 ¬p を落とし、¬¬p を引き出して、この二重否定を解き、p を結論するものです。
*18:この表は、Klement, ''Russell, His Paradoxes, and Cantor's Theorem: Part I,'' pp. 17-19 にある記述と、特にその p. 17 にある表を参考にして作成させてもらいました。
*19:ちなみに今、写像 g は単射であるとしています。もしもそれが単射でないならば、異なる概念 Gi ≠ Gj それぞれが、同じ一つの概念の外延 g(Gn) に g によって写される (g(Gi) = g(Gj) ことを許します。つまり Gi ≠ Gj ならば、g(Gi) = g(Gj) であることも許します。すると、問題の F について、F ≠ Gi でありながら、g(F) = g(Gi) であるような Gi、および g(Gi) があってもよい、ということです。ならば、たとえば F ≠ G5 でありながら g(F) = g(G5) である場合、g(F) 欄と F 行が交わる大きな丸印のマス目には、×を、かつ×だけを記せばすむことになります。なぜなら、g(F) = g(G5) であって、g(G5) 欄と G5 行の交差する対角線上のマス目には○とあるのだから、g(G5) 欄と F 行の交差するマス目、すなわち g(F) 欄とF 行の交差する対角線上の大きな丸印のマス目には、×と記せばよく、これで矛盾は生じません。
