1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 19
Текст из файла (страница 19)
Аксиома выбора, наоборот, утверждает, что в этом <<универсуме,>должнысуществоватьопределенныемножества,еслинекоторыеуже существуют. Однако в доказательствах мы свободно пользовалисьи другими условиями существования множеств, например, мы образовывали объединение АUВдвух множеств А и В, рассматривалимножество-степень Р(А), считали, что в нашем распоряжении <<имеются,> натуральные числа п Еw.Все условия существования множеств, которые мы использовали(кроме аксиомы выбора), вытекают из следующих аксиом <,существования~:1).2).Существует пустое множество 0.Если существуют множества а и Ь, то существует множество{а, Ь}.3). Если существует множество Х, то существует множество= {t I tUХ =Е х для некоторого х Е Х}.4).
Существует множество w = {О, 1, ... ,п, ... }, где О= 0 иn+ 1 ==nU{n}.5).Если существует множество А, то существует множество Р(А)={В=I В~ А}.6). Если Ф(х, у) - некоторое условие на множества х, у такое, чтодля любого множества х существует не более одного множествау, удовлетворяющего условию Ф(х, у), то для любого множестваа существует множество{ЬПример2.6.1.I Ф( с, Ь)для некоторого с Е а}.Покажем, что из аксиомствование множества А 2= {(а, Ь)12), 5)и6)следует сущеа, Ь Е А} для любого множества А.§ 2.
б.Так как (а,Ь)Фо(х,у)Аксиоматическая теория множеств{{а},{а,Ь}}, то А 2 ~ Р(Р(А)). Пусть=-{=:::;>89(существуют такие а,Ь Е А,ЧТО х= {{а}' {а, ь}}и у= х).Ясно, что для любого множества х существует не более одногомножества у, удовлетворяющего условию Ф(х, у), поэтому по аксиомам5) и 6) множество {Ь I Фо(с, Ь), с Е Р(Р(А))}2) оно совпадает с множеством А 2 .Систему аксиомl)-6)существует и по аксиомевместе с аксиомами экстенсиональности и регулярности называют системой аксиом Цермело-Френкеля и обозначают черезчерез ZFC.СистемуZF.ZFвместе с аксиомой выбора обозначают1)В рамках теорииZFCможно изложить все общепринятые в современной математике способы рассуждений.
Можно даже сказать, чтонасовременномэтаперазвитияматематикитакая«переводимостывZFC является мерилом математической строгости. (Правда, это оспаривается интуиционистами и конструктивистами, но их воззрений мыв этой книге не касаемся.) Таким образом, формальный вывод изаксиомZFCможно принять в качестве разумного уточнения понятияматематического доказательства2).Точная формулировка этого понятия имеет большое значение и составляет одну из центральных задачматематической логики.Только при наличии соответствующих точных определений можно установить недоказуемость и независимостьнекоторых утверждений.
Так, было доказано, что множеству действительных чисел можно без противоречия приписать практически любуюмощность. То обстоятельство, что правильность формального доказательствалегкопроверитьнамашине,явилосьотправнымпунктомдля перспективных исследований по машинному поиску доказательств.Исторически главную роль в созданииZFCсыграли противоречия <,наивной~ теории множеств. Как же обстоят дела с непротиворечивостьюZFC?В рамкахZFCникаких противоречий до сих пор не обнаружено.С другой стороны, было доказано, что еслиZFCнепротиворечива,этот факт нельзя установить средствами этой теории. Таким образом,непротиворечивостьZFCможно только принять на веру, что мы и будем делать.1)Для точного определения понятия условия Ф(х, у) в аксиоме 6) мыотсылаем читателя к понятию формулы сигнатуры Ео, содержащей лишь одиндвухместный предикатный символ Е (см.
гл.ZFC2)(см.3).Заметим, что все аксиомыможно записать в виде предложений сигнатуры Ео.Под формальным выводом понимается вывод в исчислении предикатов§4.5).90Гл.ВZFCТеория множеств2.имеется семь аксиом, утверждающих существование некоторых множеств. Аксиома выбора среди них занимает особое место. Она,по-видимому, является наименее <<Очевидной». Дело в том, что множества, существование которых утверждается в аксиомахделяются однозначно( например,сумма множестваUХ1)-6),опреоднозначноопределена по Х), функция же выбора для непустых подмножеств Хопределена неоднозначно.
Более того, если существует условие, определяющее однозначно функцию выбора для непустых подмножеств Х,то тогда существование функции выбора для Р(Х)сти без аксиомы выбора (т. е. вZF).\ {0} можно вывеНаличие такой неопределенностиобъекта, существование которого утверждает эта аксиома, а такженекоторые ее следствия, не согласующиеся с <<наивной»интуицией,вызвало многочисленные споры вокруг аксиомы выбора среди математиков в начале ХХ в. Некоторые даже считали, что она навернякадолжна привести к противоречию.
Однако после результата К. Гёделяо равнонепротиворечивостииZFZFCэти споры, в основном, утихли.Тем не менее, до сих пор иногда стараются приводить, если это возможно, доказательства, не использующие аксиому выбора, считая такоедоказательство более <,конструктивным,>. Отметим также доказаннуюП. Коэном равнонепротиворечивостьZFиZF+(отрицание аксиомывыбора).Оставшуюся часть параграфа мы посвятим теореме, показывающей,что аксиома выбора эквивалентна (вZF)некоторым своим следствиям,доказанным в предыдущих параграфах.Теорема2.6.2.Из аксиомZFможно вывести эквивалентностьследующих утверждений:а) аксиома выбора: для любого непустого множества А существует такое отображениевсех В~ А, В6)h:(Р(А)\ {0})-+А, чтоh(B)ЕВ для,f.
0;принцип максимума: если в частично упорядоченном множестве Qt= (А, И)каждая цепь имеет верхнюю грань, то Qt имеетмаксимальный элемент;в) принцип полного упорядочения: для любого множества А существует отношение И~ А 2 , для которого (А, И) - вполне упорядоченное множество;г) если множество А бесконечно, тоIA2 1 = IAI.д) сравнимость множеств по мощности: для любых множеств Аи В выполненоIAI~IBIилиIBI~IAI.До к аз ат ель ст в о.
В силу доказанных выше теорем, из аксиомывыбора следуют утверждения 6)-д). В доказательстве принципа полно-§ 2.6. Аксиоматическая теория множеств91го упорядочения сама аксиома выбора не используется, а используетсятолько принцип максимума, поэтому мы имеем б)==}в).в)==}а). Пусть (А, И)стве значения- вполне упорядоченное множество. В качеh(X) функции выбора h берем наименьший по отношению И элемент множества (Х, Хаксиомыn И).Эта функция существует в силу6).r)==}в). Предположим, что утверждение г) выполнено. Так как длялюбого вполне упорядоченного множества (В,(С, С 2n V)V)и любого С<;;;: В паравполне упорядоченное множество, то для доказательства в) достаточно найти инъективное отображение g : А >-+ В для-некоторого вполне упорядоченного множества (В,V).Предположим,что это не так. В частности, не существует инъективного отображениямножества А ни в какой ординал.Так как, по определению, конечные множества биективно отображаютсянаординалы,которыевполнеупорядоченыотношением€,то множество А бесконечно.Из аксиомы6)вытекает существование множестваW ={И<;;;: А2 1 (D(U), И) - вполне упорядоченное множество},гдеD(U)={а Е А 1 (а,Ь) Е И или (Ь,а) Е И для некоторого Ь Е А}.Доказательство теоремы о представлении вполне упорядоченных множеств не зависит от аксиомы выбора, поэтому по аксиоме6)существует множествоVЯсно, что={а(И)1И Е W,a(U) -тип множества(D(И),И)}.V равно множеству {а I а = U V являетсясвойствам ординалов аоlaolординал иlal~IAI}.Поординалом.
Установим, чтоIAI. Индукцией по натуральным числам легко устанавливается,lnl ~ IAI, поэтому ординал ао бесконечен. Тогда lao + 11 = laol иесли laol ~ IAI, то lao + 11 ~ IAI, ао + 1 Е V и ао Е U V = ао, что1,.чтопротиворечит аксиоме регулярности.Очевидно, что ао х А <;;;: ( ао U А) 2 . Из условия г) мы имеемследовательно, существует инъективное отобl(ao U А) 2 1 = l(ao U A)I,laolIAI,ражение f: ао х А>-+ (ао U А). Так как1,.то для любого а Е Амы имеем (f [о: 0 х {а}] n ао) -:/:- 0. Определим отображение g : А ---+ аоследующим образом: для а Е А элементво вполне упорядоченном множестветивности отображенияfg( а)((f[aoявляется наименьшимх {а}] По:0),1:). Из инъекследует инъективность отображенияg.Этопротиворечит предположению о том, что А нельзя инъективно отобразить ни в какой ординал.д)==}в).
Пусть ао=>в). Так как-ординал, определенный в доказательствеlaol 1,. IAI,то по условию д) мы имеемIAI~r)==}laol-Как92Гл.2.Теория множествуже отмечалось в начале доказательства утверждения r)===>в) из этогофакта следует условие в).DЗаметим, что доказательство теоремы Кантора не зависит от аксиомы выбора. В доказательстве теоремы Кантора-Бернштейна мы использовали следствие аксиомы выборапринцип кардинального упо-рядочения. Однако при предположении непротиворечивостиа)-д)ZFсписокиз предыдущей теоремы нельзя расширить, добавив теоремуКантора-Бернштейна. Это следует из отмеченной выше равнонепротиворечивостиZFиZF+(отрицание аксиомы выбора) и того, чтосуществует доказательство этой теоремы, не зависящее от аксиомывыбора.ДоказательствотеоремыКантора-Бернштейна,зависящее от аксиомы выбора.
Пустьинъективные отображения, Ао = А, А1 =Индукцией по п легко установить,чтоf:А---. В,неВ---. Аg[B] и Ап+2 = (fg)[Aп].Ап+l <;;; Ап, п Е w. Пустьg:П Ak и Mi = А \Ан1- Очевидно, что ( U мi) UD = Akk~iEwMi n М1 = 0 для i =1- j. Так как f · g инъективно отображает MiD =kEwина Мн2 для любогоiЕw,то отображениеh:А---.А, определенноеследующим образом:ha=если а Е (.u{ а,(f g)(a),M2i+1) U D,iEwU M2i,если а ЕiEwявляется инъективным отображением А на(UMi) U D= А1.l~iEwТак какIBI = IA11,то получаемIBI = IAI.DУпражнение1.Показать, что аксиома выбора эквивалентна вутверждению: если М2.1.3),тосуществует-ZFразбиение множества Аотображениеg:М---.А,следующему(см.дляпримеркоторогоg(m) Е m, т ЕМ, т =1- 0.
(Указание. Рассмотреть разбиение{m(B)1В Е Р(А) \{0}},где т(В)={(В,а)1а ЕВ}.)Глава3ИСТИННОСТЬ НА АЛГЕБРАИЧЕСКИХСИСТЕМАХАлгебраические системы§ 3.1.Часто объектом изучения в математике служит множество вместес определенной на нем структурой, например, множество треугольников с отношением подобия, множество действительных чисел с операциями сложения и умножения, множество вещественных функцийсо свойством дифференцируемости и операцией дифференцированияи другие. В этом параграфе мы дадим одно из уточнений этого понятия,введя определение алгебраической системы.Определение. Упорядоченная тройка :Е= (R, F, µ)называется сиг-натурой, если выполняются следующие условия:а) множестваб}µRине имеют общих элементов;Fявляется отображением множестваЭлементы множестваили функций. ОтображениеµЕслипредикатным символом присимволом приqЕF,вw.называются символами отношений илиRпредикатов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
