Решётчатая диаграмма

Решётчатая диаграмма (англ. lattice diagram) — это графическое представление частично упорядоченного множества, в котором элементы множества изображаются вершинами, а отношение порядка — рёбрами, соединяющими вершины. Решётчатые диаграммы являются одним из основных инструментов теории решёток (структур) — раздела общей алгебры, изучающего упорядоченные множества специального вида. Они позволяют наглядно отображать структуру порядков, включая такие операции, как пересечение (infimum) и объединение (supremum). Наиболее распространённым типом решётчатой диаграммы является диаграмма Хассе (Hasse diagram), в которой отношение порядка передаётся через расположение вершин по вертикали: если элемент a меньше элемента b (a ≤ b), то вершина a располагается ниже вершины b, и между ними проводится ребро, если между ними нет промежуточных элементов.

История

Понятие решётки как алгебраической структуры восходит к работам немецкого математика Рихарда Дедекинда (1831–1916), который в 1890-х годах ввёл термин «структура» (Dualgruppe) и исследовал свойства дистрибутивных и модулярных решёток. Однако систематическое использование графических представлений решёток началось в XX веке. В 1930-х годах американский математик Гарретт Биркгоф (1911–1996) в своей монографии «Теория решёток» (Lattice Theory, 1940) закрепил современную терминологию и активно применял диаграммы для иллюстрации конечных решёток. Диаграммы, названные в честь немецкого математика Гельмута Хассе (1898–1979), стали стандартным способом визуализации частичных порядков. Хассе опубликовал свои работы по теории решёток в 1920–1930-х годах, хотя сам термин «диаграмма Хассе» закрепился позже, в середине XX века.

Основные понятия

Частично упорядоченное множество

Решётчатая диаграмма строится для частично упорядоченного множества (частичного порядка) — множества, на котором задано бинарное отношение ≤, удовлетворяющее трём аксиомам:

• рефлексивность: a ≤ a для любого a;
• антисимметричность: если a ≤ b и b ≤ a, то a = b;
• транзитивность: если a ≤ b и b ≤ c, то a ≤ c.

Решётка

Решётка — это частично упорядоченное множество, в котором для любых двух элементов a и b существуют:

• точная нижняя грань (infimum, пересечение, meet) — наибольший элемент, меньший или равный обоим;
• точная верхняя грань (supremum, объединение, join) — наименьший элемент, больший или равный обоим.

На диаграмме Хассе эти операции соответствуют «встрече» (пересечению) и «соединению» (объединению) путей от двух вершин к общему предку или потомку.

Диаграмма Хассе

Диаграмма Хассе — это граф, вершины которого соответствуют элементам множества, а рёбра проведены только между элементами, находящимися в отношении покрытия: элемент a покрывается элементом b (a < b), если a ≤ b, a ≠ b, и не существует c такого, что a < c < b. Рёбра обычно изображаются прямыми или ломаными линиями, причём вершина, соответствующая меньшему элементу, располагается ниже. Транзитивные связи (a ≤ c, если есть a ≤ b и b ≤ c) не показываются, что делает диаграмму компактной.

Типы решёток и их диаграммы

Дистрибутивные решётки

Дистрибутивная решётка — это решётка, в которой операции пересечения и объединения взаимно дистрибутивны:

• a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c);
• a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c).

Диаграммы дистрибутивных решёток не содержат подрешёток, изоморфных двум запрещённым пятиэлементным решёткам — пентагону (N5) и ромбу (M3). Примером дистрибутивной решётки является булева алгебра — решётка всех подмножеств конечного множества, диаграмма которой имеет форму гиперкуба (n-мерного куба).

Модулярные решётки

Модулярная решётка удовлетворяет условию модулярности: если a ≤ c, то a ∨ (b ∧ c) = (a ∨ b) ∧ c. Диаграммы модулярных решёток допускают пентагон (N5) как запрещённую подрешётку, но не допускают ромб (M3). Пример — решётка подгрупп группы.

Булевы решётки

Булева решётка — это дистрибутивная решётка с дополнениями (каждый элемент имеет единственный дополняющий элемент). Диаграмма булевой решётки из 2^n элементов (n — число атомов) представляет собой n-мерный куб. Например, для n=2 диаграмма — квадрат, для n=3 — куб, для n=4 — тессеракт.

Полные решётки

Полная решётка — это решётка, в которой любое подмножество (включая пустое) имеет точные нижнюю и верхнюю грани. Диаграммы полных решёток могут быть бесконечными, но на практике рассматриваются конечные фрагменты. Пример — решётка всех подмножеств бесконечного множества (булеан) является полной.

Применение

Теория порядков и комбинаторика

Решётчатые диаграммы используются для визуализации частичных порядков, таких как делимость натуральных чисел, включение подмножеств, иерархии классов. В комбинаторике диаграммы Хассе помогают изучать свойства решёток Юнга (Young lattice) — частичного порядка на разбиениях целых чисел, и решёток Биркгофа — решёток подмножеств.

Алгебра и теория групп

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

Информатика и теория формальных понятий

В формальном анализе понятий (Formal Concept Analysis, FCA), разработанном Бернхардом Гантером и Рудольфом Вилле в 1980-х годах, решётчатые диаграммы (решётки понятий) используются для представления бинарных отношений между объектами и признаками. Каждая вершина диаграммы соответствует понятию — паре «объекты — признаки», а рёбра отражают иерархию обобщения. FCA применяется в анализе данных, интеллектуальном анализе текстов, онтологиях и информационном поиске.

Теория графов и кристаллография

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

Примеры

Решётка делителей числа 12

Рассмотрим множество делителей числа 12: {1, 2, 3, 4, 6, 12}. Отношение порядка — делимость (a ≤ b, если a делит b). Диаграмма Хассе:

• 1 внизу;
• 2 и 3 выше 1;
• 4 выше 2 (но не выше 3);
• 6 выше 2 и 3;
• 12 выше 4 и 6.

Рёбра: 1–2, 1–3, 2–4, 2–6, 3–6, 4–12, 6–12. Эта решётка является дистрибутивной.

Булева решётка из 4 элементов

Множество {∅, {a}, {b}, {a,b}} с отношением включения. Диаграмма — квадрат: ∅ внизу, {a} и {b} на одном уровне, {a,b} вверху. Рёбра: ∅–{a}, ∅–{b}, {a}–{a,b}, {b}–{a,b}. Это булева решётка 2^2.

Пентагон (N5)

Пентагон — это пятиэлементная решётка, не являющаяся ни дистрибутивной, ни модулярной. Диаграмма: три элемента на нижнем уровне (a, b, c), один элемент d выше a и b, один элемент e выше d и c. Такая структура встречается, например, в решётке подгрупп знакопеременной группы A4.

Интересные факты

• Диаграммы Хассе часто путают с диаграммами Венна или Эйлера, однако они имеют другую функцию: показывают не пересечения множеств, а отношения порядка.
• В теории решёток существует понятие «планарной решётки» — решётки, диаграмму которой можно нарисовать на плоскости без пересечения рёбер. Не все решётки планарны.
• Бесконечные решётки, такие как решётка всех подмножеств натуральных чисел, не могут быть полностью изображены, но их конечные фрагменты часто используются для иллюстрации.
• В компьютерной алгебре существуют программы (например, Concept Explorer, Lattice Miner), которые автоматически строят решётчатые диаграммы по заданным данным.

Источники

• Биркгоф Г. Теория решёток. — М.: Наука, 1984.
• Гантер Б., Вилле Р. Формальный анализ понятий: математические основы. — М.: МЦНМО, 2010.
• Davey B. A., Priestley H. A. Introduction to Lattices and Order. — Cambridge University Press, 2002.
• Grätzer G. Lattice Theory: Foundation. — Birkhäuser, 2011.
• Овчинников В. П. Теория решёток. — М.: МГУ, 2005.