フレーゲの定理

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

概要

『算術の基礎』及びその後の『算術の基本法則』（第一巻1893、第二巻1903年）のなかでフレーゲは論理的であると断言できる公理から全ての算術法則を導くことを試みた（論理主義 (数学)を見よ）。公理のうちほとんどは彼の『概念記法』から引き継いでいるが、一つ全く新しい法則として原理Ⅴ^[2]とよばれる原則 （今日では分出公理#無制限の内包公理として知られるもの）^[3]つまり、関数${\displaystyle f(x)}$の値域と${\displaystyle g(x)}$の値域が等しいことは${\displaystyle \forall x[f(x)=g(x)]}$であることの必要十分条件であるという原則があった。 しかし、原理Ⅴは論理命題として成立しないばかりか、ラッセルのパラドックスに従うために、結果として生ずるシステムが矛盾していることが示された。^[4]

フレーゲの基本法則の矛盾性は彼の功績に影を落としていた。が、エドワード・ザルタによれば、基本法則は「一つの無矛盾な算術の基本命題の（二階述語論理における）正当な証明のすべての重要な段階を含んでいる」と述べた。^[4]この功績が「フレーゲの定理」として知られるようになった。^[5]

命題論理におけるフレーゲの定理

(	P	→	(	Q	→	R	))	→	((	P	→	Q	)	→	(	P	→	R	))
		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

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

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

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

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

特別な場合

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

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