1611678155-8e243485e0094ed4164786c6208411db (П.Е. Алаев - Краткий конспект лекций), страница 3

Частичный порядок 6 на A является фундированным ⇔ в A нет бесконечно убывающей последовательности a0 > a1 > a2 > . . .Предложение (о индукции в фундированном ч.у.м.). Пусть A — ч.у.м. сфундированным порядком 6, B — некоторое подмножество A. Допустим, что длялюбого x ∈ A из того, что y ∈ B для всех y < x, следует, что x ∈ B.

Тогда B = A.Пусть даны два ч.у.м. (A, 6A ) и (B, 6B ).Функция f : A → B называется монотонной, если x 6A y ⇒ f (x) 6B f (y);f — изоморфизм между (A, 6A ) и (B, 6B ), если f — биекция из A на B иx 6A y ⇔ f (x) 6B f (y) при любых x, y ∈ A.Ч.у.м. называются изоморфными, если между ними существует изоморфизм. Обозначим это как (A, 6A ) ∼= (B, 6B ).Замечание.

Изоморфность обладает свойствами отношения эквивалентности:a) (A, 6A ) ∼= (A, 6A );b) если (A, 6A ) ∼= (B, 6B ), то (B, 6B ) ∼= (A, 6A );c) если (A, 6A ) ∼= (B, 6B ) и (B, 6B ) ∼= (C, 6C ), то (A, 6A ) ∼= (C, 6C ).2.6. Линейно упорядоченные множестваПусть 6 — частичный порядок на A, x, y ∈ A. Говорим, что x, y сравнимы относительно 6, если x 6 y или y 6 x. Частичный порядок 6 называется линейным,если x 6 y или y 6 x для любых x, y ∈ A, т.е. если любые два элемента в A сравнимы. В этом случае пара (A, 6) называется линейно упорядоченным множеством(л.у.м.).Замечание. Если (A, 6) — л.у.м.

и x ∈ A, тоa) x является минимальным тогда и только тогда, когда является наименьшим;b) x является максимальным тогда и только тогда, когда является наибольшим.Пусть (A, 6) — л.у.м. Подмножество S ⊆ A называется начальным сегментомA, если для любых x, y ∈ A из x ∈ S и y 6 x следует, что y ∈ S.Замечание. Если S1 , S2 — начальные сегменты л.у.м., то S1 ⊆ S2 или S2 ⊆ S1 .Начальным отрезком A, отсекаемым элементом x ∈ A, называется множествоAx = {y ∈ A | y < x}.Замечание. Начальный отрезок всегда является начальным сегментом.Лемма.

Если (A, 6), (B, 6) — л.у.м. и f : A → B — монотонная биекция, тоf — изоморфизм.132.7. Вполне упорядоченные множестваВполне упорядоченное множество (в.у.м.) — это пара (A, 6), где 6 — линейныйфундированный порядок на A. Иногда такой порядок называют полным.Замечание 1. Любой начальный сегмент в.у.м. (A, 6) либо равен A, либо является начальным отрезком.Замечание 2. Если (A, 6) — в.у.м. и B ⊆ A, то B с порядком, индуцированнымиз A, тоже является в.у.м.1−1Лемма. Если (A, 6) — в.у.м. и f : A −−→ A — монотонная функция, то f (x) > xпри всех x ∈ A.Предложение (о начальных сегментах в.у.м.). Различные начальные сегменты в.у.м.

не могут быть изоморфны друг другу.Предложение (о изоморфизме в.у.м.). Если два в.у.м. изоморфны, то изоморфизм между ними единственен.Предположим, что f : A → C и B ⊆ A. Определим сужение функции f на B,f |B , как {hx, yi ∈ f | x ∈ B}.

Легко проверить, что f |B — функция, dom(f |B ) = Bи f |B (x) = f (x) при x ∈ B.Теорема (о сравнении в.у.м.). Если даны два в.у.м., то одно из них изоморфно начальному сегменту другого.2.8. Аксиома выбора, лемма Цорна, теорема ЦермелоЕщё одна важная аксиома теории множеств —Аксиома выбора. Для любого множества A существует f : P (A)\{∅} → A такая,что f (X) ∈ X для всех X ∈ P (A) \ {∅}.Мы уже использовали её выше в некоторых доказательствах.

Она играет ключевую роль и в доказательстве леммы Цорна.Пусть (A, 6) — ч.у.м. Подмножество B ⊆ A называется цепью, если любые дваэлемента из B сравнимы, т.е. x 6 y или y 6 x при x, y ∈ B.Элемент x ∈ A называется верхней гранью подмножества B ⊆ A, если y 6 xдля всех y ∈ B, и нижней гранью, если x 6 y для всех y ∈ B. Если в множествевсех верхних граней B есть наименьший элемент, то он называется супремумомB, и обозначается sup(B). Наибольший элемент множества всех нижних гранейназывается инфимумом B, и обозначается inf(B).Лемма Цорна (принцип максимума).

Если в ч.у.м. у каждой цепи естьверхняя грань, то в этом ч.у.м. есть максимальный элемент.Говорим, что множество можно вполне упорядочить, если на нём существуетлинейный фундированный порядок, т.е. порядок, при котором оно станет вполнеупорядоченным.14Теорема Цермело. Любое множество можно вполне упорядочить.Ниже будет показано, что эти три утверждения в некотором смысле равносильны.2.9.

Парадокс РасселаРассмотрим MR — совокупность всех множеств A таких, что A 6∈ A. Предположим, что само MR является множеством. Возможны два варианта:1) MR 6∈ MR . Тогда A = MR подходит под определение выше, и MR ∈ MR . Противоречие.2) MR ∈ MR . Вновь полагая A = MR , получаем, что по определению MR 6∈ MR .Противоречие.Это рассуждение называется парадоксом Рассела. Оно показывает, что совокупность MR нельзя считать множеством. Подход, который первоначально использовался в работах основателя теории множеств Георга Кантора и предполагал, чтомножеством можно считать любую совокупность математических объектов, иногданазывают наивной теорией множеств. Парадокс Рассела показывает, что наивнаятеория множеств нуждается в корректировке.

Открытие парадоксов наивной теории множеств привело к появлению аксиоматических теорий множеств.Заметим, что к противоречию приводит и существование множества всех множеств. Если совокупность M = {A | A — множество} является множеством, тостандартные правила работы с множествами говорят, что MR = {A ∈ M | A 6∈ A}тоже является множеством.2.10. Аксиоматическая теория множеств ZFCАксиомы теории множеств Цермело–Френкеля (ZF) выглядят так:1.

Аксиома экстенсиональности. Множества a и b равны тогда и только тогда,когда для любого x [x ∈ a ⇔ x ∈ b].2. Аксиома пары. Для любых множеств a, b существует множество {a, b}.3. Аксиома объединения. Для любого множества a существует множествоSa={y | существует x ∈ a такой, что y ∈ x}.4. Аксиома множества подмножеств. Для любого множества a существуетмножество P (a) = {b | b ⊆ a}.5. Аксиома подстановки.

Пусть a — множество, а Φ(x, y) — условие, обладающее свойством: для каждого x ∈ a существует не более одного y такого, что Φ(x, y).Тогда существует множество a0 = {y | существует x ∈ a такой, что Φ(x, y)}.6. Аксиома бесконечности. Существует множество, которое содержит ∅ и вместе с каждым x содержит и x ∪ {x}.157. Аксиома регулярности. Для любого непустого множества a существует элемент x ∈ a такой, что x ∩ a = ∅.Точная формализация понятия “условие Φ(x, y)” из Аксиомы 5 может бытьдана с помощью формул исчисления предикатов (ИП), которые появятся в нашемкурсе позже. Тем самым список аксиом является пока не совсем формальным.Теория множеств Цермело-Френкеля с аксиомой выбора (ZFC) получается из ZFдобавлением аксиомы выбора.8. Аксиома выбора.

Для любого множества A существует f : P (A) \ {∅} → Aтакая, что f (X) ∈ X для всех X ∈ P (A) \ {∅}.ZFC является наиболее известной и широко распространённой теорией множеств. В нашем курсе мы пользуемся её аксиомами, считая, что они выполняютсядля множеств. При этом мы не ставим перед собой задачу строго вывести всерезультаты курса из её аксиом. Если мы работаем в рамках ZFC и хотим использовать некоторое множество, то сначала нужно доказать, используя аксиомы ZFC,что такое множество существует.

Приведём два примера таких доказательств.Пример 1. Если A — множество и Ψ(x) — некоторое условие, то существуетмножество B = {x ∈ A | Ψ(x)}.Пример 2. Для любых множеств A и B существуют множества A ∪ B, A ∩ Bи A × B.Аксиомы 1 и 7 просто фиксируют некоторые важные свойства множеств, аАксиомы 2–6 задают некоторые конструкции, которые позволяют строить новые,однозначно заданные множества из уже имеющихся. Аксиома выбора является вэтом смысле особой — она утверждает существование некоторого объекта, но неуказывает, как его можно построить или задать в явном виде. Из-за этого доказательства, использующие только ZF без аксиомы выбора, иногда рассматриваютсякак более конструктивные.Предложение.

В теории множеств ZF аксиома выбора следует из теоремыЦермело. Тем самым аксиома выбора, теорема Цермело и лемма Цорна равносильны в ZF.Если некоторая совокупность множеств сама не является множеством, но можетбыть задана как совокупность всех множеств, обладающих некоторым фиксированным свойством, то такие совокупности часто называют классами.

Например,мы можем говорить о классе всех множеств, всех бинарных отношений, или всехфункций.162.11. МощностиНемного позже мы дадим точное определение мощности множества A, которая обозначается |A|. Базисным понятием для теории мощностей является, однако,не само понятие мощности, а понятие равномощности множеств. Говорим, что мно1−1жества A и B равномощны, если существует биекция f : A −−→ B.