Решён
Задача с МХО - подкиньте идею как решать?

Михаил Попов Математика
270
3

Застрял на задаче, понять не могу откуда заходить.

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

Теорема вроде очевидная, но как аккуратно записать формальное доказательство - теряюсь. Подскажите общую идею, не обязательно дописывать за меня.

Решение
22
Участник • 13 ответов

Идея такая: решетка требует существования и супремума (join), и инфимума (meet) для любых двух элементов. У тебя по условию есть только sup.

Ключ: инфимум двух элементов a и b в частично упорядоченном множестве - это супремум множества всех нижних граней {a, b}. Множество нижних граней непусто (если порядок с наименьшим элементом) или может быть пустым в общем случае - вот тут и надо аккуратно поработать.

Формально: обозначь L(a,b) = {x в X : x <= a и x <= b}. Покажи, что L(a,b) непусто (это отдельное условие или следует из структуры твоего МХО - смотри что дано). Потом применяй условие задачи: у L(a,b) как подмножества X существует sup, и этот sup и будет inf(a,b). Проверь, что он действительно нижняя грань и наибольшая из них - две строчки из определений.

Аватар Михаил Попов

Спасибо, идея с L(a,b) понял. Значит условие "для любых двух элементов" в задаче надо распространить и на подмножества нижних граней - это и есть мост между двумя направлениями.

11
Эксперт • 1 ответ

Это классика Биркгофа. Посмотри "Lattice Theory" Birkhoff, там это доказывается в первой главе. Если нет доступа - на math.stackexchange точно есть разжеванная версия по запросу "complete semilattice is lattice".

5
Эксперт • 2 ответа

Вы уверены что задача именно про любые два элемента, а не про любые подмножества? Если про любые два - это полурешетка по объединению (join-semilattice), и она не всегда является полной решеткой без дополнительных условий. Уточните условие.

Написать ответ

Премодерация гостей

Вы отвечаете как гость. Ваш ответ будет скрыт до проверки модератором. Чтобы ответ появился сразу и вы получали репутацию — войдите в аккаунт.

Будьте вежливы и соблюдайте правила платформы.