Twierdzenie Frege'a

W metalogii i metamatematyce twierdzenie Frege'a jest metatwierdzeniem , które stwierdza, że ​​aksjomaty arytmetyki Peano można wyprowadzić w logice drugiego rzędu z zasady Hume'a . Zostało to po raz pierwszy udowodnione nieformalnie przez Gottloba Frege'a w jego Die Grundlagen der Arithmetik ( Podstawy arytmetyki ) z 1884 roku, a bardziej formalnie udowodnione w jego Grundgesetze der Arithmetik I ( Podstawowe prawa arytmetyki I) z 1893 roku. Twierdzenie zostało ponownie odkryte przez Crispina Wrighta na początku lat 80. i od tego czasu było przedmiotem znaczących prac. Leży u podstaw filozofii matematyki znanej jako neologizm (przynajmniej odmiany szkoły szkockiej ).

Przegląd

W The Foundations of Arithmetic (1884), a później w Basic Laws of Arithmetic (t. 1, 1893; t. 2, 1903), Frege próbował wyprowadzić wszystkie prawa arytmetyki z aksjomatów, które uważał za logiczne (zob . ). Większość z tych aksjomatów została przeniesiona z jego Begriffsschrift ; jedyną naprawdę nową zasadą była ta, którą nazwał zasadą podstawową V (obecnie znaną jako schemat aksjomatu nieograniczonego zrozumienia ): „zakres wartości” funkcji f ( x ) jest taki sam, jak „zakres wartości” funkcji f ( x ) funkcja g ( x ) wtedy i tylko wtedy, gdy ∀ x [ f ( x ) = g ( x )]. Jednak V Ustawa Zasadnicza nie tylko nie była twierdzeniem logicznym, ale powstały system okazał się niespójny, ponieważ podlegał paradoksowi Russella .

Niekonsekwencja w Grundgesetze Frege'a przyćmiła osiągnięcie Frege'a: według Edwarda Zalty Grundgesetze „zawiera wszystkie istotne kroki ważnego dowodu (w logice drugiego rzędu ) podstawowych twierdzeń arytmetyki z jednej spójnej zasady” . Osiągnięcie to stało się znane jako twierdzenie Fregego.

Twierdzenie Frege'a w logice zdań

(	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		✓	✓	✓
		N			✗			Y		✓	✓	✓		N		✓	✗	✗
		Y			✓			Y		✓	✓	✓		Y		✓	✓	✓
	1	2		3	4	5		6		7	8	9		10		11	12	13

W logice zdań twierdzenie Fregego odnosi się do tej tautologii :

( P → ( P → R )) → ( ( P → Q ) → ( P → R ))

Twierdzenie to zawiera się już w jednej z najsłabszych logik, jakie można sobie wyobrazić, w konstruktywnym rachunku implikacji . Dowód zgodnie z interpretacją Brouwera – Heytinga – Kołmogorowa brzmi ${\ Displaystyle f \ mapsto g \ mapsto p \ mapsto (f (p) \ circ g) ( p)}$ . Słowami: „Niech f oznacza powód, z którego P implikuje, że Q implikuje R. I niech g oznacza powód, z którego P implikuje Q. Następnie biorąc pod uwagę a f , następnie a g , następnie biorąc pod uwagę powód p dla P , wiemy, że oba Q trzyma się g , a Q implikuje, że R trzyma się f . Więc R się trzyma.

Tabela prawdy po prawej stronie daje semantyczny dowód. Dla wszystkich możliwych przypisań false ( ✗ ) lub true ( ✓ ) do P , Q i R (kolumny 1, 3, 5), każda podformuła jest obliczana zgodnie z regułami warunku materialnego , a wynik jest pokazany poniżej jej głównego operatora . Kolumna 6 pokazuje, że cała formuła w każdym przypadku jest prawdziwa , czyli jest tautologią. W rzeczywistości jego poprzednik (kolumna 2) i następnik (kolumna 10) są nawet równoważne.

Notatki

• Gottlob Frege (1884). Die Grundlagen der Arithmetik – eine logisch-mathematische Untersuchung über den Begriff der Zahl (PDF) (w języku niemieckim). Breslau: Verlag von Wilhelm Koebner.
• Gottlob Frege (1893). Grundgesetze der Arithmetik (w języku niemieckim). Tom. 1. Jena: Verlag Hermann Pohle. – Wydanie w notacji współczesnej
• Gottlob Frege (1903). Grundgesetze der Arithmetik (w języku niemieckim). Tom. 2. Jena: Verlag Hermann Pohle. – Wydanie w notacji współczesnej