Теорема Фреге
Метатеорема

В металогике и метаматематике теорема Фреге — это метатеорема , утверждающая, что аксиомы Пеано арифметики могут быть выведены в логике второго порядка из принципа Юма . Впервые она была доказана неформально Готтлобом Фреге в его работе 1884 года « Основы арифметики » [ 1] и доказана более формально в его работе 1893 года « Основные законы арифметики I » . [2] Теорема была заново открыта Криспином Райтом в начале 1980-х годов и с тех пор находится в центре внимания значительной работы. Она лежит в основе философии математики , известной как неологизм (по крайней мере, в разновидности шотландской школы ).

Обзор

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

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

Теорема Фреге в пропозициональной логике

(П→(В→Р))→((П→В)→(П→Р))
НетЗеленая галочкаИНет✓НетЗеленая галочкаИ✗✓✗Зеленая галочкаИ✗✓✗
НетЗеленая галочкаИНет✓ДаЗеленая галочкаИ✗✓✗Зеленая галочкаИ✗✓✓
НетЗеленая галочкаИДа✗НетЗеленая галочкаИ✗✓✓Зеленая галочкаИ✗✓✗
НетЗеленая галочкаИДа✓ДаЗеленая галочкаИ✗✓✓Зеленая галочкаИ✗✓✓
ДаЗеленая галочкаИНет✓НетЗеленая галочкаИ✓✗✗Зеленая галочкаИ✓✗✗
ДаЗеленая галочкаИНет✓ДаЗеленая галочкаИ✓✗✗Зеленая галочкаИ✓✓✓
ДаКрасный ХНДа✗НетЗеленая галочкаИ✓✓✓Красный ХН✓✗✗
ДаЗеленая галочкаИДа✓ДаЗеленая галочкаИ✓✓✓Зеленая галочкаИ✓✓✓
12345678910111213

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

( П → ( Q → Р )) → (( П → Р ) → ( П → Р ))

Теорема уже выполняется в одной из самых слабых логик, которые только можно себе представить, конструктивном импликационном исчислении . Доказательство в интерпретации Брауэра–Гейтинга–Колмогорова гласит : . Другими словами: «Пусть 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) даже эквивалентны.

Примечания

  1. ^ Готтлоб Фреге , Die Grundlagen der Arithmetik , Бреслау: Verlag von Wilhelm Koebner, 1884, §63.
  2. ^ ab Gottlob Frege , Grundgesetze der Arithmetik I, Йена: Verlag Hermann Pohle, 1893, §§20 и 47.
  3. ↑ Ричард Петтигрю, «Основная теория множеств», 26 января 2012 г., стр. 2.
  4. ^ abc Zalta, Edward (2013), «Теорема Фреге и основы арифметики», Стэнфордская энциклопедия философии.
  5. ^ Булос, Джордж (1998). Логика, логика и логика . Под редакцией Ричарда К. Джеффри, введение Джона П. Берджесса. Кембридж, Массачусетс: Издательство Гарвардского университета. стр. 154. ISBN 9780674537675OCLC  37509971. Поразительное открытие Фреге, о котором он мог или не мог полностью знать и которое было потеряно из виду после открытия парадокса Рассела, состояло в том, что арифметика может быть выведена в чисто логической системе, подобной системе его Begriffsschrift, из этого последовательного принципа и только из него.

Ссылки

  • Готтлоб Фреге (1884). Die Grundlagen der Arithmetik – eine logisch-mathematische Untersuruchung über den Begriff der Zahl (PDF) (на немецком языке). Бреслау: Verlag фон Вильгельма Кебнера.
  • Готтлоб Фреге (1893). Grundgesetze der Arithmetik (на немецком языке). Том. 1. Йена: Верлаг Герман Поле.– Архивное издание 2016-10-21 на Wayback Machine в современной нотации
  • Готтлоб Фреге (1903). Grundgesetze der Arithmetik (на немецком языке). Том. 2. Йена: Верлаг Герман Поле.– Архивное издание 2017-08-29 на Wayback Machine в современной нотации
Взято с "https://en.wikipedia.org/w/index.php?title=Frege%27s_theorem&oldid=1251030939"