Математическая логика - Кожухов И.Б., Романов А.В. [2008]

Пусть теперь ϕ(x1,…,xk ) = ¬ψ(x1,…,xk ). Тогда

По теореме Лося ультрапроизведение полей является полем (так как поле задаётся девятью аксиомами логики первого порядка), а ультрапроизведение линейно упорядоченных множеств линейно упорядочено (линейная упорядоченность определяется четырьмя аксиомами УИП).

3.9. Теоремы Лёвенгейма – Скулема

Пусть A – модель сигнатуры Ω, где Ф – множество символов операций, а Π – множество символов

Понятие функционально замкнутого подмножества (непустого) обобщает такие понятия, как подполугруппа,

подкольцо. Рассмотрим теперь понятие подгруппы. Если группу рассматривать в сигнатуре , то понятие функционально замкнутого подмножества (непустого) будет совпадать с понятием подполугруппы, а если взять сигнатуру , −1 , то непустые функционально замкнутые подмножества будут в точности являться

подгруппами. Что касается понятия подполя, то совершенно непонятно, как подобрать сигнатуру, чтобы подполя совпадали с непустыми функционально замкнутыми подмножествами. Подполе – это подмножество поля, которое удовлетворяет аксиомам поля. Это наводит на мысль рассматривать подмножества модели, “замкнутые относительно формул”, но об этом мы будем говорить позже, а сначала докажем лемму, касающуюся функционально замкнутых подмножеств. Алфавит переменных, участвующий

в построении формул, будем считать счётным: X = {x1,x2,x3,…}.

Лемма 1. Пусть A – модель сигнатуры Φ, Π, τ – бесконечная мощность и B0 – подмножество множества A такое, что | B0 |≤ τ. Если | Φ |≤ τ, то A имеет функционально замкнутое подмножество B такое, что B0 B и | B |≤ τ.

61

n=1

объединение множеств мощности ≤ τ, поэтому | B |≤ τ.

Докажем, что В функционально замкнуто. Пусть f Φ – п-арная операция и b1,…,bn B. Тогда

экзистенциально замкнуто.

Следующая теорема утверждает (при определённых условиях) существование подмодели “небольшой мощности” c “хорошимисвойствами”.

Теорема 6. Пусть A – модель сигнатуры Φ, Π, τ – бесконечная мощность | Φ |, | Π |≤ τ. Тогда существует подмодель B A такая, что | B |≤ τ и для любой формулы ϕ(x1,…,xn ) и любых b1,…,bn B

Дальнейшее доказательство проведём индукцией по длине формулы ϕ, т.е. по количеству входящих в неё символов , ¬ и . Если формула ϕ атомарна, то утверждение очевидно. Пусть формула ϕ имеет вид

ϕ = ¬ψ. По предположению индукции ψ(b1,…,bn ) истинна на A тогда и только тогда, когда она истинна на B. Следовательно, то же верно для формулы ϕ(b1,…,bn ) Аналогично рассматривается случай, когда ϕ = ϕ1 ϕ2 . Наконец, пусть ϕ(x1,…,xn ) = x ψ(x,x1,…,xn ). Предположим, что ϕ(b1,…,bn ) истинна на A. Тогда ψ(a,b1,…,bn ) истинна при некотором a A. Так как B экзистенциально замкнуто, то ψ(b,b1,…,bn )

истинна при некотором b B. Отсюда следует, что формула ϕ(b1,…,bn ) = x ψ(x,b1,…,bn ) истинна на B.

Теперь выведем из этой теоремы теорему Лёвенгейма – Скулема о понижении мощности.

Теорема 7 (теорема Лёвенгейма – Скулема о понижении мощности). Пусть T – множество предложений (замкнутых формул) сигнатуры Ω = Φ, Π, τ – бесконечная мощность и |T |≤ τ. Если

существует какая-нибудь модель A, в которой все предложения из T истинны, то существует модель B мощности ≤ τ (возможно, другой сигнатуры), в которой также все предложения из T истинны.

Доказательство. Пусть Φ0, Π0 – множества символов операций и отношений, входящих в формулы из T. Рассмотрим A как модель сигнатуры Ω0 = Φ0, Π0 . Очевидно, |Φ0 |, |Π0 |≤ τ. По предыдущей

теореме существует экзистенциально замкнутая подмодель B мощности ≤ τ. Ясно, что в модели B истинны все утверждения из T.

Пусть Ω = Φ, Π – сигнатура, в которую входит отношение равенства. Модель этой сигнатуры

называется нормальной, если в ней a = b в том и только том случае, если элементы a и b совпадают (представляют собой один и тот же элемент).

Теорема 8 (теорема Лёвенгейма – Скулема о повышении мощности). Пусть T – множество замкнутых формул сигнатуры Ω = Φ, Π, содержащей отношение равенства, и τ – бесконечная мощность.

3.10. Аксиоматизируемые классы моделей

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

63

аксиоматизируем, если он задаётся конечным числом аксиом. Очевидно, группы, кольца, поля, тела, частично упорядоченные множества – это конечно аксиоматизируемые классы.

В разделе 3.5 были даны аксиомы логики второго порядка, аксиоматизирующие множество

отрицательный:

Теорема 9. Для любой теории T в логике первого порядка с конечным или счётным числом аксиом, если – модель T, то у T есть так же модели, неизоморфные .

Доказательство. По теореме Лёвенгейма – Скулема о понижении мощности у теории T существует счётная модель, очевидно неизоморфная .

Напомним, что абелевой группой называется коммутативная группа. Будем использовать для абелевых групп аддитивную запись, т.е. сигнатуру =;+; 0. Тогда класс абелевых групп может быть задан аксиомами:

(1)a b c (a +b) +c = a +(b +c),

(2)a a + 0 = a,

(3)a b a +b = 0,

(4)a b a +b = b +a.

Следовательно, класс абелевых групп конечно аксиоматизируем.

Назовём абелеву группу A делимой, если для любого a A и любого натурального n уравнение nx = a разрешимо в A. (Мы используем здесь сокращённые записи термов: 2x = x +x, 3x = (x +x) +x и.д. В этой сигнатуре нет сорта натуральных чисел и поэтому a :A n : x :A nx = a не будет формулой

данной сигнатуры. Однако для делимых групп можно записать бесконечный набор аксиом – предложений УИП:

(52 ) a x 2x = a,

(53 ) a x 3x = a,

. . . . . . . . . . . . .

В силу теоремы компактности класс делимых абелевых групп не может быть задан конечным числом аксиом в логике первого порядка. Действительно, пусть {ψ1,…, ψk } – конечное множество предложений

логики первого порядка, истинных во всех делимых абелевых группах. Положим ψ = ψ1 … ψk . Для достижения поставленной цели достаточно доказать, что ψ выполнено в какой-нибудь не делимой абелевой группе. Пусть T – множество аксиом (1) – (4) и (52 ), (53 ), (54 ), ... Тогда T |= ψ. По теореме компактности

Таким образом, класс делимых абелевых групп аксиоматизируем, но не конечно аксиоматизируем. Абелева группа G называется периодической, если каждый её элемент имеет конечный порядок. Это

можно записать следующим образом: x n : nx = 0. Данное утверждение не является предложением

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

Докажем это. Пусть G, +, 0, = – периодическая абелева группа такая, что для каждого n

существует элемент xn порядка ≥ n. (Например, G = Z2 Z3 Z5 … (прямая сумма циклических групп

простых порядков). Докажем, что существует непериодическая абелева группа, удовлетворяющая в точности тем предложениям логики первого порядка, что и группа G. Пусть T =Th(G) – множество всех

предложений логики первого порядка, истинных на G. Очевидно, это теория. Введём новый константный символ c и положим T ′ =T {2c ≠ 0, 3c ≠ 0, 4c ≠ 0,…}.

64

Моделью для T0 может служить G;=;+; 0,xN . По теореме компактности, так как всякое конечное

3.10.1.Задачи для самостоятельного решения

1.Доказать, что класс групп, состоящих не более, чем из n элементов, конечно аксиоматизируем в сигнатуре , =.

2.Абелева группа называется группой без кручения, если n : a (a ≠ 0 → na ≠ 0). Доказать, что

класс абелевых групп без кручения аксиоматизируем, но не конечно аксиоматизируем.

3.Пусть K – аксиоматизируемый класс, содержащий конечные модели со сколь угодно большим количеством элементов. Доказать, что класс K содержит бесконечную модель.

4.Доказать, что следующие классы не являются аксиоматизируемыми:

а) класс конечных групп; б) класс конечных абелевых групп; в) класс циклических групп.

Указание: воспользуйтесь результатом предыдущей задачи.

5. Что из себя представляет ультрапроизведение моделей ∏U Mi , где U = F(j) – главный

i I

ультрафильтр?

Ответ: оно изоморфно Mj .

6. Доказать, чтонеявляютсяконечноаксиоматизируемымиклассы: а) бесконечных групп; б) бесконечных частично упорядоченных множеств;

в) бесконечных линейно упорядоченных множеств.

3.11. Теоремы Гёделя о неполноте

Представленные в этом разделе теоремы – возможно, самые знаменитые результаты математической логики, наравне с теоремой Кантора.

Пусть у нас есть некоторая теория T в сигнатуре Ω.

Сигнатура ΜΩ метатеории для T имеет единственный сорт – строки алфавита M, состоящего из всех логических символов логики первого порядка, символов сигнатуры Ω, а также "s ", "′", ".", "Q " и " PT " (мы считаем, что всех этих символов в Ω нет. Если они есть, то обозначим их по-другому).

В ΜΩ есть бинарная операция . (конкатенация), одноместный предикат PT (доказуемость), и

константы для всех элементов M* (то есть строк в алфавите M). .Переменными сорта строк будут s,s′,s′′,…

Мы пытаемся описать в сигнатуре ΜΩ следующую теорию MT (метатеорию T) : её универсумом

будет M*. Операция . приписывает одну строку к другой, добавляя скобки при необходимости: например, " "." s s = s " = " s s = s ", "(s "."( )" = "(s( )". Таким образом, существует алгоритм, строящий

для любой формулы ϕ сигнатуры ΜΩ представляющий её замкнутый терм, а именно "ϕ". Сигнатуры с таким свойством называются самоописывающими. Каждой константе из M* соответствует сама эта строка.

Заметим, что предикат PT позволяет сформулировать некоторые свойства теории как формулы метатеории. Именно,

1)Теория T непротиворечива, если в ней нельзя одновременно доказать и опровергнуть никакую формулу ϕ. В метатеории: ConT ≡ s (Sent(s) → ¬PT (s." ¬".s)), где Sent(s) ≡ "s представляет

замкнутую формулу".

65

2) Теория T полна, если любую формулу можно либо доказать, либо опровергнуть. В метатеории:

Таким образом, любая полная теория, в которой определим предикат доказуемости, противоречива. Теорема 10 (первая теорема Гёделя о неполноте). Никакая теория в самоописывающей сигнатуре не

может одновременно быть непротиворечивой, полной и допускать определение своего предиката доказуемости.

Теорема 11 (теорема Тарского). Пусть M – модель самоописывающей сигнатуры Ω. Тогда в M не определим предикат истинности, то есть не существует формулы сигнатуры Ω с одной свободной переменной True(x), для которой было бы верно

ϕ (M ϕ ↔ M True("ϕ")).

Доказательство. Предположим, что такая формула True(x) существует. Рассмотрим теорию Th(M). Очевидно, она непротиворечива и полна (поскольку любая замкнутая формула ϕ либо истинна, либо ложна в M). Кроме того, имеем Th(M) ϕ ↔ M ϕ ↔ M True(" ϕ") ↔Th(M) True("ϕ"), то есть True(x)

–предикат доказуемости для Th(M).

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

Следствие (первая теорема Гёделя о неполноте для PA). PA неполна.

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

66