Министерство общего и профессионального образования Российской Федерации Воронежский государственный университет Математ...
144 downloads
175 Views
257KB Size
Report
This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
Report copyright / DMCA form
Министерство общего и профессионального образования Российской Федерации Воронежский государственный университет Математический факультет Кафедра функционального анализа и операторных уравнений
Моисеев В.И.
Математическая логика Учебные материалы для студентов 4 курса математического факультета
Воронеж - 1999
2
Введение Одна из основных проблем курсов по математической логике, читаемых студентам математических и других факультетов, состоит в необходимости развития предварительной и достаточно громоздкой логической техники, во многом создающей не только поддержку, но и определенного рода препятствие для рассмотрения содержательных и глубоких проблем метаматематики. Здесь приходится выбирать – либо сосредоточить внимание на изложениии начальных сведений из области логики предикатов первого порядка, либо, не слишком глубоко вдаваясь в первоначальные понятия, рассмотреть, например, такие фундаментальные теоремы математической логики, как теоремы Гёделя. В первом случае «за деревьями не видно леса», во втором случае, наоборот, видение общего покупается ценой слишком большой поверхностности во владении базовой логической техникой. С этой точки зрения нам кажется чрезвычайно удачным подход Джозефа Шенфилда [5], в котором наиболее гармонично, с нашей точки зрения, сочетаются общее и частное. Изложение здесь сразу “берет быка за рога”, первичным понятием является в этом случае не логика высказываний и предикатов, но язык первого порядка. Не слишком усложняясь, степень общности при таком подходе тем не менее быстро нарастает, что позволяет очень скоро начать оперировать такими фундаментальными понятиями метаматематики, как “теория первого порядка” и ее “модель”. Указанные достоинства такого подхода делают его достаточно ценным для разного рода спецкурсов или элективных курсов по математической логике. В то же время и в этом случае остается потребность в некоторого рода отборе материала, формировании своего рода “выжимки” из обширной работы Дж.Шенфилда. Именно эти соображения и привели автора к мысли создания своего рода конспективного представления подхода Шенфилда, способного в то же время стать основой для создания хотя и не профильного, но достаточно содержательного курса по математической логике. Мы ставили своей целью создание такого учебного пособия по математической логике, которое, опираясь на методологию Дж.Шенфилда, позволило бы достаточно быстро ввести студента в серьезную проблематику современной математической логики. В качестве сферы выражения этой проблематики нами выбраны две теоремы Гёделя – теорема о полноте и теорема о неполноте, сыгравшие в развитии метаматематики выдающуюся роль и вызвавшие резонанс далеко за пределами математики. Изложение доказательств этих теорем доведено до некоторого промежуточного уровня детализации, позволяющего, с одной стороны, изложить идеологию доказательства и не слишком погрешить против строгости доказательства, с другой стороны. Наконец, в конце приведены два Приложения, содержащие самостоятельные результаты исследований автора по рассматриваемой проблематике и выполненные в рамках все той же методологии представления математической логики, какой мы ее находим у Дж.Шенфилда. Причем именно у этого автора мы можем обнаружить наиболее обнаженное представление видимой противоречивости двух теорем Гёделя, в то время как другие авторы стараются по возможности не акцентировать внимание
3
на этой проблеме. Мы пытаемся по возможности разъяснить существующее здесь положение дел, используя, с одной стороны, понятия двух видов полноты теории (“семантической” и “синтаксической” полноты), и, с другой стороны, выдвигаем проект нового подхода к трактовке видимого противоречия между первой и второй теоремами Гёделя. В проведении этого подхода мы опять-таки опираемся на Шенфилда, высказавшего в качестве объяснения конфликта теорем Гёделя идею двух смыслов – финитного и нефинитного - понятия “теорема”. Мы не ставили себе целью в данном пособии снабдить каждый из разделов обширной подборкой задач. При желании читатель может найти примеры таких задач в учебнике Дж.Шенфилда, мы же ограничились в нашем изложении некоторым минимумом возможных задач и примеров.
1. Природа математической логики Метаматематика – это направление математики, исследующее средствами математики математическое мышление: логику математических доказательств, структуру математического языка, условия построения математической теории, соотношение теории и ее моделей и т.д. Понятие «математическая логика» обычно трактуют либо как синоним понятия «метаматематика», либо рассматривают как раздел метаматематики, в большей мере имеющий дело с чисто логической стороной метаматематических исследований. Основные понятия метаматематики – формальная теория и ее модель. Мир математики – это во многом мир логики. Математик чаще всего имеет дело с аксиоматическими теориями, в которых выделены: 1) базовые понятия и 2) аксиомы, на основе которых определяются производные понятия и выводятся теоремы, описывающие свойства и отношения базовых и производных понятий. Обычно математик осуществляет построение аксиоматической теории в рамках так называемого содержательного подхода, не слишком сильно формализуя язык и средства аксиоматизации теории. Метод математической логики, составляющий основу метаматематики, предполагает существенное повышение степени формализации аксиоматической теории, что приводит к построению формальной аксиоматической теории. Формальная аксиоматическая теория (ФАТ) – одно из ключевых понятий математической логики и метаматематики. ФАТ – это ЯЗЫК + АКСИОМЫ + ЛОГИЧЕСКИЕ ПРАВИЛА ВЫВОДА. Отдельно для формальной аксиоматической теории определяется понятие «модели» (синонимы: «структура», «интерпретация») этой теории.
2. Язык первого порядка Любой язык предполагает некоторый алфавит символов, из которых, как упорядоченные n-ки строятся по некоторым правилам слова (выражения) этого языка. Формальное описание языка предполагает описание множества его
4
правильно построенных (в чисто формальном смысле) выражений на основе алфавита этого языка. Ниже мы описываем простейший, но одновременно и основной случай формального языка – так называемый язык первого порядка (ЯПП). Одновременно мы будем сопровождать это описание некоторым примером такого языка. 1.1.Алфавит языка первого порядка. Алфавит ЯПП рассматривается как множество следующих элементов: (а) переменные: x, y, z, x’, y’, z’, x’’, y’’, z’’, … (b) n-арные функциональные символы вида: f1( 1, 2, …, n), f2( 1, 2, …, n), … , fN( 1, 2, …, n), (здесь « » – обозначение пустого места. Само это обозначение, как и скобки, не относится к ЯПП, а используется как сокращение в метаязыке (см. ниже)). n-арные предикатные символы вида: P1( 1, 2, …, n), Р2( 1, 2, …, n), … , РМ( 1, 2, …, n). (c) символы: , ∨, ∃. (а)+ (с) – это логические символы, (b) – нелогические символы. М и N – это функции от n=0,1,2,…, т.е. М=М(n) и N=N(n). Только значениями этих функций и видом нелогических символов могут различаться между собою алфавиты ЯПП. Логические символы считаются одинаковыми у всех ЯПП. 0арные функциональные символы называются константами. Считается также, что в алфавитах всех ЯПП есть бинарный (n=2) предикатный символ равенства =L, который большинством логиков также рассматривается как логический символ. Будем рассматривать как пример некоторый ЯПП L(N), в котором следующие нелогические символы: Функциональные символы: Для n=0 введена константа 0, Для n=1 унарный функциональный символ S( ), Для n=2 бинарные функциональные символы ⊕( 1, 2), ⊗( 1, 2). Предикатные символы: Определен только для n=2 (кроме равенства): ∠( 1, 2) Заметим, что в момент построения ЯПП мы также пользуемся языком, а именно русским языком. ЯПП, который мы сейчас строим, обычно называется объектным языком, а язык, используемый для построения ЯПП (в данном случае русский язык), - метаязыком. Если объектный язык формализован, то метаязык обычно достаточно содержателен, т.е. существенно меньше формализован. В метаязыке (!) мы будем использовать переменные для обозначения выражений объектного языка (см. ниже) - так называемые
5
синтаксические переменные. Мы будем использовать жирный шрифт и следующие символы: x, y, z – для синтаксических переменных, пробегающих множество объектных переменных, f, g - для синтаксических переменных по функциональным символам, p, q – по предикатным символам, е - по константам, А, В, С, D – по формулам, а, b, c, d – по термам, u, v - по всем выражениям объектного языка. Эти переменные допускают индексацию. Следующий шаг построения ЯПП – построение выражений языка. Выражения ЯПП – это термы и формулы. 1.1.Выражения ЯПП. Выражения определяются по индукции. (а) Термы ЯПП: (i) Переменная есть терм (ii) Если u1, …, un – термы и f – n-арный функциональный символ, то f(u1, …,un) – терм. (iii) Никаких иных термов нет. (b) Формулы ЯПП: (i) Если а1, …, аn – термы и р – n-арный предикатный символ, то р(а1, …, аn) есть формула. (ii) Если u – формула, то u – формула. (iii) Если u и v – формулы, то u ∨ v – формула. (iv) Если u –формула и х – переменная, то ∃хu – формула. (v) Никаких иных формул нет. Случай (b) (i) называется случаем атомарной формулы. Итак, ЯПП – это пара (алфавит языка, выражения языка). Задание: 1. Напишите определения для выражений языка L(N) и приведите конкретные примеры термов и формул этого языка. 2. Используя индуктивные определения термов и формул, покажите, что результат замены терма а на переменную х в терме есть терм и что результат замены терма а на переменную х в формуле есть формула.
3. Семантика языка первого порядка ЯПП определяется формально – как абстрактное множество из символов и выражений. Это дань формальному подходу в математической логике вообще. Но всякий содержательный язык – это еще и смысл языка, его интерпретация. Аналог этого понятия для ЯПП – понятие «структуры» ЯПП.
6
Пусть L – некоторый ЯПП. Структура А для L – это тройка из: (i) непустого множества |A| - универсума А (элементы |А| - индивиды А) (ii) множества всех n-арных функций fA: |A|n→|A|, взаимно-однозначно сопоставленных каждому n-арному функциональному символу f из L (в частности, еА – индивид из А для константы е из L). (iii) Множества всех n-арных предикатов рА: |A|n→{И,Л}, взаимнооднозначно сопоставленных каждому n-арному предикатному символу р из L для каждого n. Например, структура А для L(N) – это тройка из: (i) непустого множества |A|, (ii) множества {0, S, +, ⋅}, где 1) 0 сопоставлен константе 0 и 0 ∈ |A|, 2) S сопоставлена S, и S: |A|→|A|, 3) + сопоставлена ⊕ и +: |A|2→|A|, ⋅ сопоставлена ⊗ и ⋅ : |A|2→|A|. 4) (iii) множества { =, < }, где 1) = сопоставлен =L и = - бинарный предикат равенства на |A|, т.е. диагональ множества |A|2, 2) < сопоставлен ∠ и < : |A|2→{И,Л}. Пока на А не накладывается больше никаких требований, кроме указанных. Например, в качестве структуры А для L(N) может выступить тройка из 1)множества {17}; 2)множества функций, где 0=17, S(17)=17, 17+17=17, 17⋅17=17; и 3)множества предикатов, где предикат < совпадает с равенством. В общем случае поименованы в ЯПП L только те индивиды из А, которые сопоставлены с константами L. Задача выражения истинности выражений L в А требует возможности для каждого индивида А иметь свое имя. С этой целью язык L может быть пополнен константами-именами для всех индивидов А. Именно, вводится множество констант, биективно сопоставленное |A|. Добавлением этих констант к L мы получаем новый язык L(А) первого порядка, отличающийся в алфавите от L только по добавленным константам (будем называть их «именами»). Изменения в выражениях L(А) относительно L выразятся в образовании тех же термов и формул, что и в L, но плюс еще с возможностью подстановок на место переменных в этих выражениях новых констант. Через i и j обозначим синтаксические переменные по добавленным константам (именам) в L(А). Например, для языка L(N) мы получаем язык L(N)[A] относительно описанной структуры А добавлением к функциональным символам имени для индивида 17, например, константы 17. Термами L(N)[A], кроме термов L(N), будут, например, такие: 17⊗0, х⊕17, S(17), и т.д.
7
Ясно, что это расширение множества термов приведет и к расширению множества формул L(N)[A] сравнительно с таковым в L(N), например, кроме формул L(N), появятся формулы вида: 17 =L y, ∃х(х∠17) и т.д. Теперь, имея базовые соответствия между нелогическими символами из L(А) и объектами из А, мы можем продолжить это соответствие на все термы и формулы, не содержащие свободных переменных (ведь именно такие выражения важны в связи с определением конкретного истинностного значения). Логический символ ∃ называется квантором существования. В термы и атомарные формулы переменные всегда входят свободно. Если переменная х входит свободно в формулу А, то в формуле ∃хА переменная х считается связанной (не свободной). Определим теперь функцию интерпретации А: ТС→|A|, где ТС – множество термов из L(А), не содержащих переменных (замкнутые термы). Функция А постулативно определена для терма а из ТС, если а = i – имя индивида А (т.е. константа, добавленная к L при построении L(A)): в этом случае А(а) и есть этот индивид. Если а – константа и не имя, т.е. а = е, то построением структуры А для L с а сопоставлен некоторый индивид еА из А: тогда А(а) = еА. Если же а ∈ ТС и а - не константа, то а = f(а1, …,аn), причем, f первично сопоставлена функция fA из A. Тогда, используя индуктивное определение замкнутых термов, мы можем предполагать, что для а1, …,аn уже определены индивиды А: А(а1), …,А(аn), и в этом случае: А(а)=fA(A(a1), …,A(an)). Таким образом, мы можем любому терму а из ТС поставить в соответствие единственный объект А(а) – индивид А. Например, для нашего языка L(N)[A] уже самим заданием структуры А определено, что А(17) = А(0) = 17. Далее получаем: А(S(a)) = S(A(a)), A(a1⊕a2) = A(a1) + A(a2), A(a1⊗a2) = A(a1) ⋅ A(a2). Т.о. функция А может быть определена индуктивно для всех замкнутых термов из L(N)[A]. Например: A(17⊕ 0) = A(17) + A(0) = 17 + 17 = 17, A(S(0⊗17)) = S(A(0⊗17)) = S(A(0) ⋅ A(17)) = S(17 ⋅17) = S(17) = 17. Далее определим функцию истинности (интерпретации) А: FC→{И,Л} для FC – множества всех замкнутых формул из L(А), т.е. формул, не содержащих свободных вхождений переменных. Элементы «И» и «Л» интерпретируются как истинностные значения, т.е. значения «истина» и «ложь» соотв. Вновь используем индуктивное определение формул. Базис индукции: пусть А – атомарная формула из FC, т.е. А = р(а1,…,аn). Для термов а1,…,аn уже определены интерпретации А(а1),…,А(аn), т.к. они из ТС. Кроме того, определением структуры А для L предикатному символу р из L
8
сопоставлен предикат рА из А. Тогда определено истинностное значение рА(А(а1),…,А(аn)). Его и обозначим через А(А). Например, для случая языка L(N)[A] получим: А(а1 =L а2) = А(а1) = А(а2) (т.е. истинностное значение формулы а1 =L а2 равно истинностному значению предиката = на паре (А(а1), А(а2))), А(а1 ∠ а2) = А(а1) < А(а2). Здесь а1, а2 – термы без переменных, и для них уже определены интерпретации А(а1) и А(а2). Индуктивное предположение: 1)Пусть А = В и для В определено А(А) = Н(В), где истинностное значение А(В). Тогда положим: Н:{И,Л}→{И,Л} – унарная истинностная функция (отрицание), и Н(И) = Л, Н(Л) = И. 2) Пусть А =В∨С и для В,С определены А(В) и А(С). Тогда положим: А(А) = Н∨ (А(В),А(С)), Где Н∨: {И,Л}2→{И,Л} – бинарная истинностная функция (дизъюнкция), табличное задание которой имеет вид: Х И И Л Л
Y И Л И Л
H∨ ∨(X,Y) И И И Л
3) Наконец, пусть А = ∃хВ и А – замкнутая формула. Тогда в В либо нет свободных вхождений переменных и здесь полагаем по определению: А = В, либо свободно в В по крайней мере одно вхождение переменной х, т.е. В = В(х) и тогда В не является замкнутой формулой. В первом случае функция А определена для В и А(А) = А(В). Во втором случае функция А не определена для В. Однако, А определена для каждой Вх[i] – результата подстановки i на места вхождения х в В(х) (в общем случае Ах[а] – обозначение формулы, полученной в результате правильной подстановки терма а на места свободного вхождения переменной х в А. Правильность (допустимость) подстановки состоит в том требовании, чтобы переменные из а не оказывались связанными в Ах[а] – если последнюю понимать как просто результат замены свободных вхождений х в А на а. Этого всегда можно добиться переименованием связанных переменных: подробнее см. [5, С.34-35]), где i – имя индивида из структуры А (добавленная константа L(А)), т.к. Вх[i] – замкнутая формула. В этом случае положим: А(А) = И тогда и только тогда, когда найдется по крайней мере одно имя i такое (или один индивид А(i) такой), что А(Вх[i]) = И. Например, для случая языка L(N)[A] имеем: А(∃х(х∠17)) = Н(А(∃х(х∠17))) = Н(найдется хотя бы один А(i) такой, что А((х∠17)х[i])=И). Так как в формуле (х∠17) нет кванторов, то любая подстановка на место х допустима, и
9
(х∠17)х[i] = (i∠17). В нашем случае i пробегает по одноэлементному множеству {17}, т.е. все возможности исчерпываются только одним случаем: 17∠17. Но А(17∠17) = А(17) < А(17) = 17 < 17 = И. Таким образом, нужный i найдется, и А(∃х(х∠17)) = И. Итак, окончательно имеем: А(∃х(х∠17)) = Н(И) = Л – истинностное значение формулы ∃х(х∠17) языка L(N)[A] в рассматриваемой нами структуре А найдено. Тем самым задается семантика ЯПП L и в общем случае. Напомним ее основные этапы: 1. Введение структуры А для языка L. 2. Построение языка L(A). 3. Построение функции интерпретации А:ЕС→I для ЕС – выражений L(А), не содержащих свободных вхождений переменных. ЕС = ТС ∪FC, I = |A| для ТС и I = {И,Л} для FC. Т.о. под семантикой ЯПП L можно понимать пару (структура А, функция интерпретации А). Семантика L – это не L (условие формальности L). Введением семантики выражения языка L приобретают значение. Функциональные символы интерпретируются как имена функций из А, предикатные символы – как имена предикатов, термы из ТС – как имена индивидов А, формулы из FC – как имена утверждений об объектах А вида: А - неверно, что А(А) А∨В А(А) или А(В) ∃хА существует такой А(i), что А(Ах(i)) Заметим, что при описанном нами подходе не получают интерпретации переменные и выражения, содержащие свободные вхождения переменных. Они рассматриваются как чисто знаковые (синтаксические) сущности, принадлежащие только языку. Такой подход не единственный, но именно он позволяет добиться существенных упрощений при определении семантики языка. Пусть А – формула L, и все переменные, имеющие свободные вхождения в формулу А, содержатся среди переменных х1,…,хn. Тогда А можно обозначать как А(х1,…,хn). А соответствует множество замкнутых формул из FC вида А[i1,…,in] – А-частные случаи формулы А. Тогда положим: А(А) = И тогда и только тогда, когда А(А′′) = И для каждого А-частного случая А′′ формулы А. Задание: 1. Дайте индуктивные определения для замкнутых термов и формул языка первого порядка. 2. Дайте индуктивные определения замкнутых термов и формул для языка L(N). 3. Определите семантику языка первого порядка, используя индуктивное определение замкнутых выражений языка первого порядка.
10
4. Логика в языке первого порядка Итак, построен некоторый язык L. Пока множество формул L – это некоторое абстрактное множество рядоположенных элементов. Следующий шаг построения ФАТ состоит в построении логики в L. Для этого в L выделяют некоторое множество формул, которые называют логическими аксиомами, и определяют правила вывода. Будем обозначать через ∀хА формулу (∃х(А)), А→В формулу (А)∨В, А∧В формулу ((А)∨(В)), А↔В формулу (А→В)∧(В→А) Каждое сокращение, например, ∀хА, - это выражение из метаязыка, но для него указано правило перевода в соответствующую формулу объектного языка, что позволяет нам использовать сокращения при работе с объектным языком (то же относится и к употреблению скобок). Через формулу (А1→А2→…→Аn)→В мы будем сокращать формулу (А1∧А2∧…∧Аn)→В. В качестве логических аксиом L выделяются следующие формулы L (см. [5, С.41]): LA1. А∨А – пропозициональная аксиома, LA2. Ах[а]→∃хА – аксиома подстановки, LA3. х =L х – аксиома тождества, LA4. Аксиома равенства: LA4.1. x1=Ly1→…→xn=Lyn→f(x1,…,xn)=Lf(y1,…,yn) – для функциональных символов, LA4.2. x1= Ly1→…→xn= Lyn→р(x1,…,xn)→р(y1,…,yn) – для предикатных символов. Заметим, что логические аксиомы формулируются в терминах синтаксических переменных, т.е. каждый случай аксиомы – это бесконечное множество формул из объектного языка (так называемая схема аксиом). Следующий шаг построения логики в L состоит в определении правил вывода. Каждое правило вывода формулируется как переход от формул А1, …, Аn (посылок) к формуле В (заключению). Мы будем изображать это в виде А1, …,Аn ├В. Правила вывода в L (см. [5, С.41]): С1. А├В∨А – правило расширения. С2. А∨А├А – правило сокращения. С3. А∨(В∨С) ├ (А∨В)∨С – правило ассоциативности. С4. А∨В, (А)∨С├В∨С – правило сечения. С5. Если х не имеет свободных вхождений в В, то А→В├∃хА→В – правило ∃-введения.
11
Задание: Покажите, что: 1. Если А – логическая аксиома, то А(А) = И для любой структуры А. 2. Если дан вывод А1,…,Аn├В и А(А1) = И,…, А(Аn) = И, то А(В) = И для любой структуры А.
5. Теория первого порядка При построении ФАТ в нее обязательно входят логические аксиомы, но, возможно, добавляются еще некоторые формулы, как отдельные формулы или схемы аксиом, которые называются нелогическими аксиомами теории. Итак, формальная аксиоматическая теория (первого порядка) Т – это тройка (язык L, нелогические аксиомы Т, правила вывода). Язык теории Т будем обозначать через L(T). Под доказательством в Т понимают конечную последовательность А1,…,Аn формул из L(T), где каждая Аi – это либо аксиома Т (логическая или нелогическая), либо Аi следует по одному из правил вывода из предшествующих формул в указанной последовательности. Доказательство считается доказательством своей последней формулы Аn. Теории первого порядка могут различаться между собой только нелогическими символами языка и нелогическими аксиомами, все остальное дано уже по общему определению теории. В связи с этим, для задания теории достаточно явно указать только на ее нелогические аксиомы и нелогические символы ее языка. Моделью теории Т называется такая структура языка L(T), в которой истинны все нелогические аксиомы Т. Формула А из L(T) называется истинной в Т, если она истинна в каждой модели Т. Приведем два примера теорий первого порядка: теории N и теории Р. У этих теорий зададим один и тот же язык, а именно рассмотренный нами выше язык L(N). Таким образом, для определения этих теорий остается лишь привести списки их нелогических аксиом. Нелогические аксиомы теории N (см [5, С.43]): N1. (S(x) =L 0) N2. S(x) =L S(y)→x =L y N3. x⊕0 =L x N4. x⊕S(y) =L S(x⊕y) N5. x⊗0 =L 0 N6. x⊗S(y) =L (x⊗y)⊕x N7. (x ∠ 0) N8. x ∠ S(y) ↔ (x ∠ y) ∨ (x =L y) N9. (x ∠ y) ∨ (x =L y) ∨ (y ∠ x)
12
Заметим, что все аксиомы N – отдельные формулы, т.к. в них использованы объектные переменные. Нелогические аксиомы теории Р (арифметики Пеано) (см. [5, С.300]): В теории Р девять аксиом. Аксиомы Р1 – Р8 – это аксиомы N1 – N8 соотв. Р9. Ах[0] ∧ ∀х(А→Ах[S(x)])→A Аксиома Р9 – это схема аксиом индукции, т.к. в ней используются синтаксические переменные. Структура А на множестве {17}, рассмотренная нами выше, не может быть моделью теорий N и Р (хотя это структура для языков этих теорий), т.к. в ней не выполнена уже первая аксиома. Моделью для этих теорий будет, например, структура на обычном множестве натуральных чисел с выделенным элементом 1 или 0 (сопоставленным константе 0), в зависимости от того, как понимается множество натуральных чисел; функциями S (сопоставляется символу S) – взятия последующего, сложения (+ - сопоставляется ⊕) и умножения (⋅ сопоставляется ⊗), и отношением строгого порядка (< - сопоставляется ∠). Эта структура называется стандартной моделью обеих теорий и будет обозначаться нами символом N. Задание: 1. Докажите, что если Т – некоторая теория первого порядка и А – формула теории Т (т.е. формула из языка L(T) теории Т), то А – теорема теории Т тогда и только тогда, когда в Т существует доказательство формулы А. 2. Докажите так называемую «теорему истинности»: если формула А – теорема теории Т, то А истинна в Т.
6. Пример одной типичной задачи Задача: доказать, что формула (х=х)∨(х=х) – теорема теории Т, не доказуемая без пропозициональной аксиомы, если теория Т не содержит нелогических аксиом. Решение: во-первых, указанная формула – это теорема, т.к. она получена как частный случай пропозициональной аксиомы. Введем далее функцию f на множестве формул, ForT, теории Т f: ForT →{И,Л}, где 1) f(A) = И, если А – атомарная формула, 2) f(A) = Л для любой формулы А, 3) f(A∨B) = f(B), 4) f(∃xA) = И. Определим, чему равна введенная функция на аксиомах Т (в нашем случае это только логические аксиомы). LА1. f(A∨A) = f(A) = Л,
13
LА2. f(Ax[a]→∃xA) = f(Ax[a]∨∃xA) = f(∃xA) = И, LА3. f(x= Lx) = И, т.к. х= Lх – атомарная формула, LА4.1. f(x1=Ly1→…→xn=Lyn→f(x1,…,xn)=Lf(y1,…,yn)) = f(f(x1,…,xn)=Lf(y1,…,yn)) = И, т.к. f(x1,…,xn)=Lf(y1,…,yn) – атомарная формула, = LA4.2. f(x1=Ly1→…→xn=Lyn→р(x1,…,xn)→р(y1,…,yn)) f(р(x1,…,xn)→р(y1,…,yn)) = f(р(x1,…,xn)∨р(y1,…,yn)) = f(р(y1,…,yn)) = И, т.к. р(y1,…,yn) – атомарная формула. Итак, функция f определена таким образом, что она дает «ложь» только на пропозициональной аксиоме. На всех остальных логических аксиомах эта функция дает значение «истина». Рассмотрим далее, какие значения принимает функция f на заключениях логических выводов, если на посылках этих выводов она дает значение «истина». С1. Пусть f(A) = И, и А├ В∨А. Тогда f(B∨A) = f(A) = И. С2. Пусть f(A∨A) = И и А∨А├А. Тогда f(A) = f(A∨A) = И. С3. Пусть f(A∨(B∨C)) = И и А∨(В∨С)├ ((А∨В)∨С). Тогда f((A∨B)∨C) = f(C) = f(A∨(B∨C)) = И. С4. Пусть f(A∨B) = И и f(A∨C) = И и А∨В, А∨С ├ В∨С. Тогда f(B∨C) = f(C) = f(A∨C) = И. С5. Пусть f(A→B) = И и А→В ├ ∃хА→В. Тогда f(∃xA→B) = f(B) = f(A→B) = И. Итак, введенная нами функция f такова, что 1)она дает значение «истина» на всех аксиомах, кроме пропозициональной аксиомы, и 2)если на посылках вывода функция f дает значение «истина», то и на заключении этого вывода она дает значение «истина». В то же время для нашей формулы (х=х)∨(х=х) имеем: f((х=х)∨(х=х)) = f((х=х)) = Л. Таким образом, эта формула не может быть выведена без пропозициональной аксиомы, т.к. на всех теоремах, выводимых без пропозициональной аксиомы, функция f дает значение «истина», в то время как на нашей формуле она дает значение «ложь». Задание: Используя описанную выше методику, покажите, что формула х=х→∃х(х=х) является теоремой теории Т, не доказуемой без аксиомы подстановки, если Т – теория без нелогических аксиом (здесь используйте такое А, отображение f, что f(A)=И для атомарных f(A)=H(f(A)), f(A∨B)=H∨(f(A),f(B)), f(∃xA)=Л).
14
7. Индуктивные определения в математической логике Как видно из вышеизложенного, в математической логике важную роль играют индуктивные определения, общий вид которых можно представить следующим образом. Пусть определяется некоторое индуктивное множество А. Для определения А определяют, во-первых, некоторые базисные множества А1, А2, …, АN, являющиеся подмножествами А, а затем вводят правила индуктивного расширения Р1, Р2, …, РM, которые можно применять к элементам уже построенных подмножеств А, получая вновь элементы А. Наконец, добавляется требование минимальности множества А как индуктивного множества. Таким образом, полное определение множества А предстает в виде трех частей – базиса индукции, индуктивного предположения и требования минимальности: (1) Элементы множеств А1, А2, …, АN – элементы множества А (базис индукции), (2) Если а1, а2, …, аkj – элементы множества А и отображение Рj , j=1,2,…,M, имеет местность kj, то Р(а1,а2,…,аkj) – элемент множества А (индуктивное предположение). (3) Никаких иных элементов в А нет (минимальность множества А). Здесь а1, а2, …, аkj – это переменные по элементам множества А. В такой форме давались определения множества термов и формул языка первого порядка. Например, для множества формул языка первого порядка в качестве базиса индукции используется множество атомарных формул, а в качестве принципов индуктивного расширения в индуктивном предположении 2)двуместное используются: 1)одноместное отображение Р(А)=А, отображение Р∨(А,В)=А∨В, 3)одноместные отображения Р∃х(А)=∃хА. Имеет смысл обращать внимание студентов на механизм действия индуктивных определений. Следует пояснить, что индуктивное множество А прирастает как бы слоями – вначале образуется объединение базисных N
множеств А1= Υ A i , затем это множество пополняется за счет принципов i =1
расширения до множества А2, затем принципы расширения начинают действовать на множество А2, расширяя его до множества А3, и т.д. Таким образом, множество А возникает как бесконечное объединение своих “слоёв” ∞
А , А , А , …, т.е. А= Υ A i. 1
2
3
i =1
Следует также отметить, что именно индуктивные определения позволяют доказывать те или иные утверждения для всех элементов индуктивного множества. Если нужно доказать, что каждый элемент индуктивного множества А обладает некоторым свойством Q, то для этого достаточно показать, что: (1) Свойство Q выполнено для элементов множеств А1, А2, …, АN (базис индукции),
15
(2) Из того, что свойство Q выполнено для элементов а1, а2, …, аkj следует, что это свойство верно для элементов Р(а1,а2,…,аkj), где Рj , j=1,2,…,M, имеет местность kj (индуктивное предположение). Например, такое доказательство используется в теореме истинности, где нужно доказать, что всякая теорема теории Т истинна во всех моделях теории Т. В этом случае индуктивным множеством является множество теорем теории Т. Базисным множеством здесь служит множество логических и нелогических аксиом, в качестве принципов индуктивного расширения выступают правила вывода. Таким образом, для доказательства теоремы истинности нам достаточно убедиться в том, что 1)всякая аксиома теории Т истинна в любой модели Т, 2)если в любой модели теории Т истинны посылки логического вывода, то истинным в этой модели Т будет и заключение вывода.
8. Теорема о полноте теорий первого порядка (первая теорема Гёделя) Для формулировки теоремы полноты дадим ряд предварительных определений и теорем. Определение. Язык L’ называется расширением языка L, если из того, что α нелогический символ L, вытекает, что α - нелогический символ L’. Определение. Теория Т* называется расширением теории Т, если L(Т*) – расширение языка L(Т) и из того, что А – теорема Т, следует, что А – теорема Т*. Определение. Теория Т* называется консервативным расширением теории Т, если Т* - расширение Т, и для любой формулы А из Т верно: если А – теорема Т*, то А – теорема Т. Определение. Пусть А – формула и х1,…,хn – все переменные, имеющие свободные вхождения в А. Тогда формула ∀х1…∀хnА называется замыканием формулы А. Через ├ТА мы будем обозначать тот факт, что А – теорема теории Т. Определение. Теория Т называется противоречивой, если ├ТА для любой формулы А из Т. В противном случае Т называется непротиворечивой. Через Т[А1,…,Аn] будем обозначать теорию Т*, образованную из Т добавлением ее формул А1,…,Аn в качестве новых нелогических аксиом Т*. Если Г = {А1,…,Аn}, то Т* = Т[Г]. Могут быть доказаны следующие теоремы: Теорема истинности [5, С.44]. Если ├ТА, то А истинна в Т. Теорема замыкания [5, С.56]. Если А* - замыкание А и А – формула Т, то ├ТА* тогда и только тогда, когда ├ТА.
16
Теорема замыкания (следствие) [5, С.56]. Если А* - замыкание А и А – формула Т, то А(А) = И тогда и только тогда, когда А(А*) = И для любой структуры А языка L(T). Теорема о константах [5, С.57]. Пусть Т* получена из Т только добавлением новых констант в L(T). Если А(х1,…,хn) – формула Т, где х1,…,хn – все переменные, имеющие свободные вхождения в А, и е1,…,еn – любой набор новых констант, то ├ТА т. и т.т., когда ├Т*А(е1,…,еn), где А(е1,…,еn) – результат подстановки еi на места свободных вхождений хi. Теорема редукции [5, С.70]. Пусть А* - замыкание А, и А – формула теории Т. Тогда ├ТА т. и т.т., когда Т[А*] противоречива. Ниже, используя эти теоремы и определения, мы рассмотрим одну из центральных теорем метаматематики – теорему полноты, в той формулировке, как она дана в [5]. Дж.Шенфилд дает эту теорему в двух формулировках (см. [5,С.70]): Теорема полноты (1-я форма). Пусть А – формула теории первого порядка Т. Тогда: ├ТА т. и т.т., когда А истинна в Т (т.е. А истинна в каждой модели Т как структуре для L(T)). Теорема полноты (2-я форма). Пусть Т – теория первого порядка. Тогда: Т непротиворечива т. и т.т., когда Т имеет модель. Ход доказательства строится Шенфилдом в следующем виде (в предположении, что А – замкнутая формула): А - теорема Т ↕ Теорема редукции Т[А] противоречива ↕ Теорема полноты (2-я форма) Т[А] не имеет модели ↕ по определению Все модели Т таковы, что в них А истинна ↕ по определению А истинна в Т Таким образом, достаточно доказать вторую форму теоремы полноты для доказательства ее первой формы. В силу теоремы замыкания и следствия из нее, первую форму теоремы полноты достаточно доказать только для замкнутых формул Т. Доказательство достаточности (если Т имеет модель, то Т непротиворечива) во 2-й форме теоремы полноты простое. Именно: Теория Т противоречива т. и т.т., когда ├ТВ∧В для некоторой формулы В из Т. В самом деле, можно доказать, что В∧В├ТС, т.е. из В∧В выводима в Т любая формула С. Пусть Т имеет модель. Нужно доказать, что Т непротиворечива. Для этого нужно показать существование формулы А такой, что неверно ├ТА. Пусть В – замкнутая формула из Т, тогда А(В∧В) = Л для
17
любой модели Т, т.е., по теореме истинности, неверно, что ├ТВ∧В, т.е. А = В ∧В. Гораздо сложнее доказательство необходимости во второй форме теоремы полноты: если Т непротиворечива, то Т имеет модель. Здесь в условиях дан только синтаксический объект – формальная теория Т. Построить же нужно семантический объект – модель Т. Основная идея решения этой проблемы состоит в построении модели на основе синтаксиса теории, как бы из материала синтаксиса. Модель Т – это, во-первых, структура А для языка L(T), т.е. нужно построить множество индивидов (универсум) |A|, ввести функции и предикаты, соотнесенные с соответствующими символами языка. Затем необходимо обеспечить семантику для L(T), т.е. для всех замкнутых формул языка, причем, выполняя условия модельности, это необходимо осуществить таким образом, чтобы все теоремы Т были истинны в А. Основные идеи решения всех этих задач следующие: 1.На множестве замкнутых термов ТС из L(T), т.е. на термах, не содержащих переменных, вводится отношение эквивалентности ≈ вида: Если а,в – замкнутые термы, то а ≈ в т. и т.т., когда ├Та=Lв (где «=L» – символ равенства в языке L(T)). Чтобы ТС было не пусто, необходимо, чтобы L(T) содержал константы (иначе нечем будет замыкать термы). 2.Множество ТС разбивается ≈ на классы эквивалентности, т.е. возникает фактор-множество ТС/≈, которое и рассматривают в качестве универсума |A| модели. Т.о. индивид А – это класс эквивалентности из ТС/≈ (о проверке свойств эквивалентности см.[5, С.72]). Если а – замкнутый терм, то через а0 будем обозначать его класс эквивалентности. 3.Для каждого функционального символа f( 1,…, n) строится функция fA на ТС/≈ по правилу: fA(а10,…,аn0) = [f(а1,…,аn)]0. 4.Для каждого предикатного символа р( 1,…, n) строится предикат рА на ТС/≈ по правилу: рA(а10,…,аn0) = И т. и т.т., когда ├Т рA(а1,…,аn). 5.Доказывается корректность этих определений, т.е. независимость от конкретного представителя из класса эквивалентности (см. [5, С.72]). 6.Теперь можно определить функцию интерпретации для всех замкнутых термов. Для констант, как 0-местных функциональных символов, имеем: А(е) = е0. Используя индуктивное определение замкнутых термов, получим: А(а) = А(f(а1,…,аn)) = fA(A(a1),…,A(an)) = fA(a10,…,аn0) = [f(a1,…,an)]0. Т.о. А(а) = а0 для всех замкнутых термов. 7.Далее, пусть А = р(а1,…,аn) – замкнутая атомарная формула. Тогда: А(A)= А(pA(A(a1),…,A(an))) = A(pA(a10,…,an0))=И т. и т.т., когда ├Tp(a1,…,an) т. и т.т., когда ├TA. Т.о. А(А) = И т. и т.т., когда ├ТА. То же верно и для предиката равенства. Теперь можно было бы попытаться доказать для более общего случая, что А(А) = И т. и т.т., когда ├ТА, т.е. для любой замкнутой формулы А. Однако здесь мы сталкиваемся со следующими трудностями.
18
8. Во-первых, возможно, что не все индивиды представимы в Т через замкнутые термы. Именно, возможен случай теоремы существования ├Т∃хА для некоторого х, когда этот х, вернее, его интерпретация – индивид, не может быть выражен через замкнутый терм а (в простейшем случае константу е) из Т. Замкнутых термов, иными словами, может не хватать для выражения всех индивидов, представимых в Т через теоремы существования (проблема индивидной представимости Т). 9. Во-вторых, коль скоро интерпретация замкнутых формул связывается с доказуемостью этих формул в Т, то может возникать вторая проблема: в конкретной теории Т совсем не обязательно доказуемость может распространяться на любую замкнутую формулу или ее отрицание (проблема пропозициональной представимости Т), и в этом случае определить интерпретацию для всех замкнутых формул не удастся. Структура, описание которой было приведено выше и которая строится из синтаксиса теории, называется канонической структурой для Т. В общем случае, как мы видим, каноническая структура для Т не может обеспечить построение модели Т. Однако, возможно следующее дальнейшее построение: 1. От теории Т мы переходим к некоторой теории Т*. 2. Теория Т* должна удовлетворять условиям индивидной и пропозициональной представимости. Тогда каноническая структура Т* должна быть моделью Т*. 3. Наконец, Т* следует построить так, чтобы на основе модели Т* можно было бы построить модель Т. Теории, в которых решена проблема индивидной представимости, носят название теорий Генкина. Именно: Т – теория Генкина, если для всякой замкнутой (!) формулы ∃хА из Т существует константа е такая, что ├Т∃хА→Ах[е]. Формула А из Т называется неразрешимой в Т, если ни А, ни А не являются теоремами Т. В противном случае А называется разрешимой. Теории с решенной проблемой пропозициональной представимости носят название полных теорий. Именно: Т – полная теория, если Т непротиворечива и любая замкнутая (!) формула Т разрешима в Т. Можно доказать (см. [5, С.74-75]), что, если Т – полная теория Генкина, то: 1) А(А) = И т. и т.т., когда ├ТА для любой замкнутой А (именно для доказательства этого факта нужны специальные аксиомы (см. ниже) – они используются при доказательстве утверждения «если ├Т∃хВ, то А(∃хВ) = И»). 2) Каноническая структура для Т – модель Т. Итак, теперь основная проблема состоит в том, чтобы на основе любой теории Т построить ее расширение Т*, где Т* - полная теория Генкина, и использовать модель Т* для построения модели Т. Построение Т* ведется в два этапа: 1) сначала Т расширяют до некоторой ТН, где ТН – теория Генкина, 2)затем ТН расширяют до полной теории Т*, причем, это расширение до полной теории осуществляют так, чтобы с приобретением