Доказуемое и недоказуемое - Манин Ю.И.
Скачать (прямая ссылка):
Возьмем булево пересечение обеих частей с ЦХ=?/|| и булеву сумму по всем Н(=0(У); затем к левой части применим формулу (6) § 4 и воспользуемся дистрибутивностью. Это дает
НЛ'епднУ = 2Ц< V 1|* = */.1Л1Н/е2||< V ||* =
(Г) 1кг)—ув
ч-— а
= 1/|1Л||1/е2|| = ;|*е2||.
в) (1) верно в У^_+\, если (3) верно в Уд. Рассмотрим элемент ?/е=0 (Х)С1 С1 У^- Согласно п. а)
1Н/е*|1Л11* = У||<||1/еУ[|.
Возьмем булево пересечение с || У = 11|:
||У€=*||Л||* = У|1Л1|У=2||<||1/еУ||Д||Г==2||.
Правая часть всегда <; [| ?/?: 2 ]|, если УеУ^ то по гг. б) или индуктивному предположению, если же У€=У^+1 новый, то по п. а).
Итак, мы установили, что для всех X, У, Е?|/®+1, и?=0(Х)
|1*/еЛГ||Л||* = У||Л||Г=2||<||1/е2||. ,
130
Воспользовавшись тем, что в любой булевой алгебре из а ДК« следует b < а' V с> получаем отсюда
|l*=r||AI|r=Z||<||l/e*||'VIJt/eZ||
и далее
Н*=У11Л||У=Я||< Л i|i/ex||'V|li/eZ||.
U^D (X)
Меняя здесь местами X и Z, получаем для всех UeD(Z)
Ц2 = У||Л||У = *||< Л \\u&z ||'V ||?/е*||-
U{=D (Z)
Из двух последних формул и (5), очевидно, следует (3).
Г) (2) верно в yf+j, если (1) верно * Vl+v Действительно, пусть UЕЕ Efl(Z). Согласно (1)
ll* = y|IA||y=i/||<||x=t/||.
Возьмем булево пересечение с \\Uc=Z\\ и булеву сумму по всем UeD(Z):
II * = у II Л( v ll^ezii д||У= г/Ц)< V ||x = t/||AI|t/e=Z||.
U^D (Z) и^р (Z)
Применяя (1)в+1 §4, получаем (2).
р) (3) верно в У®+1, если (2) верно в V%+1. Действительно, пусть U 6= ЕЙ(У). По п. а)
i|7ey||Al|y = Z||<||t/eZ||.
Взяв булево произведение с [|Х=[/|! и применив (2) к правой части, получим
l|*=?||AI|t/e=y!IAI|y=Z||<||*ezi|.
Наконец, построим булеву сумму по всем U^D(Y) и воспользуемся (1) § 4, получим (3).
Очевидно, все доказанное обеспечивает индуктивный переход от а к а+1. Теперь мы уже можем установить основной результат этого параграфа.
5.2. Предложение.
Аксиома объемности
х = у <--*?'yz (Z е х г е«/)
«истинна».
Доказательство. Формула ЦР-<—>-QII(i)=l равносильна ||РЦ(|) = = ||Q|](g). Поэтому достаточно доказать, что для всех X, Y^VB
н н= л urz:e*nviizeyii')A(iiz;e*ii'viizeyii).
ZEEV8
Неравенство 5= немедленно следует из формулы (2) § 4. Чтобы получить обратное неравенство, запишем два очевидных следствия из (3) леммы 5.1:
||*=y||<||ze*||VI|Zey[|'; l|*=y||<||Ze*||'VI|Zey||,
и возьмем булево произведение по всем Z. Предложение доказано.
Отметим, что из (2) следует общее свойство экстенсиональности: для всех
9* 131
х, г, геУв
\\х=у\\ А1|1ге2|[=||А-=К|| Л1|А-е2||.
5.3. Следствие.
Аксиомы равенства в языке Г^Бе! «истинны».
Действительно (см. предложение 4.6 гл. II), они выводятся из аксиомы
объемности, «истинной» формулы х = х и «истинной» формулы Х—У+ >-угХ
X (хег-«—>у&) с помощью стандартных правил вывода, которые сохраняют «истинность».
5.4. Замечание. В большинстве вычислений нам будут важны лишь значения ||Х<=У|| и \\Х=У\\, а не точное определение объектов X, У. Заметим в связи с этим, что следующие два бинарных отношения на Ув:
а) ||* = уц=1,
б) \\1&Х\\ = \\1 еУЦ,
совпадают (легкое следствие (2) и аксиомы объемности). Мы будем называть такие X, У эквивалентными и писать X ~ У.
6. АКСИОМЫ ПАРЫ, СУММЫ, СТЕПЕНИ И РЕГУЛЯРНОСТИ «ИСТИННЫ»
6.1. Вычисления предыдущего параграфа показывают, что основная работа по обеспечению «истинности» аксиомы объемности была вложена в определение универсума Vе. Явные формулы для рекурсивного вычисления ||ХеУ|| и ||Х=У|! отражали так много частных свойств включения и равенства, что их объединение гарантировало выполнение общей аксиомы.
Проверка ряда других аксиом требует по существу определения в Ув аналогов операций, имеющихся в V, неупорядоченной пары, множества подмножеств и т. п. Эти операции можно определить посредством формул языка 1.1 БеГ Напомним, однако, что, если Р(х)—формула с единственной свободной переменной х, то совокупность еУ, для которых Р (х^) истинна, образует, вообще говоря, лишь класс, а не множество.
Оказывается удобным ввести вспомогательное понятие «случайного класса» и по отношению к Ув. Последующие конструкции операций в Ув после этого часто производятся в два приема: сначала значением операции оказывается случайный класс, который затем уже «отождествляется» со случайным множеством с помощью отдельного рассуждения.
6.2. Определение.
а) Случайным классом называется любая функция XV на Ув со значениями в В, удовлетворяющая следующему условию экстенсиональности:
ХУ (X) Д || X = V || = ХУ (У) Д[|Х=Г|| для всех X, У(=УВ.
б) Случайный класс Ц7 называется эквивалентным случайному множеству 2еУв {запись 1У~2), если 1У(Х) = ]|Х(=2]| для всех Х(=УВ.
6.3. Примеры и замечания, а)"4 Зля любого' случайного множества 2 функция X 1-Н1-Х е=?|1 экстенсиональна]^ силу (2) § 5 и потому является случайным классом. По аналогии с этим мы часто будем писать ||Х(=1У[| вместо №{X) и для любых случайных классов У/.
б) Существуют случайные классы, неэквивалентные случайным множествам. Например, «универсальный» случайный класс: 1У(Х) = 1 для всех X. (Иначе мы имели бы ||1У(=Ц71| = 1, в противоречие с аксиомой регулярности, «истинность» которой будет проверена позже.)
