Логика l-противоречий

Вид материала

Документы

Содержание Док-во. См. теоремы 1 и 2.Определение 8 Док-во. См. теоремы 4 и 5.Определение 10

Подобный материал:

• Программа курса и темы практических занятий; Логика в таблицах и схемах. Логика как, 1722.34kb.
• Логика в образовании, 153.37kb.
• Математическая логика, 1012.22kb.
• Логика богочеловечества, 213.06kb.
• Предмет и метод экономической теории, 510.25kb.
• Н. В. Папуловская Математическая логика Методическое пособие, 786.38kb.
• Основы логики. Логика, 20.66kb.
• А. А. Ивин логика учебное пособие, 3160.22kb.
• Вопросы к экзамену по дисциплине «Логика», 15.87kb.
• А. А. Ивин логика учебное пособие, 3123.01kb.

a^j_n _f a^j для каждого j, и существуют теоремы теории Т вида b^h_n _f b^h для каждого h. Пусть переменные z₁, z₂, …, z_m, z_m+1, z _m+2, …, z _m+s – такие переменные, которые отсутствуют как в формулах А, А_n, так и в формулах В, В_n. Обозначим через формулу А* формулу A _{x1, x2, …, xm} [z₁, z₂, …, z_m], через формулу В* формулу В _{у1, у 2, …, у s} [z_m+1, z _m+2, …, z _m+s]. Тогда получим: А_n  В_n _f A _{x1, x2, …, xm} [a¹_{n  p1}, a²_{n  p2}, …, a^m_{n  pm}]  В _{y1, y2, …, ym} [b¹_{n  k1}, b²_{n  k2}, …, b^s_{n  k s}] _f A* _{z1, z2, …, zm} [a¹_{n  p1}, a²_{n  p2}, …, a^m_{n  pm}]  В* _{zm+1, z m+2, …, z m+s} [b¹_{n  k1}, b²_{n  k2}, …, b^s_{n  k s}] _f (A*  В*) _{z1, z2, …, zm, zm+1, z m+2, …, z m+s} [a¹_{n  p1}, a²_{n  p2}, …, a^m_{n  pm} , b¹_{n  k1}, b²_{n  k2}, …, b^s_{n  k s}]. Т.о. формула А_n  В_n также является формулой вида (*), и

(А_n  В_n) _f (A*  В*) _{z1, z2, …, zm, zm+1, z m+2, …, z m+s} [a¹_n, a²_n, …, a^m_n, b¹_n, b²_n, …, b^s_n] _f A* _{z1, z2, …, zm} [a¹_n, a²_n, …, a^m_n]  В* [b¹_n, b²_n, …, b^s_n] _f А_n  В_n. Следовательно, существует предел последовательности {А_n  В_n}^_n=1 и в этом случае, так что эта последовательность является формулой из L*. Аналогично могут быть рассмотрены случаи для отрицания, дизъюнкции. Остановимся только на случае с квантором существования х{А_n}^_n=1, предположив, что последовательность {А_n}^_n=1 не является стационарной последовательностью. Тогда вновь, как и ранее, можно сделать вывод, что формула А_n – это формула вида (*), т.е A_n _f A _{x1, x2, …, xm} [a¹_{n  p1}, a²_{n  p2}, …, a^m_{n  pm}], где p_j  N, j=1,…,m, и существуют теоремы теории Т вида a^j_n = a^j для каждого j. Переменная х, фигурирующая в кванторной приставке х, либо не входит свободно в формулу A_n, либо входит свободно в часть этой формулы вне термов a¹_{n  p1}, a²_{n  p2}, …, a^m_{n  pm}, либо входит свободно в один или несколько термов a¹_{n  p1}, a²_{n  p2}, …, a^m_{n  pm}. Первые два случая не влияют на предельность формулы хА_n, и последовательность таких формул будет иметь предел. Рассмотрим третий случай, когда переменная х входит свободно в один или несколько термов a¹_{n  p1}, a²_{n  p2}, …, a^m_{n  pm}. Тогда эта переменная либо свяжется уже в некоторой части формулы А_n (т.к. подстановка термов не обязательно правильная), либо будет связана только в формуле хА_n. Если х свяжется уже в некоторой части формулы А_n, то переход к формуле хА_n никак не повлияет в этом случае на эту часть формулы. Если же х впервые свяжется в некоторой части С_n формулы А_n только с переходом к формуле хА_n, то проблема существования предела у формулы хА_n будет в этом случае равносильна проблеме существования предела у формулы хС_n. В связи с этим, без ограничения общности, мы можем допустить, что С_n _f А_n. Итак, пусть переменная х свободна в формуле А_n и связана в формуле хА_n. Подберем переменные x₁, x₂, …, x_m в формуле А так, чтобы они были отличны от переменной х. Тогда хА_n _f х{A _{x1, x2, …, xm} [a¹_{n  p1}, a²_{n  p2}, …, a^m_{n  pm}]}. Поскольку от подстановки в формулы вида (*) не требуется, чтобы она была правильной, и переменная х отлична от переменных x₁, x₂, …, x_m, то мы можем записать: хА_n _f (хA) _{x1, x2, …, xm} [а¹_{n  p1}, а²_{n  p2}, …, а^m_{n  pm}]. Т.о. формула хА_n также имеет вид (*), и для нее существует предел: хА_n _f {(хA) _{x1, x2, …, xm} [а¹_{n  p1}, а²_{n  p2}, …, а^m_{n  pm}]} _f (хA) _{x1, x2, …, xm} [а¹_n, а²_n, …, а^m_n] _f х (A _{x1, x2, …, xm} [а¹_n, а²_n, …, а^m_n]) _f хА_n. Для квантора всеобщности рассуждения аналогичны.

Как следствие доказанной леммы, получаем следующие соотношения:

А_n _f А_n

А_n В_n _f А_n  В_n

А_nВ_n _f А_n  В_n

хА_n _f хА_n

хА_n _f хА_n


Определение 4. Назовем формулу языка L* {А_n}^_n=1 метатеоремой теории Т, если найдется такое m0, что для любого nm формула А_n является теоремой теории Т.


Определение 5. Назовем предельную последовательность формул {А_n}^_n=1, являющуюся метатеоремой теории Т, L-противоречием (L – от “limit”), если предел этой последовательности, А_n, имеет вид BB, где B – формула языка L.


Определение 6. Назовем теорией Т* множество метатеорем теории Т.

Теперь метатеоремы теории Т можно называть также теоремами теории Т*. Язык L* будем рассматривать как язык теории Т*. Теорию Т* назовем «ft-предельной теорией» (f – от “formula”). Описанная выше техника может быть рассмотрена как методология построения ft-предельных теорий на основе t-предельных теорий. Теорию Т* я также буду называть L-противоречивой теорией, если в ней существует L-противоречие.


Определение 7. Назовем теорию Т* непротиворечивой, если не все формулы из L* являются теоремами теории Т* (см. также теорему 19).


Теорема 1. Если теория Т непротиворечива, то теория Т* также непротиворечива.

Док-во. Если теория Т непротиворечива, то найдется формула А из языка L, которая не является теоремой теории Т. Образуем стационарную последовательность {А_n}^_n=1 формул из L, где для любого n верно: А_n = А. Последовательность {А_n}^_n=1 - это формула из L*, но она не является теоремой теории Т*. Следовательно, теория Т* непротиворечива.


Теорема 2. Если теория Т* непротиворечива, то теория Т также непротиворечива.

Док-во. Предположим противное, т.е. пусть теория Т* непротиворечива, а теория Т противоречива. Если Т противоречива, то любая формула теории Т является теоремой этой теории. Если Т* непротиворечива, то найдется формула {А_n}^_n=1 из L* такая, что {А_n}^_n=1 не является теоремой теории Т*. Это означает, что для любого m1 найдется nm такое, что формула А_n не является теоремой теории Т. Полученное противоречие доказывает требуемое.


Теорема 3. Теория Т непротиворечива е.т.е. теория Т* непротиворечива.

Док-во. См. теоремы 1 и 2.


Определение 8. Пусть М – структура для языка L. Будем говорить, что формула {А_n}^_n=1 из языка L* является истинной на структуре М при приписывании g переменным индивидов из М, если существует m1 такое, что для любого nm формула А_n является истинной в структуре М при приписывании g.


Определение 9. Структуру М для языка L назовем моделью теории Т*, если любая теорема теории Т* является истинной на структуре М при любом приписывании g.

Структуру М для языка L можно называть также структурой для языка L*.


Теорема 4. Пусть М – модель теории Т. Тогда М – модель теории Т*.

Док-во. Пусть формула {А_n}^_n=1 из языка L* является теоремой теории Т*. Тогда существует m1 такое, что для любого nm формула А_n является теоремой теории Т, т.е. А_n истинна на модели М теории Т при любом приписывании g. Но тогда и формула {А_n}^_n=1 является истинной на М при любом приписывании g. Следовательно, М – модель теории Т*.


Теорема 5. Пусть М – модель теории Т*. Тогда М – модель теории Т.

Док-во. Пусть М – модель теории Т*, и А – теорема теории Т. Построим стационарную последовательность {А_n}^_n=1, где А_n _f А для любого n. Тогда {А_n}^_n=1 - теорема теории Т*, и {А_n}^_n=1 истинна на М при любом приписывании g, т.е. существует m1 такое, что для любого nm формула А_n является истинной на М при любом приписывании g. Но т.к. А_n _f А, то формула А является истинной на М при любом приписывании g. Следовательно, М – модель теории Т.


Теорема 6. Структура М для языка L является моделью теории Т е.т.е. М является моделью теории Т*.

Док-во. См. теоремы 4 и 5.


Определение 10. Формулу {А_n}^_n=1 из языка L* назовем аксиомой теории Т*, если существует m1 такое, что для любого nm формула А_n является аксиомой теории Т.


Определение 11. Пусть Г_n – некоторое множество формул из L, и существует m1 такое, что для любого nm Г_n├ А_n – выводимость формулы А_n из множества формул Г_n в теории Т. Пусть последовательность множеств {Г_n}^_n=1 имеет предел и последовательность формул {А_n}^_n=1 также имеет предел. В этом случае будем говорить, что объект {Г_n├ А_n}^_n=1 является выводимостью в теории Т*. Будем использовать в этом случае для обозначения выводимости {Г_n├ А_n}^_n=1 сокращение {Г_n}^_n=1├_Т* {А_n}^_n=1 или просто {Г_n}^_n=1├ {А_n}^_n=1.


Определение 12. Выводимость {Г_n├ А_n}^_n=1 в теории Т* назовем доказательством в теории Т*, если существует m1 такое, что для любого nm Г_n является множеством аксиом теории Т или Г_n пусто.


Определение 13. Последовательность множеств {Г_n}^_n=1 назовем регулярной, если {Г_n}^_n=1 _f {_k=1^N{А^k_n}}^_n=1, где N – это конечное натуральное число или бесконечность, и {А^k_n}^_n=1 - формулы из L*. В этом случае договоримся {Г_n}^_n=1 записывать также в виде {{А^k_n }^_n=1}^N_k=1, а выводимость {Г_n}^_n=1├ {А_n}^_n=1 будем передавать в этом случае как {{А^k_n}^_n=1}^N_k=1├ {А_n}^_n=1, говоря, что формула {А_n}^_n=1 выводима из множества {{А^k_n}^_n=1}^N_k=1 формул {А^k_n}^_n=1 в теории Т*.

Теорема 7. Если {А_n}^_n=1 - теорема теории Т*, то {А_n}^_n=1 выводима в теории Т* из аксиом теории Т*.

Док-во. Пусть {А_n}^_n=1 - теорема теории Т*. Тогда существует m1 такое, что для любого nm формула А_n является теоремой теории Т, т.е. существует выводимость Вⁿ₁, Вⁿ₂, …, Вⁿ_{k (n)}├ А_n в теории Т, где Вⁿ₁, Вⁿ₂, …, Вⁿ_{k (n)} - аксиомы теории Т. Здесь Г_n =_z {Вⁿ₁, Вⁿ₂, …, Вⁿ_{k (n)}}, причем, Г_n может быть и пустым множеством. Заметим, что, если Г_n├ А_n, то и Гⁿ├ А_n, где Гⁿ =_z _k=0ⁿ Г_k. Последовательность {_k=0ⁿ Г_k}^_n=1 имеет предел, и этот предел равен бесконечному объединению Г^ =_z _k=0^ Г_k, причем, заметим, что Г^├ А_n, для любого nm. Занумеруем все элементы множества Г^, если Г^ не пустое множество. Получим некоторую последовательность аксиом из Т вида В₁, В₂, …, В_N, где N конечное или бесконечное. Образуем новую последовательность множеств аксиом {Г*_n}^_n=1, где Г*_n =_z Г^ для любого n. Имеем: Г*_n ├ А_n для любого nm, причем, последовательности {Г*_n}^_n=1 и {А_n}^_n=1 имеют пределы. Тогда определена выводимость {Г*_n}^_n=1├ {А_n}^_n=1 в теории Т*. Кроме того, если Г^ не пустое множество, то последовательность {Г*_n}^_n=1 является регулярной, т.к. {Г*_n}^_n=1 = {_k=1^N {В^k_n}}^_n=1, где В^k_n = В_k для любого k. В связи с этим мы можем записать последовательность {Г*_n}^_n=1 в виде {{В^k_n}^_n=1}^N_k=1, где стационарные последовательности аксиом из Т {В^k_n}^_n=1 являются аксиомами теории Т*. Следовательно, если {А_n}^_n=1 - теорема и не аксиома теории Т*, то существует выводимость {{В^k_n}^_n=1}^N_k=1├ {А_n}^_n=1 теоремы {А_n}^_n=1 теории Т* из аксиом теории Т*. Если же {А_n}^_n=1 - аксиома теории Т*, то существует выводимость {├ А_n}^_n=1 теоремы {А_n}^_n=1 теории Т* из пустого множества аксиом теории Т*.


Согласно теореме 7, любая теорема и не аксиома теории Т* может быть выведена в Т* из аксиом теории Т*, причем, множество таких аксиом теории Т* может быть представлено в этом случае как множество стационарных последовательностей аксиом из Т. Однако, одним из частных случаев такой выводимости является выводимость из пустого множества посылок для аксиом теории Т*. В этом случае среди аксиом теории Т* могут оказаться и нестационарные последовательности формул из L.