Почему множество разбиений -- решётка?

[Dims]

Рассмотрим частично-упорядоченное множество разбиений множества {1,2,3,4}:



Не могу понять, каким образом оно выполняет требование аксиомы о решётке (о существовании точной нижней грани у любой пары)? Допустим, возьмём элементы 1234 и 12/2/4. Разве у них есть точная нижняя грань? Ведь элемента, одновременно меньшего и равного обоих этих элементов не существует.

Я неправильно понимаю, что такое точная нижняя грань?

Добавлено спустя 23 минуты 17 секунд:

Кажется, понял: просто множество на этой картинке не является решёткой. Правильно?

[bot]

Dims писал(а):

Не могу понять, каким образом оно выполняет требование аксиомы о решётке (о существовании точной нижней грани у любой пары)?
Допустим, возьмём элементы 1234 и 12/2/4. Разве у них есть точная нижняя грань??

12/2/4 - не разбиение. Если имеется в виду 12/3/4, то оно содержится в 1234 и, стало быть, и будет точной нижней гранью. Собственно не важно, что имелось в виду - любое разбиение содержится в 1234.

Цитата:

Кажется, понял: просто множество на этой картинке не является решёткой.

Является. На диаграмме как раз и показаны все возможные разбиения и все имеющиеся включения. По восходящим ребрам легко находим верхние грани, а по нисходящим - нижние.

[Dims]

bot писал(а):

По восходящим ребрам легко находим верхние грани, а по нисходящим - нижние.

Я не могу найти по нисходящим рёбрам нижнюю грань для пары 1234 и 12/3/4. Подскажите, как она обозначена на рисунке?

[PAV]

Это сам элемент 12/3/4, так как он меньше или равен обоих.

[Dims]

PAV писал(а):

Это сам элемент 12/3/4, так как он меньше или равен обоих.

Если бы он был меньше элемента 1234, он бы был связан с ним нисходящим ребром, а он не связан: отношение порядка для этих двух элементов неопределено.

То есть, (12/3/4 < 1234) = false.

Добавлено спустя 4 минуты 48 секунд:

А, то есть рёбрами на графе обозначены не все случаи отношения порядка, а только необходимые, а остальные получаются за счёт транзитивности?

Добавлено спустя 3 минуты 1 секунду:

Иными словами, если в орграфе есть циклы, то отображаемое им множество не является частично-упорядоченным?

Пардон за тупые вопросы, книжку читаю и не всё не понимаю

[PAV]

Dims писал(а):

Иными словами, если в орграфе есть циклы, то отображаемое им множество не является частично-упорядоченным?

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

[bot]

Где тут увидали циклы? Стрелочек на диаграмме, конечно, нет, но по умолчанию они есть и все направлены вниз (или наоборот вверх - это уже вопрос договорённости)

Dims писал(а):

А, то есть рёбрами на графе обозначены не все случаи отношения порядка, а только необходимые, а остальные получаются за счёт транзитивности?

Да, указаны только покрытия $a\prec b$, то есть $a<b$ и не существует $c$, лежащего строго между $a$ и $b$.

Разбиениям каноническим образом соответствуют отношения эквивалентности.
Нижняя грань $\theta \wedge \eta$ отношений эквивалентности $\theta$ и $\eta$ - это обычное их пересечение $\theta \cap \eta$, а верхняя грань $\theta \vee \eta$ - это транзитивное замыкание их объединения:
$\bigcup_{n=1}^\infty \psi_1\circ \psi_2 \circ ... \circ \psi_n$,
где $\psi_i = \theta$ для нечётного $i$ и $\psi_i = \eta$ для чётного (можно наоборот - это несущественно), а $\circ$ - композиция отношений.