Колмогоров, Драгалин - Введение в математическую логику (947386), страница 16
Текст из файла (страница 16)
3. Рассмотрим язык линейного 'порядка 1(п. Этот язык' содержит лишь один сорт переменных х, у, г, ... и не содержит ни констант, ни .функциональных символов. Язык 11п содержит два двуместных предикатных символа Р и Я. Мы обозначим х=у= Р(х, у), х< у = Я (х, у) . Вот формулы языка 1(п: 'ух~/у(х<у~ ~г(х<г/~а<у) ), х<у~~(х=у~/у<х). Важнейшей моделью 11п является (Е (здесь через Я мы обо- значаем также множество рациональных чисел). Носитель.' модели Я есть множество Я.
а=Ь означает, что а и Ь равны как рациональные числа„' а<Ь означает,-что а<Ь в области рациональных чисел. Приведенные выше формулы суть законы рациональных чисел языка ) 1п. Упражнение. Убедитесь, что следующая формула на является законом рациональных чисел: ~х)/у(х=у~/х<у) .. Упражнение. Определите модель а для Ып, где х у. означает отношение «меньше» на множестве в. Какие из.' вышеуказанных формул Е!п являются законами в? 4. Определим еще язык- векторного пространства Уес(.
Этот язык содержит два сорта переменных: переменные дли действительных чисел х, у, х, ... (сорт 0) и переменные для векторов а, Ь, с, ... (сорт 1). Язык Чес1 содержит две константы: О, — енуль-действительное число», это константа сорта действительных чисел; 01 — енуль-вектор», это константа сорта векторов. Язык Чес( содержит пять функциональных символов: ) — одноместный вида (О- 0), у, й — двуместные вида (О, 0- 0), р — двуместный вида (1, ! 1), а — двуместный вида (О, 1- 1.). Обозначим ~х= $(х), (х + у) = я (х, у), (х у)= й (х, у), (а + Ь) = р (а, Ь), (х а) = д (х, а). Наконец, наш язык содержит два двуместных предикатных символа: Р вида (О, 0) и Я вида (1, 1). Введем обозначение: (х=у)= Р(х, у), (а=Ь) = Я(а, Ь).
Вот несколько формул языка Уес1: х (а+Ь) =х а+х Ь, х (у а) = (х у) а, 'уаД Ь(а+Ь=О,), Ое а=Оп 3 а 3 Ь )~х ~ у (х и + у Ь = О, ~ х = О, Л у = 0 ). Тиничной структурой языка Чес1 является л-мерное век- торное линейное пространство Е, над полем действительных чисел. Упражнение. Определите подробнее модель Е, для Чес1. Какие из вышеприведенных формул есть, законы Еь Езу Формулу Уес1 назовем законом векторного пространст- ва, если она является законом Е„при всяком л. У п р а ж н е н и е. Какие из вышеприведенных формул Уес1 суть законы векторного пространствай 5. В практике математического рассуждения часто вме- сте с основными объектами исследования используются и более сложные теоретико-множественные образования множества объектов, множества множеств объектов и т. Например,,в рассуждениях о натуральных числах исполь' зуется понятие идеала, а идеал — это особым образо устроенное множество целых чисел.
Чтобы иметь возмож ность естественно записывать такие рассуждения в точно языке, язык Аг элементарной арифметики следует попал нить, переменными для множеств натуральных чисел, а так же, если это необходимо, переменными для множеств множеств натуральных чисел. Таким образом, ~возникает расширяющаяся иерархия языков: арифметика второго порядка,- арифметика третьего порядка и т. д. — теоретико-мноксественные надстройки элементарногО языка. Объединение всех таких языков конечного порядка образует язык простой теории типов Рассела и Уайтхеда, играющий важную роль в основаниях математики.
В качестве примера опишем подробнее язык Аг2 арифметики второго порядка. Этот язык содержит два сорта переменных: переменные для натуральных чисел х, у, г, .... (сорт О) и переменные для подмножеств множества анатуральных чисел Х, У, Х, ... (сорт 1). Далее, язык Аг2 содержит те же функциональные и предикатные символы, что и язык Аг, и, кроме того, новый предикатный символ Я вида (О, 1). Обозначение ' (~Х вЂ” Я(т, Х). Подразумеваемой моделью языка Аг2 является модель, которую мы будем обозначать через гв, как и в случае эле- ментарного языка Аг.
В этой модели переменные сорта О пробегают натуральные числа. Функциональные ~и предикат- ' ные символы языка Аг2 интерпретируются в этой модели так же, как они интерпретировались в стандартной подели ы для языка Аг. Далее,:переменные Х, У, Я... сорта ! рассматриваются как пробегающие произвольные подмноже- ства множества е. Наконец, если (Г есть, подмножество в и и —,натуральное. число, то во определевию вМ Я(п, 0)~=--п~У.
Некоторые обозначения языка Аг2; Ха У у'х(хяХ=эхеи У), Х=У (Хыу)Л(ус:-Х), Хс"У (Хыу)Л 1 (Х=У), (Х вЂ” бесконечна) = 'ух~у(х суЛуеиХ). Для каждой формулы А(х) языка Аг2 можно образовать множество всех натуральных чисел х, удовлетворяю. щих условию А(х) в стандартной модели ы. Утверждение о' существовании этого множества называется аксиомой свертывания и выражается следующей формулой Аг2, истинной ~Х~ х(х~Х=А(х) ) „ где Х не входит свободно в А (х). Аналогичным образом можно определить теоретико-множественные надстройки и для других из рассмотренных нами языков. $ В.
ЛОГИЧЕСКИЕ ЗАКОНЫ а )=~ у(т+5у=п):з Д и(5т+и=п). С этой целью допустим а~~ у(т+5у=п) и установим в )=З и (5т+ и = я~. у(т+5у=п), то существует йе=ю, такое, что Но, очевидно, ~т+Яг~„=15т+Й).. Так как в )=3 «ь~ т+5й=п. 1. Сделаем несколько замечаний о сокращенных способах рассуждений с оцененными формулами. Пусть фиксирована модель М языка 11. Тогда вместо-М)= А говорят просто «истннно А», не упоминая М, или «пусть А» или даже просто «А» (это так называемое утвердительное употребление формулы А). Если нас интересует формула А при произвольной оценке, то мы употребляем сами параметры А, чтобы обозначать эту произвольную оценку.
При этом говорят примерно так: «фиксируем параметры А таким образом, что ...». Приведем два примера. 1) Покажем, что формула ~ у((х+5у) =г)~~и(-(5х+и=г) есть арифметический закон. Подробное рассуждение . может выглядеть следующим образом. Iх х~ Возьмем произвольную оценку (т „), т, пен в, и дока- жем Тогда из в~=т+5х=и следует а)=5т+й=п, что и дает в )=~ и(5т+и=а). В сокращенной форме это же рассуждение может выгля- деть таким образом.- Фиксируем х и г и докажем, что пу(х+5у=г) =э 3 и(5х+ и=я).
Пусть Яу(х+5у=г), установим ~ и(5х+и=г). Если ~ у(х+5у=г), то для некоторого у имеем х+5у=х. Но для натуральных чисел, очевидно, х+5у=-5х+у, так что 5х+у=г, а, значит, Ди(5х+и=г) (достаточно в качестве и взять у). 2) Пусть АыГщ~. Покажем, что в любой модели М язы- ка й и при любой оценке О для А будет иметь место М)=( ))ухА:з„-х 1А) О. Подробное рассуждение.
Переменная х не входит свободно в рассматриваемую формулу, поэтому можно считать, что боги О=Рч(А)~,(х). Ввиду п. 2 $2 необходимо показать, что М)= 3)Ух(АО) ~3х 3(АО). С этой целью допустим М ~ ) 'у'х(АО) и докажем, что М)==1 3 х ) (АО), Так как М )= 1'рх(АО), то неверно, что М )=з( )~х(АО). Таким образом, неверно, что для всякого объек-,' та и из области соответствующего сорта М ь= (АО),'.
(Кстати, заметим, что (АО); = А(0(,')) .) Следовательно, существует а, такое, что неверно М)=(АО);, что означает М):= ~(АО),;. По определению истинности это дает М Ь=Чх: ~(АО), что и требовалось. Сокращенное рассуждение. Возьмем произвольную модель и фиксируем параметры нашей формулы. Докажем ~)/хА:з ~к ~А.
Пусть )у'хА, установим ~х 1 А. Так,как 1у'хА, то не для всех х имеет место А, и, следовательно, найдется х, для которого )А. Таким образом, ~х1 А. Следует развивать навыки такого сокращенного рассуждения (дедуктивноподобный способ рассуждения), но, разумеется, в случае необходимости нужно уметь восстановить и все детали. 2. Формула А языка й называется логическим законом (другие термины — оби(езначимой формулой, тавтологией), если А истинна во вся~сей модели языка ьг при любой оценке. Запись )=А означает: «А есть логический закон». Покажем, например, что )= ~ А~/В~ ) (АД '( В).
С этой целью рассмотрим произвольную модель М языка ьг и произвольную оценку 8 для нашей формулы. Необходимо доказать, что М)=( )А~/В~ )(АД ) В))8. Для этого достаточно показать М)=1 (А8) ~/(ВО)~ ) ((АО)Д )(ВО)). Допустим М )= ) (А8)~/(ВО) и установим М)= ) ((АО)Л ) (ВО)), т. е. установим, что неверно М)=(АО)Д 1 (ВО). А для этого мы допустим еще, что М~=(АО)Л 1 (В8), и получим противоречие.. Но действительно, из первого допущения следует, что имеет место одно из двух: а) М ~= 1(АО), Ь) М~=(ВО). Мы видим, что обе возможности противоречат второму'допущению, так как из второго допущения следует, что М ~= АО, М ~= 1 (В8). , Утверждение доказано. Сокращенное дедуктивноподобное доказательство этого же факта моясет выглядеть следующим образом. Пусть ) А~/В, установим "1 (АД ") В).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
