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

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

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

Любой набор X может быть использован для создания свободной полурешетки FX . Свободный полурешетка определен состоять из всех конечных подмножеств из X , с полурешетке операцией , задаваемой обычным набором союзом . Свободная полурешетка обладает универсальным свойством . Универсальный морфизм является ( FX , η) , где η является единица отображения η: X → FX , который принимает х ∈ Х к одноэлементному множеству { х }. Универсальное свойство тогда таково: для любого отображения f : X → L из X в некоторую произвольную полурешетку L существует единственный полурешеточный гомоморфизм такой, что . Карта может быть явно записана; это дается ${\ displaystyle {\ tilde {f}}: FX \ to L}$${\ displaystyle f = {\ тильда {f}} \ circ \ eta}$${\ displaystyle {\ tilde {f}}}$

${\ Displaystyle S \ в FX \ mapsto \ bigvee \ left \ {f (s) \ mid s \ in S \ right \}}$

где обозначает операцию полурешетку в L . Эта конструкция может быть перенесена от полурешеток к решеткам ; по построению карта будет иметь те же свойства, что и решетка. ${\ displaystyle \ bigvee}$${\ displaystyle {\ tilde {f}}}$

Тогда конструкция X ↦ FX является функтором из категории множеств в категорию решеток. Функтор F является сопряжен слева к забывания функтора из решеток , лежащих в основе их множества. Свободная решетка - это свободный объект .

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

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

х ∧ г ∧ ( х ∨ у ) ≤ ~ х ∧ г на 5. поскольку х ∧ г ≤ ~ х ∧ г Автор: 1. поскольку х ∧ г знак равно х ∧ г

х ∧ г ≤ ~ х ∧ г ∧ ( х ∨ у ) на 7. поскольку х ∧ г ≤ ~ х ∧ г и х ∧ г ≤ ~ х ∨ у Автор: 1. поскольку х ∧ г знак равно х ∧ г на 6. поскольку х ∧ г ≤ ~ Икс на 5. поскольку Икс ≤ ~ Икс Автор: 1. поскольку Икс знак равно Икс

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

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

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

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

р _{п + 1} = х ∨ ( у ∧ ( г ∨ ( х ∧ ( у ∨ ( г ∧ р _п )))))

где x , y и z - три образующих, а p ₀ = x . Затем, используя индуктивные соотношения проблемы слов, можно показать, что p _{n +1} строго больше, чем p _n , и поэтому все бесконечно много слов p _n оцениваются в разные значения в свободной решетке FX .

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

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

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

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

К аксиомам предварительного упорядочения проблемы слов могут быть добавлены два бесконечных оператора, соответствующие meet и join. После этого можно расширить определение до индексируемого по порядку, данного ${\ 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}}$

использованная литература

• Питер Т. Джонстон, Stone Spaces , Cambridge Studies in Advanced Mathematics 3, Cambridge University Press, Cambridge, 1982. ( ISBN   0-521-23893-5 ) (см. Главу 1)