Свободная решетка

Математическая концепция

В математике , в области теории порядка , свободная решетка — это свободный объект, соответствующий решетке . Будучи свободными объектами, они обладают свойством универсальности .

Формальное определение

Поскольку понятие решетки может быть аксиоматизировано с помощью двух операций и удовлетворяет определенным тождествам, категория всех решеток составляет многообразие (универсальную алгебру) , и, таким образом, существуют (в соответствии с общими принципами универсальной алгебры ) свободные объекты внутри этой категории: решетки, в которых имеют место только те соотношения, которые следуют из общих аксиом. ${\displaystyle \wedge }$ ${\displaystyle \vee }$

Эти свободные решетки можно охарактеризовать с помощью соответствующего универсального свойства . Конкретно, свободная решетка — это функтор от множеств к решеткам, сопоставляющий каждому множеству свободную решетку, оснащенную отображением множества , присваивающим каждому соответствующий элемент . Их универсальное свойство состоит в том, что для любого отображения из в некоторую произвольную решетку существует единственный гомоморфизм решетки , удовлетворяющий или как коммутативная диаграмма : ${\displaystyle F}$ ${\displaystyle X}$ ${\displaystyle F(X)}$ ${\displaystyle \eta \colon X\longrightarrow F(X)}$ ${\displaystyle x\in X}$ ${\displaystyle \eta (x)\in F(X)}$ ${\displaystyle f\colon X\longrightarrow L}$ ${\displaystyle X}$ ${\displaystyle L}$ ${\displaystyle {\tilde {f}}\colon F(X)\longrightarrow L}$ ${\displaystyle f={\tilde {f}}\circ \eta }$

$${\displaystyle {\begin{array}{cccc}X&{\stackrel {\eta }{\longrightarrow }}&F(X)\\&\!\forall f\searrow &{\Bigg \downarrow }\exists _{1}{\tilde {f}}\!\!\!\!\!\!\!\!\!\!&\quad \\&&L\end{array}}}$$

сопряженнымфунктором забвения ${\displaystyle F}$

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

Полурешетки

В случае полурешеток явную конструкцию свободной полурешетки дать несложно; это помогает проиллюстрировать некоторые особенности определения посредством универсального свойства. Конкретно, свободная полурешетка может быть реализована как набор всех конечных непустых подмножеств с обычным объединением множеств в качестве операции соединения . Карта отображает элементы в одноэлементные множества , т. е. для всех . Для любой полурешетки и любого отображения множества соответствующий универсальный морфизм задается формулой ${\displaystyle F_{\vee }(X)}$ ${\displaystyle F_{\vee }(X)}$ ${\displaystyle X}$ ${\displaystyle \vee }$ ${\displaystyle \eta \colon X\longrightarrow F_{\vee }(X)}$ ${\displaystyle X}$ ${\displaystyle \eta (x)=\{x\}}$ ${\displaystyle x\in X}$ ${\displaystyle L}$ ${\displaystyle f\colon X\longrightarrow L}$ ${\displaystyle {\tilde {f}}\colon F_{\vee }(X)\longrightarrow L}$

$${\displaystyle {\tilde {f}}(S)=\bigvee _{x\in S}f(x)\qquad {\text{for all }}S\in F_{\vee }(X)}$$

${\displaystyle \bigvee }$ ${\displaystyle L}$

Эта форма обусловлена ​​универсальным свойством: любой может быть записан как конечное объединение элементов в форме для некоторых , говорит равенство в универсальном свойстве , и, наконец, статус гомоморфизма подразумевает для всех . Однако любое расширение до бесконечных подмножеств (если оно вообще существует) не обязательно должно однозначно определяться этими условиями, поэтому не может быть никаких элементов, соответствующих бесконечным подмножествам . ${\displaystyle {\tilde {f}}}$ ${\displaystyle S\in F_{\vee }(X)}$ ${\displaystyle \eta (x)}$ ${\displaystyle x\in X}$ ${\displaystyle {\tilde {f}}{\bigl (}\eta (x){\bigr )}=f(x)}$ ${\displaystyle {\tilde {f}}}$ ${\displaystyle {\tilde {f}}(S_{1}\cup S_{2})={\tilde {f}}(S_{1})\vee {\tilde {f}}(S_{2})}$ ${\displaystyle S_{1},S_{2}\in F_{\vee }(X)}$ ${\displaystyle {\tilde {f}}}$ ${\displaystyle X}$ ${\displaystyle F_{\vee }(X)}$ ${\displaystyle X}$

Нижние полурешетки

Аналогично можно определить свободный функтор для нижних полурешеток , но комбинация не может создать свободную решетку несколькими способами, поскольку рассматривается как просто набор: ${\displaystyle F_{\wedge }}$ ${\displaystyle F_{\wedge }(F_{\vee }(X))}$ ${\displaystyle F(X)}$ ${\displaystyle F_{\wedge }}$ ${\displaystyle F_{\vee }(X)}$

• операция соединения не распространяется на новые элементы , ${\displaystyle \vee }$ ${\displaystyle F_{\wedge }(F_{\vee }(X))}$
• существующий частичный порядок не соблюдается; взгляды и как несвязанные, не понимая, что следует сделать . ${\displaystyle F_{\vee }(X)}$ ${\displaystyle F_{\wedge }}$ ${\displaystyle a}$ ${\displaystyle a\vee b}$ ${\displaystyle a\wedge (a\vee b)=a}$

Реальная структура свободной решетки значительно сложнее, чем структура свободной полурешетки. ${\displaystyle F(X)}$

Проблема со словом

Проблема слов для свободных решеток имеет несколько интересных аспектов. Рассмотрим случай ограниченных решеток , то есть алгебраических структур с двумя бинарными операциями ∨ и ∧ и двумя константами ( нулевыми операциями ) 0 и 1. Набор всех корректных выражений , которые можно сформулировать с помощью этих операций над элементами из данного множество образующих X будем называть W ( X ). Этот набор слов содержит множество выражений, которые обозначают равные значения в каждой решетке. Например, если a — некоторый элемент X , то a  ∨ 1 = 1 и a  ∧ 1 = a . Проблема слов для свободных ограниченных решеток — это проблема определения того, какие из этих элементов W ( X ) обозначают один и тот же элемент в свободной ограниченной решетке FX и, следовательно, в каждой ограниченной решетке.

Словесную проблему можно решить следующим образом. Отношение ≤ _~ на W ( X ) может быть определено индуктивно , установив w ≤ _~ v тогда и только тогда, когда выполняется одно из следующих условий:

1.   w = v (это можно ограничить случаем, когда w и v являются элементами X ),
2.   ш = 0,
3.   v = 1,
4.   w = w ₁ ∨ w ₂ и выполняются оба w ₁ ≤ _~ v и w ₂ ≤ _~ v ,
5.   w = w ₁ ∧ w ₂ и выполняется либо w ₁ ≤ _~ v , либо w ₂ ≤ _~ v ,
6.   v = v ₁ ∨ v ₂ и выполняется либо w ≤ _~ v ₁ , либо w ≤ _~ v _{2 ,}
7.   v = v ₁ ∧ v ₂ и выполняются оба условия w ≤ _~ v ₁ и w ≤ _~ v ₂ .

Это определяет предварительный порядок ≤ _~ на W ( X ), поэтому отношение эквивалентности может быть определено как w ~ v , когда w ≤ _~ v и v ≤ _~ w . Тогда можно показать, что частично упорядоченное фактор-пространство W ( X )/~ представляет собой свободную ограниченную решетку FX . ^{[1] [2]} Классы эквивалентности W ( X ) /~ — это множества всех слов w и v с w ⩽ _~ v и v ⩽ _~ w . Два правильно построенных слова v и w в W ( X ) обозначают одно и то же значение в каждой ограниченной решетке тогда и только тогда, когда w ≤ _~ v и v ≤ _~ w ; последние условия можно эффективно решить, используя приведенное выше индуктивное определение. В таблице показан пример вычисления, показывающий, что слова x ∧ z и x ∧ z ∧( x ∨ y ) обозначают одно и то же значение в каждой ограниченной решетке. Случай неограниченных решеток рассматривается аналогично, опуская правила 2 и 3 в приведенной выше конструкции.

Решение проблемы слов на свободных решетках имеет несколько интересных следствий. Во-первых, свободная решетка трехэлементного набора образующих бесконечна. Фактически можно даже показать, что каждая свободная решетка на трех образующих содержит подрешетку , свободную для набора из четырех образующих. По индукции это в конечном итоге дает подрешетку, свободную от счетного числа образующих. ^[3] Это свойство напоминает SQ-универсальность в группах .

Доказательство бесконечности свободной решетки в трех образующих осуществляется путем индуктивного определения

п _{п +1} знак равно Икс ∨ ( y ∧ ( z ∨ ( Икс ∧ ( y ∨ ( z ∧ п _п )))))

где x , y и z — три генератора, а p0 ₌ x . Затем можно показать, используя индуктивные соотношения проблемы слов, что p _{n +1} строго больше ^[4] , чем p _n , и, следовательно, все бесконечно много слов p _n оцениваются как различные значения в свободной решетке FX .

Полная свободная решетка

Другое следствие состоит в том, что полная свободная решетка (от трех и более образующих) «не существует» в том смысле, что она является собственным классом . Доказательство этого следует и из слова проблема. Чтобы определить полную решетку в терминах отношений, недостаточно использовать конечные отношения встречи и соединения ; необходимо также иметь бесконечные отношения, определяющие встречу и соединение бесконечных подмножеств. Например, бесконечное отношение, соответствующее «объединению», может быть определено как

${\displaystyle \operatorname {sup} _{N}:(f:N\to FX)}$

Здесь f — отображение элементов кардинала N в FX ; оператор обозначает супремум, поскольку он переносит образ f в его соединение. Это, конечно, идентично «объединению», когда N — конечное число; Целью этого определения является определение соединения как отношения, даже если N — бесконечный кардинал. ${\displaystyle \operatorname {sup} _{N}}$

К аксиомам предварительного порядка проблемы слов можно присоединить два бесконечных оператора, соответствующие встречам и соединениям. После этого можно расширить определение до порядково индексированного значения , заданного формулой ${\displaystyle p_{n}}$ ${\displaystyle p_{\alpha }}$

${\displaystyle p_{\alpha }=\operatorname {sup} \{p_{\beta }\mid \beta <\alpha \}}$

когда является предельным порядковым номером . Тогда, как и прежде, можно показать, что строго больше . Таким образом, в полной свободной решетке по крайней мере столько элементов, сколько ординалов, и, следовательно, полная свободная решетка не может существовать как множество и, следовательно, должна быть собственным классом. ${\displaystyle \alpha }$ ${\displaystyle p_{\alpha +1}}$ ${\displaystyle p_{\alpha }}$

Рекомендации

1. Филип М. Уитмен , «Свободные решетки», Ann. Математика. 42 (1941) стр. 325–329.
2. Филип М. Уитмен, «Свободные решетки II», Ann. Математика. 43 (1941) стр. 104–115.
3. Л. А. Скорняков, Элементы теории решеток (1977) Adam Hilger Ltd. (см. стр. 77-78)
4. то есть p _n ≤ _~ p _{n +1} , но не p _{n +1} ≤ _~ p _n

• Питер Т. Джонстон, «Каменные пространства» , Кембриджские исследования по высшей математике 3, издательство Кембриджского университета, Кембридж, 1982. ( ISBN  0-521-23893-5 ) (см. главу 1).