В.А. Успенский - Курс лекций по математической логике, страница 4

Поскольку в хороших множествах нет наибольшего элемента, формула∃ z (ξ ≻ z)& . . . &(ξn ≻ z) тождественно истинна.z Формула имеет вид ∃ z (ξ1 ≺ z)& . . . &(ξn ≺ z) & (η1 ≻ z)& . . . &(ηm ≻ z) . Вдумаемся в то, что означает этаформула. Видно, что в ней спрашивается, найдётся ли число z, строго большее чисел ξ1 , . . . , ξn и строго меньшеечисел η1 , . . .

, ηm . Если пересечение всех интервалов вида (ξi , ηj ) непусто, то, в силу плотности множества M,такое z найдётся, в противном случае — заведомо не найдётся. Итак, получаем, что в этом случае формулаэквивалентна бескванторной формуле(ξi ≺ ηj ).&i,jТаким образом, первый этап полностью разобран.2◦ Пусть A имеет вид ∃ z(A1 ∨ . . . ∨ As ), где каждая из As — конъюнкция атомарных формул.

Протащимквантор внутрь через дизъюнкцию, получим формулу ( ∃ z A1 ) ∨ . . . ∨ ( ∃ z As ) и применим к каждой из формул∃ z Ai правила этапа 1◦ .3◦ Пусть A имеет вид ∃ zB, где B — произвольная бескванторная формула. Приведём B к нормальнойформе, тогда отрицания будут стоять при атомарных формулах. После этого уничтожим отрицания, используяследующие правила:z ξ = η ≡ (ξ ≺ η) ∨ (ξ ≻ η).z ξ ≺ η ≡ (ξ = η) ∨ (ξ ≻ η).z ξ ≻ η ≡ (ξ = η) ∨ (ξ ≺ η).После уничтожения отрицаний остаётся перейти к этапу 2◦ .4◦ Пусть A не содержит квантора ∀ , но содержит кванторы существования. Поскольку их конечное число,найдём среди них самый внутренний, т.

е. такой, который не захватывает в свою область действия других кванторов существования. К этому квантору можно применить этап 3◦ , после чего количество кванторов уменьшитсяна единицу. Осталось повторить этот процесс столько раз, сколько кванторов в нашей формуле.5◦ Пусть A — произвольная формула. Уничтожим все кванторы существования по правилу ∀ z C ≡ ∃ z C,после чего можно переходить к этапу 4◦ . Замечание. Другое доказательство этой теоремы можно прочесть в [3, стр.

115 – 117].Замечание. В формулировке теоремы присутствовало выражение «эффективно построить». Это означает,что существует алгоритм построения. Взглянув ещё раз на доказательство, легко убедиться в том, что приведение формулы к бескванторному виду можно запрограммировать, например, на C++.Следствие 1.5. Все хорошие множества элементарно эквивалентны, т. е. не существует замкнутойформулы в нашем языке упорядоченных множеств, которая была бы тождественно истинной на одном хорошем множестве и тождественно ложна на другом.

Рассмотрим замкнутую формулу A и уничтожим в ней кванторы, используя предыдущую теорему.Получим эквивалентную ей бескванторную замкнутую формулу. Она может быть либо тождественно истинной,либо тождественно ложной. Но приведение к бескванторному виду не зависит от множества. 1.3. Неэлементарные языки первого порядка1.3.1. ПредикатыПусть M — некоторое множество.Определение. Функция вида P : Mk → B называется k-местным предикатом на множестве M. Число kназывается валентностью предиката2 . Множество k-местных предикатов обозначается P (k) .Определение.

Одноместные предикаты называют свойствами, двуместные — бинарными отношениями.2 Иногдаиспользуется термин «арность», происходящий от английского arity — количество аргументов. — Прим. наб.11Поясним, откуда берётся такая терминология. Пусть P — одноместный предикат, рассмотрим множествоA := P −1 (1).

Будем говорить, что элемент x множества M обладает свойством P , если x ∈ A, т. е. если P (x) = 1.Разумеется, верно и обратное: если A ⊂ M, то можно рассмотреть предикат «x ∈ A?», определённый вполнеестественным образом:(1, x ∈ A;P (x) =0, x ∈/ A.Таким образом, между одноместными предикатами и множеством 2M установлено взаимно однозначное соответствие.Аналогично, полный прообраз истины для двуместного предиката выделит некоторое подмножество в M ×× M, поэтому можно говорить о бинарном отношении R := P −1 (1), задаваемом двуместным предикатом.Очевидно, обратное также верно, поэтому между бинарными отношениями и двуместными предикатами такжеимеется биекция.Таким образом, предикаты — это в каком-то смысле обобщение понятий свойств и отношений. Следующий пример показывает, что введение предикатных переменных в язык упорядоченных множеств позволяетпостроить формулу, различающую R и Q, хотя, как мы уже доказали, в элементарном языке такой формулыне существует.Пример 3.1.

Формулаhi∀ P ∀ x ∀ y P (x)&P (y) ⇒ x < y ⇒ ∃ z ∀ x ∀ y P (x) ⇒ x 6 z & P (y) ⇒ z 6 yистинна в R и ложна в Q. Здесь x, y, z ∈ M, a P ∈ P (1) . Левая часть этой формулы выделяет из всех подмножеств множества (или, что то же самое, из всех предикатов) те, которые задают левые классы.

Праваячасть говорит, что либо в левом классе существует наибольший элемент, либо в правом существует наимень√ший. Для R это свойствоверно, а для Q — нет: достаточно в качестве предиката взять, например, «x < 2».√Конечно, вместо 2 можно было бы взять любое другое иррациональное число.1.3.2. Общее определение языка первого порядкаКак обычно, начнём с примера, предваряющего длинное общее определение.Пример 3.2. Построим язык теории групп. Рассмотрим группу (G, ◦). В этом языке есть одно выделенноеимя — единица группы.

Обозначим её через e. Кроме основной операции ◦, есть ещё унарная операция −1 взятияобратного элемента.Определение. Определим терм теории групп следующим образом:• Единица e, а также все переменные x, y, . . . , x1 , y1 , . . . — термы.• Если t — терм, то (t−1 ) — тоже терм.• Если t, s — термы, то (t ◦ s) — тоже терм.Если t, s — термы, то (t = s) — атомная формула.

Формулы строятся из атомных формул тем же правилам,что и для языка упорядоченных множеств.Определение. Пусть задано некоторое множество M, которое мы в дальнейшем будем называть носителем. Будем говорить, что задан язык первого порядка, если заданы списки индивидных функциональных ипредикатных имён. При этом каждому функциональному и предикатному символу должна быть приписана еговалентность. Множество функциональных k-местных символов мы будем обозначать F (k) .Пример 3.3.Категория имёнИндивидные именаФункциональные именаПредикатные именаЯзык упорядоченных множеств∅∅«<»Язык теории групп«e»«◦», «−1 »∅Термы и атомные формулы языка строятся следующим образом:•••••Любое индивидное имя есть терм.Любая индивидная переменная есть терм.Если f (k) — функциональное имя валентности k, а t1 , .

. . , tk — термы, то f (t1 , . . . , tk ) — терм.Если P (k) — предикатное имя валентности k, а t1 , . . . , tk — термы, то P (t1 , . . . , tk ) — атомная формула.Если t, s — термы, то (t = s) — атомная формула.12Формулы строятся из атомных формул тем же правилам, что и для языка упорядоченных множеств.Замечание. Имя, константа, символ — это одно и то же.

Область значения индивидных переменных —обязательно носитель.Ранее мы уже давали определение элементарного языка. Настало время его уточнить.Определение. Язык называется элементарным, если в нём есть только индивидные переменные. В противном случае язык называется неэлементарным.Приведём несколько полезных примеров неэлементарных формул.Пример 3.4. Формула, ложная на всех множествах, в которых менее, чем n элементов:αn ≖ ∃ x1 . .

. ∃ xn(xi = xj ).&i6=jЗадача 1.12. Постройте формулу, истинную только на n-элементном множестве.Пример 3.5. Формула, истинная на любом бесконечном множестве:hii h.β ≖ ∃ ϕ ∀ x ∀ y ϕ(x) = ϕ(y) ⇒ x = y & ∃ z ∃ x ϕ(x) = zЗдесь ϕ ∈ F (1) . Эта формула говорит, что на данном множестве существует инъекция, не являющаяся при этомбиекцией.Мы уже видели на примере формулы, различающей Q и R, что «возможности» неэлементарных языковзначительно шире. Чтобы ещё больше подчеркнуть это различие, приведём без доказательства теорему, вернуютолько для элементарных языков:Теорема 1.9 (О компактности элементарных языков первого порядка).

Если есть список элементарных формул, каждая из конечных подсистем которого имеет модель, то и весь список имеет модель.Скажем, что список формул имеет модель3 , если найдётся носитель, на котором все эти формулы будутистинными.Рассмотрим теперь такой список формул: Σ = β; α1 , α2 , . . .

. В нём формула β — не является элементарной.Очевидно, что весь список модели не имеет: формула β не позволяет множеству M быть бесконечным, а формулаα|M|+1 не оставляет шансов и в том случае, когда |M| < ∞. Покажем теперь, что для этого списка невернатеорема компактности. Рассмотрим конечную подсистему Π ⊂ Σ. Если β ∈ Π, то достаточно взять множествоиз max {i : αi ∈ Π} элементов. Если же β ∈/ Π, то можно взять любое бесконечное множество, например, N.1.4.

Структуры и сигнатуры, интерпретации и моделиВ этом разделе мы рассмотрим понятия, которые во многом обобщают то, что было рассмотрено нами ранееи более точно определим то, о чём ранее упоминали лишь вскользь.1.4.1. Математические моделиОпределение. Математическая структура — это некоторое непустое множество M, называемое носителемструктуры (или просто носителем) + выделенные объекты: выделенные элементы M, операции над носителем, отношения на носителе и т. д.

Разумеется, в каждом конкретном случае что-либо в этом списке может иотсутствовать.Пример 4.1. Группа является математической структурой с выделенным элементом e, групповой операцией ◦ и операцией взятия обратного элемента −1 .Пример 4.2. Линейно упорядоченное множество (M, ≺) является математической структурой с бинарнымотношением ≺.Пример 4.3. Пусть M — совокупность всех точек и прямых евклидовой плоскости. Пусть одноместныйпредикат P выражает свойство быть точкой, а предикат L выражает свойство быть прямой.Определение.

Объекты x, y ∈ M называются инцидентными, если у них есть общие точки.Определим бинарное отношение инцидентности I(x, y) как свойство x, y быть инцидентными друг другу.Заметим, что это отношение симметрично. Теперь можно записать, например, одну из аксиом евклидовой геометрии: «Через любые две различные точки проходит прямая». Формула будет следующей:∀ x ∀ y P (x)&P (y) ⇒ ∃ z L(z)&I(x, z)&I(y, z) .3 Болееточное определение этого понятия будет дано в разделе 1.4.1 — Прим. наб.13Задача 1.13. Уточните аксиому требованием единственности такой прямой.Определение. Сигнатура данной структуры Σ — список имён выделенных объектов, индивидные, функциональные и предикатные переменные с указанными валентностями.Определение.

Изоморфизм структур Σ и Π с одинаковой сигнатурой Ω — биекция Φ между их носителямиM и N , сохраняющаявсе определённые операции, отношения и сигнатуру, т. е. для всякого имени N ∈ Ω имеемΦ ObjΣ (N ) = ObjΠ (N ). Здесь ObjX (N ) — элемент носителя сигнатуры X с именем N . Изоморфизм структурразличной сигнатуры не определён.Замечание. После столь длинного определения полезно сделать маленькое лирическое отступление об объектах и именах. Как говорил Владимир Андреевич Успенский, в природе нет математики, но есть имена еёжителей.