Лекция 11. Теорема о полноте

Как уже отмечалось, математика, признающая необходимость доказа-

тельства утверждений, возникла в древней Греции.

Это достижение о древних греков превратило математику в дедуктив-

ную науку. Каждая теорема должна иметь доказательство из множества

предложений, называемых аксиомами. Доказательство должно показать,

что заключение теоремы следует из данных аксиом только по законам ло-

гики.

Возникает естественный вопрос: могут ли понятия «законы логики» и

«доказательство» быть математически точными? В этом лекции мы по-

ложительно ответим на этот вопрос.

Итак, мы находимся в следующей ситуации.

1) Мы располагаем интуитивным понятием «B следует из A1, A2, . . .

только по законам логики».

2) Нам нужно описать эти законы логики в виде набора заведомо вер-

ных, строгих правила вывода.

Сразу ясно препятствие к осуществлению такого замысла. Как можно

строго описать интуитивное понятие «следует по законам логики», если

это понятие не имеет точного определения ?

Исправим ситуацию точно сформулировав понятие «B следует из

A1, A2, . . . только по законам логики».

ОПРЕДЕЛЕНИЕ 12 Пусть A1, A2, . . ., B – формулы языка L. Фор-

мула B является логическим следствием формул A1, A2, . . ., если

формула B истинна в каждой структуре A для языка L, в кото-

рой истинны формулы A1, A2, . . ..

Тем самым «следование по законам логики» обеспечивает автоматиче-

скую истинность A, если известна истинность A1, A2, . . .. Поэтому пункт

1) четко разъяснен. Приступим к реализации пункта 2). Что означают его

слова «заведомо верных»?Мы уже имеем следующие пять правил выво-

да.

Формула A – теорема, если она получена с помощью нескольких при-

менений этих правил.

Какое требование мы должны соблюдать при изобретении правил вы-

вода? Это требование очевидно. Действительно, сопоставим следующие

соглашения.

1. Если A – модель теории, то все аксиомы теории истинны в в модели

A ( по определению модели ).

2. Теоремы теории получены по правилам вывода.

3. Правила вывода отражают понятие «логическим следствие».

4. Формула B является логическим следствием формул A1, A2, . . ., ес-

ли истинность формул A1, A2, . . . в структуре A для языка L влечет

истинность в A формулы B.

Получаем: правило вывода должны быть таковым, что каждая теорема F

теории должна являться истинной в любой модели теории. Проверим, что

это действительно так для наших 5 правил.

ТЕОРЕМА 15 Каждая теорема F теории первого порядка T ис-

тинна в любой модели A этой теории.

Доказательство индукцией по шагу n, на котором получена теорема F.

Пусть n = 1. Тогда F —аксиома. По определению модели каждая акси-

ома теории истинна в модели теории. Поэтому F истинна в модели A.

Пусть утверждение доказано для всех теорем с шагом< nи F получе-

на на шаге n. При этом применялось одно из 5 правил вывода к теоремам

A, B,. . ., полученным на предыдущих шагах 1, 2, . . ., n − 1. По индукции

теоремы A, B,. . . истинны в модели A, т.е. принимают только значение И,

при любой интерпретации

x = a, y = b, . . . (30)

1 случай, применялось правило расширения

A

B ∨ A

Тогда F = B ∨A. При интерпретации (30) значение формулы V (A) равно

И . Тогда V (F) = V (B ∨ A)= И ,что и надо.

Случаи 2 , 3, 4 когда применялись правило сокращения, правило ассо-

циативности и правило сечения, аналогичны.

5 случай, применялось правило ∃ введения

A → B

∃x A→ B

, где x не является свободной переменной в B. (31)

Тогда F = ∃x A→ B. Предположим противное, при некоторой интер-

претации (30) значение формулы V (F) равно Л. Тогда V (∃x A→ B)=

И, V (B) =Л. Имеем некоторое значения a переменной x в интерпретации

(30). Поскольку x не является свободной переменной в B, то изменение

значения x на a1 в интерпретации (30) не изменяет значения V (B).

Поскольку V (∃x A)= И, то существует замена x на a1 в интерпретации

(30)такая, что V (∃x A)=И. Для этой новой интерпретации V (A)=Ии,

поэтому, V (A → B)=Л, противоречие. Теорема доказана.

Обратное утверждение для данной теоремы является одним из основ-

ных положений логики.

ТЕОРЕМА 16 (теорема К.Геделя о полноте). Если формула F

теории первого порядка T истинна в любой модели A этой тео-

рии, то F теорема теории T.

Доказательство теоремы достаточно сложное и опускается. Обсудим

значение этой теоремы.

Мы можем рассмотреть два множества формул теории первого поряд-

ка T, а именно:

• M1 —множество теорем теории T;

• M2—множество формул теории T, истинных в любой моделиAэтой

теории.

По определению логического следования формулы B из формул

A1, A2, . . . множество M2 есть множество формул, являющихся логиче-

ским следствием аксиом теории T.

Две предыдущие теоремы утверждают, что M1 ⊆ M2 и M2 ⊆ M1, т.е.

M1 = M2.

Мы имеем пять правил вывода. Естественно задать вопрос. Какие еще

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

список теорем в теории первого порядка. Ответ следующий: нам не нуж-

ны никакие новые правила. Действительно, пусть к старому набору пра-

вил с 5 правилами добавляется новое правило и получается новый набор

правил с новым набором теорем M_

1. Ясно, что M1 ⊆ M_

1 . Как сказано

выше новый набор правил должен быть таким, что: каждая теорема тео-

рии первого порядка T c этим набором правил истинна в любой модели A

этой теории. Поэтому необходимоM_

1

⊆ M2. С учетомM2 = M1 получаем

M_

1

⊆ M1 иM_

1 = M1.