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

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

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

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

Эти свободные решетки можно охарактеризовать с помощью соответствующего универсального свойства . Конкретно, свободная решетка является функтором $F$ от множеств к решеткам, присваивая каждому множеству $X$ свободная решетка $F(X)$ оснащен установленной картой $\eta \colon X\longrightarrow F(X)$ назначение каждому $x\in X$ соответствующий элемент $\eta (x)\in F(X)$ . Их универсальное свойство состоит в том, что для любого отображения $f\colon X\longrightarrow L$ от $X$ к некоторой произвольной решетке $L$ существует единственный решеточный гомоморфизм ${\tilde {f}}\colon F(X)\longrightarrow L$ удовлетворяющий $f={\tilde {f}}\circ \eta$ или в виде коммутативной диаграммы : ${\begin{array}{cccc}X&{\stackrel {\eta }{\longrightarrow }}&F(X)\\&\!\forall f\searrow &{\Bigg \downarrow }\exists _{1}{\tilde {f}}\!\!\!\!\!\!\!\!\!\!&\quad \\&&L\end{array}}$ Функтор $F$ остается сопряженным с забывчивым функтором от решеток к лежащим в их основе множествам.

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

Полурешетки

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

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

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

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

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

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

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

Пример вычисления x ∧ z ~ x ∧ z ∧( x ∨ y )

		x ∧ z ∧( x ∨ y )	≤ _~	x ∧ z
на 5.	с	x ∧ z	≤ _~	x ∧ z
на 1.	с	x ∧ z	=	x ∧ z

		x ∧ z	≤ _~	x ∧ z ∧( x ∨ y )
к 7.	с	x ∧ z	≤ _~	x ∧ z	и			x ∧ z	≤ _~	x ∨ y
на 1.	с	x ∧ z	=	x ∧ z		на 6.	с	x ∧ z	≤ _~	х
						на 5.	с	х	≤ _~	х
						на 1.	с	х	=	х

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

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

w = v (это можно ограничить случаем, когда w и v являются элементами X ),
ш = 0,
v = 1,
w = w ₁ ∨ w ₂ и выполняются оба w ₁ ≤ _~ v и w ₂ ≤ _~ v ,
w = w ₁ ∧ w ₂ и либо w ₁ ≤ _~ v , либо w ₂ ≤ _~ v , выполняется
v = v ₁ ∨ v ₂ и либо w ≤ _~ v _1, либо w ≤ _~ v _{2 ,} выполняется
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 .

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

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

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

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

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

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

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

Ссылки

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

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

[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

[1]

[2]

[3]

[4]