2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Почему множество разбиений -- решётка?
Сообщение16.01.2007, 08:21 
Заслуженный участник
Аватара пользователя


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

Изображение

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

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

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

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

 Профиль  
                  
 
 Re: Почему множество разбиений -- решётка?
Сообщение16.01.2007, 10:26 
Заслуженный участник
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Почему множество разбиений -- решётка?
Сообщение16.01.2007, 18:33 
Заслуженный участник
Аватара пользователя


16/03/06
406
Moscow
bot писал(а):
По восходящим ребрам легко находим верхние грани, а по нисходящим - нижние.

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

 Профиль  
                  
 
 
Сообщение16.01.2007, 18:44 
Супермодератор
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение16.01.2007, 19:06 
Заслуженный участник
Аватара пользователя


16/03/06
406
Moscow
PAV писал(а):
Это сам элемент 12/3/4, так как он меньше или равен обоих.

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

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

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

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

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

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

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

 Профиль  
                  
 
 
Сообщение16.01.2007, 19:16 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Dims писал(а):
Иными словами, если в орграфе есть циклы, то отображаемое им множество не является частично-упорядоченным?


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

 Профиль  
                  
 
 
Сообщение17.01.2007, 07:37 
Заслуженный участник
Аватара пользователя


21/12/05
5903
Новосибирск
Где тут увидали циклы? Стрелочек на диаграмме, конечно, нет, но по умолчанию они есть и все направлены вниз (или наоборот вверх - это уже вопрос договорённости)
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