Презентация 15 (Лекции), страница 2
Описание файла
Файл "Презентация 15" внутри архива находится в папке "Лекции". PDF-файл из архива "Лекции", который расположен в категории "". Всё это находится в предмете "математическая логика и логическое программирование" из 6 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 2 страницы из PDF
, XNПройдёмся по этим множествам от первого к N-му, и изкаждого (i-го) выберем элемент eiX1e1...X1 × · · · × XNXNeNИнтерлюдия: некоторые свойства множествА теперь другое утверждение:УтверждениеДля любого натурального числа N декартовопроизведение N непустых множеств непустоДоказательство.Рассмотрим произвольные непустые множества X1 , . . . , XNПройдёмся по этим множествам от первого к N-му, и изкаждого (i-го) выберем элемент eiТогда элемент (e1 , . . .
, eN ) принадлежит декартовупроизведению X1 × · · · × XNe1eNX1XN...X1 × · · · × XN (e1 , . . . , eN )HИнтерлюдия: некоторые свойства множествОснова справедливости этих двух утверждений — возможностьвыбрать по одному элементу из каждого множества заданногосемейства X и составить из этих элементов новое множествоИнтерлюдия: некоторые свойства множествОснова справедливости этих двух утверждений — возможностьвыбрать по одному элементу из каждого множества заданногосемейства X и составить из этих элементов новое множествоА можно ли сделать то же самое в случае произвольногосемейства множеств?Интерлюдия: некоторые свойства множествОснова справедливости этих двух утверждений — возможностьвыбрать по одному элементу из каждого множества заданногосемейства X и составить из этих элементов новое множествоА можно ли сделать то же самое в случае произвольногосемейства множеств?Например, если X = 2N0 \ {∅}, то можно выбрать наименьшеечисло из каждого множестваИнтерлюдия: некоторые свойства множествОснова справедливости этих двух утверждений — возможностьвыбрать по одному элементу из каждого множества заданногосемейства X и составить из этих элементов новое множествоА можно ли сделать то же самое в случае произвольногосемейства множеств?Например, если X = 2N0 \ {∅}, то можно выбрать наименьшеечисло из каждого множестваА если X = 2R ?Интерлюдия: некоторые свойства множествОснова справедливости этих двух утверждений — возможностьвыбрать по одному элементу из каждого множества заданногосемейства X и составить из этих элементов новое множествоА можно ли сделать то же самое в случае произвольногосемейства множеств?Например, если X = 2N0 \ {∅}, то можно выбрать наименьшеечисло из каждого множестваА если X = 2R ?Iнаименьшее число из каждого множества выбрать нельзя:его может и не бытьИнтерлюдия: некоторые свойства множествОснова справедливости этих двух утверждений — возможностьвыбрать по одному элементу из каждого множества заданногосемейства X и составить из этих элементов новое множествоА можно ли сделать то же самое в случае произвольногосемейства множеств?Например, если X = 2N0 \ {∅}, то можно выбрать наименьшеечисло из каждого множестваА если X = 2R ?IIнаименьшее число из каждого множества выбрать нельзя:его может и не бытьпошаговый процесс выбора описать тоже нельзя:множество |2R | несчётноИнтерлюдия: некоторые свойства множествОснова справедливости этих двух утверждений — возможностьвыбрать по одному элементу из каждого множества заданногосемейства X и составить из этих элементов новое множествоА можно ли сделать то же самое в случае произвольногосемейства множеств?Например, если X = 2N0 \ {∅}, то можно выбрать наименьшеечисло из каждого множестваА если X = 2R ?IIнаименьшее число из каждого множества выбрать нельзя:его может и не бытьпошаговый процесс выбора описать тоже нельзя:множество |2R | несчётноТогда возможность такого выбора становится неочевиднойАксиома выбораПопробуем сформулировать утверждение о том, что такойвыбор всегда можно произвестиАксиома выбораПопробуем сформулировать утверждение о том, что такойвыбор всегда можно произвестиАксиома выбора: для любого семейства X непустых множествсуществует функция F , сопоставляющая каждому множеству изX элемент этого множестваАксиома выбораПопробуем сформулировать утверждение о том, что такойвыбор всегда можно произвестиАксиома выбора: для любого семейства X непустых множествсуществует функция F , сопоставляющая каждому множеству изX элемент этого множестваAC : ∀X (∅ ∈/ X → ∃F (Func(F) & ∀z (z ∈ X → Val(F, z) ∈ z)))Аксиома выбораПопробуем сформулировать утверждение о том, что такойвыбор всегда можно произвестиАксиома выбора: для любого семейства X непустых множествсуществует функция F , сопоставляющая каждому множеству изX элемент этого множестваAC : ∀X (∅ ∈/ X → ∃F (Func(F) & ∀z (z ∈ X → Val(F, z) ∈ z)))Недостающие определения:D∈/ :¬x1 ∈ x2Аксиома выбораПопробуем сформулировать утверждение о том, что такойвыбор всегда можно произвестиАксиома выбора: для любого семейства X непустых множествсуществует функция F , сопоставляющая каждому множеству изX элемент этого множестваAC : ∀X (∅ ∈/ X → ∃F (Func(F) & ∀z (z ∈ X → Val(F, z) ∈ z)))Недостающие определения:D∈/ :¬x1 ∈ x2DFunc : ∀z (z ∈ x1 → ∃x ∃y z = Pair(x, y))Аксиома выбораПопробуем сформулировать утверждение о том, что такойвыбор всегда можно произвестиАксиома выбора: для любого семейства X непустых множествсуществует функция F , сопоставляющая каждому множеству изX элемент этого множестваAC : ∀X (∅ ∈/ X → ∃F (Func(F) & ∀z (z ∈ X → Val(F, z) ∈ z)))Недостающие определения:D∈/ :¬x1 ∈ x2DFunc : ∀z (z ∈ x1 → ∃x ∃y z = Pair(x, y))& ∀x ∃!y (Pair(x, y) ∈ x1 )Аксиома выбораПопробуем сформулировать утверждение о том, что такойвыбор всегда можно произвестиАксиома выбора: для любого семейства X непустых множествсуществует функция F , сопоставляющая каждому множеству изX элемент этого множестваAC : ∀X (∅ ∈/ X → ∃F (Func(F) & ∀z (z ∈ X → Val(F, z) ∈ z)))Недостающие определения:D∈/ :¬x1 ∈ x2DFunc : ∀z (z ∈ x1 → ∃x ∃y z = Pair(x, y))& ∀x ∃!y (Pair(x, y) ∈ x1 )DPair : y = {{Un(x1 )} , {Un(x1 ), x2 }}Аксиома выбораПопробуем сформулировать утверждение о том, что такойвыбор всегда можно произвестиАксиома выбора: для любого семейства X непустых множествсуществует функция F , сопоставляющая каждому множеству изX элемент этого множестваAC : ∀X (∅ ∈/ X → ∃F (Func(F) & ∀z (z ∈ X → Val(F, z) ∈ z)))Недостающие определения:D∈/ :¬x1 ∈ x2DFunc : ∀z (z ∈ x1 → ∃x ∃y z = Pair(x, y))& ∀x ∃!y (Pair(x, y) ∈ x1 )DPair : y = {{Un(x1 )} , {Un(x1 ), x2 }}DUn : y = {{∅} , {∅, x1 }}Аксиома выбораПопробуем сформулировать утверждение о том, что такойвыбор всегда можно произвестиАксиома выбора: для любого семейства X непустых множествсуществует функция F , сопоставляющая каждому множеству изX элемент этого множестваAC : ∀X (∅ ∈/ X → ∃F (Func(F) & ∀z (z ∈ X → Val(F, z) ∈ z)))Недостающие определения:D∈/ :¬x1 ∈ x2DFunc : ∀z (z ∈ x1 → ∃x ∃y z = Pair(x, y))& ∀x ∃!y (Pair(x, y) ∈ x1 )DPair : y = {{Un(x1 )} , {Un(x1 ), x2 }}DUn : y = {{∅} , {∅, x1 }}DVal : Pair(x2 , y) ∈ x1Аксиома выбораПопробуем сформулировать утверждение о том, что такойвыбор всегда можно произвестиАксиома выбора: для любого семейства X непустых множествсуществует функция F , сопоставляющая каждому множеству изX элемент этого множестваAC : ∀X (∅ ∈/ X → ∃F (Func(F) & ∀z (z ∈ X → Val(F, z) ∈ z)))Недостающие определения:D∈/ :¬x1 ∈ x2DFunc : ∀z (z ∈ x1 → ∃x ∃y z = Pair(x, y))& ∀x ∃!y (Pair(x, y) ∈ x1 )DPair : y = {{Un(x1 )} , {Un(x1 ), x2 }}DUn : y = {{∅} , {∅, x1 }}DVal : Pair(x2 , y) ∈ x1А насколько правдоподобна аксиома выбора?Аксиома выбораТеория Цермело-Френкеля с аксиомой выбора (ZFC) состоит изаксиом ZF и аксиомы выбораАксиома выбораТеория Цермело-Френкеля с аксиомой выбора (ZFC) состоит изаксиом ZF и аксиомы выбораТеорема (Гёдель, 1940)Если теория ZF непротиворечива, то теория ZFC такженепротиворечиваАксиома выбораТеория Цермело-Френкеля с аксиомой выбора (ZFC) состоит изаксиом ZF и аксиомы выбораТеорема (Гёдель, 1940)Если теория ZF непротиворечива, то теория ZFC такженепротиворечиваЗначит, аксиома выбора действительно правдоподобнаАксиома выбораТеория Цермело-Френкеля с аксиомой выбора (ZFC) состоит изаксиом ZF и аксиомы выбораТеорема (Гёдель, 1940)Если теория ZF непротиворечива, то теория ZFC такженепротиворечиваЗначит, аксиома выбора действительно правдоподобнаА может, эта аксиома логически следует из ZF?Аксиома выбораТеория Цермело-Френкеля с аксиомой выбора (ZFC) состоит изаксиом ZF и аксиомы выбораТеорема (Гёдель, 1940)Если теория ZF непротиворечива, то теория ZFC такженепротиворечиваЗначит, аксиома выбора действительно правдоподобнаА может, эта аксиома логически следует из ZF?ZF¬C — теория, состоящая из аксиом ZF и аксиомы ¬ACАксиома выбораТеория Цермело-Френкеля с аксиомой выбора (ZFC) состоит изаксиом ZF и аксиомы выбораТеорема (Гёдель, 1940)Если теория ZF непротиворечива, то теория ZFC такженепротиворечиваЗначит, аксиома выбора действительно правдоподобнаА может, эта аксиома логически следует из ZF?ZF¬C — теория, состоящая из аксиом ZF и аксиомы ¬ACТеорема (Коэн, 1963)Если теория ZF непротиворечива, то теория ZF¬Cтакже непротиворечиваАксиома выбораТеория Цермело-Френкеля с аксиомой выбора (ZFC) состоит изаксиом ZF и аксиомы выбораТеорема (Гёдель, 1940)Если теория ZF непротиворечива, то теория ZFC такженепротиворечиваЗначит, аксиома выбора действительно правдоподобнаА может, эта аксиома логически следует из ZF?ZF¬C — теория, состоящая из аксиом ZF и аксиомы ¬ACТеорема (Коэн, 1963)Если теория ZF непротиворечива, то теория ZF¬Cтакже непротиворечиваЗначит, возможность выбирать элементы из произвольныхсемейств множеств ни в каком виде не присутствует в теорииЦермело-ФренкеляИнтерлюдия: мощности множествА насколько просто в теории Цермело-Френкеля рассуждать омощностях множеств?Интерлюдия: мощности множествА насколько просто в теории Цермело-Френкеля рассуждать омощностях множеств?Для начала вернёмся к наивному определению мощностимножестваИнтерлюдия: мощности множествА насколько просто в теории Цермело-Френкеля рассуждать омощностях множеств?Для начала вернёмся к наивному определению мощностимножества:мощность множества X — этокласс всех множеств, равномощных XыИнтерлюдия: мощности множествА насколько просто в теории Цермело-Френкеля рассуждать омощностях множеств?Для начала вернёмся к наивному определению мощностимножества:мощность множества X — этокласс всех множеств, равномощных XыА класс всех множеств, равномощных заданному — этомножество?Интерлюдия: мощности множествА насколько просто в теории Цермело-Френкеля рассуждать омощностях множеств?Для начала вернёмся к наивному определению мощностимножества:мощность множества X — этокласс всех множеств, равномощных XыА класс всех множеств, равномощных заданному — этомножество?А если это множество, то какая у него мощность?Интерлюдия: мощности множествА насколько просто в теории Цермело-Френкеля рассуждать омощностях множеств?Для начала вернёмся к наивному определению мощностимножества:мощность множества X — этокласс всех множеств, равномощных XыА класс всех множеств, равномощных заданному — этомножество?А если это множество, то какая у него мощность?Наивное определение мощности множества оказываетсяпарадоксальным в рамках теории Цермело-ФренкеляИнтерлюдия: мощности множествА насколько просто в теории Цермело-Френкеля рассуждать омощностях множеств?Для начала вернёмся к наивному определению мощностимножества:мощность множества X — этокласс всех множеств, равномощных XыА класс всех множеств, равномощных заданному — этомножество?А если это множество, то какая у него мощность?Наивное определение мощности множества оказываетсяпарадоксальным в рамках теории Цермело-ФренкеляЗначит, чтобы рассуждать о мощностях множеств в терминахтеории Цермело-Френкеля, требуется другое определениемощностиОрдиналыЧтобы рассуждать о мощности множеств в теорииЦермело-Френкеля, необходимо определить мощность какнекоторое (хорошее) множествоОрдиналыЧтобы рассуждать о мощности множеств в теорииЦермело-Френкеля, необходимо определить мощность какнекоторое (хорошее) множествоПопробуем сделать так:мощность множества X — это хорошее множество Y,такое что существует биекция X → YОрдиналыЧтобы рассуждать о мощности множеств в теорииЦермело-Френкеля, необходимо определить мощность какнекоторое (хорошее) множествоПопробуем сделать так:мощность множества X — это хорошее множество Y,такое что существует биекция X → YОсталось описать общий вид таких хороших множествОрдиналыЧтобы рассуждать о мощности множеств в теорииЦермело-Френкеля, необходимо определить мощность какнекоторое (хорошее) множествоПопробуем сделать так:мощность множества X — это хорошее множество Y,такое что существует биекция X → YОсталось описать общий вид таких хороших множествМножество X транзитивно, если каждый элемент X является егоподмножествомОрдиналыЧтобы рассуждать о мощности множеств в теорииЦермело-Френкеля, необходимо определить мощность какнекоторое (хорошее) множествоПопробуем сделать так:мощность множества X — это хорошее множество Y,такое что существует биекция X → YОсталось описать общий вид таких хороших множествМножество X транзитивно, если каждый элемент X является егоподмножествомМножество X — ординал, если оно и каждый его элементтранзитивныОрдиналыПримеры ординаловОрдиналыПримеры ординалов0=∅ОрдиналыПримеры ординалов0=∅1 = {∅}ОрдиналыПримеры ординалов0=∅1 = {∅}2 = {∅, {∅}}ОрдиналыПримеры ординалов0=∅1 = {∅}2 = {∅, {∅}}3 = {∅, {∅} , {∅, {∅}}}ОрдиналыПримеры ординалов0=∅1 = {∅}2 = {∅, {∅}}3 = {∅, {∅} , {∅, {∅}}}...n...ОрдиналыПримеры ординалов0=∅1 = {∅}2 = {∅, {∅}}3 = {∅, {∅} , {∅, {∅}}}...n...ω = N0ОрдиналыПримеры ординалов0=∅1 = {∅}2 = {∅, {∅}}3 = {∅, {∅} , {∅, {∅}}}...n...ω = N0ω + 1 = N0 ∪ {N0 }ОрдиналыПримеры ординалов0=∅1 = {∅}2 = {∅, {∅}}3 = {∅, {∅} , {∅, {∅}}}...n...ω = N0ω + 1 = N0 ∪ {N0 }ω + 2 = N0 ∪ {N0 , N0 ∪ {N0 }}ОрдиналыПримеры ординалов0=∅1 = {∅}2 = {∅, {∅}}3 = {∅, {∅} , {∅, {∅}}}...n...ω = N0ω + 1 = N0 ∪ {N0 }ω + 2 = N0 ∪ {N0 , N0 ∪ {N0 }}ω + 3 = N0 ∪ {N0 , N0 ∪ {N0 } , N0 ∪ {N0 , {N0 ∪ {N0 }}}}...ОрдиналыПримеры ординалов0=∅1 = {∅}2 = {∅, {∅}}3 = {∅, {∅} , {∅, {∅}}}...n...ω = N0ω + 1 = N0 ∪ {N0 }ω + 2 = N0 ∪ {N0 , N0 ∪ {N0 }}ω + 3 = N0 ∪ {N0 , N0 ∪ {N0 } , N0 ∪ {N0 , {N0 ∪ {N0 }}}}...2ω = ?...А какие ещё есть ординалы?ОрдиналыУтверждение: вложенность ординаловЕсли X — ординал и Y ∈ X, то Y — ординалОрдиналыУтверждение: вложенность ординаловЕсли X — ординал и Y ∈ X, то Y — ординалДоказательство.Множество Y транзитивно:Любой элемент Z множества Y транзитивен:ОрдиналыУтверждение: вложенность ординаловЕсли X — ординал и Y ∈ X, то Y — ординалДоказательство.Множество Y транзитивно: потому что Y ∈ X и X — ординалЛюбой элемент Z множества Y транзитивен:ОрдиналыУтверждение: вложенность ординаловЕсли X — ординал и Y ∈ X, то Y — ординалДоказательство.Множество Y транзитивно: потому что Y ∈ X и X — ординалЛюбой элемент Z множества Y транзитивен:Z ∈ Y и Y ∈ X, множество X транзитивноОрдиналыУтверждение: вложенность ординаловЕсли X — ординал и Y ∈ X, то Y — ординалДоказательство.Множество Y транзитивно: потому что Y ∈ X и X — ординалЛюбой элемент Z множества Y транзитивен:Z ∈ Y и Y ∈ X, множество X транзитивноТогда Z ∈ XОрдиналыУтверждение: вложенность ординаловЕсли X — ординал и Y ∈ X, то Y — ординалДоказательство.Множество Y транзитивно: потому что Y ∈ X и X — ординалЛюбой элемент Z множества Y транзитивен:Z ∈ Y и Y ∈ X, множество X транзитивноТогда Z ∈ X, и это означает, что множество Z транзитивноHОрдиналыУтверждение: вложенность ординаловЕсли X — ординал и Y ∈ X, то Y — ординалДоказательство.Множество Y транзитивно: потому что Y ∈ X и X — ординалЛюбой элемент Z множества Y транзитивен:Z ∈ Y и Y ∈ X, множество X транзитивноТогда Z ∈ X, и это означает, что множество Z транзитивноВведём порядок на множестве ординалов:X<Y⇔X∈YHОрдиналыУтверждение: вложенность ординаловЕсли X — ординал и Y ∈ X, то Y — ординалДоказательство.Множество Y транзитивно: потому что Y ∈ X и X — ординалЛюбой элемент Z множества Y транзитивен:Z ∈ Y и Y ∈ X, множество X транзитивноТогда Z ∈ X, и это означает, что множество Z транзитивноВведём порядок на множестве ординалов:X<Y⇔X∈YСледствие: индуктивность ординаловЛюбой ординал есть объединение всех меньшихординалов:X = {Y | Y < X}HОрдиналыУтверждение: фундированность ординаловДля любого ординала X и любой формулы ϕ(Y)множество {Y | Y < X & ϕ} существует и либо пусто, либоимеет минимальный элементОрдиналыУтверждение: фундированность ординаловДля любого ординала X и любой формулы ϕ(Y)множество {Y | Y < X & ϕ} существует и либо пусто, либоимеет минимальный элементДоказательство.По схеме выделения множество {Y | Y < X & ϕ} существуетОрдиналыУтверждение: фундированность ординаловДля любого ординала X и любой формулы ϕ(Y)множество {Y | Y < X & ϕ} существует и либо пусто, либоимеет минимальный элементДоказательство.По схеме выделения множество {Y | Y < X & ϕ} существуетПо аксиоме регулярности это множество содержит минимальныйэлемент (это подробно обсуждалось в лекции 14)HОрдиналыУтверждение: фундированность ординаловДля любого ординала X и любой формулы ϕ(Y)множество {Y | Y < X & ϕ} существует и либо пусто, либоимеет минимальный элементДоказательство.По схеме выделения множество {Y | Y < X & ϕ} существуетПо аксиоме регулярности это множество содержит минимальныйэлемент (это подробно обсуждалось в лекции 14)Hϕ-минимальный ординал, где ϕ — произвольное свойство, — этоординал X, удовлетворяющий свойству ϕ и такой что еслиY < X, то ординал Y не удовлетворяет свойству ϕОрдиналыУтверждение: фундированность ординаловДля любого ординала X и любой формулы ϕ(Y)множество {Y | Y < X & ϕ} существует и либо пусто, либоимеет минимальный элементДоказательство.По схеме выделения множество {Y | Y < X & ϕ} существуетПо аксиоме регулярности это множество содержит минимальныйэлемент (это подробно обсуждалось в лекции 14)Hϕ-минимальный ординал, где ϕ — произвольное свойство, — этоординал X, удовлетворяющий свойству ϕ и такой что еслиY < X, то ординал Y не удовлетворяет свойству ϕПо индуктивности и фундированности ординалов, еслисуществует ординал, удовлетворяющий свойству ϕ, тосуществует и ϕ-минимальный ординалОрдиналыУтверждение: фундированность ординаловДля любого ординала X и любой формулы ϕ(Y)множество {Y | Y < X & ϕ} существует и либо пусто, либоимеет минимальный элементДоказательство.По схеме выделения множество {Y | Y < X & ϕ} существуетПо аксиоме регулярности это множество содержит минимальныйэлемент (это подробно обсуждалось в лекции 14)Hϕ-минимальный ординал, где ϕ — произвольное свойство, — этоординал X, удовлетворяющий свойству ϕ и такой что еслиY < X, то ординал Y не удовлетворяет свойству ϕПо индуктивности и фундированности ординалов, еслисуществует ординал, удовлетворяющий свойству ϕ, тосуществует и ϕ-минимальный ординалПо аксиоме объёмности такой ординал единствененОрдиналыУтверждение: линейная упорядоченность ординалов< — отношение строгого линейного порядкаОрдиналыУтверждение: линейная упорядоченность ординалов< — отношение строгого линейного порядкаДоказательство.Антирефлексивность:Транзитивность:Линейность:ОрдиналыУтверждение: линейная упорядоченность ординалов< — отношение строгого линейного порядкаДоказательство.Антирефлексивность: потому что ∀x x ∈/xТранзитивность:Линейность:ОрдиналыУтверждение: линейная упорядоченность ординалов< — отношение строгого линейного порядкаДоказательство.Антирефлексивность: потому что ∀x x ∈/x(по аксиоме регулярности; подробно обсуждалось в лекции 14)Транзитивность:Линейность:ОрдиналыУтверждение: линейная упорядоченность ординалов< — отношение строгого линейного порядкаДоказательство.Антирефлексивность: потому что ∀x x ∈/x(по аксиоме регулярности; подробно обсуждалось в лекции 14)Транзитивность: если x ∈ y и y ∈ z, то по транзитивностиординала z верно x ∈ zЛинейность:ОрдиналыУтверждение: линейная упорядоченность ординалов< — отношение строгого линейного порядкаДоказательство.Антирефлексивность: потому что ∀x x ∈/x(по аксиоме регулярности; подробно обсуждалось в лекции 14)Транзитивность: если x ∈ y и y ∈ z, то по транзитивностиординала z верно x ∈ zЛинейность: Пусть существуют несравнимые ординалы X, YОрдиналыУтверждение: линейная упорядоченность ординалов< — отношение строгого линейного порядкаДоказательство.Антирефлексивность: потому что ∀x x ∈/x(по аксиоме регулярности; подробно обсуждалось в лекции 14)Транзитивность: если x ∈ y и y ∈ z, то по транзитивностиординала z верно x ∈ zЛинейность: Пусть существуют несравнимые ординалы X, YРассмотрим ϕ-минимальный ординал Z для такого свойства:ϕ: ∃Y ¬(X = Y ∨ X < Y ∨ Y < X)ОрдиналыУтверждение: линейная упорядоченность ординалов< — отношение строгого линейного порядкаДоказательство.Антирефлексивность: потому что ∀x x ∈/x(по аксиоме регулярности; подробно обсуждалось в лекции 14)Транзитивность: если x ∈ y и y ∈ z, то по транзитивностиординала z верно x ∈ zЛинейность: Пусть существуют несравнимые ординалы X, YРассмотрим ϕ-минимальный ординал Z для такого свойства:ϕ: ∃Y ¬(X = Y ∨ X < Y ∨ Y < X)Рассмотрим ψ-минимальный ординал U для такого свойства Y:ψ: ¬(Z = Y ∨ Z < Y ∨ Y < Z)ОрдиналыУтверждение: линейная упорядоченность ординалов< — отношение строгого линейного порядкаДоказательство.Антирефлексивность: потому что ∀x x ∈/x(по аксиоме регулярности; подробно обсуждалось в лекции 14)Транзитивность: если x ∈ y и y ∈ z, то по транзитивностиординала z верно x ∈ zЛинейность: Пусть существуют несравнимые ординалы X, YРассмотрим ϕ-минимальный ординал Z для такого свойства:ϕ: ∃Y ¬(X = Y ∨ X < Y ∨ Y < X)Рассмотрим ψ-минимальный ординал U для такого свойства Y:ψ: ¬(Z = Y ∨ Z < Y ∨ Y < Z)Тогда любой элемент u ординала Z является элементомординала U, и наоборотОрдиналыУтверждение: линейная упорядоченность ординалов< — отношение строгого линейного порядкаДоказательство.Антирефлексивность: потому что ∀x x ∈/x(по аксиоме регулярности; подробно обсуждалось в лекции 14)Транзитивность: если x ∈ y и y ∈ z, то по транзитивностиординала z верно x ∈ zЛинейность: Пусть существуют несравнимые ординалы X, YРассмотрим ϕ-минимальный ординал Z для такого свойства:ϕ: ∃Y ¬(X = Y ∨ X < Y ∨ Y < X)Рассмотрим ψ-минимальный ординал U для такого свойства Y:ψ: ¬(Z = Y ∨ Z < Y ∨ Y < Z)Тогда любой элемент u ординала Z является элементомординала U, и наоборотЗначит, Z = UОрдиналыУтверждение: линейная упорядоченность ординалов< — отношение строгого линейного порядкаДоказательство.Антирефлексивность: потому что ∀x x ∈/x(по аксиоме регулярности; подробно обсуждалось в лекции 14)Транзитивность: если x ∈ y и y ∈ z, то по транзитивностиординала z верно x ∈ zЛинейность: Пусть существуют несравнимые ординалы X, YРассмотрим ϕ-минимальный ординал Z для такого свойства:ϕ: ∃Y ¬(X = Y ∨ X < Y ∨ Y < X)Рассмотрим ψ-минимальный ординал U для такого свойства Y:ψ: ¬(Z = Y ∨ Z < Y ∨ Y < Z)Тогда любой элемент u ординала Z является элементомординала U, и наоборотЗначит, Z = U, что невозможно по построению этих ординалов HАрифметика ординаловТак какие же есть ординалы?Арифметика ординаловТак какие же есть ординалы?Начнём с множеств 0, 1, .