Отношение полного частичного порядка на множестве

[mymind]

Пожалуйста, помогите разобраться в теме отношений порядка на множестве. Не могу понять, что такое полное частично упорядоченное множество. Мне кажется, что тема отношений порядка -- это очень важная часть во многих математических разделах. Хочу резюмировать, как я это понимаю. Но это всего лишь теория. Как это все устроено на практике, понять затрудняюсь.

Пусть $M$ -- некоторое множество. На этом множестве мы можем рассматривать бинарные отношения. Произвольное бинарное отношение на $M$ -- это подмножество множества $M \times M$.  

Бинарное отношение $\mathcal{R}$ на $M$ называют отношением порядка, если выполнены следующие условия:
(i) рефлексивность: $\forall a \in M (a, a) \in \mathcal{R}$;
(ii) транзитивность: для $a, b, c \in M $ если $(a, b) \in \mathcal{R}$ и $(b, c) \in \mathcal{R}$, то $(a, c) \in \mathcal{R}$;
(iii) кососимметричность (или антисимметричность): для $a, b \in M $ если $(a, b) \in \mathcal{R}$ и $(b, a) \in \mathcal{R}$, то $a = b$.

Вообще говоря, некоторые два элемента $a, b \in M $ могут и не удовлетворять вышеуказанным условиям. И в общем случае, отношение порядка называется частичным порядком. Множество с заданным частичным порядком называют частично упорядоченным множеством. Однако, если каждая пара $a, b \in M$ удовлетворяет отношению $\mathcal{R}$, то говорят, что на множестве $M$ задан линейный порядок. И такое множество называют линейно упорядоченным. Линейно упорядоченные множества также называются монотонно упорядоченными, или просто упорядоченными.

Другими словами. Пусть $(M, \preccurlyeq)$ -- частично упорядоченное множество $M$ с отношением  $\preccurlyeq$. Если для каких-то $a, b \in M$ имеет место $a \preccurlyeq  b$ либо $b \preccurlyeq  a$, говорят, что $a$ и $b$ сравнимы (в противном случае $a, b$ несравнимы). Если все элементы множества $M$ сравнимы, то на $M$ задан линейный порядок. Например, отношение "a делит b" на множестве натуральных чисел является отношением частичного порядка, но не линейного, так как, например, числа 2, 3 несравнимы. На множестве целых это же самое отношение не будет вообще отношением порядка, так как не выполняется кососимметричность. Понятно, что в любом частично упорядоченном множестве с отношением $\preccurlyeq$ можно выделить (достаточно выбрать сравнимые элементы) линейно упорядоченное подмножество с тем же отношением. Такое подмножество называют цепью в частично упорядоченном множестве. Например, цепь на множестве натуральных чисел с отношением частичного порядка "a делит b" -- это множество $\{2^{n}\colon n \geqslant 0, n \in \mathbb{N}\}$.

Пусть $(M, \preccurlyeq)$ -- частично упорядоченное множество с отношением $\preccurlyeq$ и $P \subset M$ -- его подмножество. Элемент $m_{0} \in M$ называют верхней границей (или верхней гранью) подмножества $P$, если $\forall m \in P ~m \preccurlyeq m_{0}$.

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

Здесь я теряюсь что-то сказать. Ну, например, думаю, что множество целых отрицательных с отношением "a делит b" является полным частично упорядоченным множеством. Частично упорядоченное множество натуральных чисел с отношением "a делит b" является полным. Верно?

[mihaild]

mymind в сообщении #1555158 писал(а):

Например, отношение "a делит b" на множестве натуральных чисел

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

mymind в сообщении #1555158 писал(а):

Например, цепь на множестве натуральных чисел с отношением частичного порядка "a делит b" -- это множество $\{2^{n}\colon n \geqslant 0, n \in \mathbb{N}\}$.

Одна из цепей (вы это скорее всего понимаете, но лучше говорить аккуратнее).

mymind в сообщении #1555158 писал(а):

Ну, например, думаю, что множество целых отрицательных с отношением "a делит b"

Тут ИМХО стоит доказать, что отрицательные числа с этим отношением порядка изоморфны положительным, и после этого про делимость отрицательных не думать.

mymind в сообщении #1555158 писал(а):

Частично упорядоченное множество натуральных чисел с отношением "a делит b" является полным.

И какая же будет верхняя грань у множеств:
1) $\varnothing$
2) $\{1,2,3,4,5,6,7,8,9,10\}$
3) $\{1, 2, 4, 8, 16, \ldots\}$
4) $\mathbb N$
?

[mymind]

mihaild в сообщении #1555169 писал(а):

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

Не совсем понимаю. Берем пару $(a, b) \in M \times M$ и однозначно задаем отношение "$a \mid b$". Не понимаю, как по другому, что уточнять?

-- 22.05.2022, 16:24 --

mihaild в сообщении #1555169 писал(а):

И какая же будет верхняя грань у множеств:
1) $\varnothing$
2) $\{1,2,3,4,5,6,7,8,9,10\}$
3) $\{1, 2, 4, 8, 16, \ldots\}$
4) $\mathbb N$
?

Что-то не понятно, почему такие выбраны подмножества. Цепями, если я правильно понимаю, являются только 3) и 4). Там мы требуем существование верхней грани. Если мы рассматриваем отношение порядка "а делит b", то верхней гранью будет единица -- элемент, который делит все элементы.

[mihaild]

mymind в сообщении #1555174 писал(а):

Берем пару $(a, b) \in M \times M$ и однозначно задаем отношение "$a | b$". Не понимаю, как по другому, что уточнять?

Так понятно, да. Просто по фразе "$a$ делит $b$" не совсем очевидно, означает ли она принадлежность отношению пары $(a, b)$ или $(b, a)$.

mymind в сообщении #1555158 писал(а):

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

mymind в сообщении #1555174 писал(а):

Цепями, если я правильно понимаю, являются только 3) и 4).

1) тоже.

mymind в сообщении #1555174 писал(а):

то верхней гранью будет единица -- элемент, который делит все элементы

Так у вас же $(1, 2) \in \mathcal R$, так что единица меньше двойки.

[mymind]

mihaild в сообщении #1555178 писал(а):

Так у вас же $(1, 2) \in \mathcal R$, так что единица меньше двойки.

Так я же рассматриваю отношение делимости, а не "меньше или равно". Причем тут отношение "a меньше b", зачем написано слово "меньше"?

mymind в сообщении #1555158 писал(а):

Пусть $(M, \preccurlyeq)$ -- частично упорядоченное множество с отношением $\preccurlyeq$ и $P \subset M$ -- его подмножество. Элемент $m_{0} \in M$ называют верхней границей (или верхней гранью) подмножества $P$, если $\forall m \in P ~m \preccurlyeq m_{0}$.

Символ $\preccurlyeq$ -- это просто символ -- произвольное отношение. Абстрактно, как я это понимаю, должен найтись на заданном множестве такой элемент, который будет сравним по фиксированному отношению с любыми элементами подмножества заданного множества. Таким элементом и будет единица на множестве натуральных по отношению частичного порядка "a делит b".

[mihaild]

mymind в сообщении #1555190 писал(а):

Так я же рассматриваю отношение делимости, а не "меньше или равно".

Потому что вы рассматриваете его как отношение порядка. При этом почти всегда используют именно язык "меньше/больше".

mymind в сообщении #1555190 писал(а):

который будет сравним

Нет, не просто сравним, а именно справа будет.
Ну т.е. в терминах отношений как множеств, если $\mathcal R$ - наше отношение порядка, то $m_0$ - верхняя грань множества $M$ если $\foramm m \in P: (m, m_0) \in \mathcal R$. А у вас, как я понял, $\mathcal R = \{\langle a, b\rangle | \exists k: b = k\cdot a\}$. И тогда $1$ не может быть верхней гранью множества, содержащего $2$, т.к. $\langle 2, 1\rangle$ множеству не принадлежит.

mymind в сообщении #1555158 писал(а):

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

А откуда такое определение? Это свойство используется в лемме Цорна, но никогда не слышал, чтобы его называли "полным порядком" (а слышал что полным порядком называют вполне упорядоченный линейный, просто вполне упорядоченный и просто линейный).

[mymind]

mihaild в сообщении #1555196 писал(а):

Нет, не просто сравним, а именно справа будет.

Нигде такого не требуется. Нужно, чтобы соблюдалось либо "a делит b", либо "b делит a".

-- 22.05.2022, 21:50 --

mihaild в сообщении #1555196 писал(а):

А откуда такое определение?

Из книжки -- http://gorod.bogomolov-lab.ru/ps/stud/a ... _total.pdf (стр. 19, Определение I.3).

-- 22.05.2022, 21:56 --

mihaild в сообщении #1555196 писал(а):

Это свойство используется в лемме Цорна, но никогда не слышал, чтобы его называли "полным порядком" (а слышал что полным порядком называют вполне упорядоченный линейный, просто вполне упорядоченный и просто линейный).

Отношение порядка на вполне упорядоченном множестве называется полным порядком. А я рассматриваю частично упорядоченное множество, а не вполне упорядоченное.

[mihaild]

mymind в сообщении #1555204 писал(а):

Нужно, чтобы соблюдалось либо "a делит b", либо "b делит a".

Посмотрите еще раз на определение верхней грани. Там требуется не сравнимость, а неравенство в конкретную сторону.
Отношение "$a$ делит $b$ или $b$ делит $a$" отношением порядка не является (нет антисимметричности).

mymind в сообщении #1555204 писал(а):

стр. 19, Определение I.3

Ну вот там говорится о вполне упорядоченности для линейно упорядоченных множеств (впрочем из вполне упорядоченности линейная упорядоченность следует).
Ни слова про цепи я там не вижу.

mymind в сообщении #1555204 писал(а):

А я рассматриваю частично упорядоченное множество, а не вполне упорядоченное

Вот мне интересно, откуда ваше определение

mymind в сообщении #1555158 писал(а):

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