Математическая логика
Математическая логика и символическая логика (устаревший и материально - технический ) является филиалом математики , в частности , в качестве метода меты-математики и применения современной формальной логики . Часто он снова делится на подобласти теории моделей , теории доказательств , теории множеств и теории рекурсии . Исследования в области математической логики способствовали изучению основ математики и были мотивированы этим. В результате ее стали называть метаматематикой .
Одним из аспектов изучения математической логики является изучение выразительности формальных логик и формальных систем доказательства . Один из способов измерить сложность таких систем - определить, что они могут доказать или определить.
история
Термин математическая логика использовался Джузеппе Пеано для символической логики. В классическом варианте это сопоставимо с логикой Аристотеля , но формулируется с помощью символов, а не естественного языка . Математики с философским образованием, такие как Лейбниц или Ламберт , на раннем этапе пытались рассматривать операции формальной логики, используя символический или алгебраический подход, но их работа оставалась в значительной степени изолированной и неизвестной. В середине XIX века Джордж Буль и Август де Морган представили систематический взгляд на логику. Традиционное аристотелевское учение логики было реформировано и дополнено, и оно стало адекватным инструментом для изучения основ математики . Было бы ошибкой утверждать, что все фундаментальные противоречия с 1900 по 1925 год были разрешены, но философия математики в значительной степени прояснилась с помощью новой логики.
В то время как греческое развитие логики уделяло большое внимание формам аргументации, сегодняшнюю математическую логику можно описать как комбинаторное изучение содержания . Сюда входят как синтаксические (исследование формальных символьных строк как таковых), так и семантические (присвоение таким символьным строкам значения).
Исторически важные публикации являются концептуальные письма от Фреге , Исследования в области логики под редакцией Чарльза Сандерса Пирса , Principia Mathematica по Бертран Рассел и Альфред Норт Уайтхед и по сравнению с формально неразрешимой теоремы о Principia Mathematica и родственных систем I от Курта Гёделя .
Формальная логика
Математическая логика часто связана с математическими концепциями, которые выражаются через формальные логические системы. Система логики предикатов первого порядка получила наибольшее распространение как из-за ее применимости в области основ математики, так и из-за ее свойств, таких как полнота и правильность . Также изучаются логика высказываний , более сильные классические логики, такие как исчисление предикатов второй или неклассические логики, такие как интуиционистская логика .
Подразделы математической логики
Справочник по математической логике (1977) делит математическую логику в следующих четырех областях:
- Теория множеств - это изучение множеств , которые представляют собой абстрактные совокупности объектов. В то время как простые понятия, такие как подмножество, часторассматриваютсяв области наивной теории множеств , современные исследования работают в области аксиоматической теории множеств , которая использует логические методы для определения того, какие математические утверждения содержатся в различных формальных теориях, таких как теория Цермело-Френкеля. Теория множеств (ZFC) или Новые основы доказуемы.
- Теория доказательств - это изучение формальных доказательств и различных систем логического вывода. Доказательства представлены в виде математических объектов, чтобы их можно было исследовать с помощью математических методов. Фреге занимался математическими доказательствами и формализовал понятие доказательства.
- Теория моделей - это изучение моделей из формальных теорий. Совокупность всех моделей определенной теории называется « элементарным классом ». Классическая теория моделей пытается определить свойства моделей определенного элементарного класса или то, являются ли определенные классы структур элементарными. Метод исключения кванторов используется, чтобы показать, что модели некоторых теорий не могут быть слишком сложными.
- Теория рекурсии , также называемая теорией вычислимости , - это изучение вычислимых функций и степеней Тьюринга , которые классифицируют невычислимые функции в соответствии со степенью их невычислимости. Кроме того, теория рекурсии также включает изучение обобщенной предсказуемости и определимости.
Границы между этими областями, а также между математической логикой и другими областями математики не всегда точно определены. Например, теорема Гёделя о неполноте не только имеет первостепенное значение в теории рекурсии и теории доказательств, но также привела к теореме Лёба , которая важна для модальной логики . Теория категорий использует множество формальных аксиоматических методов, которые очень похожи на методы математической логики. Однако теория категорий обычно не рассматривается как часть математической логики.
Связь с информатикой
Между математической логикой и информатикой существует много связей . Многие пионеры информатики, такие как Алан Тьюринг , сформировали эту дисциплину как математики и логики. Части математической логики рассматриваются в области теоретической информатики . Описательная теория сложности в частности , создает тесную связь между математической логикой и теорией сложности рассматривается в теоретической информатике .
Важные результаты
- Теорема Löwenheim-Skolem (1919) утверждает , что теория в счетном первом порядок языке , который имеет бесконечную модель имеет модели любой бесконечной мощности.
- Полнота теорема (1929) (фон Гедель ) показала эквивалентность семантического и синтаксического логический вывода в классической логике предикатов первого уровня.
- Теорема о неполноте (1931 г.) (фон Гёдель) показала, что никакая достаточно сильная формальная система не может доказать свою непротиворечивость.
- Алгоритмическая неразрешимость проблемы принятия решений , независимо открытая Аланом Тьюрингом и Алонзо Черчем в 1936 году, показала, что не существует компьютерной программы, которая правильно решает, истинно ли какое-либо математическое утверждение.
- Независимость гипотезы континуума от ZFC показала, что как доказательство, так и опровержение гипотезы невозможны. Тот факт, что ZFC согласован вместе с гипотезой континуума, если ZFC согласован, был продемонстрирован Гёделем в 1940 году. Тот факт, что отрицание гипотезы континуума также согласуется с ZFC (если ZFC согласован), был доказан Полом Коэном в 1963 году .
- Алгоритмическая неразрешимость десятой проблемы Гильберта была показана в 1970 году Юрием Матиясевичем . Он доказал, что не существует компьютерной программы, которая правильно решает, есть ли у многочлена целые нули от нескольких переменных с целыми коэффициентами.
литература
- Джон Барвайз (ред.): Справочник по математической логике. 1977, ISBN 0-444-86388-5 .
- Х.-Д. Эббингауз, Дж. Флум, В. Томас: Введение в математическую логику. 5-е издание. Spectrum Academic Publishing House, 2007, ISBN 3-8274-1691-4 .
- Вольфганг Раутенберг : Введение в математическую логику . 3. Издание. Vieweg + Teubner, Висбаден 2008 г., ISBN 978-3-8348-0578-2 .