>>105199Вернёмся теперь к обычным отношениям. Мы определили, что такое свойство функциональности. Кроме функциональности, отношения могут обладать и другими свойствами. Итак, пусть φ - отношение на множестве X.
φ рефлексивно, если для любого x из X верно, что xφx.
φ симметрично, если для любых x, y из X из того, что xφy, вытекает, что yφx.
φ транзитивно, если для любых x, y, z из X из того, что xφy и yφz, вытекает, что xφz.
φ тотально, если для любых x, y из X верно, что xφy или yφx.
φ антирефлексивно, если для любого x из X неверно, что xφx.
φ антисимметрично, если для любых x, y из X из того, что xφy и yφx, вытекает, что x=y.
φ асимметрично, если для любых x, y из X неверно, что "xφy и yφx".
Отношение φ называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Отношение эквивалентности - это что-то вроде абстрактного равенства элементов. Рефлексивность значит, что каждый элемент эквивалентен сам себе. Симметричность означает, что если первый элемент эквивалентен второму, то и второй элемент эквивалентен первому. Транзитивность означает, что если первое эквивалентно второму, а второе - третьему, то первое и третье эквивалентны. Эквивалентностей бывает довольно много. Например, отношение "параллельность" на множестве всех прямых в плоскости является отношением эквивалентности.
Всякому отношению эквивалентности на каком-то множестве можно сопоставить одно-единственное разбиение этого множества на непересекающиеся классы: эквивалентные друг другу элементы образуют класс. Обратно, всякому разбиению множества на непересекающиеся классы можно сопоставить одно-единственное отношение эквивалентности: два элемента будут эквивалентными тогда и только тогда, когда они лежат в одном классе. Идея о разбиении множества на классы эквивалентности - это очень глубокая идея, встречающаяся не в одной только теории множеств, но и много где ещё.
Отношение φ называется отношением нестрогого частичного порядка, если оно рефлексивно, антисимметрично и транзитивно. Таковы, например, известные отношения ≤ и ≥ на множестве вещественных чисел. Важный пример нестрогого частичного порядка - это когда у нас есть множество M, и элементы ℘(M) упорядочены по включению, то есть xφy тогда и только тогда, когда x⊂y. Если отношение вдобавок тотально, то оно называется отношением линейного порядка. Тотальность означает, что любые два элемента сравнимы, что из любых двух элементов один больше другого. Бывают частично упорядоченные множества, в которых имеются несравнимые элементы. Например, таков булеан множества {1,2,3}; множества {1,2} и {2,3} несравнимы, ни одно из них не является подмножеством другого. Частично упорядоченные множества обычно называются ЧУМ или poset.
Отношение φ называется отношением строгого частичного порядка, если оно антирефлексивно и транзитивно. Таковы, например, отношения < и > на множестве вещественных чисел. Антирефлексивность означает, что ни для какого x не может случиться так, что x < x. Если это отношение вдобавок тотально, то оно называется отношением линейного порядка. Отношения линейного порядка обладают важным свойством. Для любых x и y выполняется один и только один из трёх вариантов: либо xφy, либо x=y, либо yφx. Это свойство называется трихотомией. Из антирефлексивности и транзитивности следует асимметричность (если есть такие x и y, что xφy и yφx, то по транзитивности xφx, что противоречит антирефлексивности). Асимметричность означает, что не бывает таких x и y, что x<y и y<x.
Если у нас есть отношение строгого порядка <, то мы всегда можем ввести по нему отношение нестрогого порядка: "x≤y" тогда и только тогда, когда "x<y или x=y". Обратно, по отношению нестрогого порядка ≤ мы всегда можем построить строгий порядок: "x<y" тогда и только тогда, когда "x≤y и x≠y". Поэтому мы можем позволить себе говорить просто об упорядоченных множествах; символ < всегда означает строгий порядок, ≤ - нестрогий. Ясно, что подмножество упорядоченного множества является, в свою очередь, упорядоченным множеством.
Пусть X - множество, упорядоченное отношением φ; пусть Y - множество, упорядоченное отношением ψ; пусть f - функция из X в Y.
Мы говорим, что f сохраняет порядок, если из того, что a φ b, следует, что f(a) ψ f(b).
Сохраняющую порядок биекцию мы называем порядковым изоморфизмом; сами множества мы называем порядково изоморфными.
Порядковый изоморфизм множества в себя мы назовём порядковым автоморфизмом.
Если φ и ψ являются отношениями строгого линейного порядка, то мы говорим, что функция f - строго монотонно возрастающая.
Пусть у нас есть упорядоченное множество M.
Элемент m называется максимальным, если для любого x из M неверно, что m < x.
Элемент m называется минимальным, если для любого x из M неверно, что x < m.
Элемент m называется наибольшим (синоним: последним), если для любого x из M верно, что x ≤ m.
Элемент m называется наименьшим (синоним: первым), если для любого x из M верно, что m ≤ x.
Во множестве может быть много минимальных и максимальных элементов, но наибольший элемент может быть только один и наименьший элемент может быть только один; впрочем, если множество упорядочено линейно, то максимальный элемент совпадает с наибольшим, а минимальный с наименьшим. Разумеется, ни минимальных, ни максимальных, ни наибольших, ни наименьших элементов во множестве может не быть вовсе.
Пусть X - подмножество M.
Элемент m из M называется верхней гранью (синоним: мажорантой) множества X, если для каждого x из X верно, что x ≤ m.
Элемент m из M называется нижней гранью (синоним: минорантой) множества X, если для каждого x из X верно, что m ≤ x.
Наименьший элемент множества всех мажорант X называется "супремум X".
Наибольший элемент множества всех минорант X называется "инфимум X".
X называется ограниченным сверху, если у него есть хотя бы одна мажоранта.
X называется ограниченным снизу, если у него есть хотя бы одна миноранта.
Множество может быть ограниченным сверху, но не иметь супремума; может быть ограниченным снизу, но не иметь инфимума.
Множество, упорядоченное отношением линейного порядка, называется вполне упорядоченным, если каждое непустое его подмножество имеет наименьший элемент. В частности, если множество непусто, то оно (так как является своим подмножеством) имеет наименьший элемент.
Упорядоченное множество X называется направленным, если для любых x, y из X существует такой z из X, что x≤z, y≤z.
Подмножество Y в упорядоченном множество X называется кофинальным (или конфинальным) множеству X, если для любого x из X существует такой y из Y, что x≤y.
С помощью функций и порядков мы вырвемся за пределы конечных совокупностей.
В 1638 году Галилей опубликовал свою книгу "Две науки". В ней содержалось несколько диалогов, излагающих взгляды Галилея; диалоги вели персонажи по имени Симплицио и Сальвати. Между всем прочим, эти персонажи обсуждали идею бесконечного. Сальвати предложил Симплицио рассмотреть целые положительные числа. Некоторые из них, как известно, являются квадратами: например, 4 является квадратом 2, а 9 является квадратом 3. Однако же некоторые числа, например 17, не являются квадратом никакого целого числа. Поскольку целое больше своей части, следует думать, что чисел, являющихся квадратами, меньше, чем всех положительных целых чисел; это с одной стороны. С другой стороны, каждое число можно возвести в квадрат, а это означает, что целых чисел ровно столько же, сколько и всех квадратов; каждому положительному целому числу соответствует один определённый квадрат. Таким образом, говорил Сальвати, мы имеем противоречие: часть и меньше целого, и равна ему.
Это рассуждение известно как парадокс Галилея. Галилей считал свой парадокс свидетельством, что бесконечные множества непознаваемы. Но на самом деле это лишь кажущийся парадокс, связанный с недостаточной продуманностью понятия "больше". Если уточнить, что же означает понятие "больше", то парадокс исчезает. На самом деле Галилей открыл вовсе не парадокс: он открыл, что совокупность целых чисел может быть биективно отображена на своё собственное подмножество (забегая вперёд, скажу, что если между неким множеством и совокупностью целых чисел есть хотя бы одна биекция, то это множество называется счётным). Галилей не был первым, кто размышлял над идеей взаимно-однозначного соответствия между бесконечными множествами. За тысячи лет до него Аристотель размышлял об ободе колеса, который демонстрировал, казалось бы, противоречивые свойства. Тем не менее, лишь в конце XIX века люди перестали рассматривать существование биекций между всей совокупностью и некоторой её частью как что-то противоречивое. Среди всех учёных, рамышлявших над биекциями такого рода, дальше всех продвинулись Дедекинд и особенно Кантор. Кантор практически единолично определил ключевые понятия теории множеств. Он всего в нескольких публикациях сумел ввести основные понятия теории множеств, классифицировать бесконечности, создать теорию кардиналов и теорию ординалов, а также мимоходом изобрести теоретико-множественную топологию.
Философские идеи Кантора казались его современникам довольно туманными. Они даже в наши дни выглядят несколько размыто. Вот предположим прежде всего, что нам даны совокупности предметов, причём они даны нам в каком-то порядке. Чтобы исследовать эти совокупности, нужно уметь выделять в них какие-то общие черты. Ради этого нужно абстрагироваться от частностей.
Нашим первым актом абстрагирования будет отказ от исследования природы данных нам предметов и изучение только лишь того порядка, в котором они нам даны. После этого первого абстрагирования у нас от конкретного множества останется лишь его
порядковый тип. Порядковый тип - это то общее, что имеют между собой одинаково упорядоченные множества. Порядковые типы разных множеств довольно сильно различаются между собой. Например, во множестве положительных целых чисел есть первый элемент: число 1. А вот во множестве всех вещественных чисел первого элемента нет. Или вот во множестве всех вещественных чисел между любыми двумя не равными друг другу числами имеется ещё бесконечно много других чисел, а во множестве целых чисел между двумя числами имеется только лишь конечное количество точек. Порядковых типов очень много; всё ещё слишком много, чтобы устанавливать о них теоремы. Чтобы начать развивать теорию порядковых типов, нужно ещё немного сузить границы рассматриваемого. Ограничимся рассмотрением типов вполне упорядоченных множеств. Такие порядковые типы называются ординалами.
А что будет, если мы позволим себе переупорядочивать элементы? Что, если мы совершим второй акт абстрагирования: забудем даже и о том, в каком порядке даны нам элементы множества? В таком случае от множества останется лишь его
мощность: количество элементов, которое это множество содержало. Два множества имеют одну и ту же мощность, если между ними можно установить хотя бы одно взаимно-однозначное соответствие. Например, в рассуждении Галилея устанавливается взаимно-однозначное соответствие между целыми положительными числами и их квадратами; это значит, что два этих множества
равномощны. Мощность - это то общее, что есть у равномощных друг другу множеств. Мощность множества есть некое особое, новое число:
кардинальное число. Введение кардинальных чисел оправдано тем, что, оказывается, существуют разные бесконечности: имеются такие бесконечные множества, что между ними не существует ни одной биекции.
Теперь мы сосредоточимся на том, чтобы, пользуясь всеми введёнными ранее понятиями, изложить, что же всё-таки такое ординалы и кардиналы. Можно было бы убедиться, что отношение "быть порядково изоморфным" и "быть равномощным" - это отношения эквивалентности, и попросту объявить ординалами и кардиналами классы эквивалентности по этим отношениям. Проблема в том, что даже один-единственный класс всех равномощных друг другу множеств уже слишком велик, чтобы быть множеством. То есть при таком подходе ординалы и кардиналы не будут множествами и, стало быть, не будут постижимы средствами ZFC, а мы всё-таки хотим, чтобы ординалы и кардиналы были объектами, которые мы можем изучать. Поэтому мы будем следовать другому подходу, который развивали Цермело, Френкель и фон Нейман: создадим в качестве ординалов и кардиналов некоторые особо хорошие, избранные множества, и затем укажем способ, с помощью которого можно сопоставлять эти ординалы и кардиналы произвольным множествам.
Предположим, что у нас есть вполне упорядоченное множество. Предположим, что у нас есть монотонно возрастающее отображение, отображающее это множество в себя. Я утверждаю, что тогда каждый элемент нашего множества либо меньше своего образа, либо равен ему. Докажем это, рассмотрев совокупность тех элементов, которые больше своих образов, - то есть совокупность тех элементов, образы которых меньше их. Совокупность таких элементов, как и всякая часть нашего множества, имеет наименьший элемент. Для этого элемента, как и для любого другого элемента интересующей нас совокупности, имеем неравенство: образ элемента меньше элемента. Если мы применим к этому неравенству наше монотонно возрастающее отображение, то получим другое неравенство: образ образа элемента меньше образа элемента. Откуда получаем, что образ элемента входит в рассматриваемую нами совокупность. Этого быть не может.
Множество всех элементов вполне упорядоченного множества, меньших элемента x, называется начальным отрезком этого множества, заданным концом x.
Никакое вполне упорядоченное множество не изоморфно своему начальному отрезку. В противном случае конец отрезка был бы больше своего образа.
Докажем теперь, что единственный порядковый автоморфизм вполне упорядоченного множества - тождественное отображение. В самом деле, автоморфизм - возрастающая функция. Мы выяснили, что в таком случае каждый элемент меньше или равен своему образу. По свойству автоморфизма это означает, что прообраз каждого элемента больше или равен самому элементу. Отсюда применением отображения получаем, что каждый элемент больше или равен своему образу. Таким образом, верны два факта: каждый элемент и больше или равен своему образу, и меньше или равен своему образу. Это возможно лишь в том случае, когда каждый элемент равен своему образу.
Из этого следует, что если два вполне упорядоченных множества изоморфны, то этот изоморфизм единствен. Если бы было два изоморфизма, то, взяв композицию первого изоморфизма и обратного второму, а затем композицию второго и обратного первому, мы получили бы два разных автоморфизма, чего не может быть.
Этой теории достаточно, чтобы доказать
теорему. Пусть есть два вполне упорядоченных множества, назовём их X и Y. Тогда выполняется один и только один случай: либо они изоморфны, либо первое изоморфно начальному отрезку второго, либо второе изоморфно начальному отрезку первого.
Доказательство.
Определим отображение f, отображающее некое подмножество первого множества (возможно, пустое) во второе множество. Положим f(x) = y, если начальный отрезок первого множества с концом в x с помощью какого-нибудь изоморфизма изоморфен начальному отрезку второго множества с концом в y. Это определение могло бы быть некорректным: если бы начальный отрезок с концом в x был бы изоморфен двум разным начальным отрезкам второго множества, то мы бы получили, что x может отображаться в два разных элемента второго множества, то есть символ f(x) был бы неоднозначным. Однако в таком случае, так как один из двух этих отрезков является начальным отрезком другого, мы бы получили изоморфизм вполне упорядоченного множества на его начальный отрезок, чего не может быть. Так что определение отображения f корректно.
Похожим образом можно доказать, что отображение f инъективно - разные точки переходят в разные. Ибо если бы оно не было инъективно, то некие две разные точки переходили бы в одну, и некий начальный отрезок первого множества был бы изоморфен своему начальному отрезку.
Докажем, что отображение f сохраняет порядок. Рассмотрим два элемента из домена f, первый меньше второго. Назовём их x1 и x2, x1 < x2. Нам нужно доказать, что f(x1) < f(x2). Для этого заметим, что, по определению f, имеются некие изоморфизмы g и h, которые переводят отрезки первого множества, заданные элементами x1 и x2, в отрезки второго множества, заданные соответственно элементами f(x1) и f(x2). От противного предположим, что f(x2) ≤ f(x1). Тогда h∘g' будет изоморфизмом вполне упорядоченного множества, - отрезка, заданного элементом f(x1), - на свой начальный отрезок, что невозможно. Поэтому предлположение неверно, и f(x1) < f(x2).
Отображение f инъективно и сохраняет порядок. Поэтому оно является биекцией (домена на образ, но не обязательно биекцией X и Y, так как образ f может отличаться от Y), и, следовательно, f является изоморфизмом. С помощью этого факта докажем саму теорему.
Если домен f совпадает с X, а образ f совпадает с Y, то X и Y изоморфны с помощью отображения f. Это даёт нам первый случай.
Если домен f не совпадает с X, то множество X\dom(f) непусто, поэтому в нём есть наименьший элемент, обозначим его x. Предположим, что образ f не совпадает с Y. Множество Y\im(f) тоже непусто, и в нём тоже есть наименьший элемент, обозначим его y. Элемент x задаёт начальный отрезок множества X. На нём функция f определена, ибо x - наименьший из элементов, на которых f не определена. Элемент y, в свою очередь, задаёт начальный отрезок множества Y, причём этот начальный отрезок совпадает с образом f. Получается, что отображение f есть изоморфизм начального отрезка, заданного элементом x, на начальный отрезок, заданный элементом y. Но в таком случае, по определению f, отображение f должно быть определено в точке x и причём f(x) = y. Противоречие означает, что образ f совпадает со множеством Y, что даёт нам второй случай.
Третий случай получается аналогично второму. Пусть образ f не совпадает с Y, в таком случае предположим, что домен f не совпадает с X, откуда выведем противоречие, которое будет означать, что домен f совпадает с X.
Все случаи разобраны, теорема доказана.
