WikiSort.ru - Не сортированное

В математической логике теория называется полной, если любая синтаксически корректная замкнутая формула или ее отрицание доказуемы в данной теории^[1]. Если же существует замкнутая формула ${\displaystyle \varphi }$ такая, что ни ${\displaystyle \varphi }$ , ни отрицание ${\displaystyle \varphi }$ не доказуемы в теории ${\displaystyle T}$ , то такая теория называется неполной. Замкнутость формулы означает, что она не содержит внешних параметров, а синтаксическая корректность означает соответствие правилам формального языка теории. Под доказуемостью формулы понимается существование последовательности формальных утверждений, каждое из которых либо является аксиомой теории, либо получается по формальным правилам вывода из предыдущих утверждений, причём последнее утверждение в последовательности совпадает с доказываемой формулой.

Неформально говоря, теория полна, если любое корректно сформулированное утверждение в ней можно доказать или опровергнуть. Так, в классической логике любая противоречивая теория очевидным образом полна, так как любая формула в ней выводится вместе со своим отрицанием. Из знаменитой теоремы Гёделя о неполноте следует, что всякая достаточно сильная рекурсивно аксиоматизируемая непротиворечивая теория первого порядка неполна. В частности, таковой является арифметика Пеано — теория, описывающая привычные свойства натуральных чисел со сложением и умножением.

Не следует путать введенное выше понятие полноты теории с понятием полноты логики, означающим, что в любой теории этой логики все общезначимые формулы окажутся выводимыми из аксиом логики. Например, теорема Гёделя о полноте утверждает, что классическая логика первого порядка полна. Это значит, что в любой теории первого порядка любая тождественно истинная формула (то есть истинная независимо от интерпретации сигнатуры и от значений переменных) будет выводима.

Примеры полных теорий

• Исчисление высказываний второго порядка^[en].
• Система аксиом Тарского для евклидовой геометрии.
• Арифметика Пресбургера — теория, описывающая натуральные числа со сложением, но без умножения.
• Теория рациональных чисел с отношением порядка и сложением.
• Теория вещественно замкнутых полей. В частности, теория действительных чисел со сложением, умножением и отношением порядка (теорема Тарского — Зайденберга).
• Теория плотных линейно упорядоченных множеств без первого и последнего элемента.

Примеры теорий, не являющихся полными

Интуитивно ясно, что наиболее общие теории, такие как, например, теория групп, теория линейно упорядоченных множеств, не должны быть полными: иначе это означало бы, что для всех групп или для всех линейно упорядоченных множеств истинны одни и те же замкнутые формулы. Очевидно, что это не так.

• Формальная арифметика со сложением и умножением натуральных чисел. Нетривиальный пример утверждения, записываемого на языке этой теории и недоказуемого в ней, — теорема о последовательностях Гудстейна.
• Теория полугрупп с умножением, содержащая аксиому ассоциативности.
• Теория групп с аксиомами ассоциативности, существования нейтрального и обратного элемента.
• Теория равенства, содержащая единственный предикат равенства и аксиомы равенства.

См. также

• Критерий Лося — Воота
• Непротиворечивая теория
• Разрешимая теория

Примечания

Литература

• Верещагин Н. К. , Шень А. Лекции по математической логике и теории алгоритмов. Часть 2: Языки и исчисления, М.: МЦНМО, 2012.
• Гильберт Д., Аккерман В. Основы теоретической логики. — М.: URSS, 2010. — 304 с. — ISBN 978-5-484-01144-5.
• Карри, Хаскелл Б. Основания математической логики. — М.: Мир, 1969. — 567 с.
• Клини С. К. Введение в метаматематику. — М.: Изд-во иностранной литературы, 1957. — 526 с.
• Линдон Р. Заметки по логике. — М.: Мир, 1968. — 128 с.