Теория (математическая логика)

В математической логике теория на (также называемая формальной теорией ) представляет собой набор предложений формальном языке . В большинстве сценариев дедуктивная система сначала понимается из контекста, после чего элемент $\phi \in T$ дедуктивно закрытой теории $T$ тогда называется теоремой теории. Во многих дедуктивных системах обычно имеется подмножество $\Sigma \subseteq T$ это называется «набором аксиом » теории $T$ , и в этом случае дедуктивную систему еще называют « аксиоматической системой ». По определению каждая аксиома автоматически является теоремой. Теория первого порядка — это набор первого порядка предложений (теорем) , рекурсивно полученных с помощью правил вывода системы, примененных к набору аксиом.

Общие теории (выраженные формальным языком)

При определении теорий для фундаментальных целей необходимо проявлять дополнительную осторожность, поскольку обычный теоретико-множественный язык может оказаться непригодным.

Построение теории начинается с указания определенного непустого концептуального класса. ${\mathcal {E}}$ , элементы которого называются операторами . Эти исходные утверждения часто называют примитивными элементами или элементарными утверждениями теории, чтобы отличить их от других утверждений, которые могут быть на их основе выведены.

Теория ${\mathcal {T}}$ — это концептуальный класс, состоящий из некоторых из этих элементарных утверждений. Элементарные высказывания, принадлежащие ${\mathcal {T}}$ называются элементарными теоремами ${\mathcal {T}}$ и говорят, что это правда . Таким образом, теорию можно рассматривать как способ обозначения подмножества ${\mathcal {E}}$ которые содержат только верные утверждения.

Этот общий способ обозначения теории предполагает, что истинность любого из ее элементарных утверждений неизвестна без ссылки на ${\mathcal {T}}$ . Таким образом, одно и то же элементарное утверждение может быть истинным по отношению к одной теории, но ложным по отношению к другой. Это напоминает случай в обычном языке, когда такие утверждения, как «Он честный человек», не могут быть признаны истинными или ложными без интерпретации того, кем «он» является, и, в этом отношении, что такое «честный человек» согласно этой теории. . ^[1]

Подтеории и расширения

Теория ${\mathcal {S}}$ является подтеорией теории ${\mathcal {T}}$ если ${\mathcal {S}}$ является подмножеством ${\mathcal {T}}$ . Если ${\mathcal {T}}$ является подмножеством ${\mathcal {S}}$ затем ${\mathcal {S}}$ называется расширением или супертеорией ${\mathcal {T}}$

Дедуктивные теории

Теория называется дедуктивной, если ${\mathcal {T}}$ является индуктивным классом , то есть его содержание основано на некоторой формальной дедуктивной системе и что некоторые из его элементарных утверждений принимаются как аксиомы . В дедуктивной теории любое предложение, которое является логическим следствием одной или нескольких аксиом, также является предложением этой теории. ^[1] Более формально, если $\vdash$ в стиле Тарского является отношением следствия , тогда ${\mathcal {T}}$ закрыт под $\vdash$ (и, следовательно, каждая из его теорем является логическим следствием его аксиом) тогда и только тогда, когда для всех предложений $\phi$ на языке теории ${\mathcal {T}}$ , если ${\mathcal {T}}\vdash \phi$ , затем $\phi \in {\mathcal {T}}$ ; или, что то же самое, если ${\mathcal {T}}'$ является конечным подмножеством ${\mathcal {T}}$ (возможно, набор аксиом ${\mathcal {T}}$ в случае конечно аксиоматизируемых теорий) и ${\mathcal {T}}'\vdash \phi$ , затем $\phi \in {\mathcal {T}}'$ , и поэтому $\phi \in {\mathcal {T}}$ .

Последовательность и полнота

Синтаксически непротиворечивая теория — это теория, из которой не каждое предложение основного языка может быть доказано (относительно некоторой дедуктивной системы , которая обычно ясна из контекста). В дедуктивной системе (такой как логика первого порядка), которая удовлетворяет принципу взрыва , это эквивалентно требованию, чтобы не существовало предложения φ такого, что и φ, и его отрицание могут быть доказаны с помощью теории.

Выполнимая теория — это теория, имеющая модель . Это означает, что существует структура M , которая удовлетворяет каждому предложению теории. Любая выполнимая теория синтаксически непротиворечива, потому что структура, удовлетворяющая теории, будет удовлетворять ровно одному из φ и отрицанию φ для каждого предложения φ.

Непротиворечивая теория иногда определяется как синтаксически непротиворечивая теория, а иногда определяется как выполнимая теория. Для логики первого порядка следует , наиболее важного случая, из теоремы о полноте , что оба значения совпадают. ^[2] В других логиках, таких как логика второго порядка , существуют синтаксически непротиворечивые теории, которые невыполнимы, например, ω-несогласованные теории .

Полная непротиворечивая теория (или просто полная теория ) — это непротиворечивая теория. ${\mathcal {T}}$ такой, что для каждого предложения φ на его языке либо φ доказуемо из ${\mathcal {T}}$ или ${\mathcal {T}}$ $\cup$ {φ} противоречиво. Для теорий, замкнутых с точки зрения логического следствия, это означает, что для каждого предложения φ в теории содержится либо φ, либо его отрицание. ^[3] Неполная теория — это непротиворечивая теория, которая не является полной.

( см. также в ω-согласованной теории более сильное понятие непротиворечивости .)

Интерпретация теории

Интерпретация теории - это связь между теорией и некоторым предметом изучения, когда существует соответствие «многие к одному» между определенными элементарными утверждениями теории и определенными утверждениями, относящимися к предмету. Если каждое элементарное утверждение в теории имеет корреспондента, это называется полной интерпретацией , в противном случае — частичной интерпретацией . ^[4]

Теории, связанные со структурой

Каждая структура имеет несколько связанных теорий. Полная теория структуры A — это набор всех первого порядка предложений над сигнатурой A , удовлетворяет A. которым Он обозначается Th( A ). В более общем смысле, теория K первого порядка, которым , класс σ-структур, представляет собой набор всех σ-предложений удовлетворяют все структуры в K , и обозначается Th( K ). Очевидно, Th( A ) = Th({ A }). Эти понятия также могут быть определены по отношению к другим логикам.

Для каждой σ-структуры A существует несколько связанных теорий в большей сигнатуре σ', которая расширяет σ путем добавления одного нового постоянного символа для каждого элемента области A. определения (Если новые постоянные символы отождествляются с элементами A , которые они представляют, σ' можно принять равным σ $\cup$ А.) Мощность σ', таким образом, является большей из мощности σ и мощности A . ^{[ нужны дальнейшие объяснения ]}

Диаграмма , A атомарных или отрицательных атомарных σ'-предложений , которым удовлетворяет A и обозначается Diag _A. состоит из всех Позитивная диаграмма A A — это множество всех атомарных σ'-предложений, которым удовлетворяет . Обозначается диаг. ⁺_А. Элементарной диаграммой A , является множество eldiag _A всех , или, что то же самое -предложений первого порядка, которым удовлетворяет A полная (первого порядка) теория естественного расширения A σ' до сигнатуры σ'.

Теории первого порядка

Теория первого порядка ${\mathcal {QS}}$ это набор предложений формального языка первого порядка. ${\mathcal {Q}}$ .

Вывод в теории первого порядка

Существует множество формальных систем вывода («доказательств») логики первого порядка. К ним относятся дедуктивные системы в стиле Гильберта , естественная дедукция , секвенциальное исчисление , табличный метод и резолюция .

Синтаксическое следствие в теории первого порядка

Формула . A является синтаксическим следствием теории первого порядка ${\mathcal {QS}}$ если существует вывод A с использованием только формул из ${\mathcal {QS}}$ как нелогические аксиомы. Такую формулу А еще называют теоремой ${\mathcal {QS}}$ . Обозначение " ${\mathcal {QS}}\vdash A$ " указывает на то, что A является теоремой ${\mathcal {QS}}$ .

Интерпретация теории первого порядка

Интерпретация теории первого порядка обеспечивает семантику формул теории. Говорят, что интерпретация удовлетворяет формуле, если формула истинна в соответствии с интерпретацией. Модель теории первого порядка ${\mathcal {QS}}$ представляет собой интерпретацию, в которой каждая формула ${\mathcal {QS}}$ удовлетворен.

Теории первого порядка с тождеством

Теория первого порядка ${\mathcal {QS}}$ является теорией первого порядка с тождеством, если ${\mathcal {QS}}$ включает символ тождественного отношения "=" и схемы аксиом рефлексивности и замены для этого символа.

Темы, связанные с теориями первого порядка

Примеры

Один из способов конкретизировать теорию — определить набор аксиом на определенном языке. По желанию теория может включать только те аксиомы или их логические или доказуемые следствия. Теории, полученные таким способом, включают ZFC и арифметику Пеано .

Второй способ определить теорию — начать со структуры , и пусть теория будет набором предложений, которым удовлетворяет структура. Это метод создания полных теорий с помощью семантического пути с примерами, включающими набор истинных предложений в структуре ( N , +, ×, 0, 1, =), где N — набор натуральных чисел, и набор истинных предложений по структуре ( R , +, ×, 0, 1, =), где R — множество действительных чисел. Первую из них, называемую теорией истинной арифметики , нельзя записать как совокупность логических следствий какого-либо перечислимого множества аксиом. теория ( R Тарский показал, что , +, ×, 0, 1, =) разрешима ; это теория вещественных замкнутых полей ( см. Разрешимость теорий действительных чисел первого порядка подробнее ).

См. также

Ссылки

^ Jump up to: ^а ^б Хаскелл Карри , Основы математической логики , 2010.
^ Вайс, Уильям; Д'Мелло, Шери (2015). «Основы теории моделей» (PDF) . Университет Торонто — математический факультет .
^ «Полнота (в логике) — Математическая энциклопедия» . www.энциклопедияofmath.org . Проверено 1 ноября 2019 г.
^ Хаскелл Карри (1963). Основы математической логики . Макгроу Хилл. Здесь: стр.48

Дальнейшее чтение

Ходжес, Уилфрид (1997). Более короткая модель теории . Издательство Кембриджского университета . ISBN 0-521-58713-1 .

[curry-1] Jump up to: ^а ^б Хаскелл Карри , Основы математической логики , 2010.

[2] Вайс, Уильям; Д'Мелло, Шери (2015). «Основы теории моделей» (PDF) . Университет Торонто — математический факультет .

[3] «Полнота (в логике) — Математическая энциклопедия» . www.энциклопедияofmath.org . Проверено 1 ноября 2019 г.

[4] Хаскелл Карри (1963). Основы математической логики . Макгроу Хилл. Здесь: стр.48

[1]

[2]

[3]

[4]