2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Почему множество разбиений -- решётка?
Сообщение16.01.2007, 08:21 
Аватара пользователя
Рассмотрим частично-упорядоченное множество разбиений множества {1,2,3,4}:

Изображение

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

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

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

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

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

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

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

 
 
 
 Re: Почему множество разбиений -- решётка?
Сообщение16.01.2007, 18:33 
Аватара пользователя
bot писал(а):
По восходящим ребрам легко находим верхние грани, а по нисходящим - нижние.

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

 
 
 
 
Сообщение16.01.2007, 18:44 
Аватара пользователя
Это сам элемент 12/3/4, так как он меньше или равен обоих.

 
 
 
 
Сообщение16.01.2007, 19:06 
Аватара пользователя
PAV писал(а):
Это сам элемент 12/3/4, так как он меньше или равен обоих.

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

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

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

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

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

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

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

 
 
 
 
Сообщение16.01.2007, 19:16 
Аватара пользователя
Dims писал(а):
Иными словами, если в орграфе есть циклы, то отображаемое им множество не является частично-упорядоченным?


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

 
 
 
 
Сообщение17.01.2007, 07:37 
Аватара пользователя
Где тут увидали циклы? Стрелочек на диаграмме, конечно, нет, но по умолчанию они есть и все направлены вниз (или наоборот вверх - это уже вопрос договорённости)
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$ - композиция отношений.

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group