Введение в теорию множеств

Эквивалентность и порядок. Изоморфизмы

Разбить на страницы
Показывать лекцию целиком

Отношения эквивалентности и порядка

Напомним, что бинарным отношением на множестве $$X$$ называется подмножество $$R\hm\subset X\hm\times X$$ ; вместо $$\langle x_1,x_2\rangle \hm\in R$$ часто пишут $$x_1 R x_2$$.

Бинарное отношение $$R$$ на множестве $$X$$ называется отношением эквивалентности, если выполнены следующие свойства:

  • (рефлексивность) $$xRx$$ для всех $$x\hm\in X$$ ;
  • (симметричность) $$xRy \hm\Rightarrow yRx$$ для всех $$x,y\hm\in X$$ ;
  • (транзитивность) $$xRy \text{ и } yRz \hm\Rightarrow xRz$$ для любых элементов $$x,y,z\hm \in X$$.
    •

    Имеет место следующее очевидное, но часто используемое утверждение:

    Теорема 11. (а) Если множество $$X$$ разбито в объединение непересекающихся подмножеств, то отношение " лежать в одном подмножестве" является отношением эквивалентности.

    (б) Всякое отношение эквивалентности получается описанным способом из некоторого разбиения.

    Доказательство. Первое утверждение совсем очевидно; мы приведем доказательство второго, чтобы было видно, где используются все пункты определения эквивалентности. Итак, пусть $$R$$ - отношение эквивалентности. Для каждого элемента $$x\hm\in X$$ рассмотрим его класс эквивалентности - множество всех $$y\in X$$, для которых верно $$xRy$$.

    Докажем, что для двух различных $$x_1$$, $$x_2$$ такие множества либо не пересекаются, либо совпадают. Пусть они пересекаются, то есть имеют общий элемент $$z$$. Тогда $$x_1 R z$$ и $$x_2 R z$$, откуда $$z R x_2$$ (симметричность) и $$x_1 R x_2$$ (транзитивность), а также $$x_2 R x_1$$ (симметричность). Поэтому для любого $$z$$ из $$x_1 R z$$ следует $$x_2 R z$$ (транзитивность) и наоборот.

    Осталось заметить, что в силу рефлексивности каждый элемент $$x$$ принадлежит задаваемому им классу, то есть действительно все множество $$X$$ разбито на непересекающиеся классы.

    78. Покажите, что требования симметричности и транзитивности можно заменить одним: $$\text{xRz и yRz} \Rightarrow xRy$$ (при сохранении требования рефлексивности).

    79. Сколько различных отношений эквивалентности существует на множестве $$\{1,2,3,4,5\}$$?

    80. На множестве $$M$$ задано два отношения эквивалентности, обозначаемые $$\sim_1$$ и $$\sim_2$$, имеющие $$n_1$$ и $$n_2$$ классов эквивалентности соответственно. Будет ли их пересечение $$x\sim y \hm\Leftrightarrow [(x\sim_1 y)\text{ и }(x\sim_2 y)]$$ отношением эквивалентности? Сколько у него может быть классов? Что можно сказать про объединение отношений?

    81. (Теорема Рамсея) Множество всех $$k$$ - элементных подмножеств бесконечного множества $$A$$ разбито на $$l$$ классов ( $$k$$, $$l$$ - натуральные числа). Докажите, что найдется бесконечное множество $$B\hm\subset A$$, все $$k$$ - элементные подмножества которого принадлежат одному классу.

    (При $$k\hm=1$$ это очевидно: если бесконечное множество разбито на конечное число классов, то один из классов бесконечен. При $$k=2$$ и $$l=2$$ утверждение можно сформулировать так: из бесконечного множества людей можно выбрать либо бесконечно много попарно знакомых, либо бесконечно много попарно незнакомых. Конечный вариант этого утверждения - о том, что среди любых шести людей есть либо три попарно знакомых, либо три попарно незнакомых, - известная задача для школьников.)

    Множество классов эквивалентности называют фактор - множеством множества $$X$$ по отношению эквивалентности $$R$$. (Если отношение согласовано с дополнительными структурами на $$X$$, получаются фактор - группы, фактор - кольца и т.д)

    Отношения эквивалентности нам не раз еще встретятся, но сейчас наша основная тема - отношения порядка.

    Бинарное отношение $$\le$$ на множестве $$X$$ называется отношением частичного порядка, если выполнены такие свойства:

  • (рефлексивность) $$x\le x$$ для всех $$x\hm\in X$$ ;
  • (антисимметричность) $$x\le y \text{ и } y\le x \hm\Rightarrow x\hm=y$$ для всех $$x,y\hm\in X$$ ;
  • (транзитивность) $$x\le y\text{ и }y\le z \hm\Rightarrow x\hm\le z$$ для всех $$x,y,z\hm \in X$$.
    •

    (Следуя традиции, мы используем символ $$\le$$ (а не букву) как знак отношения порядка.) Множество с заданным на нем отношением частичного порядка называют частично упорядоченным.

    Говорят, что два элемента $$x,y$$ частично упорядоченного множества сравнимы, если $$x\le y$$ или $$y\le x$$. Заметим, что определение частичного порядка не требует, чтобы любые два элемента множества были сравнимы. Добавив это требование, мы получим определение линейного порядка ( линейно упорядоченного множества ).

    Приведем несколько примеров частичных порядков:

  • Числовые множества с обычным отношением порядка (здесь порядок будет линейным).
  • На множестве $$\mathbb{R}\hm\times\mathbb{R}$$ всех пар действительных чисел можно ввести частичный порядок, считая, что $$\langle x_1,x_2\rangle \hm\le \langle y_1,y_2\rangle$$, если $$x_1\hm\le x_2$$ и $$y_1\hm\le y_2$$. Этот порядок уже не будет линейным: пары $$\langle 0,1\rangle$$ и $$\langle 1,0\rangle$$ не сравнимы.
  • На множестве функций с действительными аргументами и значениями можно ввести частичный порядок, считая, что $$f\hm\le g$$, если $$f(x)\hm\le g(x)$$ при всех $$x\in\bbR$$. Этот порядок не будет линейным.
  • На множестве целых положительных чисел можно определить порядок, считая, что $$x\hm\le y$$, если $$x$$ делит $$y$$. Этот порядок тоже не будет линейным.
  • Отношение " любой простой делитель числа $$x$$ является также и делителем числа $$y$$ " не будет отношением порядка на множестве целых положительных чисел (оно рефлексивно и транзитивно, но не антисимметрично).
  • Пусть $$U$$ - произвольное множество. Тогда на множестве $$P(U)$$ всех подмножеств множества $$U$$ отношение включения $$\subset$$ будет частичным порядком.
  • На буквах русского алфавита традиция определяет некоторый порядок ( $$\text{а}\hm\le\text{б}\hm\le\text{в}\hm\le\ldots\hm\le\text{я}$$ ). Этот порядок линеен - про любые две буквы можно сказать, какая из них раньше (при необходимости заглянув в словарь).
  • На словах русского алфавита определен лексикографический порядок (как в словаре). Формально определить его можно так: если слово $$x$$ является началом слова $$y$$, то $$x\hm\le y$$ (например, $$\text{кант}\hm\le\text{кантор}$$ ). Если ни одно из слов не является началом другого, посмотрим на первую по порядку букву, в которой слова отличаются: то слово, где эта буква меньше в алфавитном порядке, и будет меньше. Этот порядок также линеен (иначе что бы делали составители словарей?).
  • Отношение равенства ( $$(x\hm\le y)\hm\Leftrightarrow (x\hm=y)$$ ) также является отношением частичного порядка, для которого никакие два различных элемента не сравнимы.
  • Приведем теперь бытовой пример. Пусть есть множество $$X$$ картонных коробок. Введем на нем порядок, считая, что $$x\hm\le y$$, если коробка $$x$$ целиком помещается внутрь коробки $$y$$ (или если $$x$$ и $$y$$ - одна и та же коробка). В зависимости от набора коробок этот порядок может быть или не быть линейным.
    •

    Пусть $$x,y$$ - элементы частично упорядоченного множества $$X$$. Говорят, что $$x<y$$, если $$x\le y$$ и $$x\ne y$$. Для этого отношения выполнены такие свойства: $$\begin{gather*} x \not< x;\\ (x< y) \text{ и } (y < z)\ \Rightarrow\ x < z. \end{gather*}$$ (Первое очевидно, проверим второе: если $$x\hm<y$$ и $$y\hm<z$$, то есть $$x\hm\le y$$, $$x\hm\ne y$$, $$y\hm\le z$$, $$y\hm\ne z$$, то $$x\hm\le z$$ по транзитивности; если бы оказалось, что $$x\hm=z$$, то мы бы имели $$x\hm\le y\hm\le x$$ и потому $$x\hm=y$$ по антисимметричности, что противоречит предположению.)

    Терминологическое замечание: мы читаем знак $$\le$$ как " меньше или равно", а знак $$<$$ - как " меньше", неявно предполагая, что $$x\hm\le y$$ тогда и только тогда, когда $$x\hm<y$$ или $$x\hm=y$$. К счастью, это действительно так. Еще одно замечание: выражение $$x\hm>y$$ (" $$x$$ больше $$y$$ ") означает, что $$y\hm<x$$, а выражение $$x\ge y$$ (" $$x$$ больше или равно $$y$$ ") означает, что $$y\hm\le x$$.

    82. Объясните, почему не стоит читать $$x\hm\le y$$ как " $$x$$ не больше $$y$$ ".

    В некоторых книжках отношение частичного порядка определяется как отношение $$<$$, удовлетворяющее двум указанным свойствам. В этом случае отношение $$x\hm\le y \hm\Leftrightarrow [(x\hm<y) \text{ или } (x\hm=y)]$$ является отношением частичного порядка в смысле нашего определения.

    83.Проверьте это.

    Во избежание путаницы отношение $$<$$ иногда называют отношением строгого порядка, а отношение $$\le$$ - отношением нестрогого порядка. Одно и то же частично упорядоченное множество можно задавать по - разному: можно сначала определить отношение нестрогого порядка $$\le$$ (рефлексивное, антисимметричное и транзитивное) и затем из него получить отношение строгого порядка $$<$$, а можно действовать и наоборот.

    84. Опуская требование антисимметричности в определении частичного порядка, получаем определение предпорядка. Докажите, что любой предпорядок устроен так: множество делится на непересекающиеся классы, при этом $$x\hm\le y$$ для любых двух элементов $$x$$, $$y$$ из одного класса, а на фактор - множестве задан частичный порядок, который и определяет результат сравнения двух элементов из разных классов.

    Вот несколько конструкций, позволяющих строить одни упорядоченные множества из других.

  • Пусть $$Y$$ - подмножество частично упорядоченного множества $$(X,\le)$$. Тогда на множестве $$Y$$ возникает естественный частичный порядок, индуцированный из $$X$$. Формально говоря,$$(\le _Y) = (\le) \cap (Y\times Y).$$ Если порядок на $$X$$ был линейным, то и индуцированный порядок на $$Y$$, очевидно, будет линейным.
  • Пусть $$X$$ и $$Y$$ - два непересекающихся частично упорядоченных множества. Тогда на их объединении можно определить частичный порядок так: внутри каждого множества элементы сравниваются как раньше, а любой элемент множества $$X$$ по определению меньше любого элемента $$Y$$. Это множество естественно обозначить $$X+Y$$. (Порядок будет линейным, если он был таковым на каждом из множеств.)

    Это же обозначение применяют и для пересекающихся (и даже совпадающих множеств). Например, говоря об упорядоченном множестве $$\mathbb{N}+\mathbb{N}$$, мы берем две непересекающиеся копии натурального ряда $$\{0,1,2,\dots\}$$ и $$\{\overline 0,\overline 1,\overline 2,\dots\}$$ и рассматриваем множество $$\{0,1,2,\dots,\overline 0, \overline1, \overline2,\dots\}$$, причем $$k\le \overline l$$ при всех $$k$$ и $$l$$, а внутри каждой копии порядок обычный.

  • Пусть $$(X, \le_{X})$$ и $$(Y,\le_Y)$$ - два упорядоченных множества. Можно определить порядок на произведении $$X\hm\times Y$$ несколькими способами. Можно считать, что $$\langle x_1,y_1\rangle \hm\le \langle x_2,y_2\rangle$$, если $$x_1 \le_X x_2$$ и $$y_1\le_Y y_2$$ (покоординатное сравнение). Этот порядок, однако, не будет линейным, даже если исходные порядки и были линейными: если первая координата больше у одной пары, а вторая у другой, как их сравнить? Чтобы получить линейный порядок, договоримся, какая координата будет " главной" и будем сначала сравнивать по ней, а потом (в случае равенства) - по другой. Если главной считать $$X$$ - координату, то $$\langle x_1,y_1\rangle \hm\le\langle x_2,y_2\rangle$$, если $$x_1 <_X x_2$$ или если $$x_1=x_2$$, а $$y_1 \le_Y y_2$$. Однако по техническим причинам удобно считать главной вторую координату. Говоря о произведении двух линейно упорядоченных множеств как о линейно упорядоченном множестве, мы в дальнейшем подразумеваем именно такой порядок (сначала сравниваем по второй координате).
    •

    85. Докажите, что в частично упорядоченном множестве $$\mathbb{N}\hm\times\mathbb{N}$$ (порядок покоординатный) нет бесконечного подмножества, любые два элемента которого были бы несравнимы. Верно ли аналогичное утверждение для $$\mathbb{Z}\hm\times\mathbb{Z}$$?

    86. Докажите аналогичное утверждение для $$\mathbb{N}^k$$ (порядок покоординатный).

    87. Пусть $$U$$ - конечное множество из $$n$$ элементов. Рассмотрим множество $$P(U)$$ всех подмножеств множества $$U$$, упорядоченное по включению. Какова максимально возможная мощность множества $$S\subset P(U)$$, если индуцированный на $$S$$ порядок линеен? если никакие два элемента $$S$$ не сравнимы? (Указание: см. задачу 14.)

    88. Сколько существует различных линейных порядков на множестве из $$n$$ элементов?

    89. Докажите, что всякий частичный порядок на конечном множестве можно продолжить до линейного (" продолжить" означает, что если $$x\hm\le y$$ в исходном порядке, то и в новом это останется так).

    90. Дано бесконечное частично упорядоченное множество $$X$$. Докажите, что в нем всегда найдется либо бесконечное подмножество попарно несравнимых элементов, либо бесконечное подмножество, на котором индуцированный порядок линеен.

    91. (Конечный вариант предыдущей задачи.) Даны целые положительные числа $$m$$ и $$n$$. Докажите, что во всяком частично упорядоченном множестве мощности $$mn+1$$ можно указать либо $$m+1$$ попарно несравнимых элементов, либо $$n+1$$ попарно сравнимых.

    92. В строчку написаны $$mn+1$$ различных чисел. Докажите, что можно часть из них вычеркнуть так, чтобы осталась либо возрастающая последовательность длины $$m+1$$, либо убывающая последовательность длины $$n+1$$. (Указание: можно воспользоваться предыдущей задачей.)

    93. Рассмотрим семейство всех подмножеств натурального ряда, упорядоченное по включению. Существует ли у него линейно упорядоченное (в индуцированном порядке) подсемейство мощности континуум? Существует ли у него подсемейство мощности континуум, любые два элемента которого несравнимы?

    Элемент частично упорядоченного множества называют наибольшим, если он больше любого другого элемента, и максимальным, если не существует большего элемента. Если множество не является линейно упорядоченным, то это не одно и то же: наибольший элемент автоматически является максимальным, но не наоборот. (Одно дело коробка, в которую помещается любая другая, другое - коробка, которая никуда больше не помещается.)

    Аналогичным образом определяются наименьшие и минимальные элементы.

    Легко понять, что наибольший элемент в данном частично упорядоченном множестве может быть только один, в то время как максимальных элементов может быть много.

    94. Докажите, что любые два максимальных элемента не сравнимы. Докажите, что в конечном частично упорядоченном множестве $$X$$ для любого элемента $$x$$ найдется максимальный элемент $$y$$, больший или равный $$x$$.

    Изоморфизмы

    Два частично упорядоченных множества называются изоморфными, если между ними существует изоморфизм, то есть взаимно однозначное соответствие, сохраняющее порядок. (Естественно, что в этом случае они равномощны как множества.) Можно сказать так: биекция $$f\colon A\hm\to B$$ называется изоморфизмом частично упорядоченных множеств $$A$$ и $$B$$, если$$a_1 \le a_2 \ \Leftrightarrow \ f(a_1) \le f(a_2)$$ для любых элементов $$a_1,a_2\hm\in A$$ (слева знак $$\le$$ обозначает порядок в множестве $$A$$, справа - в множестве $$B$$ ).

    Очевидно, что отношение изоморфности рефлексивно (каждое множество изоморфно самому себе), симметрично (если $$X$$ изоморфно $$Y$$, то и наоборот) и транзитивно (два множества, изоморфные третьему, изоморфны между собой). Таким образом, все частично упорядоченные множества разбиваются на классы изоморфных, которые называют порядковыми типами. (Правда, как и с мощностями, тут необходима осторожность - изоморфных множеств слишком много, и потому говорить о порядковых типах как множествах нельзя.)

    Теорема 12. Конечные линейно упорядоченные множества из одинакового числа элементов изоморфны.

    Доказательство. Конечное линейно упорядоченное множество всегда имеет наименьший элемент (возьмем любой элемент; если он не наименьший, возьмем меньший, если и он не наименьший, еще меньший - и так далее; получим убывающую последовательность $$x\hm>y\hm>z\hm>\ldots$$, которая рано или поздно должна оборваться). Присвоим наименьшему элементу номер $$1$$. Из оставшихся снова выберем наименьший элемент и присвоим ему номер $$2$$ и так далее. Легко понять, что порядок между элементами соответствует порядку между номерами, то есть что наше множество изоморфно множеству $$\{1,2,\dots,n\}$$.

    95. Докажите, что множество всех целых положительных делителей числа $$30$$ с отношением " быть делителем" в качестве отношения порядка изоморфно множеству всех подмножеств множества $$\{a,b,c\}$$, упорядоченному по включению.

    96. Будем рассматривать финитные последовательности натуральных чисел, то есть последовательности, у которых все члены, кроме конечного числа, равны $$0$$. На множестве таких последовательностей введем покомпонентный порядок: $$(a_0,a_1,\dots) \hm\le (b_0,b_1,\dots)$$, если $$a_i\hm\le b_i$$ при всех $$i$$. Докажите, что это множество изоморфно множеству всех положительных целых чисел с отношением " быть делителем" в качестве порядка.

    Взаимно однозначное отображение частично упорядоченного множества $$A$$ в себя, являющееся изоморфизмом, называют автоморфизмом частично упорядоченного множества $$A$$. Тождественное отображение всегда является автоморфизмом, но для некоторых множеств существуют и другие автоморфизмы. Например, отображение прибавления единицы ( $$x\mapsto x+1$$ ) является автоморфизмом частично упорядоченного множества $$\bbZ$$ целых чисел (с естественным порядком). Для множества натуральных чисел та же формула не дает автоморфизма (нет взаимной однозначности).

    97. Покажите, что не существует автоморфизма упорядоченного множества $$\bbN$$ натуральных чисел, отличного от тождественного.

    98. Рассмотрим множество $$P(A)$$ всех подмножеств некоторого $$k$$ - элементного множества $$A$$, частично упорядоченное по включению. Найдите число автоморфизмов этого множества.

    99. Покажите, что множество целых положительных чисел, частично упорядоченное отношением " $$x$$ делит $$y$$ ", имеет континуум различных автоморфизмов.

    Вот несколько примеров равномощных, но не изоморфных линейно упорядоченных множеств (в силу теоремы 12 они должны быть бесконечными).

  • Отрезок $$[0,1]$$ (с обычным отношением порядка) не изоморфен множеству $$\bbR$$, так как у первого есть наибольший элемент, а у второго нет. (При изоморфизме наибольший элемент, естественно, должен соответствовать наибольшему.)
  • Множество $$\bbZ$$ (целые числа с обычным порядком) не изоморфно множеству $$\bbQ$$ (рациональные числа). В самом деле, пусть $$\alpha\colon\bbZ\hm\to\bbQ$$ является изоморфизмом. Возьмем два соседних целых числа, скажем, $$2$$ и $$3$$. При изоморфизме $$\alpha$$ им должны соответствовать какие - то два рациональных числа $$\alpha(2)$$ и $$\alpha(3)$$, причем $$\alpha(2)\hm<\alpha(3)$$, так как $$2\hm<3$$. Но тогда рациональным числам между $$\alpha(2)$$ и $$\alpha(3)$$ должны соответствовать целые числа между $$2$$ и $$3$$, которых нет.
  • Более сложный пример - множества $$\bbZ$$ и $$\bbZ\hm+\bbZ$$. Возьмем в $$\bbZ\hm+\bbZ$$ две копии нуля (из той и другой компоненты); мы обозначали их $$0$$ и $$\overline 0$$. При этом $$0\hm<\overline 0$$. При изоморфизме им должны соответствовать два целых числа $$a$$ и $$b$$, для которых $$a\hm<b$$. Тогда всем элементам между $$0$$ и $$\overline 0$$ (их бесконечно много: $$1$$, $$2$$, $$3$$, $$\dots$$, $$-\overline3$$, $$-\overline2$$, $$-\overline1$$ ) должны соответствовать числа между $$a$$ и $$b$$ - но их лишь конечное число.

    Этот пример принципиально отличается от предыдущих тем, что здесь разницу между свойствами множеств нельзя записать формулой. Как говорят, упорядоченные множества $$\bbZ$$ и $$\bbZ\hm+\bbZ$$ " элементарно эквивалентны".

    •

    100. Докажите, что линейно упорядоченные множества $$\bbZ\hm\times\bbN$$ и $$\bbZ\hm\times\bbZ$$ (с описанным выше порядком) не изоморфны.

    101. Будут ли изоморфны линейно упорядоченные множества $$\bbN\hm\times\bbZ$$ и $$\bbZ\hm\times\bbZ$$?

    102.Будут ли изоморфны линейно упорядоченные множества $$\bbQ\hm\times\bbZ$$ и $$\bbQ\hm\times\bbN$$?

    Отображение $$x\hm\mapsto \sqrt{2}x$$ осуществляет изоморфизм между интервалами $$(0,1)$$ и $$(0,\sqrt{2})$$. Но уже не так просто построить изоморфизм между множествами рациональных точек этих интервалов (то есть между $$\bbQ\hm\cap(0,1)$$ и $$\bbQ\hm\cap(0,\sqrt{2})$$ ), поскольку умножение на $$\sqrt{2}$$ переводит рациональные числа в иррациональные. Тем не менее изоморфизм построить можно. Для этого надо взять возрастающие последовательности рациональных чисел $$0\hm<x_1\hm<x_2\hm<\dots$$ и $$0\hm< y_1\hm<y_2\hm<\dots$$, сходящиеся соответственно к $$1$$ и $$\sqrt{2}$$ и построить кусочно - линейную функцию $$f$$, которая переводит $$x_i$$ в $$y_i$$ и линейна на каждом из отрезков $$[x_i,x_{i+1}]$$ (рис.7.1 ). Легко понять, что она будет искомым изоморфизмом.

    (рис 7.1) Ломаная осуществляет изоморфизм

    103. Покажите, что множество рациональных чисел интервала $$(0,1)$$ и множество $$\mathbb{Q}$$ изоморфны. (Указание: здесь тоже можно построить ломаную; впрочем, у этой задачи есть и другое решение, которое начинается с того, что функция $$x\hm\mapsto 1/x$$ переводит рациональные числа в рациональные.)

    Более сложная конструкция требуется в следующей задаче (видимо, ничего проще, чем сослаться на общую теорему 13, тут не придумаешь).

    104. Докажите, что множество двоично - рациональных чисел интервала $$(0,1)$$ изоморфно множеству $$\bbQ$$. (Число считается двоично - рациональным, если оно имеет вид $$m/2^n$$, где $$m$$ - целое число, а $$n$$ - натуральное.)

    Два элемента $$x$$, $$y$$ линейно упорядоченного множества называют соседними, если $$x\hm<y$$ и не существует элемента между ними, то есть такого $$z$$, что $$x\hm<z\hm<y$$. Линейно упорядоченное множество называют плотным, если в нем нет соседних элементов (то есть между любыми двумя есть третий).

    Теорема 13. Любые два счетных плотных линейно упорядоченных множества без наибольшего и наименьшего элементов изоморфны.

    Доказательство. Пусть $$X$$ и $$Y$$ - данные нам множества. Требуемый изоморфизм между ними строится по шагам. После $$n$$ шагов у нас есть два $$n$$ - элементных подмножества $$X_n\hm\subset X$$ и $$Y_n\hm\subset Y$$, элементы которых мы будем называть " охваченными", и взаимно однозначное соответствие между ними, сохраняющее порядок. На очередном шаге мы берем какой - то неохваченный элемент одного из множеств (скажем, множества $$X$$ ) и сравниваем его со всеми охваченными элементами $$X$$. Он может оказаться либо меньше всех, либо больше, либо попасть между какими - то двумя. В каждом из случаев мы можем найти неохваченный элемент в $$Y$$, находящийся в том же положении (больше всех, между первым и вторым охваченным сверху, между вторым и третьим охваченным сверху и т.п.). При этом мы пользуемся тем, что в $$Y$$ нет наименьшего элемента, нет наибольшего и нет соседних элементов, - в зависимости от того, какой из трех случаев имеет место. После этого мы добавляем выбранные элементы к $$X_n$$ и $$Y_n$$, считая их соответствующими друг другу.

    Чтобы в пределе получить изоморфизм между множествами $$X$$ и $$Y$$, мы должны позаботиться о том, чтобы все элементы обоих множеств были рано или поздно охвачены. Это можно сделать так: поскольку каждое из множеств счетно, пронумеруем его элементы и будем выбирать неохваченный элемент с наименьшим номером (на нечетных шагах - из $$X$$, на четных - из $$Y$$ ). Это соображение завершает доказательство.

    105. Сколько существует неизоморфных счетных плотных линейно упорядоченных множеств (про наименьший и наибольший элементы ничего не известно). (Ответ: $$4$$.)

    106. Приведите пример двух плотных линейно упорядоченных множеств мощности континуум без наименьшего и наибольшего элементов, не являющихся изоморфными. (Указание: возьмите множества $$\mathbb{Q}\hm+\mathbb{R}$$ и $$\mathbb{R}\hm+\mathbb{Q}$$.)

    Теорема 14. Всякое счетное линейно упорядоченное множество изоморфно некоторому подмножеству множества $$\mathbb{Q}$$.

    Доказательство. Заметим сразу же, что вместо множества $$\mathbb{Q}$$ можно было взять любое плотное счетное всюду плотное множество без первого и последнего элементов, так как они все изоморфны.

    Доказательство этого утверждения происходит так же, как и в теореме 13 - с той разницей, что новые необработанные элементы берутся только с одной стороны (из данного нам множества), а пары к ним подбираются в множестве рациональных чисел.

    107. Дайте другое доказательство теоремы 14, заметив, что любое множество $$X$$ изоморфно подмножеству множества $$\bbQ\times X$$.

    Страницы:

    Отношения эквивалентности и порядка

    Напомним, что бинарным отношением на множестве $$X$$ называется подмножество $$R\hm\subset X\hm\times X$$ ; вместо $$\langle x_1,x_2\rangle \hm\in R$$ часто пишут $$x_1 R x_2$$.

    Бинарное отношение $$R$$ на множестве $$X$$ называется отношением эквивалентности, если выполнены следующие свойства:

  • (рефлексивность) $$xRx$$ для всех $$x\hm\in X$$ ;
  • (симметричность) $$xRy \hm\Rightarrow yRx$$ для всех $$x,y\hm\in X$$ ;
  • (транзитивность) $$xRy \text{ и } yRz \hm\Rightarrow xRz$$ для любых элементов $$x,y,z\hm \in X$$.
    •

    Имеет место следующее очевидное, но часто используемое утверждение:

    Теорема 11. (а) Если множество $$X$$ разбито в объединение непересекающихся подмножеств, то отношение " лежать в одном подмножестве" является отношением эквивалентности.

    (б) Всякое отношение эквивалентности получается описанным способом из некоторого разбиения.

    Доказательство. Первое утверждение совсем очевидно; мы приведем доказательство второго, чтобы было видно, где используются все пункты определения эквивалентности. Итак, пусть $$R$$ - отношение эквивалентности. Для каждого элемента $$x\hm\in X$$ рассмотрим его класс эквивалентности - множество всех $$y\in X$$, для которых верно $$xRy$$.

    Докажем, что для двух различных $$x_1$$, $$x_2$$ такие множества либо не пересекаются, либо совпадают. Пусть они пересекаются, то есть имеют общий элемент $$z$$. Тогда $$x_1 R z$$ и $$x_2 R z$$, откуда $$z R x_2$$ (симметричность) и $$x_1 R x_2$$ (транзитивность), а также $$x_2 R x_1$$ (симметричность). Поэтому для любого $$z$$ из $$x_1 R z$$ следует $$x_2 R z$$ (транзитивность) и наоборот.

    Осталось заметить, что в силу рефлексивности каждый элемент $$x$$ принадлежит задаваемому им классу, то есть действительно все множество $$X$$ разбито на непересекающиеся классы.

    78. Покажите, что требования симметричности и транзитивности можно заменить одним: $$\text{xRz и yRz} \Rightarrow xRy$$ (при сохранении требования рефлексивности).

    79. Сколько различных отношений эквивалентности существует на множестве $$\{1,2,3,4,5\}$$?

    80. На множестве $$M$$ задано два отношения эквивалентности, обозначаемые $$\sim_1$$ и $$\sim_2$$, имеющие $$n_1$$ и $$n_2$$ классов эквивалентности соответственно. Будет ли их пересечение $$x\sim y \hm\Leftrightarrow [(x\sim_1 y)\text{ и }(x\sim_2 y)]$$ отношением эквивалентности? Сколько у него может быть классов? Что можно сказать про объединение отношений?

    81. (Теорема Рамсея) Множество всех $$k$$ - элементных подмножеств бесконечного множества $$A$$ разбито на $$l$$ классов ( $$k$$, $$l$$ - натуральные числа). Докажите, что найдется бесконечное множество $$B\hm\subset A$$, все $$k$$ - элементные подмножества которого принадлежат одному классу.

    (При $$k\hm=1$$ это очевидно: если бесконечное множество разбито на конечное число классов, то один из классов бесконечен. При $$k=2$$ и $$l=2$$ утверждение можно сформулировать так: из бесконечного множества людей можно выбрать либо бесконечно много попарно знакомых, либо бесконечно много попарно незнакомых. Конечный вариант этого утверждения - о том, что среди любых шести людей есть либо три попарно знакомых, либо три попарно незнакомых, - известная задача для школьников.)

    Множество классов эквивалентности называют фактор - множеством множества $$X$$ по отношению эквивалентности $$R$$. (Если отношение согласовано с дополнительными структурами на $$X$$, получаются фактор - группы, фактор - кольца и т.д)

    Отношения эквивалентности нам не раз еще встретятся, но сейчас наша основная тема - отношения порядка.

    Бинарное отношение $$\le$$ на множестве $$X$$ называется отношением частичного порядка, если выполнены такие свойства:

  • (рефлексивность) $$x\le x$$ для всех $$x\hm\in X$$ ;
  • (антисимметричность) $$x\le y \text{ и } y\le x \hm\Rightarrow x\hm=y$$ для всех $$x,y\hm\in X$$ ;
  • (транзитивность) $$x\le y\text{ и }y\le z \hm\Rightarrow x\hm\le z$$ для всех $$x,y,z\hm \in X$$.
    •

    (Следуя традиции, мы используем символ $$\le$$ (а не букву) как знак отношения порядка.) Множество с заданным на нем отношением частичного порядка называют частично упорядоченным.

    Говорят, что два элемента $$x,y$$ частично упорядоченного множества сравнимы, если $$x\le y$$ или $$y\le x$$. Заметим, что определение частичного порядка не требует, чтобы любые два элемента множества были сравнимы. Добавив это требование, мы получим определение линейного порядка ( линейно упорядоченного множества ).

    Приведем несколько примеров частичных порядков:

  • Числовые множества с обычным отношением порядка (здесь порядок будет линейным).
  • На множестве $$\mathbb{R}\hm\times\mathbb{R}$$ всех пар действительных чисел можно ввести частичный порядок, считая, что $$\langle x_1,x_2\rangle \hm\le \langle y_1,y_2\rangle$$, если $$x_1\hm\le x_2$$ и $$y_1\hm\le y_2$$. Этот порядок уже не будет линейным: пары $$\langle 0,1\rangle$$ и $$\langle 1,0\rangle$$ не сравнимы.
  • На множестве функций с действительными аргументами и значениями можно ввести частичный порядок, считая, что $$f\hm\le g$$, если $$f(x)\hm\le g(x)$$ при всех $$x\in\bbR$$. Этот порядок не будет линейным.
  • На множестве целых положительных чисел можно определить порядок, считая, что $$x\hm\le y$$, если $$x$$ делит $$y$$. Этот порядок тоже не будет линейным.
  • Отношение " любой простой делитель числа $$x$$ является также и делителем числа $$y$$ " не будет отношением порядка на множестве целых положительных чисел (оно рефлексивно и транзитивно, но не антисимметрично).
  • Пусть $$U$$ - произвольное множество. Тогда на множестве $$P(U)$$ всех подмножеств множества $$U$$ отношение включения $$\subset$$ будет частичным порядком.
  • На буквах русского алфавита традиция определяет некоторый порядок ( $$\text{а}\hm\le\text{б}\hm\le\text{в}\hm\le\ldots\hm\le\text{я}$$ ). Этот порядок линеен - про любые две буквы можно сказать, какая из них раньше (при необходимости заглянув в словарь).
  • На словах русского алфавита определен лексикографический порядок (как в словаре). Формально определить его можно так: если слово $$x$$ является началом слова $$y$$, то $$x\hm\le y$$ (например, $$\text{кант}\hm\le\text{кантор}$$ ). Если ни одно из слов не является началом другого, посмотрим на первую по порядку букву, в которой слова отличаются: то слово, где эта буква меньше в алфавитном порядке, и будет меньше. Этот порядок также линеен (иначе что бы делали составители словарей?).
  • Отношение равенства ( $$(x\hm\le y)\hm\Leftrightarrow (x\hm=y)$$ ) также является отношением частичного порядка, для которого никакие два различных элемента не сравнимы.
  • Приведем теперь бытовой пример. Пусть есть множество $$X$$ картонных коробок. Введем на нем порядок, считая, что $$x\hm\le y$$, если коробка $$x$$ целиком помещается внутрь коробки $$y$$ (или если $$x$$ и $$y$$ - одна и та же коробка). В зависимости от набора коробок этот порядок может быть или не быть линейным.
    •

    Пусть $$x,y$$ - элементы частично упорядоченного множества $$X$$. Говорят, что $$x<y$$, если $$x\le y$$ и $$x\ne y$$. Для этого отношения выполнены такие свойства: $$\begin{gather*} x \not< x;\\ (x< y) \text{ и } (y < z)\ \Rightarrow\ x < z. \end{gather*}$$ (Первое очевидно, проверим второе: если $$x\hm<y$$ и $$y\hm<z$$, то есть $$x\hm\le y$$, $$x\hm\ne y$$, $$y\hm\le z$$, $$y\hm\ne z$$, то $$x\hm\le z$$ по транзитивности; если бы оказалось, что $$x\hm=z$$, то мы бы имели $$x\hm\le y\hm\le x$$ и потому $$x\hm=y$$ по антисимметричности, что противоречит предположению.)

    Терминологическое замечание: мы читаем знак $$\le$$ как " меньше или равно", а знак $$<$$ - как " меньше", неявно предполагая, что $$x\hm\le y$$ тогда и только тогда, когда $$x\hm<y$$ или $$x\hm=y$$. К счастью, это действительно так. Еще одно замечание: выражение $$x\hm>y$$ (" $$x$$ больше $$y$$ ") означает, что $$y\hm<x$$, а выражение $$x\ge y$$ (" $$x$$ больше или равно $$y$$ ") означает, что $$y\hm\le x$$.

    82. Объясните, почему не стоит читать $$x\hm\le y$$ как " $$x$$ не больше $$y$$ ".

    В некоторых книжках отношение частичного порядка определяется как отношение $$<$$, удовлетворяющее двум указанным свойствам. В этом случае отношение $$x\hm\le y \hm\Leftrightarrow [(x\hm<y) \text{ или } (x\hm=y)]$$ является отношением частичного порядка в смысле нашего определения.

    83.Проверьте это.

    Во избежание путаницы отношение $$<$$ иногда называют отношением строгого порядка, а отношение $$\le$$ - отношением нестрогого порядка. Одно и то же частично упорядоченное множество можно задавать по - разному: можно сначала определить отношение нестрогого порядка $$\le$$ (рефлексивное, антисимметричное и транзитивное) и затем из него получить отношение строгого порядка $$<$$, а можно действовать и наоборот.

    84. Опуская требование антисимметричности в определении частичного порядка, получаем определение предпорядка. Докажите, что любой предпорядок устроен так: множество делится на непересекающиеся классы, при этом $$x\hm\le y$$ для любых двух элементов $$x$$, $$y$$ из одного класса, а на фактор - множестве задан частичный порядок, который и определяет результат сравнения двух элементов из разных классов.

    Вот несколько конструкций, позволяющих строить одни упорядоченные множества из других.

  • Пусть $$Y$$ - подмножество частично упорядоченного множества $$(X,\le)$$. Тогда на множестве $$Y$$ возникает естественный частичный порядок, индуцированный из $$X$$. Формально говоря,$$(\le _Y) = (\le) \cap (Y\times Y).$$ Если порядок на $$X$$ был линейным, то и индуцированный порядок на $$Y$$, очевидно, будет линейным.
  • Пусть $$X$$ и $$Y$$ - два непересекающихся частично упорядоченных множества. Тогда на их объединении можно определить частичный порядок так: внутри каждого множества элементы сравниваются как раньше, а любой элемент множества $$X$$ по определению меньше любого элемента $$Y$$. Это множество естественно обозначить $$X+Y$$. (Порядок будет линейным, если он был таковым на каждом из множеств.)

    Это же обозначение применяют и для пересекающихся (и даже совпадающих множеств). Например, говоря об упорядоченном множестве $$\mathbb{N}+\mathbb{N}$$, мы берем две непересекающиеся копии натурального ряда $$\{0,1,2,\dots\}$$ и $$\{\overline 0,\overline 1,\overline 2,\dots\}$$ и рассматриваем множество $$\{0,1,2,\dots,\overline 0, \overline1, \overline2,\dots\}$$, причем $$k\le \overline l$$ при всех $$k$$ и $$l$$, а внутри каждой копии порядок обычный.

  • Пусть $$(X, \le_{X})$$ и $$(Y,\le_Y)$$ - два упорядоченных множества. Можно определить порядок на произведении $$X\hm\times Y$$ несколькими способами. Можно считать, что $$\langle x_1,y_1\rangle \hm\le \langle x_2,y_2\rangle$$, если $$x_1 \le_X x_2$$ и $$y_1\le_Y y_2$$ (покоординатное сравнение). Этот порядок, однако, не будет линейным, даже если исходные порядки и были линейными: если первая координата больше у одной пары, а вторая у другой, как их сравнить? Чтобы получить линейный порядок, договоримся, какая координата будет " главной" и будем сначала сравнивать по ней, а потом (в случае равенства) - по другой. Если главной считать $$X$$ - координату, то $$\langle x_1,y_1\rangle \hm\le\langle x_2,y_2\rangle$$, если $$x_1 <_X x_2$$ или если $$x_1=x_2$$, а $$y_1 \le_Y y_2$$. Однако по техническим причинам удобно считать главной вторую координату. Говоря о произведении двух линейно упорядоченных множеств как о линейно упорядоченном множестве, мы в дальнейшем подразумеваем именно такой порядок (сначала сравниваем по второй координате).
    •

    85. Докажите, что в частично упорядоченном множестве $$\mathbb{N}\hm\times\mathbb{N}$$ (порядок покоординатный) нет бесконечного подмножества, любые два элемента которого были бы несравнимы. Верно ли аналогичное утверждение для $$\mathbb{Z}\hm\times\mathbb{Z}$$?

    86. Докажите аналогичное утверждение для $$\mathbb{N}^k$$ (порядок покоординатный).

    87. Пусть $$U$$ - конечное множество из $$n$$ элементов. Рассмотрим множество $$P(U)$$ всех подмножеств множества $$U$$, упорядоченное по включению. Какова максимально возможная мощность множества $$S\subset P(U)$$, если индуцированный на $$S$$ порядок линеен? если никакие два элемента $$S$$ не сравнимы? (Указание: см. задачу 14.)

    88. Сколько существует различных линейных порядков на множестве из $$n$$ элементов?

    89. Докажите, что всякий частичный порядок на конечном множестве можно продолжить до линейного (" продолжить" означает, что если $$x\hm\le y$$ в исходном порядке, то и в новом это останется так).

    90. Дано бесконечное частично упорядоченное множество $$X$$. Докажите, что в нем всегда найдется либо бесконечное подмножество попарно несравнимых элементов, либо бесконечное подмножество, на котором индуцированный порядок линеен.

    91. (Конечный вариант предыдущей задачи.) Даны целые положительные числа $$m$$ и $$n$$. Докажите, что во всяком частично упорядоченном множестве мощности $$mn+1$$ можно указать либо $$m+1$$ попарно несравнимых элементов, либо $$n+1$$ попарно сравнимых.

    92. В строчку написаны $$mn+1$$ различных чисел. Докажите, что можно часть из них вычеркнуть так, чтобы осталась либо возрастающая последовательность длины $$m+1$$, либо убывающая последовательность длины $$n+1$$. (Указание: можно воспользоваться предыдущей задачей.)

    93. Рассмотрим семейство всех подмножеств натурального ряда, упорядоченное по включению. Существует ли у него линейно упорядоченное (в индуцированном порядке) подсемейство мощности континуум? Существует ли у него подсемейство мощности континуум, любые два элемента которого несравнимы?

    Элемент частично упорядоченного множества называют наибольшим, если он больше любого другого элемента, и максимальным, если не существует большего элемента. Если множество не является линейно упорядоченным, то это не одно и то же: наибольший элемент автоматически является максимальным, но не наоборот. (Одно дело коробка, в которую помещается любая другая, другое - коробка, которая никуда больше не помещается.)

    Аналогичным образом определяются наименьшие и минимальные элементы.

    Легко понять, что наибольший элемент в данном частично упорядоченном множестве может быть только один, в то время как максимальных элементов может быть много.

    94. Докажите, что любые два максимальных элемента не сравнимы. Докажите, что в конечном частично упорядоченном множестве $$X$$ для любого элемента $$x$$ найдется максимальный элемент $$y$$, больший или равный $$x$$.

    Изоморфизмы

    Два частично упорядоченных множества называются изоморфными, если между ними существует изоморфизм, то есть взаимно однозначное соответствие, сохраняющее порядок. (Естественно, что в этом случае они равномощны как множества.) Можно сказать так: биекция $$f\colon A\hm\to B$$ называется изоморфизмом частично упорядоченных множеств $$A$$ и $$B$$, если$$a_1 \le a_2 \ \Leftrightarrow \ f(a_1) \le f(a_2)$$ для любых элементов $$a_1,a_2\hm\in A$$ (слева знак $$\le$$ обозначает порядок в множестве $$A$$, справа - в множестве $$B$$ ).

    Очевидно, что отношение изоморфности рефлексивно (каждое множество изоморфно самому себе), симметрично (если $$X$$ изоморфно $$Y$$, то и наоборот) и транзитивно (два множества, изоморфные третьему, изоморфны между собой). Таким образом, все частично упорядоченные множества разбиваются на классы изоморфных, которые называют порядковыми типами. (Правда, как и с мощностями, тут необходима осторожность - изоморфных множеств слишком много, и потому говорить о порядковых типах как множествах нельзя.)

    Теорема 12. Конечные линейно упорядоченные множества из одинакового числа элементов изоморфны.

    Доказательство. Конечное линейно упорядоченное множество всегда имеет наименьший элемент (возьмем любой элемент; если он не наименьший, возьмем меньший, если и он не наименьший, еще меньший - и так далее; получим убывающую последовательность $$x\hm>y\hm>z\hm>\ldots$$, которая рано или поздно должна оборваться). Присвоим наименьшему элементу номер $$1$$. Из оставшихся снова выберем наименьший элемент и присвоим ему номер $$2$$ и так далее. Легко понять, что порядок между элементами соответствует порядку между номерами, то есть что наше множество изоморфно множеству $$\{1,2,\dots,n\}$$.

    95. Докажите, что множество всех целых положительных делителей числа $$30$$ с отношением " быть делителем" в качестве отношения порядка изоморфно множеству всех подмножеств множества $$\{a,b,c\}$$, упорядоченному по включению.

    96. Будем рассматривать финитные последовательности натуральных чисел, то есть последовательности, у которых все члены, кроме конечного числа, равны $$0$$. На множестве таких последовательностей введем покомпонентный порядок: $$(a_0,a_1,\dots) \hm\le (b_0,b_1,\dots)$$, если $$a_i\hm\le b_i$$ при всех $$i$$. Докажите, что это множество изоморфно множеству всех положительных целых чисел с отношением " быть делителем" в качестве порядка.

    Взаимно однозначное отображение частично упорядоченного множества $$A$$ в себя, являющееся изоморфизмом, называют автоморфизмом частично упорядоченного множества $$A$$. Тождественное отображение всегда является автоморфизмом, но для некоторых множеств существуют и другие автоморфизмы. Например, отображение прибавления единицы ( $$x\mapsto x+1$$ ) является автоморфизмом частично упорядоченного множества $$\bbZ$$ целых чисел (с естественным порядком). Для множества натуральных чисел та же формула не дает автоморфизма (нет взаимной однозначности).

    97. Покажите, что не существует автоморфизма упорядоченного множества $$\bbN$$ натуральных чисел, отличного от тождественного.

    98. Рассмотрим множество $$P(A)$$ всех подмножеств некоторого $$k$$ - элементного множества $$A$$, частично упорядоченное по включению. Найдите число автоморфизмов этого множества.

    99. Покажите, что множество целых положительных чисел, частично упорядоченное отношением " $$x$$ делит $$y$$ ", имеет континуум различных автоморфизмов.

    Вот несколько примеров равномощных, но не изоморфных линейно упорядоченных множеств (в силу теоремы 12 они должны быть бесконечными).

  • Отрезок $$[0,1]$$ (с обычным отношением порядка) не изоморфен множеству $$\bbR$$, так как у первого есть наибольший элемент, а у второго нет. (При изоморфизме наибольший элемент, естественно, должен соответствовать наибольшему.)
  • Множество $$\bbZ$$ (целые числа с обычным порядком) не изоморфно множеству $$\bbQ$$ (рациональные числа). В самом деле, пусть $$\alpha\colon\bbZ\hm\to\bbQ$$ является изоморфизмом. Возьмем два соседних целых числа, скажем, $$2$$ и $$3$$. При изоморфизме $$\alpha$$ им должны соответствовать какие - то два рациональных числа $$\alpha(2)$$ и $$\alpha(3)$$, причем $$\alpha(2)\hm<\alpha(3)$$, так как $$2\hm<3$$. Но тогда рациональным числам между $$\alpha(2)$$ и $$\alpha(3)$$ должны соответствовать целые числа между $$2$$ и $$3$$, которых нет.
  • Более сложный пример - множества $$\bbZ$$ и $$\bbZ\hm+\bbZ$$. Возьмем в $$\bbZ\hm+\bbZ$$ две копии нуля (из той и другой компоненты); мы обозначали их $$0$$ и $$\overline 0$$. При этом $$0\hm<\overline 0$$. При изоморфизме им должны соответствовать два целых числа $$a$$ и $$b$$, для которых $$a\hm<b$$. Тогда всем элементам между $$0$$ и $$\overline 0$$ (их бесконечно много: $$1$$, $$2$$, $$3$$, $$\dots$$, $$-\overline3$$, $$-\overline2$$, $$-\overline1$$ ) должны соответствовать числа между $$a$$ и $$b$$ - но их лишь конечное число.

    Этот пример принципиально отличается от предыдущих тем, что здесь разницу между свойствами множеств нельзя записать формулой. Как говорят, упорядоченные множества $$\bbZ$$ и $$\bbZ\hm+\bbZ$$ " элементарно эквивалентны".

    •

    100. Докажите, что линейно упорядоченные множества $$\bbZ\hm\times\bbN$$ и $$\bbZ\hm\times\bbZ$$ (с описанным выше порядком) не изоморфны.

    101. Будут ли изоморфны линейно упорядоченные множества $$\bbN\hm\times\bbZ$$ и $$\bbZ\hm\times\bbZ$$?

    102.Будут ли изоморфны линейно упорядоченные множества $$\bbQ\hm\times\bbZ$$ и $$\bbQ\hm\times\bbN$$?

    Отображение $$x\hm\mapsto \sqrt{2}x$$ осуществляет изоморфизм между интервалами $$(0,1)$$ и $$(0,\sqrt{2})$$. Но уже не так просто построить изоморфизм между множествами рациональных точек этих интервалов (то есть между $$\bbQ\hm\cap(0,1)$$ и $$\bbQ\hm\cap(0,\sqrt{2})$$ ), поскольку умножение на $$\sqrt{2}$$ переводит рациональные числа в иррациональные. Тем не менее изоморфизм построить можно. Для этого надо взять возрастающие последовательности рациональных чисел $$0\hm<x_1\hm<x_2\hm<\dots$$ и $$0\hm< y_1\hm<y_2\hm<\dots$$, сходящиеся соответственно к $$1$$ и $$\sqrt{2}$$ и построить кусочно - линейную функцию $$f$$, которая переводит $$x_i$$ в $$y_i$$ и линейна на каждом из отрезков $$[x_i,x_{i+1}]$$ (рис.7.1 ). Легко понять, что она будет искомым изоморфизмом.

    (рис 7.1) Ломаная осуществляет изоморфизм

    103. Покажите, что множество рациональных чисел интервала $$(0,1)$$ и множество $$\mathbb{Q}$$ изоморфны. (Указание: здесь тоже можно построить ломаную; впрочем, у этой задачи есть и другое решение, которое начинается с того, что функция $$x\hm\mapsto 1/x$$ переводит рациональные числа в рациональные.)

    Более сложная конструкция требуется в следующей задаче (видимо, ничего проще, чем сослаться на общую теорему 13, тут не придумаешь).

    104. Докажите, что множество двоично - рациональных чисел интервала $$(0,1)$$ изоморфно множеству $$\bbQ$$. (Число считается двоично - рациональным, если оно имеет вид $$m/2^n$$, где $$m$$ - целое число, а $$n$$ - натуральное.)

    Два элемента $$x$$, $$y$$ линейно упорядоченного множества называют соседними, если $$x\hm<y$$ и не существует элемента между ними, то есть такого $$z$$, что $$x\hm<z\hm<y$$. Линейно упорядоченное множество называют плотным, если в нем нет соседних элементов (то есть между любыми двумя есть третий).

    Теорема 13. Любые два счетных плотных линейно упорядоченных множества без наибольшего и наименьшего элементов изоморфны.

    Доказательство. Пусть $$X$$ и $$Y$$ - данные нам множества. Требуемый изоморфизм между ними строится по шагам. После $$n$$ шагов у нас есть два $$n$$ - элементных подмножества $$X_n\hm\subset X$$ и $$Y_n\hm\subset Y$$, элементы которых мы будем называть " охваченными", и взаимно однозначное соответствие между ними, сохраняющее порядок. На очередном шаге мы берем какой - то неохваченный элемент одного из множеств (скажем, множества $$X$$ ) и сравниваем его со всеми охваченными элементами $$X$$. Он может оказаться либо меньше всех, либо больше, либо попасть между какими - то двумя. В каждом из случаев мы можем найти неохваченный элемент в $$Y$$, находящийся в том же положении (больше всех, между первым и вторым охваченным сверху, между вторым и третьим охваченным сверху и т.п.). При этом мы пользуемся тем, что в $$Y$$ нет наименьшего элемента, нет наибольшего и нет соседних элементов, - в зависимости от того, какой из трех случаев имеет место. После этого мы добавляем выбранные элементы к $$X_n$$ и $$Y_n$$, считая их соответствующими друг другу.

    Чтобы в пределе получить изоморфизм между множествами $$X$$ и $$Y$$, мы должны позаботиться о том, чтобы все элементы обоих множеств были рано или поздно охвачены. Это можно сделать так: поскольку каждое из множеств счетно, пронумеруем его элементы и будем выбирать неохваченный элемент с наименьшим номером (на нечетных шагах - из $$X$$, на четных - из $$Y$$ ). Это соображение завершает доказательство.

    105. Сколько существует неизоморфных счетных плотных линейно упорядоченных множеств (про наименьший и наибольший элементы ничего не известно). (Ответ: $$4$$.)

    106. Приведите пример двух плотных линейно упорядоченных множеств мощности континуум без наименьшего и наибольшего элементов, не являющихся изоморфными. (Указание: возьмите множества $$\mathbb{Q}\hm+\mathbb{R}$$ и $$\mathbb{R}\hm+\mathbb{Q}$$.)

    Теорема 14. Всякое счетное линейно упорядоченное множество изоморфно некоторому подмножеству множества $$\mathbb{Q}$$.

    Доказательство. Заметим сразу же, что вместо множества $$\mathbb{Q}$$ можно было взять любое плотное счетное всюду плотное множество без первого и последнего элементов, так как они все изоморфны.

    Доказательство этого утверждения происходит так же, как и в теореме 13 - с той разницей, что новые необработанные элементы берутся только с одной стороны (из данного нам множества), а пары к ним подбираются в множестве рациональных чисел.

    107. Дайте другое доказательство теоремы 14, заметив, что любое множество $$X$$ изоморфно подмножеству множества $$\bbQ\times X$$.

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^