Теорема Фреге - Frege's theorem

В металогики и метаматематике , теорема Фрега является метатеоремой , что говорится , что Аксиомы Пеаны из арифметики может быть выведено в логике второго порядка от принципа Юма . Впервые это было неформально доказано Готтлобом Фреге в его книге « Die Grundlagen der Arithmetik» ( «Основы арифметики» ) 1884 г. и более формально доказано в его « Grundgesetze der Arithmetik I» 1893 г. (« Основные законы арифметики I»). Теорема была повторно открыта Криспином Райтом в начале 1980-х годов и с тех пор стала предметом значительных исследований. Он лежит в основе философии математики, известной как неологицизм (по крайней мере, из разновидности шотландской школы ).

Обзор

В «Основах арифметики» (1884 г.), а затем в « Основных законах арифметики» (том 1, 1893; том 2, 1903) Фреге попытался вывести все законы арифметики из аксиом, которые он считал логическими (см. Логицизм ). Большинство этих аксиом было заимствовано из его Begriffsschrift ; единственным действительно новым принципом был тот, который он назвал Основным законом V (теперь известным как схема аксиом неограниченного понимания ): «диапазон значений» функции f ( x ) совпадает с «диапазоном значений» функция g ( x ) тогда и только тогда, когда ∀ x [ f ( x ) = g ( x )]. Тем не менее, Основной закон V не только не был логическим утверждением, но и полученная система оказалась непоследовательной, потому что она была подвержена парадоксу Рассела .

Несоответствие в Grundgesetze Фреге затмило достижение Фреге: согласно Эдварду Залте , Grundgesetze «содержит все существенные этапы достоверного доказательства (в логике второго порядка ) фундаментальных положений арифметики из единого непротиворечивого принципа». Это достижение стало известно как теорема Фреге.

Теорема Фреге в логике высказываний

(	п	→	(	Q	→	р	))	→	((	п	→	Q	)	→	(	п	→	р	))
		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

В логике высказываний теоремы Фреге относятся к этой тавтологии :

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

Теорема уже верна в одной из самых слабых логик, которую только можно вообразить, - в конструктивном импликационном исчислении . Доказательство в интерпретации Брауэра – Гейтинга – Колмогорова читается . Словами: «Пусть f обозначает причину, по которой P подразумевает, что Q подразумевает R. И пусть g обозначает причину, по которой P подразумевает Q. Затем дано f , затем дано g , а затем дана причина p для P , мы знаем, что оба Q выполняется по g и что Q влечет R выполняется по f . Значит, R выполняется ". ${\ Displaystyle е \ mapsto g \ mapsto p \ mapsto (f (p) \ circ g) (p)}$

Таблица истинности справа дает семантическое доказательство. Для всех возможных присвоений ложных ( ✗ ) или истинных ( ✓ ) значений P , Q и R (столбцы 1, 3, 5) каждая подформула оценивается в соответствии с правилами для материального условного выражения , результат отображается под основным оператором. . Столбец 6 показывает, что вся формула истинна в каждом случае, т.е. что это тавтология. Фактически, его антецедент (столбец 2) и его следствие (столбец 10) даже эквивалентны.

Ноты

Ссылки

• Готтлоб Фреге (1884). Die Grundlagen der Arithmetik - eine logisch-Mathematische Untersuchung über den Begriff der Zahl (PDF) (на немецком языке). Бреслау: Verlag von Wilhelm Koebner.
• Готтлоб Фреге (1893 г.). Grundgesetze der Arithmetik (на немецком языке). 1 . Йена: Verlag Hermann Pohle.- Издание в современной нотации
• Готтлоб Фреге (1903). Grundgesetze der Arithmetik (на немецком языке). 2 . Йена: Verlag Hermann Pohle.- Издание в современной нотации