Подрешётка ― непустое подмножество некоторой решётки, замкнутое относительно обеих алгебраических операций и , вычисленных в исходной решётке. Другими словами, подрешётка — подалгебра некоторой решётки, определённой как универсальная алгебра, имеющая две бинарные операции.
Подрешётка — второе основное понятие теории решёток после понятия решётки.
Подмножество решётки может быть решёткой и в то же время не быть подрешёткой.
Примеры выпуклых подрешёток: любое одноэлементное подмножество решётки; идеал; фильтр; интервал. Идеал и фильтр обладают свойством кастовости, то есть их можно определить следующим образом: два элемента им принадлежат тогда и только тогда, когда им принадлежит соответствующая бинарная операция с этими элементами.
Подрешётка может быть порождена любым подмножеством решётки.
Определение Существует некоторое подмножество решётки . Тогда множество частично упорядочено при том же отношении порядке, которое действует на его надмножестве , но при этом в общем случае не обязательно решётка.
При описанной ситуации возможно, что подмножество оказывается решёткой, но для некоторых их (или ) в подмножестве отличается от (соответственно от ), который определён в надмножестве .
Причём этот (или этот ) оказывается больше (соответственно меньше), чем этот (соответственно этот ). Действительно, поскольку , то в множество , как и любое другое подмножество из , может иметь только более обширный набор верхних (соответственно нижних) границ, чем в .
Подрешётка — подмножество решётки такое, что при произвольной паре обе её грани и , которые вычислены в исходной решётке , лежат снова в подмножестве . Другими словами, подрешётка есть подалгебра некоторой решётки, определённой как универсальная алгебра, имеющая две бинарные операции.
Подрешётки, как и решётки, также обозначаются упорядоченной парой или упорядоченной тройкой , где — множество-носитель подрешётки.
Когда есть подрешётка решётки , то для произвольного конечного подмножества из его верхние (или нижние) грани, вычисленные как в , так и в , совпадают.
Произвольное подмножество линейно упорядоченного множества образует её подрешётку, причём в общем случае невыпуклую.
Множество всех подрешёток некоторой решётки, которые упорядочены отношением включения, образуют решётку.
Примеры решёток как не подрешёток
1. На рисунке справа четыре закрашенных элемента решётки образуют в ней частично упорядоченное множество — решётку относительно порядка, индуцированного исходной решёткой. Но это частично упорядоченное множество — не подрешётка исходной решётки, поскольку оно не замкнуто относительно операции взятия точной верхней грани.
2. Есть трёхмерное евклидово пространство , а в нём — наклонная плоскость , то есть плоскость, которой принадлежат все векторы .
Множество векторов указанного вида есть решётка. Действительно, пусть и , тогда их точная верхняя грань в множестве есть вектор , где , . Точно так же вычисляется и точная нижняя грань.
Но для тех же векторов их точная верхняя грань в равен , где , причём может отличаться от .
Например, если , , , , то , но .
Виды подрешёток Выпуклая подрешётка Выпуклая подрешётка (выпуклое подмножество решётки) — подрешётка (соответственно подмножество) , для которой (для которого) из , и следует . Характерный пример взаимопроникновения алгебраических и теоретико-порядковых понятий.
Примеры выпуклых подрешёток: любое одноэлементное подмножество решётки; идеал; фильтр; интервал.
Идеал и фильтр
Идеал — подрешётка решётки при условии, что для произвольных элементов и .
Иногда от идеала решётки требуется быть непустым. Непустота идеалов обладает тем преимуществом, что даёт возможность доказывать обращение некоторых теорем, и тем недостатком, что невозможно непустое пересечение бесконечного множества непустых идеалов, если решётка не имеет наименьшего элемента . Но в случае, когда в решётке содержится , все идеалы содержат и недостатка нет.
Фильтр — подрешётка решётки при условии, что для произвольных элементов и . Синонимы фильтра: коидеал; дуальный идеал
Понятие фильтра и всех утверждений, к нему относящихся, получаются из понятий идеала и соответственных утверждений, к нему относящихся, по принципу двойственности.
Альтернативные определения
Следующее утверждение в некоторых источниках является определением идеала:
Непустое подмножество решётки есть идеал тогда и только тогда, когда: для произвольных элементов ; для произвольных элементов , , .
Это подтверждается тем, что если — идеал, то, поскольку подрешётка, из следует , а при получается , то есть условия верны. Обратно, когда для выполняются оба условия, то при верно , и поскольку , то , то есть — подрешётка, а при , верно , откуда , то есть — идеал.
Следующее утверждение, называемое свойством кастовости идеала, также может служить определением идеала:
Непустое подмножество решётки есть идеал тогда и только тогда, когда если и только если .
Некоторые авторы называют фильтром только собственный дуальный идеал решётки всех подмножеств произвольного множества.
Виды идеалов и фильтров
Собственный идеал — идеал решётки такой, что . Простой идеал — собственный идеал решётки такой, что из условий и следует или . Простой фильтр называют также ультрафильтром.
Интервал
Интервал — подрешётка
решётки , где произвольные , .
Для подрешётки , которая представляет собой линейно упорядоченное множество, и её произвольных элементов определяются следующие понятия:
Открытый интервал — подрешётка
подрешётки . Полуоткрытый интервал''' — любая из подрешёток
подрешётки .
Открытый интервал и полуоткрытые интервалы — примеры выпуклых подрешёток, когда они непусты.
Порождённая подрешётка Теоретико-множественное пересечение любого набора подрешёток решётки тоже замкнуто относительно обеих операций и исходной решётки. Поэтому произвольное подмножество , содержится в некотором наименьшем подмножестве , замкнутом относительно и .
Подрешётка, порождённая множеством , — наименьшая подрешётка решётки , содержащая множество .
Порождающее множество подрешётки — множество , которым порождена подрешётка решётки .
Когда , вместо пишут или даже просто .
Непустое теоретико-множественное пересечение произвольного количества выпуклых подрешёток (идеалов, фильтров) решётки опять есть выпуклая подрешётка (идеал, фильтр), поэтому аналогично определяется выпуклая подрешётка (идеал , фильтр ), порождённая непустым подмножеством'' .
Главный идеал (главный фильтр) — идеал (фильтр), порождённый одним элементом решётки и обозначаемый , или , или (, или , или ).
В произвольной решётке, имеющей конечную длину, любой идеал или фильтр — главный. Это утверждение верно и для произвольной решётки с конечными цепями.
Примечания Комментарии
Источники
Литература
Дополнительная литература
Категория:Теория решёток Категория:Теория множеств