неизоморфные отношения частичного порядка

[jkjkuUidffhj]

Здравствуйте. Нужна помощь: Найти все неизоморфные отношения частичного порядка, существующие на четырехэлементном множестве.
----
Пусть $A=\{a,b,c,d\}$. В этом примере можно считать в качестве отношения отношение меньше или равно $\leqslant$ ($b$ следует за $a$ или $b$ равно $a$).
Мной было составлено прямое произведение $\{(a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,a), (c,b), (c,c), (c,d), (d,a), (d,b), (d,c), (d,d)\}$.
Как быть дальше не понятно. Что конкретно выписывать не понятно. Изоморфизм по сути это биекция. Как быть дальше? Всем заранее спасибо.

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

jkjkuUidffhj
Наберите все формулы и термы $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Вернул.
Посмотрите, как набирать фигурные скобки.

[provincialka]

Про диаграмму Хассе слышали? Может, она вам поможет.

[jkjkuUidffhj]

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

[provincialka]

Да какая разница, какие элементы. Важно, как они связаны. Например, линейно: $a-b-c-d$. Или "вилкой", $a-b-c$, плюс $b-d$. Можно "боковую ветку" выпустить из элемента $a$. Это я пытаюсь описать диаграммы Хассе искомых порядков.

Так вы знаете диаграмму Хассе?

[jkjkuUidffhj]

Диаграммы эти мне известны. Надо полагать, Вы намекаете на то, что ответом могут быть все виды диаграмм Хассе, отличающиеся структурой? И сколько их? Есть ли формула для подсчёта количества пар диаграмм Хассе, отличающиеся структурой? Если их $2^4$ (другой формулы просто не знаю), т.е. 16, значит, нужно 16 диаграмм нарисовать?

[provincialka]

Да, намекаю на это, но количество не знаю, не думала пока.

-- 02.11.2013, 10:04 --

Для двух элементов получается 2 диаграммы (есть связь / нет связи), для трех - 4 (все элементы отдельно, пара плюс один, вилка и цепочка). Не думаю, что есть простая формула, легче просто все нарисовать.

[jkjkuUidffhj]

Спасибо. 16 диаграмм получилось - а формула даёт 16 - просто вывода (доказательства) формулы у меня нет

[provincialka]

Какая формула? $2^n$, где n - число элементов? Для 2 и 3 элементов она неверна.

-- 02.11.2013, 10:27 --

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

[jkjkuUidffhj]

Для трех элементов: разве можно цепочку образовать? у нас отношение с частичным порядком, вроде в этом случае вершины,лежащие на одном уровне, не соединяются, т.е. не находятся в отношении с заданным порядком. Можно посмотреть несколько примеров диаграмм Хассе и ни в одном случае вершины одного уровня соединены не будут. Если есть пример - буду не против посмотреть

[provincialka]

Вопрос о терминологии: является ли полный порядок частичным? Если нет - вычитайте единицу (линейный порядок).

-- 02.11.2013, 13:56 --

Вершины одного уровня соединять, конечно, нельзя.

Для четырех вершин нашла только 15 порядков, включая линейный. На самом деле две диаграммы Хассе могут задавать один порядок, если элемент можно передвигать на другой уровень.

[arseniiv]

jkjkuUidffhj в сообщении #783488 писал(а):

Если их $2^4$ (другой формулы просто не знаю)

А не надо формулы перебирать. Их выводить надо. А в данном случае всё можно и так перечислить.

provincialka в сообщении #783609 писал(а):

Вопрос о терминологии: является ли полный порядок частичным?

Думаю, нигде не должно быть обратного, это как не считать пустое множество множеством, сами понимаете. Подобное получается с частичными функциями: любая функция — и частичная функция тоже.