フレーゲの定理とは？わかりやすく解説

フレーゲの定理(Frege's theorem)とは、算術の公理（ペアノの公理）は二階述語論理においてヒュームの原理から演繹できるとする定理のこと。ゴットロープ・フレーゲによって最初1884年刊行の『算術の基礎』(Die Grundlagen der Arithmetik)^[1]において略式で証明され、さらに1893年と1903年に出版された2巻本『算術の基本法則』(Grundgesetze der Arithmetik)^[2]において正確に証明された。フレーゲの定理は1980年代前半にクリスピン・ライトによって再発見され、重要な研究主題となっている。新論理主義(neo-logicism)の名で知られる数学の哲学の考え方の核心である。

概要

『算術の基礎』及びその後の『算術の基本法則』（第一巻1893、第二巻1903年）のなかでフレーゲは論理的であると断言できる公理から全ての算術法則を導くことを試みた（論理主義 (数学)を見よ）。公理のうちほとんどは彼の『概念記法』から引き継いでいるが、一つ全く新しい法則として原理Ⅴ^[2]とよばれる原則（今日では分出公理#無制限の内包公理として知られるもの）^[3]つまり、関数 $f(x)$ Y ✓ Y ✗ ✓ ✗ Y ✗ ✓ ✗ Y ✓ Y ✗ ✓ ✗ Y ✗ ✓ ✓ Y ✗ Y ✗ ✓ ✓ Y ✗ ✓ ✗ Y ✓ Y ✗ ✓ ✓ Y ✗ ✓ ✓ Y ✓ Y ✓ ✗ ✗ Y ✓ ✗ ✗ Y ✓ Y ✓ ✗ ✗ Y ✓ ✓ ✓ ✗ ✗ Y ✓ ✓ ✓ ✗ ✓ ✗ ✗ Y ✓ Y ✓ ✓ ✓ Y ✓ ✓ ✓ 1 2 3 4 5 6 7 8 9 10 11 12 13

命題論理では、フレーゲの定理はこの恒真式が参照される:

{\big (}P\to (Q\to R){\big )}\to {\big (}(P\to Q)\to (P\to R){\big )}

この定理はすでに想像しうる最も弱い論理の一つに含まれる構成的な含意論理（implicational calculus）を示している。BHK(Brower-Heyting-Kolmogorov)解釈における証明では $f\mapsto g\mapsto p\mapsto (f(p)\circ g)(p)$ と解釈される。言葉にすれば:「 $f$ は $P$ ならば『 $Q$ ならば $R$ 』である証拠を示しているとする。さらに $g$ は $P$ ならば $Q$ である証拠を示しているとする。このとき、 $f,g$ そして $P$ の証拠として $p$ が与えられたとすると、我々は $g$ によって $Q$ が判断され、 $f$ によって $Q$ ならば $R$ が判断されることをどちらも知っている。したがって、 $R$ が判断される」となる。

右に示した真理値表は意味論的な証明を与えている。 $P,Q$ そして $R$ に対して可能なすべての偽(✗)または真(✓)の割り当て（列1,3,5）に対し、各々の部分式は論理包含の規則にしたがって評価され、その結果が主要な演算子の下に示されている。列6は全体の論理式がいかなる場合も真であることを示している。実際、論理式の前提（列2）とその結果（列10）はまったく等しい。

特別な場合

ふつうは $\neg P$ を $P\to \bot$ という意味として取る。ここで $\bot$ は偽の命題を意味するとする。 $R$ を $\bot$ とすると、フレーゲの定理は否定導入の原則のカリー化された形式を意味する。

{\big (}(P\to \neg Q{\big )}\land (P\to Q){\big )}\to \neg P

脚注

^ Gottlob Frege, Die Grundlagen der Arithmetik, Breslau: Verlag von Wilhelm Koebner, 1884, §63.
^ ^a ^b Gottlob Frege, Grundgesetze der Arithmetik I, Jena: Verlag Hermann Pohle, 1893, §§20 and 47.
^ Richard Pettigrew, "Basic set theory", January 26, 2012, p. 2.
^ ^a ^b Zalta, Edward (2013), “Frege's Theorem and Foundations for Arithmetic”, Stanford Encyclopedia of Philosophy .
^ Boolos, George (1998). Logic, Logic, and Logic. Edited by Richard C. Jeffrey, introduction by John P. Burgess. Cambridge, Mass: Harvard University Press. p. 154. ISBN 9780674537675. OCLC 37509971. "Frege's startling discovery, of which he may or may not have been fully aware and which has been lost to view since the discovery of Russell's paradox, was that arithmetic can be derived in a purely logical system like that of his Begriffsschrift from this consistent principle and from it alone."

参考文献

Gottlob Frege (1884) (German). Die Grundlagen der Arithmetik – eine logisch-mathematische Untersuchung über den Begriff der Zahl. Breslau: Verlag von Wilhelm Koebner
Gottlob Frege (1893) (German). Grundgesetze der Arithmetik. 1. Jena: Verlag Hermann Pohle – Edition Archived 2016-10-21 at the Wayback Machine. in modern notation
Gottlob Frege (1903) (German). Grundgesetze der Arithmetik. 2. Jena: Verlag Hermann Pohle – Edition Archived 2017-08-29 at the Wayback Machine. in modern notation

[:0-1] Gottlob Frege, Die Grundlagen der Arithmetik, Breslau: Verlag von Wilhelm Koebner, 1884, §63.

[:1-2] Gottlob Frege, Grundgesetze der Arithmetik I, Jena: Verlag Hermann Pohle, 1893, §§20 and 47.

[3] Richard Pettigrew, "Basic set theory", January 26, 2012, p. 2.

[Zalta-4] Zalta, Edward (2013), “Frege's Theorem and Foundations for Arithmetic”, Stanford Encyclopedia of Philosophy .

[5] Boolos, George (1998). Logic, Logic, and Logic. Edited by Richard C. Jeffrey, introduction by John P. Burgess. Cambridge, Mass: Harvard University Press. p. 154. ISBN 9780674537675. OCLC 37509971. "Frege's startling discovery, of which he may or may not have been fully aware and which has been lost to view since the discovery of Russell's paradox, was that arithmetic can be derived in a purely logical system like that of his Begriffsschrift from this consistent principle and from it alone."

[1]

[2]

[3]

フレーゲの定理とは？ わかりやすく解説