В.Б. Шехтман - Курс лекций по логике и теории алгоритмов (1161807), страница 8
Текст из файла (страница 8)
Замечание наборщика. Такое совпадение доказательств не случайно. Когда мы брали фактор по отношению эквивалентности, мы имели дело с «гомоморфизмом» интерпретаций.Определение. Интерпретации изоморфны, если между ними существует изоморфизм.Утверждение 2.39. Изоморфизм интерпретаций является отношением эквивалентности. Очевидно. Определение.
Модели называют элементарно эквивалентными, если их элементарные теории совпадают.Теорема 2.40. Изоморфные теории элементарно эквивалентны. Следует из леммы 2.38. 23Построим пример элементарно эквивалентных неизоморфных теорий.Пример 4.1. Рассмотрим стандартную сигнатуру арифметики Ω0 : константы 0 и 1, предикатный символ равенства, функциональные символы сложения и умножения. Пусть N0 = (N, I) — её стандартная интерпретация.Элементарная теория этой модели Th(N0 ) носит название полной арифметики.Также рассмотрим сигнатуру Ω1 := Ω ∪ {∞} и в ней теорию T : Th(N0 ) ∪ {∞ =6 0, ∞ 6= 1, . .
.}. Всякое конечное подмножество этой теории выполнимо, следовательно, в силу теоремы компактности Гёделя – Мальцева,у этой теории существует некоторая модель N1 T . При этом, очевидно, N1 Th(N0 ). Однако, эти моделинеизоморфны: элементу ∞ ∈ N1 в Th(N0 ) не найдётся соответствия.Замечание наборщика. А почему, собственно, они будут элементарно эквивалентны?Лемма 2.41 (о полноте). Теория полна тогда и только тогда, когда все её модели элементарно эквивалентны.
Пусть теория полна и M и M ′ — её модели. Для любой формулы ϕ имеем: либо T ϕ, откуда M ϕи M ′ ϕ, либо то же самое выполнено относительно ¬ϕ. Значит, все истинные формулы у этих моделей однии те же, что и требовалось. Теперь докажем в обратную сторону. Пусть все модели теории T элементарноэквивалентны. Тогда если T 6⊢ ϕ, то для некоторой модели (а значит и для всех) M 6 ϕ, откуда T ¬ϕ.
2.4.2. Сильная категоричность и счётная категоричностьОпределение. Теория первого порядка называется сильно категоричной, если все её модели изоморфны.Определение. Теория первого порядка называется счётно – категоричной, если все её счётные модели изоморфны.Утверждение 2.42. Любая сильно категоричная теория полна. Следует из леммы о полноте. Утверждение 2.43 (признак Вота). Любая счётно – категоричная теория, не имеющая конечных моделей, полна. Пусть теория T непротиворечива (иначе, она, конечно, полна). Тогда у неё есть модель M T, и этамодель счётна (по условию).Утверждение 2.44.T ϕ ⇔ M ϕ. В одну сторону это очевидно, ведь M — это модель T .
Докажем, что T 6 ϕ ⇒ M 6 ϕ. Действительно,если T 6 ϕ, то теория T ∪ {¬ϕ} выполнима, а значит, по теореме Лёвенгейма – Сколема, она имеет счётнуюмодель. Однако, по условию, она будет изоморфна исходной, откуда M ¬ϕ. Это утверждение завершает доказательство признака Вота. Пример 4.2. Построим теорию плотного линейного порядка без наименьшего и наибольшего элементов(DLO↔ — dense linear order). Сигнатура будет состоять из двух предикатных символов: {<, =}. А в теориювойдут следующие аксиомы:1. ∀ x ¬x < x;2. ∀ x ∀ y ∀ z x < y & y < z → x < z;3. ∀ x ∀ y x < y & y < x → x = y;4.
∀ x ∀ y x < y → ∃ z (x < z & z < y) — это и есть плотность;5. ∀ x ∃ y x < y;6. ∀ x ∃ y y < x.Согласно теореме Кантора, эта теория счётно – категорична.Пример 4.3. Рассмотрим самую простую сигнатуру с равенством: {=}. Теория будет состоять из следующихформул:^T = {βn |n > 1} βn = ∃ x 1 . . . ∃ x n xi 6= xj .16i<j6nОна счётно – категорична (очевидно).Теорема 2.45.
Элементарная теория конечной интерпретации сильно категорична.24 Мы докажем эту теорему лишь для случая конечной сигнатуры.Итак, пусть M = {a1 , . . . , an }. Рассмотрим следующую формулу:ϕM := ∃ x 1 . . . ∃ x n ^xi 6= xj & ∀ yi<j&^^y = xii=116i1 <...<ik 6n&n_16i1 <...<ik 6n!{c = xi |c ∈ Cnst, M c = ai } &i=1P (xi1 , . . . , xik )|P k ∈ Pr, M P (ai1 , . . . , aik ) &^16i1 <...<ik 6nn^¬P (xi1 , .
. . , xik )|P k ∈ Pr, M ¬P (ai1 , . . . , aik ) &&Утверждение 2.46.&f (xi1 , . . . , xik ) = xj |f k ∈ Fm, M f (ai1 , . . . , aik ) = aj .N ϕM ⇔ N ∼= M.Ясно, что в доказательстве нуждается лишь прямое (⇒) утверждение. Итак, пустьN ϕM = ∃ x 1 . . . ∃ x n ψ(x1 , . . . , xn ).Это означает, что N ψ(b1 , . . . , bn ) для некоторого набора элементов bi . Нам также известно, что есть набор ai ,для которого M ψ(a1 , . . . , an ).
Покажем, что отображениеπ : ai 7→ biявляется изоморфизмом интерпретаций. Необходимо проверить, чтоπ(f (ai1 , . . . , aik ) = f (πai1 , . . . , πaik ) и P (ai1 , . . . , aik ) = P (πai1 , . . . , πaik ).Пусть f (bi1 , . . . , bik ) = bj . Это означает, что в формуле ϕM содержится «множитель» вида f (xi1 , . . . , xik ) = xj ,а значит, в модели M будет иметь место равенство f (ai1 , . . . , aik ) = aj . Аналогичное рассуждение позволяетубедиться, что значения предикатов также сохраняются. Непосредственно из доказанного утверждения следует сильная категоричность. Следствие 2.4. Для конечных теорий изоморфизм равносилен элементарной эквивалентности.3.
Теория алгоритмов3.1. Введение в системы Поста3.1.1. Построение и примеры систем ПостаОпределение. Система Поста (над алфавитом A ) есть четвёрка конечных множеств E = (A , B, V , S ),первые три из которых попарно не пересекаются. Их называют, соответственно, основной алфавит, вспомогательный алфавит, множество переменных и множество схем. Множество схем состоит из кортежей вида (t1 , .
. . , tn , t),где n > 0, а элементы ti и t суть слова над алфавитами A , B, V (их называют термами).В дальнейшем для обозначения множества всех слов над некоторым алфавитом, скажем, A , будет использоваться запись A ∗ . Таким образом, термы являются элементами множества (A ∪ B ∪ V )∗ . Схемы будут записывать так:t1 , . . . , tn.tВ случае, когда n = 0, будем говорить, что t — схема аксиом.
Если в схему вместо всех входящих в неё переменных подставить некоторые замкнутые термы, получим правило вывода (либо аксиому). Понятия «вывода»и «вывода из посылок» определяются аналогично тому, как это делалось в обычной логике высказываний.Определение. Язык, порождаемый системой Поста E — это множество всех слов, выводимых в этой системеПоста:L(E) := {α ∈ A ∗ | ⊢E α} .Определение. Множество слов над некоторым алфавитом называется (рекурсивно) перечислимым, еслионо совпадает с языком, порождённым некоторой системой Поста над этим алфавитом.25Пример 1.1.
Построим систему Поста, которая порождает множество всех пропозициональных формул.A = {p, |, &, ∨, →, ¬, (, )} ,B = {A, F } , V = {x, y} ,F x, F y F xAx Ax F x F x, F y F x, F y,,,,,,.S = Ap,Ax| F x F ¬x F (x & y) F (x ∨ y) F (x → y) xПример 1.2. Построим систему Поста, которая порождает всё множество A ∗ .xxA = {a1 , . . . , an }, S = Λ,,...,.xa1xanЗдесь и далее Λ обозначает пустое слово.Теорема 3.1.
Объединение и пересечение перечислимых множеств само перечислимо. Итак, пусть X, Y ⊆ A ∗ — перечислимы, то есть X = L(E) и Y = L(F ), где E = (A , BE , VE , SE ) иF = (A , BF , VF , SF ) — некоторые системы Поста. Рассмотрим случай объединения. Будем строить системуПоста G = (A , B, V , S ), для которой X ∪ Y = L(G). Ввдеём новые символы A, ε, ϕ, x и положимB = BE ∪ BF ∪ {A, ε, ϕ} ,V = VE ∪ VF ∪ {x} .Теперь заполним множество схем S . Пусть в SE содержится схема видаt1 , . . . , tn,tтогда в S включим схемуεt1 , .
. . , εtn.εtВ случае, если такая схема есть в SF , добавляем в S схемуϕt1 , . . . , ϕtn.εtКроме схем, получаемых таким образом, добавим ещё схемыA,AxAx Ax, εx Ax, ϕx,...,,,.Axa1AxanxxТеперь уже несложно убедиться, что для такой системы G будет выполнена следующая лемма.Лемма 3.2.1.
⊢G At ⇔ t ∈ A ∗2. ⊢G εt ⇔⊢E t3. ⊢G ϕt ⇔⊢F t4. ⊢G α ∈ A ∗ ⇔ α ∈ X ∪ YЧто же касается доказательства для случая пересечения, его единственным отличием будет то, что вместосхемAx, εx Ax, ϕx,xxследует добавлять схемуAx, εx, ϕx.x3.1.2. Подстановки и правилаЛемма 3.3. Пусть даны термы rk , . . . , rk , t, s и переменные x1 , . . . , xk , y, причём все они все попарно различны. Тогда([r1′ , . . . , rk′ , s/x1 , .
. . , xk , y] t, y 6∈ x[s/y] [r/x] t =[r1′ , . . . , rk′ /x1 , . . . , xk ] t, y ∈ x,где ri′ := [s/y] ri .26.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
