Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Московская финансово-юридическая академия

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

И.А. Пушкарев логика

.pdf

Скачиваний:

Добавлен:

10.05.2015

Размер:

729.77 Кб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 7 8 9 10 11 12 13 1415 / 1615 16 > Следующая >>>

141

§15. Собственные интерпретации и нормальные модели

1. Нормальные интерпретации

Предположим, что в сигнатуру обязательно входит символ бинарного

отношения «х=y»,	который	обязательно интерпретируется	как	совпадение
элементов х и y	носителя.	Тем самым мы сужаем	класс	возможных

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

Поскольку нормальных моделей меньше, то возникает вопрос: при каком
условии теория имеет нормальную модель? Напомним, что по теореме Гёделя о
полноте	исчисления	предикатов	непротиворечивость		равноси
существованию какой-то модели, которая нормальной быть не обязана.
Совершенно очевидно, что		равенство –	эквивалентность,	поэтому	в
любой нормальной модели должны выполняться аксиомы:
(А14)	Аx (x = x);
(А15)	AxAy ((x = y)® (y = x));
(А16)	AxAyAz (((x = y)Ù (y = z))® (x = z )).
Этого мало. Для всех функциональных символов и для всех символов
отношений	рассматриваемой	сигнатуры	следует написать	по	отдельной
аксиоме, утверждающей, что от замены аргумента функции(предиката)					на
равный его значение не изменится. Для функции двух переменных					такая
аксиома имеет схему:
(А?) AxAyAzAt (((x = y)Ù (z = t ))® ( f (x, z )= f (y,t ))).

Для двухместного предиката требуется аксиома такого вида:

(А??) AxAyAzAt (((x = y)Ù (z = t ))® (S(x, z )® S (y,t))).

Вот теперь достаточноJ. Построенное семейство аксиом назовём

аксиомами равенства.

142

Теорема 15.1. (о полноте исчисления предикатов для нормальных

моделей). Теория Т имеет нормальную модель тогда и только тогда, когда остаётся непротиворечивой при добавлении к ней аксиом равенства.

Доказательство. В нормальной модели истинность аксиом равенства

несомненна, поэтому в одну сторону теорема очевидна. Осталось показать, что

если теория совместна с аксиомами равенства, то		она имеет	нормальную
модель.
Рассмотрим произвольную	интерпретацию	теории(таковая есть по
«обычной» теореме о полноте),	пусть М – её	носитель.	Отношение,

соответствующее в этой интерпретации символу«=» не обязано быть обыкновенным равенством, однако обязано быть отношением эквивалентности,

поскольку	удовлетворяет	аксиомам(А14) –			(А16). Следовательно,				можно
рассмотреть множество		классов				M	на	которые		это
				эквивалентности = ,
отношение разбивает множествоМ.				При	этом	класс	элементах		будем
обозначать [x].
Для	любого k-местного символа			функции(отношения) f (S) положим:
f ([x1 ],...,[xk ])= [f (x1,..., xk )]		( S ([x1 ],...,[xk ])= [S(x1,..., xk )]). В силу аксиом (А?) и
(А??) определения		корректны, поэтому				получается		интерпретация
рассматриваемого множества формул				с носителемM = . Осталось убедиться,
что на построенной интерпретации истинны те же самые формулы, что и на
исходной.	Интуитивно	это	очевидно. Формальное				доказательство –
тривиальная индукция по множеству формул.
									QED
Из	теоремы 15.1.	очевидно		следует		теорема		компактности		для
нормальных моделей.

143

Теорема 15.2. Если любое конечное множество формул теорииТ имеет нормальную модель, то и сама теория Т имеет нормальную модель.

QED

2. Теорема о повышении мощности

Теорема 15.3. (теорема Лёвенгейма – Сколема о повышении мощности)

Пусть А – бесконечная нормальная интерпретация некоторой сигнатурыσ с

равенством. Тогда существует нормальная интерпретация сигнатурыσ любой мощности, большей, чем мощность А, являющаяся нормальным расширением интерпретации А.

Доказательство. Можно увеличить сигнатуруσ						до сигнатурыs А ,
добавив	к ней	по	константе для каждого элемента носителяА (для тех
элементов, для которых константа уже есть добавлять необязательно, но тоже
можно – по приколу J). Рассмотрим теорию Th(A) состоящую из тех и только
тех формул сигнатуры s А , которые истинны в интерпретации А. Очевидно, что
любое	элементарное		расширение	интерпретации	А	будет	моделью теории
Th(A), и наоборот,		любая модель Th(A) является элементарным расширением
интерпретации А.
Добавим к			сигнатуреs А	множество новых		констант		требуемой
(большей) мощности			и семейство	аксиомØ(с = d )	для	любой	пары	новых
констант с и d.

Полученная теория непротиворечива по теореме компактности для


нормальных		моделей:	конечные			множества		формул		рассматриваемой
сигнатуры	непротиворечивы			просто		потому	что	содержат только			конечное
число новых аксиом и, следовательно – новых констант. Поскольку модель А
бесконечна, этим новым константам нетрудно приписать какие-то значения, не
равные	значениям		никаких		переменных, использованных				в	остальных
формулах. По теореме о полноте для нормальных моделей эта теория имеет
интерпретацию,		мощность		которой		не	меньше		мощности		множества
добавленных констант. Правда, может оказаться больше J.

144

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

QED

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

3. Категоричность и полнота теорий

Было бы очень приятно, если бы некоторые теории имели бы ровно одну

модель (чтобы не заботиться о том, что в различных моделях могут быть очень

разные обстоятельства). Такую теорию можно было бы назвать				категоричной
(то есть – исчерпывающе описывающей явление). Теорема 15.3 показывает, что
хотеть этого не вредно, но бесполезно. Однако эта			теорема	не	запрещает
теорий, категоричных относительно данной мощности, имеющих ровно одну
интерпретацию этой мощности.
Теорема 15.4. (критерий Лося – Воота)
Непротиворечивая	теория Т с	равенством в	конечной		или счётной
сигнатуре, категоричная	относительно	некоторой	бесконечной		мощности,

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

Ø p ).

Доказательство. Если ни одна из двух формул не выводима из теории, то обе теории T È p и T È Ø p непротиворечивы, то есть имеют нормальные модели, которые – ой – не могут совпадать. Пополнив, если нужно, теорию Т как в доказательстве теоремы 15.3, получим две различные модели «той самой» мощности, которых не существует.

145

QED

Имеет место знаменитая и трудная теорема.

Теорема 15.5. (Морли) Теория с равенством, категоричная в одной

несчётной мощности, категорична и в остальных несчётных мощностях.

	§16. Ещё раз о теореме Гёделя
В	занимательной	логике	распространён , использующийсюжет

специфический воображаемый остров. Все жители этого острова делятся на два типа. Одни всегда говорят правду («рыцари»), другие – всегда лгут («лжецы»). В контексте этой простенькой модели можно иногда обсудить нечто важное.

Например, на острове не существует жителя(назовём его «сверхлжецом»), способного произнести фразу «Я – лжец» (почему?). Следовательно, если ктото всё-таки эту фразу сказал, то – одно из двух: либо рассматриваемый мир всё же не так прост, либо нам просто послышалосьJ. Удивительно, сколько

серьёзнейших математических результатов можно получить на основе этой конструкции!

Примеры

антидиагональных

рассуждений

встречались

нам

раньше.

Можно упомянуть теорему Кантора о несчётности отрезка [0, 1] действительной

прямой

теорему

об

алгоритмической

неразрешимости

пробл

самоприменимости (и то и другое

оказалось невероятно круто для своего

времени). В данном параграфе этот принцип используется для доказательства

четырёх результатов, которые многие считают вершинами

классической

математической логики.

1. Теорема Тарского

Пусть у нас есть:

а) нумерация g

множества всех формул без параметра;

б) нумерация d всех формул с одним параметром.

d (F (x)) = q ,

Заметим,

что

свойство «если

формулуF (x) ,

одним

параметром, вместо параметра x подставить число r, то получится формула без

параметра F (r )

номером p:

g (F (r )) = p »

является алгоритмически

проверяемым. Поэтому существует арифметическая формула S ( p, q, r ) с тремя

параметрами,

выражающая

это

свойство(напомним, что

существует

стандартный

способ

превращения

машины

Тьюринга

арифметическую

формулу).

Теорема 16.1. (теорема Тарского) Множество

арифметических

истин

неарифметично.

146

Доказательство. Идея доказательства состоит в том, что если множество


арифметических	истин		арифметично,		существует «странная»
арифметическая	истина, утверждающая,			что	она	ложна(на	острове
«истинности-ложности», то		есть – в очень		простом мире,		некто сказал: «я –
лжец»). Такого быть не может, поэтому сделанное предположение неверно.
Итак, пусть	множество		арифметических		истин	арифметично. Тогда
существует арифметическая		формула t (x)		с одним	параметром, выражающая

свойство «быть арифметической истиной»: формула s без параметров истинна тогда и только тогда, когда t (g (s)) = 1. Заметим:

(1) формула S (z, y, y )	выражает свойство: «если в формулу F (x) с одним
параметром, такую, что	d (F (x)) = y вместо параметра подставитьy, то

получится формула без параметра, номер которой будет равенz» (мы рассматриваем утверждения, содержащие суждения о самих себе);

(2) формула Øt (z ) Ù S (z, y, y ) выражает свойство: «(1), и эта полученная

формула с номером z ложна (точнее – не является арифметической истиной)»;

(3) формула G(y)= Еz(Øt (z )Ù S (z, y, y )) с одним параметромy выражает свойство «подставив в формулу с одним параметром (δ-номер которой равен y), её d-номер, мы получим ложную формулу без параметров(с номером z, который, конечно, существует)». Это примерно как сказать: «y –лжец».

(4) Пусть d (G (x)) = m . Из чистого любопытства посмотрим на формулу G (m) («я – лжец»): истинна ли она? Пусть g (G (m)) = n .

Сл.1 Если G (m) истинна, то t (n) = 1. Поэтому формула Øt (n) Ù S (n, m, m) ложна, и, следовательно, ложна формула G (m) , поскольку для единственного кандидата на должность z, которым является n, формула ложна. Противоречие.

Сл.2 Если G (m)	ложна, то t (n) = 0 , Øt (n) = 1 ,	S (n, m, m) = 1. Поэтому формула
Øt (n) Ù S (n, m, m)	истинна, и, следовательно,	истинна формула G (m) (n

подошла). Снова получилось противоречие.

Следовательно, формулы G не существует. Поскольку в существовании формулы S сомнений нет, то это означает, что не существует формулы t.

QED

Подведём итог: мир «истинности-ложности» был бы слишком сложен, если бы в нём можно было судить об арифметичности свойств чисто арифметически: в этом случае в нём появился бы сверхлжец. Но такового быть не может. Следовательно, арифметичность – более сложное свойство, чем те, которые можно обсуждать арифметически.

			147
2. Теорема Гёделя о неполноте
Теорема	Гёделя	о	неполноте	доказывает		существование		некоторого
довольно странного объекта. Она вполне аналогична теореме Тарского.
Единственное	отличие –		изменение	понятия «лжец».		Вместо	«не	быть
арифметической истиной»			свойство «быть лжецом»		означает		«не	иметь
доказательства». Соответственно, мы				оказываемся	в	более	сложном мире
«доказуемости-недоказуемости», в котором существование
Пусть кроме двух введённых выше нумераций есть ещё одна:

в) нумерация ζ всех доказательств (что бы ни означало это понятие). Естественные ограничения: во-первых, множество доказательств разрешимо

(существует	алгоритм, позволяющий		проверить,		действительно		ли
рассматриваемый	объект	является		доказательством); -вторых, по
доказательству можно алгоритмически определить, доказательством чего оно
является (например – доказывается всегда последняя формула,						написанная	в
доказательстве).	Соответственно,	существует		ещё	одна	арифметическая
формула P(x, y)	с двумя параметрами, выражающая свойство «доказательство

с ζ-номером x доказывает формулу без параметров с γ-номером y».

Теорема 16.2. (теорема Гёделя о неполноте) Существует арифметическая формула, которая имеет доказательство тогда и только тогда, когда она ложна.


Замечание. Тем самым, любое исчисление, содержащее арифметику, либо
неадекватно (позволяет доказать ложное утверждение), либо неполно (не
позволяет	доказать	по	крайней		мере	одно	истинное ).утвержде
Адекватность обычно сомнений не вызывает, отсюда – название теоремы.
Доказательство. Вместо (как				оказалось – не		существующей) формулы
Øt (x), выражающей		свойство		формулы«не		быть	истинной» следует

использовать (на этот раз – реально существующую) формулу ØЕyP(y, x), или,

что то	же	самое, АyØP(y, x),: «не иметь доказательства» (доказательство					с
любым ζ-номером y				доказывает	неx, а что-то другое). Это немедленно
приводит к формуле с одним					параметромy: H (y)= ØЕxЕzP(x, z )Ù S (z, y, y),
выражающей свойство «формула без параметров, полученная подстановкой							в
формулу	с		одним	параметром	δеё-номера (которой равен y), не имеет
доказательства».					d (H (y))= n . Рассмотрим
Продолжая			аналогию: пусть			формулу	без
параметров		H (n)= ØЕxЕzP(x, z )Ù S (z, n, n), которая, соответственно, говорит:

«я – лжец», в данном случае– «я не имею доказательства». Возможны два случая.

Сл. 1. Формула H (n)	(γ-номер которой обозначен z) имеет доказательство,
номер которого можно обозначитьx.		Это обстоятельство	обеспечивает
истинность формулы ЕxЕzP(x, z)Ù S (z, y,		y). Следовательно, её	отрицание –
формула H (n) – ложна.
Сл. 2. Формула H (n)	не имеет доказательства. Тогда формула H (n), об этом
и говорящая, истинна.			QED
			QED

148

Мир «доказуемости-недоказуемости» оказался достаточно сложен, чтобы в нём появился сверхлжец. Возможно, есть и другие истинные утверждения, не имеющие доказательства? Очень печальная истина для тех, кто надеялся, что любую истину можно доказать…

3. Теорема Чёрча

Теорема Чёрча утверждает, что множество теорем(полного) исчисления предикатов неразрешимо, то есть не существует алгоритма, позволяющего по данной формуле решить за конечное время, не является ли она, случайно, теоремой исчисления предикатов. Можно, конечно, перебрать все доказательства, то есть, если формула действительно является теоремой, то мы это рано или поздно узнаем; но вот если она теоремой не является, то мы этого (по крайней мере – этим способом) не узнаем никогда…

Для начала обсуждения требуется предъявить формульный аналог понятия разрешимости.

Определение. Формулу Q(x1, x2 , ..., xn ) назовём определённой, если любая формула без параметров, полученная как из неё, так и из формулыØQ подстановкой вместо параметров конкретных чисел, доказуема тогда и только

тогда, когда она истинна.
Лемма. Определённость	формулы	равносильна( лгоритмической)

разрешимости соответствующего свойства.

Замечание. Собственно, это – переформулировка «простой теоремы Поста»:

перечислимое

множество

разрешимо тогда

и только тогда, когда его

дополнение

перечислимо.

Действительно,

рассматриваемом

контексте

«перечислимость» – почти то же самое, что и «доказуемость».

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

соответствующее

свойство

для

набора

натуральных

чисел(y , y

, ..., y

Множество всех

доказательств

перечислимо, а

функция,

сопоставляющая

доказательству

формулу, которую

оно

доказывает, вычислима.

Запустим

перечисляющую все доказательства процедуру. В момент, когда она печатает очередное доказательство, применим к доказательству функцию. Результат её

работы	сравним	с	формулами	без	параметровQ(y , y , ..., y	n	)	и
					1 2	n

ØQ(y1, y2 , ..., yn ). Определённость формулы означает, что, рано или поздно, на выходе процедуры появится доказательство одной из этих формул, которая, соответственно, истинна. Следовательно, другая формула ложна, и ждать появления её доказательства бессмысленно. Отсюда, в зависимости от того, какая из формул доказалась, следует ответ на вопрос, выполняется ли для вектора (y1, y2 , ..., yn ) соответствующее свойство.

QED

			149
Теорема 16.3.	(Достаточный		признак	неразрешимости теории) Если в
некоторой аксиоматизируемой теории Т формулы P(x, y) и S (x, y, z)							являются
определёнными, то эта теория неразрешима.
Доказательство.		Снова				рассмотрим
H (y)= ØЕxЕzP(x, z)Ù S(z, y,		y).	Она истинна		тогда	и только	тогда, когда
недоказуема, то есть определённо– не является определённой. С другой
стороны, формулы S (z, y, y) и P(x, z ) – определённые, и							функция,
сопоставляющая	формуле y	формулу z –		вычислима		(почему?).	Поэтому
определёнными являются формулы P(x, z )Ù S (z,					y, y) и	ЕzP(x, z)Ù S(z, y, y).

Добавление	отрицания, в силу симметричности относительно него понятия
определённости, не могло привести к возникновению				неопределённости.
Поэтому она возникла в момент появления квантораЕx . Переменная x не
участвует	в S, поэтому	неопределённой	является	формулаЕxP(x, z),

выражающая свойство формулы с γ-номером z иметь доказательство, то есть – быть теоремой (рассматриваемого «богатого на определённые формулы» исчисления). Следовательно, соответствующее свойство неразрешимо.

QED

Замечание. Оказалось, что кванторы существования бывают разныеJ. Добавление одних разрушает определённость, а других – нет. Это глубокое различие выражает разницу свойств«существует, потому что можно явно построить за конечное время» и «существует по неясной причине». Например,

формула ЕzP(x, z )		является	определённойJ. Тем, кому не очень нравится
«кавалерийский»		характер	выявления		момента		возникнове
неопределённости,		можно	посоветовать	рассмотреть		более	аккуратную
		¢
равносильную формулу H (y)= ØЕx(ЕtP(x, t )Ù ЕzS (z, y, y)Ù (t = z)).
Теорема	16.4	(теорема	Чёрча о неразрешимости множества теорем
исчисления	предикатов) Множество всех			общезначимых		формул	логики

предикатов неразрешимо.

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

Доказательство основано на возможности построить теорию, с одной стороны – достаточно богатую, чтобы в ней оказались бы определёнными формулы S (z, y, y) и P(x, z ), а с другой стороны– настолько скромную, что всю её аксиоматику можно выразить одной формулойD (многозначительная тонкость: богатые сами по себе– неинтересны; скромные сами по себе– неинтересны; интересны скромные, но богатые).

150

Построение теории. Потребуем, чтобы рассматриваемый язык содержал бы все необходимые символы арифметических операций. Их число конечно. Далее, запишем конечным числом формул все аксиомы исчисления предикатов. Это не совсем просто: таковых аксиом бесконечно много. Например, аксиомой

является	любая	формула	видаp ® (q ® p). Можно, конечно,	написать
«формулу»	"p"q (p ® (q ® p)),		но в ней переменныеp и q не числовые, а
формульные, то есть это ещё не формула. Но обозначив символом pˆ				формулу
(без параметров),		γ-номер которой равен р, то есть g (pˆ )= p , можно написать:
"p"q (pˆ ® (qˆ ® pˆ )).

Совершенно аналогично можно написать и все аксиомы, обеспечивающие

правильное	понимание	символов	операций(хотя	бы – выполнение
надлежащего	набора свойств	этих операций), например:		"x"y (x + y = y + x).

Получится большой, но конечный набор формул. Конъюнкцию всех этих

формул обозначим D. Это – настоящая формула.
Доказательство	теоремы.		Пусть	формула р	является	теоремой
рассматриваемой теории. Это означает, что D f p . Согласно лемме о дедукции
это означает, что f (D ® p),		то	есть формулаp является		теоремой	богатого
исчисления тогда	и только	тогда, когда		формула D ® p	является	теоремой

исчисления предикатов.

Предположим, существует разрешающая процедура для множества теорем исчисления предикатов. Применяя её к формулам видаD ® p , мы построим разрешающую процедуру для рассматриваемой«богатой» теории. Но таковой не существует. Противоречие. Тем самым, теорема доказана.

QED

4. Теорема Гёделя о недоказуемости непротиворечивости

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

теории	действительных		чисел. Позднее		непротиворечивость			теории
действительных чисел была выведена из непротиворечивости некоторой другой
теории. Эта практика не вызывает удовлетворения: всегда где-то впереди есть
некая	теория, в	непротиворечивости		которой		нельзя	быть	полностью
уверенным. В этой ситуации надо всей математикой постоянно висит дамоклов
меч противоречивости: а что, если вся наука противоречива, и значит – можно
доказать всё что угодно? Тогда ценность любого доказательства								окажется
равной нулю.

<<< < Предыдущая 1 2 3 4 5 6 7 8 9 10 11 12 13 1415 / 1615 16 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
10.05.2015261.12 Кб9Земельное право.doc
#
10.05.2015306.69 Кб10Земельное право.doc
#
10.05.201557.35 Кб7Земельное право_51-60.docx
#
22.04.2019344.58 Кб3Земцева_Е.М._Реорганизация_юридических_лиц_2011....doc
#
10.12.2018155.14 Кб1ЗП.doc
#
10.05.2015729.77 Кб32И.А. Пушкарев логика.pdf
#
16.03.2016489.98 Кб82ИГиПЗС. Ответы к дифференцированному зачету.doc
#
10.05.201534.82 Кб21ИГПЗС (Балаклеец) ЭКЗАМЕН.doc
#
10.05.201531.23 Кб68ИГПЗС Зачет.doc
#
10.05.201516.38 Кб10ИГПР Кочешков.doc
#
10.05.2015247.3 Кб4ИЗЛ.doc