Бинарные отношения | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
« ✓ » указывает, что свойство столбца требуется в определении строки. Например, определение отношения эквивалентности требует, чтобы оно было симметричным. Все определения неявно требуют транзитивности и рефлексивности . |
Решетка представляет собой абстрактную структуру изучаться в математической Поддисциплин теории порядка и абстрактной алгебры . Она состоит из частично упорядоченного множества , в котором каждые два элемента имеют уникальную грань (также называется крайней мере до верхней границы или присоединиться к ) и уникальный инфимумом (также называется нижняя грань или встречаются ). Примером служат натуральные числа , частично упорядоченные по делимости , для которых уникальная верхняя грань является наименьшим общим кратным, а уникальная нижняя грань является наибольшим общим делителем .
Решетки также можно охарактеризовать как алгебраические структуры, удовлетворяющие определенным аксиоматическим тождествам . Поскольку два определения эквивалентны, теория решеток опирается как на теорию порядка, так и на универсальную алгебру . К полурешеткам относятся решетки, которые, в свою очередь, включают гейтинговые и булевы алгебры . Все эти «решетчатые» структуры допускают теоретико-упорядоченное, а также алгебраическое описание.
Решетки как частично упорядоченные множества
Если ( L , ≤) является частично упорядоченное множество (ч.у.м.), и S ⊆ L произвольное подмножество, то элемент U ∈ L называется быть верхняя граница из S , если s ≤ U для каждого s ∈ S . У набора может быть много верхних границ или вообще не быть. Верхняя граница U из S назовет ее минимум до верхней границы , или присоединиться к , или супремум , если у ≤ х для каждого верхней границы х из S . У набора не обязательно должна быть наименьшая верхняя граница, но не может быть более одной. Двойственно , л ∈ L называется быть нижняя граница из S , если л ≤ ев для каждого s ∈ S . Нижняя граница л из S назовет его точным нижней границей , или встречаются , или инфимум , если х ≤ л для каждого нижней грани х из S . Набор может иметь много нижних границ или не иметь вообще, но может иметь не более одной наибольшей нижней границы.
Частично упорядоченное множество ( L , ≤) называется присоединиться к -полурешетка , если каждый из двух элементов подмножества { , Ь } ⊆ L имеет присоединиться (т.е. минимум до верхней границы), и называется Meet-полурешетка , если каждый из двух элементов подмножество имеет пересечение (то есть точную нижнюю границу), обозначаемую a ∨ b и a ∧ b соответственно. ( L , ≤) называется решеткой, если она одновременно является полурешеткой соединения и встречной. Это определение делает ∨ и ∧ бинарными операциями . Обе операции монотонны относительно заданного порядка: a 1 ≤ a 2 и b 1 ≤ b 2 означает, что a 1 ∨ b 1 ≤ a 2 ∨ b 2 и a 1 ∧ b 1 ≤ a 2 ∧ b 2 .
Из аргумента индукции следует, что каждое непустое конечное подмножество решетки имеет точную верхнюю границу и точную нижнюю границу. С дополнительными предположениями можно сделать дальнейшие выводы; см. Полноту (теория порядка) для более подробного обсуждения этого предмета. В этой статье также обсуждается, как можно перефразировать приведенное выше определение в терминах существования подходящих связей Галуа между связанными частично упорядоченными множествами - подход, представляющий особый интерес для теоретико-категориального подхода к решеткам и для анализа формальных понятий .
Ограниченная решетка является решеткой , которая дополнительно имеет наибольший элемент (называемый также максимум , или верхний элемент, и обозначается через 1, или путем) и наименьший элемент (также называемый минимальным или нижним , обозначается 0 или), которые удовлетворяют
- 0 ≤ х ≤ 1 для каждого х в L .
Каждую решетку можно вложить в ограниченную решетку, добавив искусственный наибольший и наименьший элемент, и каждая непустая конечная решетка ограничена, взяв соединение (соответственно, пересечение) всех элементов, обозначенное (соответственно ) где .
Частично упорядоченное множество является ограниченной решеткой тогда и только тогда, когда каждый конечный набор элементов (включая пустой набор) имеет соединение и пересечение. Для каждого элемента x чугуна тривиально верно (это пустая истина ), что а также , и поэтому каждый элемент poset является одновременно верхней и нижней границей пустого множества. Это означает, что объединение пустого набора является наименьшим элементом, а встреча пустого множества - наибольший элемент . Это согласуется с ассоциативностью и коммутативностью встречи и соединения: объединение объединения конечных множеств равно объединению объединений множеств, и, вдвойне, совпадение объединения конечных множеств равно объединению объединения конечных множеств. пересечения множеств, т. е. для конечных подмножеств A и B ч.у.набора L ,
а также
держать. Принимая B за пустое множество,
а также
что согласуется с тем фактом, что .
Говорят, что элемент решетки y покрывает другой элемент x , если y > x , но не существует z такого, что y > z > x . Здесь y > x означает x ≤ y и x ≠ y .
Решетка ( L , ≤) называется градуированной , иногда ранжированной (но см. Ранговое множество для альтернативного значения), если она может быть оснащена функцией ранга r от L до, иногда до ℤ, совместимой с упорядочением (так что r ( x ) < r ( y ) всякий раз, когда x < y ) такой, что всякий раз, когда y покрывает x , то r ( y ) = r ( x ) + 1 . Значение функции ранга элемента решетки называется его рангом .
Учитывая подмножество решетки, H ⊆ L , встречаются и присоединитесь ограничиться частичными функциями - они не определены , если их стоимость не входит в подмножество Н . Полученная структура на H называетсячастичная решетка . В дополнение к этому внешнему определению как подмножество некоторой другой алгебраической структуры (решетки), частичная решетка также может быть внутренне определена как набор с двумя частичными бинарными операциями, удовлетворяющими определенным аксиомам. [1]
Решетки как алгебраические структуры
Общая решетка
Алгебраическая структура , состоящий из набора и две бинарные, коммутативные и ассоциативные операции , а также , на является решеткой, если для всех элементов выполняются следующие аксиоматические тождества, иногда называемые законами поглощения .
Следующие два тождества также обычно рассматриваются как аксиомы, даже если они следуют из двух законов поглощения, взятых вместе. [примечание 1] Это называется идемпотентными законами .
Эти аксиомы утверждают, что обе а также являются полурешетками . Законы поглощения, единственные вышеприведенные аксиомы, в которых встречаются и встречаются, и объединяются, отличают решетку от произвольной пары полурешеточных структур и гарантируют, что две полурешетки взаимодействуют надлежащим образом. В частности, каждая полурешетка двойственна другой.
Ограниченная решетка
Ограниченная решеткой является алгебраической структурой вида такой, что решетка, (нижняя часть решетки) - это тождественный элемент для операции соединения, а также (вершина решетки) является единичным элементом для операции встречи .
См. Полурешетку для получения дополнительной информации.
Связь с другими алгебраическими структурами
Решетки имеют некоторые связи с семейством групповых алгебраических структур . Поскольку meet и join и коммутируют, и ассоциируют, решетку можно рассматривать как состоящую из двух коммутативных полугрупп, имеющих одну и ту же область. Для ограниченной решетки эти полугруппы фактически являются коммутативными моноидами . Закон поглощения - единственное определяющее свойство, присущее теории решетки.
По коммутативности, ассоциативности и идемпотентности можно рассматривать соединение и встречу как операции над непустыми конечными множествами, а не над парами элементов. В ограниченной решетке соединение и пересечение пустого множества также могут быть определены (как а также , соответственно). Это делает ограниченные решетки несколько более естественными, чем решетки общего вида, и многие авторы требуют, чтобы все решетки были ограниченными.
Алгебраическая интерпретация решеток играет важную роль в универсальной алгебре .
Связь между двумя определениями
Решетка теории порядка порождает две бинарные операции ∨ и. Поскольку коммутативные, ассоциативные законы и законы поглощения легко проверяются для этих операций, они превращают ( L , ∨, ∧) в решетку в алгебраическом смысле.
Обратное также верно. Для данной алгебраически определенной решетки ( L , ∨, ∧) можно определить частичный порядок ≤ на L , положив
- a ≤ b, если a = a ∧ b , или
- a ≤ b, если b = a ∨ b ,
для всех элементов через и Ь из L . Законы поглощения гарантируют, что оба определения эквивалентны:
a = a ∧ b влечет b = b ∨ ( b ∧ a ) = ( a ∧ b ) ∨ b = a ∨ b
и вдвойне в другом направлении.
Теперь можно проверить, что отношение ≤, введенное таким образом, определяет частичный порядок, в котором двоичные встречи и соединения задаются посредством исходных операций ∨ и ∧.
Поскольку два определения решетки эквивалентны, можно свободно использовать аспекты любого определения любым способом, который соответствует поставленной цели.
Примеры
Рис. 1: Подмножества {x, y, z} при включении множества . Название «решетка» подсказано формой изображающей ее диаграммы Хассе .
Рис. 2: Решетка целых делителей 60, упорядоченных по принципу « делит ».
Рис. 3: Решетка перегородок из {1, 2, 3, 4}, по заказу " уточняет ".
Рис. 4: Решетка натуральных чисел, упорядоченная по ≤.
Рис. 5: Решетка неотрицательных целочисленных пар, упорядоченная покомпонентно.
- Для любого множества А , совокупность всех подмножеств множества A ( так называемых силовой агрегат из А ) можно заказать с помощью включения подмножества , чтобы получить ограниченную решетку А сами и пустого множество. Задайте пересечение и объединение, интерпретацию, встречу и соединение соответственно (см. Рис. 1).
- Для любого множества A набор всех конечных подмножеств A , упорядоченных по включению, также является решеткой и будет ограниченным тогда и только тогда, когда A конечно.
- Для любого множества А , совокупность всех разделов из A , упорядоченных по утонченности , является решеткой (см. Фото 3).
- Эти положительные целые числа в их обычном порядке образуют решетку, в соответствии с операциями «мин» и «макс». 1 - нижний; верха нет (см. рис. 4).
- Декартовый квадрат из натуральных чисел, упорядочены так , что ( , б ) ≤ ( с , d ) , если ≤ C и B ≤ d . Пара (0, 0) - нижний элемент; верха нет (см. рис. 5).
- Натуральные числа также образуют решетку при операциях взятия наибольшего общего делителя и наименьшего общего кратного с делимостью в качестве отношения порядка: a ≤ b, если a делит b . 1 - нижний; 0 - это верх. Рис. 2 показана конечная подрешетка.
- Всякая полная решетка (см. Также ниже ) является (довольно специфической) ограниченной решеткой. На этом занятии можно найти множество практических примеров .
- Множество компактных элементов в качестве арифметической полной решетки является решеткой с наималейшим элементом, где решетки операции заданного путем ограничения соответствующих операций арифметической решетки. Это особое свойство, которое отличает арифметические решетки от алгебраических решеток , для которых компакты образуют только полурешетку соединения . Оба эти класса полных решеток изучаются в теории областей .
Дополнительные примеры решеток приведены для каждого из дополнительных свойств, обсуждаемых ниже.
Примеры нерешеток
Большинство частично упорядоченных множеств не являются решетками, включая следующие.
- Дискретный чум, означающий чум, такой, что x ≤ y влечет x = y , является решеткой тогда и только тогда, когда он имеет не более одного элемента. В частности, двухэлементное дискретное множество не является решеткой.
- Хотя набор {1, 2, 3, 6}, частично упорядоченный по делимости, является решеткой, упорядоченный таким образом набор {1, 2, 3} не является решеткой, потому что пара 2, 3 не имеет соединения; аналогично, 2, 3 не имеет пересечения в {2, 3, 6}.
- Множество {1, 2, 3, 12, 18, 36}, частично упорядоченное по делимости, не является решеткой. Каждая пара элементов имеет верхнюю границу и нижнюю границу, но пара 2, 3 имеет три верхние границы, а именно 12, 18 и 36, ни одна из которых не является наименьшей из этих трех при делимости (12 и 18 не делят друг с другом). Точно так же пара 12, 18 имеет три нижние границы, а именно 1, 2 и 3, ни одна из которых не является наибольшей из этих трех по делимости (2 и 3 не делят друг друга).
Морфизмы решеток
Соответствующее понятие морфизма между двумя решетками легко вытекает из приведенного выше алгебраического определения. Принимая во внимание две решетки ( L , ∨ L , ∧ L ) и ( М , ∨ М , ∧ М ) , А решеточный гомоморфизм из L в M является функцией F : L → М такое , что для всех в , б ∈ L :
- f ( a ∨ L b ) = f ( a ) ∨ M f ( b ) и
- f ( a ∧ L b ) = f ( a ) ∧ M f ( b ).
Таким образом, f является гомоморфизмом двух лежащих в основе полурешеток . Когда рассматриваются решетки с большей структурой, морфизмы также должны «уважать» дополнительную структуру. В частности, гомоморфизм ограниченной решетки (обычно называемый просто «решеточным гомоморфизмом») f между двумя ограниченными решетками L и M также должен обладать следующим свойством:
- f (0 L ) = 0 M и
- f (1 л ) = 1 м .
В теоретико-порядковой формулировке эти условия просто утверждают, что гомоморфизм решеток - это функция, сохраняющая двоичные пересечения и соединения. Для ограниченных решеток сохранение наименьшего и наибольшего элементов - это просто сохранение соединения и встречи пустого множества.
Любой гомоморфизм решеток обязательно монотонен относительно ассоциированного отношения порядка; см. Функция сохранения предела . Обратное неверно: монотонность ни в коем случае не означает требуемого сохранения встреч и объединений (см. Рис. 9), хотя сохраняющая порядок биекция является гомоморфизмом, если ее обратное также сохраняет порядок.
Учитывая стандартное определение изоморфизмов как обратимых морфизмов, решеточный изоморфизм - это просто биективный решеточный гомоморфизм. Аналогично, решеточный эндоморфизм - это решеточный гомоморфизм решетки в себя, а решеточный автоморфизм - это биективный решеточный эндоморфизм. Решетки и их гомоморфизмы образуют категорию .
Позволять а также - две решетки с 0 и 1 . Гомоморфизм из к называется 0,1 - разделяющим тогда и только тогда, когда (разделяет 0 ) и ( отделяет 1).
Подрешетки
Подрешетки из решетки L представляет собой подмножество L , что является решеткой с одной и той же встречаются и присоединиться к операции , как L . То есть, если L является решеткой , и М представляет собой подмножество L таких , что для каждой пары элементов через , Ь в М и ∧ б и ∨ Ь находятся в М , то М является подструктурой L . [2]
Подрешетка М из решетки L является выпуклой подрешеткой из L , если х ≤ г ≤ у и х , у в М означают , что г принадлежит М , для всех элементов х , у , г в L .
Свойства решеток
Теперь мы введем ряд важных свойств, которые приводят к интересным специальным классам решеток. Один из них - ограниченность - уже обсуждался.
Полнота
ЧУМ называется полной решеткой, если все его подмножества имеют как соединение, так и пересечение. В частности, всякая полная решетка является ограниченной решеткой. В то время как ограниченные решеточные гомоморфизмы в общем случае сохраняют только конечные соединения и пересечения, полные решеточные гомоморфизмы необходимы для сохранения произвольных соединений и пересечений.
Каждый ч.у., являющийся полной полурешеткой, также является полной решеткой. С этим результатом связано интересное явление, заключающееся в том, что существуют различные конкурирующие понятия гомоморфизма для этого класса множеств, в зависимости от того, рассматриваются ли они как полные решетки, полные соединения-полурешетки, полные пересекающиеся полурешетки, либо как полные с соединением, либо как пересекающиеся. полные решетки.
Обратите внимание, что «частичная решетка» не является противоположностью «полной решетки» - скорее, «частичная решетка», «решетка» и «полная решетка» становятся все более ограничительными определениями.
Условная полнота
Условно полная решетка является решеткой , в которой каждое непустое подмножество , что имеет верхнюю грань имеет присоединиться к (то есть, не менее верхняя граница). Такие решетки обеспечивают самое непосредственное обобщение полноты аксиомы из действительных чисел . Условно полная решетка - это либо полная решетка, либо полная решетка без ее максимального элемента 1, минимального элемента 0 или обоих.
Распределительность
Поскольку решетки поставляются с двумя бинарными операциями, то естественно спросить , есть ли один из них распространяет над другим, то есть ли один или другой из следующих двойственных имеет законы для каждых трех элементов , б , гр из L :
- Распределимость над ∨
- a ∨ ( b ∧ c ) = ( a ∨ b ) ∧ ( a ∨ c ).
- Распределимость над ∧
- a ∧ ( b ∨ c ) = ( a ∧ b ) ∨ ( a ∧ c ).
Решетка, удовлетворяющая первой или, что эквивалентно (как выясняется), второй аксиоме, называется дистрибутивной решеткой . Единственные недистрибутивные решетки, содержащие менее 6 элементов, называются M 3 и N 5 ; [3] они показаны на Рисунках 10 и 11 соответственно. Решетка дистрибутивна тогда и только тогда, когда она не имеет подрешетки, изоморфной M 3 или N 5 . [4] Каждая дистрибутивная решетка изоморфна решетке множеств (с объединением и пересечением как соединением и встречей соответственно). [5]
Для обзора более сильных понятий дистрибутивности, которые подходят для полных решеток и которые используются для определения более специальных классов решеток, таких как каркасы и полностью дистрибутивные решетки , см. Дистрибутивность в теории порядка .
Модульность
Для некоторых приложений условие дистрибутивности является слишком сильным, и часто бывает полезно следующее более слабое свойство. Решетка ( L , ∨, ∧) является модульной , если для всех элементов через , Ь , с из L , имеет место тождество.
- Модульная идентичность
- ( a ∧ c ) ∨ ( b ∧ c ) = (( a ∧ c ) ∨ b ) ∧ c .
Это условие эквивалентно следующей аксиоме.
- Модульное право
- a ≤ c влечет a ∨ ( b ∧ c ) = ( a ∨ b ) ∧ c .
Решетка является модульной тогда и только тогда, когда в ней нет подрешетки, изоморфной N 5 (изображенной на рис. 11). [4] Кроме распределительных решеток, примеры модульных решеток решетка двусторонних идеалов одного кольца , решетки подмодулей модуля , и решетка нормальных подгрупп одного группы . Набор терминов первого порядка с упорядочением « более конкретно , чем » не является модулярной решеткой используется в автоматизированных рассуждений .
Полумодулярность
Конечная решетка модулярна тогда и только тогда, когда она одновременно верхняя и нижняя полумодулярная . Для градуированной решетки (верхняя) полумодулярность эквивалентна следующему условию на ранговую функцию r :
- r ( x ) + r ( y ) ≥ r ( x ∧ y ) + r ( x ∨ y ).
Еще одно эквивалентное (для градуированных решеток) условие - условие Биркгофа :
- для каждого x и y в L , если x и y покрывают x ∧ y , то x ∨ y покрывает и x, и y .
Решетка называется полумодулярной снизу, если двойственная к ней полумодулярна. Для конечных решеток это означает, что предыдущие условия выполняются с заменой ∨ и, заменой "покрытий" на "покрывается" и обращением неравенств. [6]
Непрерывность и алгебраичность
В теории предметной области естественно стремиться аппроксимировать элементы в частичном порядке «гораздо более простыми» элементами. Это приводит к классу непрерывных множеств , состоящих из множеств, где каждый элемент может быть получен как верхняя грань направленного множества элементов, находящихся намного ниже элемента. Если можно дополнительно ограничить их компактными элементами чугуна для получения этих ориентированных множеств, то чум будет даже алгебраическим . Обе концепции могут быть применены к решеткам следующим образом:
- Непрерывная решетка является полной решеткой , которая непрерывно как посета.
- Алгебраическая решетка является полной решеткой , которая является алгебраической как посет.
Оба эти класса обладают интересными свойствами. Например, непрерывные решетки можно охарактеризовать как алгебраические структуры (с бесконечными операциями), удовлетворяющие определенным тождествам. Хотя такая характеристика не известна для алгебраических решеток, их можно описать «синтаксически» с помощью информационных систем Скотта .
Дополнения и псевдодополнения
Пусть L ограниченная решетка с наибольшим элементом 1 и наименьшим элементом 0. Два элемента х и у из L являются дополняющими друг друга , если и только если:
- х ∨ у = 1 и х ∧ у = 0 .
В общем, некоторые элементы ограниченной решетки могут не иметь дополнения, а другие могут иметь более одного дополнения. Например, множество {0, ½, 1} с его обычным порядком является ограниченной решеткой, а ½ не имеет дополнения. В ограниченной решетке N 5 элемент a имеет два дополнения: б и в (см. рис. 11). Ограниченная решетка, каждый элемент которой имеет дополнение, называется решеткой с дополнениями .
Дополненная решетка, которая также является дистрибутивной, является булевой алгеброй . Для дистрибутивной решетки дополнение к x , если оно существует, единственно.
В случае, если дополнение уникально, мы пишем ¬ x = y и, что эквивалентно, ¬ y = x . Соответствующая унарная операция над L , называемая дополнением, вводит аналог логического отрицания в теорию решеток.
Алгебры Гейтинга являются примером дистрибутивных решеток, в которых некоторые элементы могут не иметь дополнений. С другой стороны, каждый элемент x алгебры Гейтинга имеет псевдодополнение , также обозначаемое ¬ x . Псевдодополнение - это наибольший элемент y такой, что x ∧ y = 0 . Если псевдодополнение каждого элемента алгебры Гейтинга на самом деле является дополнением, то алгебра Гейтинга на самом деле является булевой алгеброй.
Условие цепи Джордана – Дедекинда
Цепь от й 0 до й п представляет собой набора, где . Длина этой цепи п , или один меньше , чем его количество элементов. Цепь максимальна, если x i покрывает x i −1 для всех 1 ≤ i ≤ n .
Если для любой пары x и y , где x < y , все максимальные цепи от x до y имеют одинаковую длину, то говорят, что решетка удовлетворяет условию цепочки Жордана – Дедекинда .
Бесплатные решетки
Любой набор X может быть использован для создания свободной полурешетки FX . Свободная полурешетка определяется как состоящая из всех конечных подмножеств X , причем операция полурешетки задается обычным объединением множеств . Свободная полурешетка обладает универсальным свойством . Для свободной решетки над множеством X , Уитмен дал конструкцию , основанную на полиномы над X ' членами s. [7] [8]
Важные теоретико-решеточные понятия
Теперь мы определим некоторые теоретико-порядковые понятия, важные для теории решеток. В дальнейшем пусть х быть элементом некоторой решетки L . Если L имеет нижний элемент 0, иногда требуется x ≠ 0 . x называется:
- Регистрация неприводимым , если х = ∨ Ь влечет х = а или х = Ь для всех а , Ь в Ь . Когда первое условие обобщается на произвольные соединения, x называется вполне объединяемой неприводимой (или ∨-неприводимой). Двойственное понятие - это неприводимость (∧-неприводимость). Например, на рис. 2 элементы 2, 3, 4 и 5 являются неприводимыми к соединению, а элементы 12, 15, 20 и 30 - неприводимыми. В решетке действительных чисел с обычным порядком каждый элемент является неприводимым по объединению, но ни один элемент не является полностью неприводимым по объединению.
- Соедините простое число, если x ≤ a ∨ b влечет x ≤ a или x ≤ b . Это тоже можно обобщить, чтобы получить понятие полностью соединить простое число . Двойственное понятие - это простое совпадение . Каждый элемент с простым соединением также является неприводимым по соединению, и каждый элемент с простым соединением также является неприводимым. Обратное верно, если L дистрибутивна.
Пусть L имеет нижний элемент 0. Элемент x из L является атомом, если 0 < x и не существует такого элемента y из L , что 0 < y < x . Затем L вызывается:
- Атомарно, если для каждого ненулевого элемента x из L существует атом a из L такой, что a ≤ x ;
- Атомистично, если каждый элемент L является супремумом атомов.
Понятия идеалов и двойственное понятие фильтров относятся к определенным видам подмножеств частично упорядоченного множества и поэтому важны для теории решеток. Подробности можно найти в соответствующих записях.
Смотрите также
- Присоединяйтесь и знакомьтесь
- Карта решеток
- Ортодополненная решетка
- Общий заказ
- Идеал и фильтр (двойственные понятия)
- Косая решетка (обобщение до некоммутативного соединения и встречи)
- Решетка Эйлера
- Решетка столба
- Решетка Тамари
- Решетка Юнга – Фибоначчи
- 0,1-простая решетка
Приложения, использующие теорию решеток
Обратите внимание, что во многих приложениях наборы представляют собой только частичные решетки: не каждая пара элементов имеет пересечение или соединение.
- Бессмысленная топология
- Решетка подгрупп
- Спектральное пространство
- Инвариантное подпространство
- Оператор закрытия
- Абстрактная интерпретация
- Решетка поглощения
- Теория нечетких множеств
- Алгебраизации логики первого порядка
- Семантика языков программирования
- Теория предметной области
- Онтология (информатика)
- Множественное наследование
- Анализ формальных концепций и Lattice Miner (теория и инструмент)
- Фильтр Блума
- Поток информации
- Порядковая оптимизация
- Квантовая логика
- Медианный график
- Пространство знаний
- Регулярное изучение языка
- Аналогичное моделирование
Заметки
- ^ a ∨ a = a ∨ ( a ∧ ( a ∨ a )) = a , и двойственно для другого идемпотентного закона. Дедекинд, Ричард (1897), «Убер Zerlegungen von Zahlen durch ihre grössten gemeinsamen Teiler», Braunschweiger Festschrift : 1–40.
Рекомендации
- ^ Grätzer 1996 , стр. 52 .
- ^ Баррис, Стэнли Н. и Санкаппанавар, HP, 1981. Курс универсальной алгебры . Springer-Verlag. ISBN 3-540-90578-2 .
- ↑ Davey & Priestley (2002) , Упражнение 4.1, стр. 104 .
- ^ a b Дэйви и Пристли (2002) , теорема 4.10, с. 89 .
- ↑ Davey & Priestley (2002) , теорема 10.21, стр. 238–239 .
- ^ Стэнли, Ричард П. , Перечислительная комбинаторика (том 1) , Cambridge University Press, стр. 103–104, ISBN 0-521-66351-2
- ^ Филип Уитмен (1941). «Свободные решетки I». Анналы математики . 42 : 325–329. DOI : 10.2307 / 1969001 .
- ^ Филип Уитмен (1942). «Свободные решетки II». Анналы математики . 43 : 104–115. DOI : 10.2307 / 1968883 .
Монографии доступны бесплатно онлайн:
- Беррис, Стэнли Н. и Санкаппанавар, HP, 1981. Курс универсальной алгебры. Springer-Verlag. ISBN 3-540-90578-2 .
- Джипсен, Питер и Генри Роуз, Разновидности решеток , Конспект лекций по математике 1533, Springer Verlag, 1992. ISBN 0-387-56314-8 .
- Нация, Дж. Б., Заметки по теории решеток . Главы 1-6. Главы 7–12; Приложения 1–3.
Элементарные тексты, рекомендуемые для людей с ограниченной математической зрелостью :
- Доннеллан, Томас, 1968. Теория решеток . Пергамон.
- Гретцер, Джордж , 1971. Теория решеток: первые концепции и распределительные решетки . WH Freeman.
Стандартный современный вводный текст, несколько сложнее, чем приведенный выше:
- Дэйви, BA; Пристли, HA (2002), Введение в решетки и порядок , Cambridge University Press , ISBN 978-0-521-78451-1
Продвинутые монографии:
- Гаррет Биркгоф , 1967. Теория решеток , 3-е изд. Vol. 25 публикаций коллоквиума AMS. Американское математическое общество .
- Роберт П. Дилворт и Кроули, Питер, 1973. Алгебраическая теория решеток . Прентис-Холл. ISBN 978-0-13-022269-5 .
- Гретцер, Джордж (1996) [1978]. Общая теория решеток (второе изд.). Базель: Биркхойзер. ISBN 978-3-7643-6996-5.
На свободных решетках:
- Р. Фриз, Дж. Джезек и Дж. Б. Нация, 1985. "Свободные решетки". Математические обзоры и монографии Vol. 42. Математическая ассоциация Америки .
- Джонстон, PT , 1982. Каменные пространства . Кембриджские исследования в области высшей математики 3. Издательство Кембриджского университета.
К истории теории решеток:
- Štĕpánka Bilová (2001). Эдуард Фукс (ред.). Теория решеток - ее рождение и жизнь (PDF) . Прометей. С. 250–257.
О приложениях теории решетки:
- Гаррет Биркгоф (1967). Джеймс С. Эббот (ред.). Что решетки могут для вас сделать? . Ван Ностранд. Оглавление
Внешние ссылки
- "Решеточно-упорядоченная группа" , Математическая энциклопедия , EMS Press , 2001 [1994]
- Вайсштейн, Эрик В. «Решетка» . MathWorld .
- JB Nation, Заметки по теории решеток , неопубликованные заметки по курсу доступны в виде двух файлов PDF.
- Ральф Фриз, "Домашняя страница теории решеток" .
- Последовательность OEIS A006966 (количество немаркированных решеток с n элементами)