рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Полнота аксиоматических теорий

Полнота аксиоматических теорий - раздел Математика, КОНСПЕКТ ЛЕКЦИЙ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ Любая Содержательная Формальная Теория Строится Для Обоснования Рассуждений В...

Любая содержательная формальная теория строится для обоснования рассуждений в некоторых содержательных теориях. Возникает вопрос: насколько полно описывает формальная теория соответствующую содержательную теорию ? Более точно: насколько тесно связаны понятия истинности формулы в формальной теории и в содержательной ?

Для формальной теории истинность теоремы означает, прежде всего, её доказуемость. Для содержательной теории утверждение истинно, если оно истинно в любой модели данной теории. Таким образом, и для любой формальной теории возникают a’ priori два понимания “истинности” формулы: доказуемость и тождественная истинность (истинность при любой интерпретации рассматриваемой теории).

Интерпретация формальной теории (или модель теории) определяется аналогично введённому выше (см. § 4 главы II) понятию интерпретации для множества формул исчисления предикатов. Не вдаваясь в формальности, ограничимся только намёком: модель теории (или интерпретация) – это некоторое множество вместе с зафиксированными на нём конкретными константами, предикатами и функциями для всех выделенных константных, предикатных и функциональных символов, участвующих в аксиомах теории. При этом требуется, чтобы все аксиомы теории в любой интерпретации этой теории представляли собой истинные в этой модели утверждения.

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

Для незамкнутой формулы A(x1 , … , xn) теории со свободными объектными переменными x1 , … , xn можно ввести понятие интерпретации формулы теории : это – любая модель теории вместе с фиксированными объектами o1 , … , on для свободных переменных. После замены в этой формуле всех участвующих в ней символов на соответствующие конкретные высказывания, объекты, предикаты и функции модели, а переменных x1 , … , xn – на объекты o1 , … , on получится высказывание, которое может быть истинным или ложным. Значит, можно говорить о значениях формулы теории при её интерпретациях, и о тождественно истинных формулах теории – формулах, принимающих значение истина при любой интерпретации. При этом незамкнутая формула A(x1 , … , xn) теории со свободными объектными переменными x1 , … , xn тождественно истинна тогда и только тогда, когда тождественно истинна замкнутая формула той же теории (" x1 (" x2 ( … (" xn A(x1 , … , xn))))).

Замечания: 1. При интерпретации специальной теории все логические связки и кванторы интерпретируются стандартным образом (в соответствии с неформальными аксиомами § 3 главы I и § 1 главы II).

2. При интерпретации формальных теорий исчисления высказываний и предикатов сами истинностные значения логических связок, как и истинностные значения формул, полученных навешиванием кванторов, могут изменяться (подробнее об этом см. § 5).

Ясно, что правила вывода теории предикатов, применённые к тождественно истинным формулам, снова приводят к тождественно истинным формулам. Поэтому любая доказуемая формула специальной теории является тождественно истинной. Таким образом, сформулированный выше вопрос полноты можно поставить так: верно ли, что любая тождественно истинная формула специальной формальной теории доказуема ? Этот вопрос нетривиален даже для формальной теории исчисления предикатов (для формальной теории исчисления высказываний он будет решён положительно (но не просто) в § 6).

Система аксиом формальной теории, как и сама теория, называется полной в широком смысле, если любая тождественно истинная формула этой формальной теории доказуема.

Теорема (о полноте в широком смысле).Любая непротиворечивая специальная теория полна в широком смысле.

Доказательство. Используем (без доказательства) следующую нетривиальную теорему:

Теорема (о существовании модели).Теория непротиворечива тогда и только тогда, когда она имеет модель.

Если теперь А – некоторая недоказуемая, но тождественно истинная формула некоторой специальной теории, то формула также недоказуема: если бы она была доказуема, то была бы истинной в каждой модели, вопреки тождественной истинности формулы А. Более того, присоединение к аксиомам рассматриваемой теории формулы приводит к противоречивой теории: если бы эта новая теория была бы непротиворечива, то у неё существовала бы модель, в которой была бы истинна формула , что невозможно ввиду тождественной истинности формулы А. Итак, существует такое конечное множество Г аксиом исходной теории, что Г, Ф и Г, . По правилу опровержения отсюда получим Г , т.е. (с учётом аксиомы ® A и правила силлогизма) Г А .

Теорема доказана.

Итак, понятие доказуемости формулы формальной теории совпадает с понятием тождественной истинности. Этот факт укреплял уверенность математиков в том, что программа Гильберта обоснования математики путём формализации приведёт к успеху.

Систему аксиом или саму теорию назовём полной, если для любой замкнутой формулы Ф этой теории доказуема либо сама формула Ф, либо её отрицание . Система аксиом формальной теории, как и сама теория, называется полной в узком смысле, если добавление любой недоказуемой в этой теории замкнутой формулы к списку аксиом теории приводит к противоречивой теории. Наконец, теорию или её систему аксиом назовём ф-категоричной, если для любой её модели множества истинных в этой модели замкнутых формул теории одно и то же. Приведённое определение ф-категоричности не совпадает с общепринятым определением категоричности теории, которое требует понятия изоморфизма моделей, не рассматриваемое в этих лекциях.

Следует отметить, что далеко не каждая содержательная математическая теория полна: утверждение о доказуемости отрицания недоказуемого математического утверждения не верно. Например, утверждение, представляющее аксиому параллельности Евклида (через каждую точку плоскости, не лежащую на заданной прямой, проходит ровно одна прямая, параллельная этой прямой) недоказуемо в системе аксиом абсолютной геометрии, как и его отрицание.

Теорема (о взаимосвязях понятий полноты).Следующие утверждения для любой специальной теории эквивалентны:

(1) теория полна,

(2) теория полна в узком смысле,

(3) теория ф-категорична.

Доказательство.Ясно, что противоречивая теория полна, полна в узком смысле и ф-категорична (?!). Для непротиворечивой теории используем следующую схему доказательства: .

(1) Þ (2) Пусть теория полна, и замкнутая формула Ф не доказуема в этой теории. Тогда доказуема формула , т.е. Г , где Г – некоторое конечное множество аксиом теории. Нужно понять, что добавление формулы Ф к списку аксиом приводит к противоречивой теории. Действительно, Г, Ф и Г, Ф Ф, что и требовалось доказать.

(2) Þ (3) Пусть специальная теория полна в узком смысле, но существует замкнутая формула Ф этой теории, истинная в одной модели этой теории и ложная в другой. Тогда формула Ф недоказуема, т.к. доказуемые формулы не могут быть ложными в моделях, причём добавление к исходной теории недоказуемой замкнутой формулы Ф не привело к противоречивой теории ввиду наличия модели расширенной теории. Это противоречие доказывает (3).

(3) Þ (1) Пусть теория ф-категорична, но Ф – недоказуемая замкнутая формула этой теории, для которой также недоказуема. Присоединим недоказуемую формулу к списку аксиом теории.

Если полученная теория будет непротиворечива, то по теореме о существовании модели у неё существует модель, в которой истинна. Ввиду ф-кате­горичности тождественно истинна, и по теореме о полноте в широком смысле, доказуема – противоречие.

Если же полученная теория будет противоречива, то существует такое конечное множество Г аксиом теории, что Г, А и Г, для некоторой формулы А. Отсюда по правилу опровержения получаем Г , т.е. Ф доказуема (?!) – снова противоречие. Таким образом, либо Ф, либо доказуема, и теория полна.

Теорема доказана.

Как же обстоит дело со свойством полноты в трёх рассматриваемых модельных формальных теориях исчислений высказываний, предикатов и формальной теории арифметики ?

Для теорий исчисления высказываний и предикатов условие полноты не выполнено, что и неудивительно: это универсальные теории общего назначения, используемые в различных областях знания. Поэтому одна и та же формула (например, формула (a Ú b) исчисления высказываний или формула ($ x P(x)) исчисления предикатов) может быть истинна в одной модели, а в другой ложна. Таким образом, эти теории имеют много различных моделей, отличающихся истинными в них формулами, а потому не полны.

Теорема (о неполноте в узком смысле исчислений высказываний и предикатов).Формальные теории исчисления высказываний и предикатов не полны в узком смысле, не ф-категоричны, но полны в широком смысле.

Упражнения: 1.Докажите, что присоединение к исчислению высказываний в качестве аксиомы формулы x , где х – пропозициональная переменная, приводит к непротиворечивой теории.

2. Докажите, что присоединение к исчислению предикатов в качестве аксиомы формулы ($ x P(x)), где х – объектная переменная, а P(_) – предикатный

символ, приводит к непротиворечивой теории.

3. Докажите, что присоединение к аксиомам формальной арифметики формулы (2´2=5) приводит к противоречивой теории.

Теорема (Линдебаума о пополнении теории).Если специальная теория непротиворечива, то существует её полное непротиворечивое расширение.

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

Пусть 1 , Ф2 , … } – множество всех замкнутых формул рассматриваемой непротиворечивой теории Т. Построим последовательность непротиворечивых теорий Т = Т0 Í Т1 Í Т2 Í … , объединение которых T= и будет искомой непротиворечивой полной теорией, содержащей исходную теорию Т.

Полагаем Т0 = Т – непротиворечивая теория. Если уже построена непротиворечивая теория Тn (n ³ 0) , то для построения теории Тn+1 рассмотрим формулу . Если эта формула доказуема в теории Тn , то положим Тn+1 = Тn , получая снова непротиворечивую теорию. Если же не доказуема в теории Тn , то добавим Фn+1 к списку аксиом теории Тn , получая новую теорию Тn+1 . Эта теория тоже непротиворечива. Действительно, если она противоречива, то любая формула в ней доказуема, в частности, выводима из конечного множества аксиом теории Тn+1 . Если в этом конечном множестве аксиом отсутствует Фn+1 , то доказуема в теории Тn , что противоречит условию непротиворечивости Tn при построении теории Тn+1 . Таким образом, для некоторого конечного множества Г аксиом теории Тn верно Г, Фn+1 . Учитывая очевидный факт Г, Фn+1 Фn+1 , и применяя правило опровержения , получим Г – противоречие с построением теории Тn+1 .

Докажеми теперь, что теория T= и будет искомой непротиворечивой полной теорией, содержащей исходную теорию Т. Она непротиворечива ввиду теоремы компактности: если противоречие есть, то оно получается из некоторого конечного списка аксиом, т.е. должно присутствовать и в некоторой теории Tn , что противоречит доказанной непротиворечивости всех теорий Tn (n ³ 0).

Пусть теперь Ф – произвольная замкнутая формула теории T, являющаяся, конечно, и формулой теории T. Значит Ф = Фт для некоторого m Î N, и поэтому представляются следующие возможности: либо доказуема в теории Tm , а значит и в T, либо недоказуема в теории Tm , но тогда Фm является аксиомой теории Tm+1 , доказуема в Tm+1 , а значит и в T. Таким образом, для любой замкнутой формулы Ф теории Tодна из формул Ф, доказуема в этой теории.

Теорема о пополнении доказана.

В отличие от формальных теорий исчисления высказываний и предикатов, которые слишком общи, чтобы быть полными, формальная теория арифметики имеет дело с конкретными объектами – натуральными числами, изучаемыми с детства. Поэтому доказанная К. Гёделем в 1931 г. теорема о неполноте арифметики вызвала эффект разорвавшейся бомбы.

Теорема (Гёделя о неполноте формальной арифметики).Если формальная арифметика непротиворечива, то можно указать конкретную замкнутую формулу, которая, как и её отрицание, не доказуемы в формальной арифметике, т.е. формальная арифметика не полна. В качестве такой формулы можно взять, например, формулу, выражающую факт недоказуемости теоремы арифметики (0 ¹ 1) .

Таким образом, натуральные числа, изучаемые в школе – это лишь одна из возможных моделей формальной арифметики. Оказывается, что существует модель формальной арифметики даже на множестве R всех действительных чисел. К сожалению, приходится сделать вывод: аксиомы не могут выразить адекватно все свойства формализуемого математического объекта; полученные модели аксиоматической теории могут иметь свойства, не предусмотренные в аксиомах и далёкие от первоначального замысла их создателя. Теперь математик, пытающийся доказать какую-либо теорему, должен учитывать возможность того, что она, как и её отрицание, могут быть недоказуемыми в рамках аксиоматики изучаемой теории.

Заметим ещё, что упомянутая в прошлом параграфе обобщённая теоерема Гёделя о неполноте не противоречит теореме о пополнении: просто полное непротиворечивое расширение арифметики (как и любой конструктивно аксиоматизируемой теории, о которой идёт речь) уже не будет конструктивно аксиоматизируемым. Причина этого кроется в том, что, не всегда возможно эффективно определить, доказуема ли в данной теории заданная замкнутая формула.

 

 

– Конец работы –

Эта тема принадлежит разделу:

КОНСПЕКТ ЛЕКЦИЙ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ

Государственное образовательное учреждение... Тобольская государственная социально педагогическая академия... им Д И Менделеева...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Полнота аксиоматических теорий

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Тобольск – 2010
УДК 510.6Печатается по решению редакционно-издательского ББК 22.12 я 73 совета Тобольской государственной социально- В 15пе

С О Д Е Р Ж А Н И Е
ПРЕДИСЛОВИЕ . . . . . . . . . . . . . .       Глава I.

П Р Е Д И С Л О В И Е
Хотя настоящее учебно-методическое пособие предназначено, в первую очередь, для студентов физико-математических специальностей пединститутов, оно может быть использовано и при чтении курса математи

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

Язык исчисления высказываний
В любом естественном языке есть возможность строить из простых высказываний более сложные. Примеры: 1. “Сейчас температура воздуха на улице от –25 до –30 гра

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

И равносильные формулы
  Примеры предыдущего параграфа показывают, что таблицы истинности формул могут быть разнообразны. Формулы, принимающие при любых наборах значений пропозициональных переменных одно и

Нормальные формы
x1 … xn A(x1 , … , xn ) … … …

Булевы функции
  После того как каждой формуле A(x1 , … , xn) при любом наборе x1 = e1 , … … , xn = en (ei

Логическое следование
  Понятие логического следования является одним из важнейших в математической логике и имеет непосредственное отношение к жизни. Нам часто приходится обосновывать те или иные утвержде

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

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

Равносильные и тождественно истинные предикаты
  Два предиката P(x1 , … , xn ) и Q(x1 , … , xn ), определённые на множестве А (т.е. предикаты с условиями An

Теорема (об основных равносильностях с кванторами).
(0) " x Î A P(x, y) º " z Î A P(z, y), $ x Î A P(x, y) º $ z Î A P(z, y), где P(x,

Язык исчисления предикатов
  С помощью предикатов можно формулировать содержательные утверждения в различных областях знания. Поэтому важно дать средства построения осмысленных выражений с предикатами и приписы

Интерпретации формул исчисления предикатов
Уже в исчислении высказываний возникала ситуация, когда было невозможно однозначно говорить об истинности или ложности формулы: при одних значениях пропозициональных переменных эта формула может пр

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

О структуре современных математических теорий
  Очень кратко, не претендуя на полноту, опишем лишь основные черты, присущие всем математическим теориям на современном этапе развития. Фундаментом любой математической теор

Некоторые методы доказательства теорем
  Под теоремой обычно понимается математическое утверждение, которое можно доказать. Доказательством теоремыТ называется конечная последовательность теорем Т1

Формальные и неформальные аксиоматические теории
Нами изучены две математические теории, относящиеся к логике: алгебра высказываний и алгебра предикатов. В обоих случаях делалось следующее: · были объявлены первоначальные (неопределяемые

Непротиворечивость аксиоматических теорий
Система аксиом формальной теории, как и сама теория, называются непротиворечивой, если не существует такой формулы Ф этой формальной теории, что Ф и

Разрешимость аксиоматических теорий
Проблема разрешимости теории может быть сформулирована несколькими способами: (Проблема доказуемости):Существует ли алгоритм, позволяющий за конечное число шагов эф

Независимость системы аксиом теории
Создавая аксиоматическую теорию, естественно стремиться не выписывать лишних аксиом – тех, которые выводимы из остальных. Система аксиом формальной теории называется независимой, если ни одн

Формальное исчисление высказываний
Подробно рассмотрим формальную теорию исчисления высказываний (ИВ). Нашей целью будет обоснование адекватности этой теории, описанной формально в § 1 главы III, неформальной алгебре высказыв

B, A (A Ù B) дедукция
11 · Г, B, A (A Ù B) расширение посылок 12 · Г, А, В

A Ù B) ® ((A Ú C) Ù (B Ú C))) дедукция
13 · (С ® (A Ú C)) (Д2) 14 · С (A Ú C) де

A Ú C) (В ® ((A Ù B) Ú C)) дедукция
10 · (A Ú C) (С ® ((A Ù B) Ú C)) (почему ?!) 11 ·

Дедукция
4 · (A Ù B) B (почему ?!) 5 ·

A, , (A ® B) Bдедукция
3 · A, , (A ® B)

A ® B) (Ú ) силлогизм
19 · (Ú )

A ® B)) дедукция
8 · (B ® (A ® B)) (И1) 9 · ((® (A ® B)) ® ((B ® (A ® B)) ® ((

Правило опровержения
Упражнение:Докажите формально остальные основные равносильности. 6. Доказуемость и тождественная истинность формул. Теперь уже можно доказать основной рез

Азы наивной теории множеств
В фундаменте современных математических теорий лежат понятия множества, элемента множества, отношения принадлежности элемента множеству. Интуитивный смысл этих понятий ясен: под множеством п

Аксиоматика Цермело-Френкеля теории множеств
  В § 1 приложения были даны основные понятия теории множеств. Однако развиваемая на этом основании Г. Кантором наивная теория множеств столкнулась в конце XIX в. с трудностями. Вот –

Кущи или адские дебри ?
Попытаемся неформально проанализировать общематематические достижения в задаче обоснования теории множеств. Сразу нужно отметить, что замкнутого изложения основ формальная теория множеств не даёт.

Л И Т Е Р А Т У Р А
А) ОСНОВНАЯ ЛИТЕРАТУРА: 1.Глухов М.М., Козлитин О.А., Шапошников В.А., Шишков А.Б. Задачи и упражнения по математической логике, дискретным функциям и тео

СПИСОК ОСНОВНЫХ ОБОЗНАЧЕНИЙ
N – множество всех натуральных чисел, Q – множество всех рациональных чисел, R – множество в

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
А аксиома объёмности................................................. 150 аксиома (неупорядоченной) пары..............................

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги