Теория порядка и решеток

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

Definition

Математическое изучение частичных порядков — рефлексивных, антисимметричных, транзитивных отношений — и решеток, которые представляют собой частично упорядоченные множества, в которых каждые два элемента имеют объединение (супремум) и пересечение (инфимум).

Scope

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

Sub-topics

• Решетки и булевы алгебры
• Частично упорядоченные множества

Core questions

• Как можно формализовать и визуализировать отношение предшествования между элементами?
• Когда упорядоченное множество обладает супремумами и инфимумами, что делает его решеткой?
• Какие решетки являются дистрибутивными и как они представляются?
• Как возникают теоретико-порядковые двойственности и теоремы о неподвижной точке?

Key concepts

• Частичный порядок
• Диаграмма Хассе
• Цепи и антицепи
• Объединение и пересечение
• Дистрибутивная решетка
• Булева алгебра

Clinical relevance

Теория порядка и решеток лежит в основе семантики языков программирования (теория доменов и неподвижные точки), формального концептуального анализа в интеллектуальном анализе данных, алгебры логики и структуры комбинаторных семейств, упорядоченных по включению или уточнению.

History

Теория решеток была разработана как самостоятельная дисциплина Биркгофом в 1930-х годах, основываясь на работах Дедекинда XIX века; ее комбинаторная сторона была развита теорией Мёбиуса на частично упорядоченных множествах Роты.

Key figures

• Garrett Birkhoff
• Richard Dedekind
• Gian-Carlo Rota

Seminal works

• davey2002

Frequently asked questions

В чем разница между частичным порядком и полным порядком?

В полном порядке любые два элемента сравнимы, тогда как частичный порядок может оставлять некоторые пары несравнимыми, как, например, с подмножествами, упорядоченными по включению.

Почему решетка является одновременно и порядком, и алгеброй?

Решетка может быть определена порядком, в котором существуют объединения и пересечения, или, эквивалентно, двумя бинарными операциями, удовлетворяющими аксиомам решетки; эти две точки зрения описывают одну и ту же структуру.