Решётка (, ) (ранее использовался термин структура) — частично упорядоченное множество, каждое двухэлементное подмножество которого обладает одновременно точной верхней и точной нижней гранями. Поэтому у произвольного непустого конечного подмножества решётки также имеются обе эти грани.
Решётка — частный случай не только частично упорядоченного множества, но также и направленного множества как по возрастанию, так и по убыванию.
Линейно упорядоченное множество — частный случай решётки.
Понятие решётки () возникло в середине XIX века, и наиболее полное определение было дано в работах Рихарда Дедекинда.
Определение Решетка — частично упорядоченное множество , в котором выполняются три аксиомы частичного порядка и одна специальная аксиома: I. Отношение рефлексивности: для каждого всегда выполняется ; II. Отношение транзитивности: для любых , , всегда выполняется ; III. Отношение антисимметричности: для любых , , всегда выполняется ; IV. Для любых найдётся супремум и инфимум .
Синонимы: решёточно упорядоченное множество; бинаправленное множество.
Решётка — частный случай не только частично упорядоченного множества, но также и направленного множества как по возрастанию, так и по убыванию.
Линейно упорядоченное множество — частный случай решётки.
Решётка в общем случае может не иметь нуля и единицы, то есть и в решётке могут не существовать.
Значимость решёток Наиболее востребованы с получением важных результатов следующие частные случаи решёток: алгебраическая решётка, атомная решётка, решётка Брауэра, векторная решётка, дедекиндова решётка, дистрибутивная решётка, мультипликативная решётка, ортомодулярная решётка, полная решётка, свободная решётка, решётка с дополнениями, булева алгебра.
Теория решёток используется при рассмотрении таких понятий, как идеал, фильтр, пополнение сечениями. Исключительное значение имеют алгебраические образования, которые одновременно есть решётки (например, структурно упорядоченная группа). Но самое большое количество приложений теории решёток связано с булевыми алгебрами. Некоторые виды решёток используют квантовая механика и физика.
История Понятие булевой алгебры возникло в первой половине XIX века при исследовании английского математика и логика Джоржа Буля формализации пропозициональной логики. Понятие решётки возникло в середине XIX века.
В конце XIX века, занимаясь аксиоматикой булевых алгебр, американский логик и математик Чарльз Пирс и немецкий математик и логик Эрнст Шрёдер определили понятие решётки, но без введения самого термина. Наиболее полно это понятие независимо от них сформулировал немецкий математик Рихард Дедекинд в трудах 1894 и 1897 годов (у него решётка — ) при изучении идеалов алгебраических чисел. Кроме того, Дедекинд изучал модулярность (модулярная решётка — ), то есть ослабленную дистрибутивность. Ряд достаточно элегантных и глубоких ранних результатов этих математиков и американского математика не были всё-таки замечены математической общественностью.
В середине тридцатых годов XX века труды американского математика Гарретта Биркгофа наконец подтолкнули общее развитие теории решёток, так как и сам Биркгоф, и советский математик и логик Валерий Иванович Гливенко, австрийско-американский математик Карл Менгер, венгеро-американский математик Джон фон Нейман, норвежский математик Ойстин Оре и другие достаточно продвинулись в этой новой области. В результате Биркгоф успешно «подал» теорию решёток математической общественности в первом издании монографии «Теория решёток». Развитие этой области математики отслеживается по первому, второму и третьему изданиям этой книги (1940, 1948, 1967).
Сам термин (), который затем первоначально перевели на русский как «структура», был введён в 1933 году Биркгофом. Сейчас термин «структура» из-за его многозначности в математике в русской терминологии вытеснен термином «решётка».
Исторически значимость теории решёток основана на том факте, что многие результаты, связанные с множеством всех идеалов некоторого кольца или множеством всех нормальных подгрупп некоторой группы, выглядят похоже и их можно доказать, используя теорию дедекиндовых решёток.
Обилие решёток в различных разделах математики не было ясно осознано до Дедекинда. После Дедекинда немецкий математик Эмми Нетер указала на важность решёток в алгебре. Важность в других разделах математики признавали независимо друг от друга немецкий математик Фриц Клейн-Бармен, Менгер и Биркгоф.
В 30-х годах XX века теория решёток обрела самостоятельность как раздел алгебры. Её наиболее важные разделы следующие: модулярные решётки, полные решётки, дистрибутивные решётки, булевы алгебры.
В итоге развитие теории решёток имеет три этапа. Первый период начался с опубликования в 1847 году английским математиком и логиком Джорджем Булем статьи «Математический анализ логики». Вслед за этим рядом математиков-логиков были рассмотрены аксиомы булевой алгебры и алгебры отношений. Итоги опубликованы в 1890—1895 годах немецким математиком и логиком Эрнстом Шрёдером в трёхтомной «Алгебре логики».
В 1930 году вышла классическая книга «Современная алгебра», которую написал голландский математик и историк математики Бартель Леендерт Ван дер Варден. Второй этап развития теории структур наступил через два года. В 1933—1937 годах вышло несколько статей, написанных Биркгофом, Нейманом, Маршаллом Стоуном и советским математиком Леонидом Витальевичем Канторовичем, которые показали, что обобщения булевой алгебры до соответствующих «структур» основополагающие для современной алгебры, проективной геометрии, теории точечных множеств, функционального анализа, логики и теории вероятностей. Часть этих статей были предвосхищены в двух работах Дедекинда (которые остались почти незамеченными), Менгера, польско-американского математика и логика Альфреда Тарского и Фрица Клейна-Бармена.
Третий, современный, период характеризуется непрерывным возникновением новых исследований теории решёток, которая стала существенным направлением современной алгебры. как и её старшая сестра — теория групп — теория решёток богата абстрактными идеями, общими для нескольких направлений математики, которые до сих пор не были связаны. Основа обеих теорий — аксиомы, которые обладают очень простой и общематематической природой.
Решётка как универсальная алгебра
Определение универсальной алгебры на основе решётки Решётку можно также определить как универсальную алгебру с двумя бинарными операциями. Для этого определяют следующие две операции:
Вместо обозначений и часто используют другие символы: соответственно либо и , либо и .
Операция называется сложением, операция — умножением.
Синонимы операций: операции и называются также соответственно объединение и пересечение, или супре́мум и и́нфимум.
Так определённая универсальная алгебра отвечает следующим тождествам: L1) идемпотентность: (1) , (1') ; L2) коммутативность: (2) , (2') ; L3) ассоциативность: (3) , (3') ; L4) поглощение: (4) , (4') .
Кроме того, элементы и отвечают равенствам , , , , при любых , причём первые три из них аналогичны соответствующим законам обычной арифметики.
Определение решётки на основе универсальной алгебры И наоборот, рассмотрим множество с некоторыми двумя бинарными операциями, которые удовлетворяют приведённым ранее свойствам L1—L4. Тогда на множестве можно определить порядок следующим образом: при , при этом сразу автоматически получится и следующее определение: при , другими словами, следующие три утверждения эквивалентны: , , .
Получающееся при таком конструировании частично упорядоченное множество оказывается решёткой со следующими определениями:
В итоге получаем, что решётка определяется как универсальная алгебра, которая определяется приведёнными ранее тождествами L1—L4, то есть решётка образует многообразие универсальных алгебр.
Примеры решёток Большая доля важнейших изучаемых в математике частично упорядоченных систем суть решётки. Более того, в таких системах точная верхняя и нижняя границы и обычно отвечают достаточно известным и важным построениям.
1. . Множество всех подмножеств данного множества, которые упорядочены по включению множеств следующим образом:
Если взять не все подмножества некоторого множества, а некоторые их них, хоть и упорядоченное по тому же закону, то такой набор может и не быть решёткой.
2. Любое линейно упорядоченное множество: при имеем: .
3. Все подпространства некоторого векторного пространства, которые упорядочены по включению множеств следующим образом:
.
4. . Все неотрицательные (или положительные) целые числа, которые упорядочены по делимости, то есть при для некоторого . Здесь — наименьшее общее кратное, а — наибольший общий делитель данных чисел. Это множество частично упорядочено в отличие от множества натуральных чисел (с нулём или без), упорядоченного по возрастанию, которое есть линейно упорядоченное множество. Например, при упорядочении по делимости числа 8 и 12 не сравнимы, а наименьшее число, следующим за 8 и 12 — их наименьшее общее кратное 24.
5. Все вещественные функции, определённые на единичном отрезке , упорядоченные следующим условием: , если для всех . Здесь имеем: , .
Например, если , , то
Если взять не всё множество таких функции, а некоторое их подмножество, хоть и упорядоченное по тому же закону, то такое подмножество может и не быть решёткой.
6. Все подгруппы некоторой группы с теоретико-множественным включением. В этом случае бинарные операции решётки суть обычные объединение и пересечение множеств.
7. Рассмотрим множество всех отношений конгруэнтности на абстрактной алгебре . Введём отношение порядка случай, когда есть подразбиение , то есть из вытекает . Тогда есть решётка. Причём задаёт произведение разбиений и в обычном смысле, то есть равносильно и . Кроме того, в вырожденном случае, то есть когда на не задано никаких операций, есть решётка, состоящая из всех разбиений множества .
8. Произвольное векторное пространство вещественных чисел , для любых двух векторов и которого определено неравенство , если для всех , причём по крайней мере при одном из . Любое ограниченное подмножество этого пространства обладает точной верхней и точной нижней гранями, которые задаются покоординатно. Другими словами, пусть подмножество , , причём ограничено сверху. Тогда
где при любом .
9. Аналогично предыдущему примеру, упорядочивается множество всех векторов бесконечномерного вещественного векторного пространства. И также любое ограниченное подмножество этого пространства обладает точной верхней и точной нижней гранями, которые задаются покоординатно.
10. Совокупность всех порядковых чисел первого и второго классов как любых типов полного упорядочения конечных и счётных множеств упорядочена по возрастанию, так как два произвольных трансфинитных числа сравнимы.
11. Множество всех идеалов произвольного частично упорядоченного множества.
Примеры упорядоченных множеств, которые не являются решётками
1. Множество, которое состоит из всех подмножеств некоторого множества, за исключением пустого множества, есть частично упорядоченное множество, но не является решёткой.
2. Множество всех вещественных функций, определённые на единичном отрезке , причём каждая функция больше нуля по крайней мере в одной точке, есть частично упорядоченное множество, но не решётка. Это следует из того, что отсутствует в этом множестве тогда, когда в любой точке .
Например, если , то
3. Дискретный порядок, когда любые два разных элемента несравнимы, будет решёткой, только если элемент один-единственный.
4. Делители числа 36 без 6 — {1, 2, 3, 12, 18, 36}, упорядоченные по делимости. Числа 2 и 3 не имеют точной верхней грани, а 12 и 18 — точной нижней.
Описания решётки Для иллюстрации результатов или опровержения предположений можно алгебраически описывать решётки, как это было сделано в примерах. Кроме того, описывать конкретные решётки можно ещё тремя способами.
Табличный способ Конечная решётка наглядно описывается с помощью двух таблиц: