Непротиворечивость и полнота аксиоматической теории исчисления высказываний

КУРСОВАЯ РАБОТА

по дисциплине «Математическая логика»

 

на тему:

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

 

 

Выполнил:

студент 4 курса группы 120821

факультета математики, физики и

информатики

направления «Математическое

обеспечение и администрирование

информационных систем»

профиля «Информационные

системы и базы данных»

Тюрин Иван Евгеньевич

 

Научный руководитель:

к.ф. – м.н., профессор Устян А. Е.

 

Тула 2016

 

Содержание

Введение 3

Аксиоматические теории 3

Непротиворечивость и полнота аксиоматической теории исчисления высказываний 5

Аксиоматические теории первого порядка 6

Метод резолюции 7

Логика предикатов 9

Основные равносильности для предикатов 10

Получение дизъюнктов 11

Дифференциальные уравнения первого порядка 13

Введение в формальные теории 23

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

Формальные теории множеств 25

Парадоксы «наивной» теории множеств 25

Поиск путей выхода из кризиса 27

Система аксиом Цермело-Френеля и некоторые следствия из нее 28

О других аксиоматиках формальной теории множеств 35

Знаменитые проблемы теории множеств 36

Список литературы 39

 

 

Введение

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

Предика́ т (n-местный, или n-арный) — это функция с областью значений {0, 1}(или «Истина» и «Ложь»), определённая на n-й декартовой степени множества M. Таким образом, каждую n-ку элементов M он характеризует либо как «истинную», либо как «ложную».

Предикат можно связать с математическим отношением: если n-ка принадлежит отношению, то предикат будет возвращать на ней 1.

Предикат — один из элементов логики первого и высших порядков. Начиная с логики второго порядка, в формулах можно ставить кванторы по предикатам. Квантор же это…

Ква́ нтор — общее название для логических операций, ограничивающих область истинности какого-либо предиката и создающих высказывание. Чаще всего упоминают:

· Квантор всеобщности (обозначение: , читается: «для любого…», «для каждого…», «для всех…» или «каждый…», «любой…», «все…»).

· Квантор существования (обозначение: , читается: «существует…» или «найдётся…»).

·

Предикат называют тождественно-истинным и пишут:

P (x₁, …, x_n) ≡ 0

если на любом наборе аргументов он принимает значение 1.

Предикат называют тождественно-ложным и пишут:

P (x₁, …, x_n) ≡ 0

если на любом наборе аргументов он принимает значение 0.

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

Так как предикаты принимают только два значения, то к ним применимы все операции булевой алгебры, например: отрицание, импликация, конъюнкция, дизъюнкция и т. д.

Аксиоматические теории

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

1. Язык:

а) Символы теории, это

- буквы (для определенности, заглавные латинские): A, B, C, ..., Z

- специальные символы: (, ), ®,

б) Последовательности символов образуют выражения.

Например, выражениями будут AB ® (B или другое, более приятное глазу,

(A ® B) ® (B)

Формулами будем называть выражения, задаваемые индуктивно следующим образом:

а) Любая буква (A... Z) есть формула.

б)Если А, В - формулы, то ( А ), A, A ® B - также формулы.

2. Аксиомы зададим тремя схемами аксиом:

A ® (A ® B)

(A ® (B ® C)) ® ((A ® B) ® (A ® C))

(A ® B) ® (B ® A)

В схемы аксиом вместо A, B, C могут быть подставлены любые формулы. В результате конкретных подстановок на основе схем аксиом будут появляться конкретные аксиомы.

3. Правила вывода: В данной конкретной версии аксиоматической теории используется всего одно (но самое известное) правило вывода modus ponens

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

A , A ® B ½ ¾ B

Символ ½ ¾ читается как " выводимо". То есть в данной теории из формул

A и A ® B выводима формула B или формула B есть теорема данной теории.

Выводом (в данной теории) называется последовательность формул Ф₁, Ф₂, ..., Ф_n, где каждая следующая формула является аксиомой, или следует по правилу вывода из предыдущих. Последняя формула вывода называется теоремой.

 

Важное замечание. При описании теории, в том числе и ее языка, использовались средства, не принадлежащие определяемому (целевому) языку: запятые, точки, слова русского языка и т.д. Совокупность средств, используемых при описании целевого языка, называется метаязыком.

 

Пример:

 

Лемма: ½ ¾ A ® A

Ф1: Возьмем схему аксиом 2 и подставим А = А, С = А, В = А ® А, в результате получим:

(A ® ((A ® A) ® A)) ® ((A ® (A ® A)) ® (A ® A))

Ф2: Из схемы аксиом 1, при А = А, В = А ® А, получим:

(А ® ((А ® А) ® А))

из Ф1, Ф2 по m.p. получаем Ф3: (A ® (A ® A)) ® (A ® A)

Ф4: Из схемы аксиом 1, при А = А, В = А, получим:

(А ® (А ® А))

из Ф3, Ф4 по m.p. получаем Ф5: A ® A

 

Логика предикатов

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

Если переменная одна, то предикат одноместный, две - двухместный и т.д.

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

Операции:

Из элементарных (атомарных) предикатов с помощью логических операций можно получить сложные предикаты.

Здесь уместно сделать важное содержательное замечание:

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

 

В логике предикатов к операциям, имеющим место в логике высказываний, добавляются операции навешивания кванторов.

" - квантор общности. " x P(x) - " для всех х - P(x)".

$ - квантор существования. $x P(x) - " есть такие х, что P(x)".

( $! или $₁ - существует и притом единственный).

Кванторы связывают соответствующие переменные. Связанные переменные можно воспринимать как константы, а несвязанные переменные - свободные переменные -

как собственно переменные.

 

Содержательные примеры предикатов:

R(x) - х любит кашу (одноместный предикат).

" x R(x) - все любят кашу (нульместный предикат - высказывание).

$x R(x) - некоторые (есть такие) х любят кашу.

L(x, y) - х любит y (двухместный предикат).

$x" y L(x, y) - Существует x, который любит всех y.

" x ( C(x) ® O(x) ) - Все студенты C(x) отличники O(x).

$x ( C(x) & O(x) ) - Некоторые студенты C(x) отличники O(x).

Здесь есть повод поразмышлять об использовании операций ® и & в двух последних высказываниях.

 

Для конечных областей можно операции навешивания кванторов выразить через конъюнкцию и дизъюнкцию:

Пусть х Î {a₁, a₂, ..., a_n}

" x P(x) = P(a₁) & P(a₂) & ... & P(a_n).

$x P(x) = P(a₁) Ú P(a₂) Ú ... Ú P(a_n).

Получение дизъюнктов

 

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

В общем случае необходимо пройти три этапа:

1. Получить предваренную нормальную форму.

2. Произвести сколемизацию.

3. Получить дизъюнкты.

 

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

Сколемизация (от фамилии математика - Skö lem)позволяет получать запись замкнутого предиката в форме без кванторов.

Избавляемся от кванторов существования:

1) Если левее нет кванторов общности, то

соответствующая переменная заменяется константой сколема;

2) Иначе переменная заменяется функцией сколема от переменных, на которые навешаны кванторы общности, стоящие левее данного квантора существования.

После чего кванторы общности просто отбрасываются.

 

Пример:

" x ( " yP(x, y) Ú $zR(z) ® Q(x) & " yM(x, y)) º

º " x ( $yP(x, y) & $zR(z) Ú Q(x) & " yM(x, y) ) º

º $x ( (" yP(x, y) Ú " zR(z)) & (Q(x) Ú $yM(x, y)) ) º

º $x ( " yz (P(x, y) Ú R(z)) & $y( Q(x) Ú M(x, y)) ) º

º $x" y" z$h ( (P(x, y) Ú R(z)) & ( Q(x) Ú M(x, h)) ) º

º (P(a^c, y) Ú R(z)) & (Q(a^c) Ú M(a^c, f^c(y, z)))

Каждая элементарная дизъюнкция в полученном выражении является дизъюнктом.

Дифференциальным уравнением называется уравнение, связывающее независимую переменную х, искомую функцию у = f (x) и ее производные различных порядков.

Порядком дифференциального уравнения называется порядок старшей производной, входящей в это уравнение.

Дифференциальное уравнение n-го порядка в общем виде записывается так:

 

F (x, y, y', y'', ... y ⁽ⁿ⁾) = 0.

 

Решением дифференциального уравнения называется любая функция y = φ (x),

обращающая это уравнение в тождество.

Решение F (x, y) = 0, заданное в неявном виде, называется интегралом дифференциального уравнения.

График решения дифференциального уравнения называется интегральной кривой.

Общим решением дифференциального уравнения n - го порядка называется функция

у = φ (х, С₁, С₂,..., С_n),

зависящая от х и n произвольных независимых постоянных С₁, С₂,..., С_n, обращающая это уравнение в тождество.

Общее решение, заданное в неявном виде

Ф (х, y, С₁, С₂,..., С_n) = 0,

называется общим интегралом.

Частным решением дифференциального уравнения называется решение, которое получается из общего, если придать определенные значения произвольным постоянным, т.е. решение вида:

у = φ (х, С⁰₁, С⁰₂,..., С⁰_n),

где С⁰₁, С⁰₂,..., С⁰_n - фиксированные числа.

Частным интегралом называется интеграл, полученный из общего путем

фиксирования произвольных постоянных:

Ф (х, y, С⁰₁, С⁰₂,..., С⁰_n) = 0,

где С⁰₁, С⁰₂,..., С⁰_n - фиксированные числа.

 

Краткая теория

Общий вид дифференциального уравнения первого порядка:

F (x, у, у') = 0. (12.1)

Если это уравнение разрешимо относительно у', то

у' = f(х, у) или dу = f(x, y)dx. (12.2)

Это уравнение можно записать так:

P(x, y)dx + Q(x, y)dy = 0. (12.3)

Общим решением уравнения (12.1) называется функция

y = φ (x, C) (12.4)

от х и произвольной постоянной С, обращающая это уравнение в тождество.

Общее решение, заданное в неявном виде

Ф (x, y, C ) = 0, (12.5)

называется общим интегралом.

Геометрически общее решение (и общий интеграл) представляет собой семейство интегральных кривых на плоскости, зависящих от одного параметра С.

Частным решением уравнения (12.1) называется решение, полученное из общего решения (12.4) при фиксированном значении С:

y = φ (x, C⁰) (12.6)

где C⁰ - фиксированное число.

Частным интегралом уравнения (1) называется интеграл, полученный из общего интеграла (5) при фиксированном значении С:

Ф (x, y, C⁰) = 0. (12.7)

Теорией первого порядка или просто теорией называется формальная

система Т такая, что:

• языком формальной системы является язык первого порядка;

• аксиомами формальной системы являются логические аксиомы

языка теории T и некоторые другие аксиомы, называемые нелоги-

ческими аксиомами;

• правилами вывода формальной системы являются правило расши-

рения, правило сокращения, правило ассоциативности, правило се-

чения и правило ∃ введения.

 

Теперь разъясним эти понятия подробно.

Язык первого порядка. Чтобы задать язык первого порядка нужно

определить символы языка и определить формулы языка.

Символами языка первого порядка является:

1. переменные x, y, z, x_, y_, ..., x1, y1, z1, ... ;

2. n-арные функциональные символы f, g, h, ... и n-арные предикат-

ные символы p, q, r, ..., где n _ 0;

3. символы ￢, ∨, ∃ .

Следующие символы называются

логическими символами: переменные, знаки ￢, ∨, ∃ и знак =.

Функциональные и предикатные символы, отличные от знака =, являют-

ся нелогическими символами. Они зависят от теории. Логические сим-

волы одни и те же во всех теориях. У каждой теории свой, индивидуаль-

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

тия данной теории. Число n-арных функциональных и предикатных сим-

волов для данного n произвольно и в, частности, может равняться 0. Од-

нако среди предикатных символов должен быть символ =.

Рассмотрим предназначение каждого типа знаков.

Символ = будет использоваться для обозначения равенства. Пере-

менные служат для обозначения произвольных объектов теории T. На-

пример, x может означать в арифметике число, в геометрии вектор, пря-

мую и т.п. Функциональные символы является знаками для обозначения

функций, а предикатные символы является знаками для обозначения пре-

дикатов.

Рассмотрим на примере арифметики необходимость каждого из трех

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

относящиеся к сложению, умножению, отношению > и отношению «сле-

довать за». Тогда мы запишем следующую систему аксиом.

N1. Sx _= 0. N6. x · Sy = (x · y) + x.

N2. Sx = Sy → x = y. N7. ￢ (x < 0).

N3. x + 0 = x. N8. x < Sy ↔ x < y ∨ x = y.

N4. x + Sy = S(x + y). N9. x < y ∨ x = y ∨ y < x.

N5. x · 0 = 0.

Смысл некоторых выражений уточним ниже, а пока рассмотрим симво-

лы, которые нам потребовались. Мы использовали следующие логиче-

ские символы: переменные x, y, знаки ￢, ∨ и знак =. Нелогические сим-

волы следующие: унарный функциональный символ S для обозначения

функции следования, бинарные функциональные символы + и · для вы-

ражения понятий сложения и умножения, бинарный предикатный символ

< для выражения понятия меньше, константа 0 для обозначения конкрет-

ного элемента.

Чтобы определить язык математической теории, заданной в виде фор-

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

Рассмотрим вначале пример, а затем точное определения формулы.

Пример. Рассмотрим формулу N2: Sx = Sy → x = y, изображающую

следующее свойство. Если последующее число для x равно последующе-

му числу для y , то число x равно числу y.

Построение формулы начинается следующим образом: рассматрива-

ется x - это переменная, она предназначена для обозначения конкретных

натуральных чисел. Переменная x— это терм. Далее используем знак S

- это знак для функции «последующий элемент». Выражение Sx — это

терм. Терм изображает значение функции S от элемента x. Заметим, что

вместо традиционного S(x) мы записываем это выражение без скобок.

Дадим точное определение терма.

1. Переменная является термом;

2. если u1, ...un —термы и f —n-арный функциональный символ, то

fu1u2 ...un —терм;

3. то, что выражение является термом устанавливается несколькими

применениями правил 1 и 2.

Скобки и запятые отсутствуют среди символов теории первого поряд-

ка и поэтому их нет в определении терма. Однако для наглядности мы бу-

дем употреблять запись f(u1, u2, ..., un), подразумевая вместо нее запись

fu1u2 ...un.

Отдельный нульарный функциональный символ - это терм. Действи-

тельно, выражение fu1u2 ...un при n = 0 имеет вид f. Нульарный функ-

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

значение функции от 0 переменных не может изменяться. Символ 0 в N1

– это терм.

Вернемся к рассмотрению предыдущего примера – формулы из N2

Sx = Sy → x = y отражающей мысль: если объект Sx совпадает с объ-

ектом Sy, т.е. последующий элемент за x равен последующему элементу

за y, то x = y. Эта формула построена в несколько шагов сборки 1–5.

1. Рассмотрим переменную x. Это – терм.

2. Рассмотрим переменную y. Это – терм.

3. Рассмотрим выражение Sx, образованное из унарного предикатного

символа y и ранее построенного терма x. Это выражение – терм.

4. Возьмем Sy. Это выражение – терм.

5. Рассмотрим символ бинарный предикатный символ =. Построим

выражения Sx = Sy и x = y. Эти выражения является атомными

формулами. Построим окончательное выражение Sx = Sy → x = y.

с помощью определяемого знака → . Это выражение является фор-

мулой, но не атомной формулой.

Введем точные определения атомной формулы и формулы в языке 1-го

порядка.

Атомной формулой называется выражение вида pu1u2 ...un, где

p—n-арный предикатный символ, u1, ..., un—термы.

Определение формулы.

1. Атомная формула является формулой.

2. Если A и B - произвольные формулы, то ￢ A, ∨ AB - формулы.

3. Если A - формула, то ∃ xA - формула.

4. Выражение является формулой тогда и только тогда, когда оно по-

лучено несколькими применениями правил 1-3.

Задание символов и формул, полностью определяет язык 1-го порядка.

Отметим, что в пункте 2 речь идет о способе построении формул таком

же, как в исчислении высказываний. В пункте 3 добавляется новая кон-

струкция ∃ xA. Она предназначена для отражения высказываний следую-

щего вида: существует x, для которого верно A. Например (∃ x x2 > 4)

существует число с условием x2 > 4).

Соглашения о записях. Мы продолжаем использовать соглашения

из исчисления высказываний: вместо ∨ AB для удобства восприятия за-

писываем A ∨ B, применяем определяемые знаки →, ↔, ∧ и т.п. Со-

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

что у нас нет квантора ∀ . Это обусловлено следующей равносильностью:

∀ x P(x) ≡ ￢ ∃ x￢ P(x), рассматривавшейся во вводном курсе математи-

ки. Поэтому ∀ – определяемый знак и запись ∀ xP(x) является сокраще-

нием для записи ￢ ∃ x￢ P(x).

Вместо puv и fuv где p - бинарный предикатный символ, а f - бинар-

ный функциональный символ, записываем upv, и ufv. Кроме того, форму-

лу ￢ upv будем записывать перечеркивая знак p, например, Sx _= 0 изоб-

ражает формулу ￢ Sx = 0.

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

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

теорем. Наряду с синтаксическим аспектом будем рассматривать семан-

тический аспект теории. Переход от синтаксиса к семантике совершается

тогда, когда вместо функциональных и предикатных символов, рассмат-

риваемых как буквы и только, мы начинаем изучать конкретные функции

и предикаты на некотором множестве M. Множество M будем называть

универсумом, а его элементы – индивидами.

Представим, что мы рассматриваем одну из теорий первого порядка—

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

ны рассмотреть конкретную группу. Это означает, что нужно задать кон-

кретное множество, элементы которого являются элементами группы, ко-

торую мы представляем. Вместо бинарного предикатного символа · , рас-

сматриваемой как знак в языке теории групп, мы должны ввести кон-

кретное умножение на множестве M. В общем случае мы должны вместо

функциональных символов f, g, h, ... рассматривать конкретные функции

на множестве M. Вместо предикатных символов p, q, нужно рассмотреть

конкретные предикаты на множестве M.

Сформулируем обсуждаемые понятия более точно.

Структура для языка первого порядка. Пусть L — язык первого

порядка. Структура A для языка L состоит из следующего.

1. Непустого множества M, называемого универсумом структуры A

( элементы изM называются индивидами структуры);

2. n-арной функции fA из M в M для каждого n-арного функциональ-

ного символа f из L;

3. n-арного предиката pA на M для каждого n-арного предикатного

символа p из L, отличного от =.

Напомним определение функций и предикатов, кото-

рое мы применяем. Пусть M — некоторое множество и

Mn = M × ... × M—n-ая степень множества M. Элемен-

тами Mn являются всевозможные строки (a1, ..., an), то есть

Mn = {(a1, ..., an) | ai ∈ M}.

 

Если f—некоторая n-арная функция на множестве M, то она являет-

ся сопоставлением (a1, ..., an) _→ a ∈ M. Таким образом, a1, ..., an—

значения аргумента, a—значение функции, т.е. f(x1, ..., xn) = a при

x1 = a1, ..., xn = an. Аргументы и значения функции берутся из одно-

го и того же множества M.

n-арным предикатом на множестве M называется произвольное под-

множества R из декартова произведения Mn = M × M × M... × M.

Если (a1, ..., an) ∈ R , то говорят, что элементы a1, ..., an находится в

отношении R. При n = 2 записываем a1 R a2.

Поскольку мы имеем конкретные функции и предикаты на множестве,

то мы сможем приписывать нашим формулам значения истина или ложь.

В формуле A заменяем значения переменных на конкретные индивиды из

M и приписываем формуле значение И или Л ( истина или ложь ). При

этом мы будем говорить, что формула A была истинна в A, если все ее

значения истинны.

Пример. Рассмотрим формулу x + y = 3. Возьмем в качестве универ-

сума множество натуральных чисел, функциональный символ + истол-

ковываем как обычное сложение. Заменяем значение переменной x на 2,

а значение переменной y на 1. Значения формулы равно И. При x = 2,

y = 3 значение формулы равно Л.

Опишем процедуру приписывания значение формуле A более точно.

Пусть L — язык первого порядка и A– структура для языка L с уни-

версумом M, n-арными функциями fA, gA, ... и n-арными предикатами

pA, qA, ...

Заменим произвольным образом значения переменных x, y, ... языка L

на конкретные индивиды a, b, ... изM

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

По существу это равенство задает отображение переменных языка пер-

вого порядка L в универсум M. Назовем такое отображение интерпрета-

цией.

Рассмотрим произвольный терм u. Он имеет запись fu1u2un, где

u1, ..., un — ранее построенные термы и f –n-арный функциональный

символ. По теореме об однозначности построения терма части u1, ..., un

определены однозначно. Далее разберем однозначно на части каждый

из термов u1, ..., un и т.д. В результате получим сборку u из его ча-

стей. Части, с которых начинается сборка терма u имеют некоторый вид

 

g(x1, x2, ...), где x1, x2, ... — переменные. Они должны заменяться на

конкретные индивиды a1, a2, ... из M в соответствие с интерпретацией

(29). В терме g(x1, x2, ...) заменим функциональный символ g на функцию

gA, а переменные x1, x2, ... на a1, a2, .... Получим индивид gA(a1, a2, ...)

из M. Подставим это значение в качестве аргумента в следующий терм,

участвующий в сборке терма u. Повторив действие несколько раз, полу-

чим значение a ∈ M терма u при интерпретации (29).

Рассмотрим атомную формулу p(u1, u2, ..., un), где p– n-арный пре-

дикатный символ. Заменим символ p на предикат pA, т.е. на некоторое

подмножества R из декартова произведения Mn = M × M × M... × M.

При интерпретации (29) вместо термов u1, u2, ..., un получатся элементы

a1, ..., an изM.

Если n-ка элементов (a1, ..., an) содержится в R, то приписываем

атомной формуле p(u1, ..., un) значение И, в противном случае – значе-

ние Л.

Рассмотрим процесс приписывания значений И, Л произвольной фор-

муле X.

Напомним, что

1. Атомная формула является формулой

2. Если A и B - произвольные формулы, то ￢ A, ∨ AB - формулы.

3. Если A - формула, то ∃ xA - формула

4. Выражение является формулой тогда и только тогда, когда оно по-

лучено несколькими применениями правил 1-3.

По теореме построения сборка формулы X из ее частей A, B, ... одно-

значна. Исходный элемент для сборки формулы X —атомные формулы.

При каждой интерпретации (29) атомная формула принимает значение И

или Л. Поэтому нужно лишь указать, как вычислять значение формулы

Y из значений ее частей при построениях вида (2), (3), (4). Обозначаем

значение произвольной формулы Y через V(Y).

• Пусть Y = ￢ A. Тогда значение формулы Y противоположно значе-

нию формулы A, т.е. V (Y) = ￢ V (A) (если V (A) =И, то V (Y) =–Л

и наоборот);

• Пусть Y = A ∨ B. Тогда V (Y) = V (A) ∨ V (B).

 

• Пусть Y = ∃ xA. Наряду с интерпретацией (29), рассматриваем ин-

терпретации, где значения переменных, отличных от x, те же, что и

в интерпретации (29). Эти значения переменных, отличных от x, со-

четаем с произвольным выбором x = a, x = b, ... и вычисляем зна-

чение формулы A. Если хотя бы один раз получается значение И,

то формуле Y = ∃ xA приписываем значение И, в противном случае

приписываем значение Л.

Пусть T — теория с языком L и A — структура для языка первого

порядка. Тем самым задан универсум M, заданы n-арные функции fA и

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

f для каждого n-арного предикатного символа p из L. При каждой ин-

терпретации каждая формуле принимает значение И или Л.

ОПРЕДЕЛЕНИЕ 11 Формула A теории T, называется истинной

в структуре A если при каждой интерпретации формула A при-

нимает значение И.

Структура A для языка L теории T называется моделью теории T, если

при каждой интерпретации все нелогические аксиомы из T принимают

значение И.

Другими словами структура A для языка L теории T —модель теории

T, если все нелогические аксиомы из T истинны в структуре A.

В определении речь идет лишь о нелогических аксиомах, т.к. логиче-

ские аксиомы истинны в любой структуре.

ТЕОРЕМА 14 Пусть A структура для языка L теории T и X —

логическая аксиома теории T. Тогда X истинна в A.

Доказательство. По определению логическая аксиома X имеет один из

видов:

пропозициональная аксиома ￢ A ∨ A;

аксиома равенства, имеющая один из видов a) или б)

a) x1 = y1 → x2 = y2 → · · ·→ fx1 ...xn = fy1 ...yn,

б) x1 = y1 → x2 = y2 → · · ·→ px1 ...xn = py1 ...yn;

аксиома подстановки Ax[u] → ∃ xA;

аксиома тождества x = x.

 

Рассмотрим произвольную интерпретацию, т.е. заменим значения пере-

менных x, y, ... на конкретные индивиды a, b, ... из M; x = a, y = b, ... .

Вычислим истинностное значение V (X) формулы X.

1 случай, X = ￢ A∨ A. Тогда V (X) = ￢ V (A) ∨ V (A). Если истинност-

ное значение V (A) формулы A равно И, то V (X) = ￢ V (A)∨ И=И. Если

V (A)=Л, то V (X) = ￢ Л ∨ V (A) =И ∨ V (A)= И.

В случае 2, предположим противное, т.е. при некоторой замене в фор-

мула X значений переменных: x1 = a1, y1 = b1, ... истинностное зна-

чение V (X) равно Л. Тогда посылка a1 = b1 истинна, а заключение

a2 = b2 → · · · → f(a1 ...an) = f(b1 ... bn) ложно (напомним, что A → B

–сокращение для ￢ A ∨ B и, поэтому, имеет такое правило для приписы-

вания И, Л).

Получили совпадение элементов a1 и b1. Аналогично получаем a2 =

b2, .... и ложность равенства f(a1 ...an) = f(b1 ... bn).

Тогда совпадение элементов a1 = b1, a2 = b2, ... влечет совпадение

значений функции f(a1 ...an) = f(b1 ... ), противоречие с допущением

f(a1 ...an) _= f(b1 ... bn)

В случае 2 б) поступаем аналогично.

Случай 3, X имеет вид Ax[a] → ∃ xA. Предположим противное, т.е. при

некоторой интерпретации формула X имеет значение Л. Тогда V (Ax[u])

равно И, V (∃ xA) равно Л. Терм u при заменяется при интерпретации на

некоторый элемент a ∈ M. Замена x на этот элемент приводит к значе-

нию V (Ax[a]) равному И. Итак, существует значение переменной x, ко-

торое которое вместе со значениями переменных, отличных от x, таково,

что значение V (A равное И. Тогда значение формулы V (∃ xA) равно И,

что противоречит допущению.

Случай 4, X имеет вид x = x. Подставим индивид a переменной x.

Получим a = a.

Предикат= по своему определению должен быть таковым, что резуль-

тат замены a = a имеет значение И. Теорема доказана.

Формальные теории множеств

Ранее в примере 26.7 были рассмотрены различные аксиоматики содержательной (" наивной", канторовской) теории множеств. Одной из важнейших ролей теории множеств является та, которую она играет в вопросах доказательства в тех или иных математических теориях, т. е. фактически в самых основах математики. Мы говорили, что одним из основных методов доказательства непротиворечивости математической теории является метод моделей (или интерпретаций). В качестве основных понятий и отношений выбираются элементы какого-либо конкретного множества и отношения между ними, а затем проверяется, будут ли выполняться для выбранных понятий и отношений аксиомы данной теории. Строя модель исследуемой теории, мы сводим вопрос о ее непротиворечивости к вопросу о непротиворечивости другой математической теории. Интерпретации для многих математических теорий строятся с использованием теории множеств, поэтому непротиворечивость всей математики в значительной мере упирается в непротиворечивость теории множеств.

 

Парадоксы " наивной" теории множеств

 

С момента создания теории множеств Кантором в начале 1870-х гг. и до конца XIX в. математики считали ее незыблемой основой всего математического здания. Но в конце XIX в. в самой теории множеств были обнаружены противоречия, получившие название антиномий (парадоксов) теории множеств. Причем в рассуждениях, приводящих к этим противоречиям, не содержалось никаких логических ошибок. Это обстоятельство поколебало веру в безусловную надежность математических доказательств.

 

Первый такой парадокс обнаружил сам Кантор в 1895 г. и сообщил об этом Гильберту. В 1897 г. его переоткрыл и впервые опубликовал Бурали-Форти. Хотя ни Кантор, ни Бурали-Форти не были способны в то время предложить разрешение антиномии, ситуация не казалась слишком серьезной: эта первая антиномия возникла в довольно специальной области теории вполне упорядоченных множеств, и, вероятно, казалось, что легкий пересмотр доказательств теорем, входящих в эту область, мог бы спасти положение и все здание теории множеств затронуто не будет. Но в 1902 г. английский философ, логик и математик Бертран Рассел обнаруживает антиномию, относящуюся к самым началам теории множеств и показывающую, что в основаниях этой дисциплины что-то неблагополучно. Антиномия Рассела потрясла основы не только теории множеств, но и логики: требовалось лишь легкое изменение в формулировке, чтобы перевести антиномию Рассела в противоречие, которое можно сформулировать в терминах самых основных понятий логики. Антиномия Рассела сильнейшим образом затронула самые фундаментальные понятия двух самых " точных" наук — логики и математики.

 

Суть парадокса (антиномии) Рассела состоит в следующем. Распределим все множества по двум классам: в первый класс включим все те множества, которые содержат себя в качестве своего элемента, во второй класс — все те множества, которые не содержат себя в качестве своего элемента. (Например, множество всех планет не является планетой и поэтому не есть собственный элемент. Напротив, множество всех множеств является своим собственным элементом.) Рассмотрим множество , элементами которого являются все множества второго класса. Спрашивается, к какому из двух вышеназванных классов принадлежит множество ? Допустим, что оно принадлежит к первому классу. Тогда множество содержит себя как элемент. Но элементами множества являются множества второго класса, а значит, множество принадлежит ко второму классу. Мы пришли к противоречию. Допустим теперь, что множество принадлежит ко второму классу. Так как все множества второго класса являются элементами множества , то содержит себя как элемент и поэтому принадлежит первому классу. Мы вновь пришли к противоречию.

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

Противоречию относительно можно придать и следующий (логический) вид, если задаться вопросом, какое утверждение для имеет место: или . Ответ будет обескураживающим. В самом деле, если , то принадлежит второму классу и, значит, . Если же предположить, что