Полурешётки

Естественный частичный порядок в решётке можно определить двумя способами:

a b := aÇb = a или a b := aÈb = b.

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

Множество M c операцией Ç : M ´ M ® M называется полурешёткой, если выполнены следующие условия (аксиомы полурешётки):

1. aÇa = a идемпотентность

2. aÇb = bÇa коммутативность

3. aÇ(bÇc) = (aÇb)Çc ассоциативность

Такой набор свойств встречается достаточно часто, так что многие операции образуют полурешётку.

Пример Операции объединения и пересечения множеств образуют полурешётки.

Как видно из доказательства теоремы 1 подраздела 2.5.4, аксиом полурешетки достаточно для определения естественного частичного порядка a b := aÇb = a.

ЗАМЕЧАНИЕ Для доказательства рефлексивности используется идемпотентность, для доказательства антисимметричности – коммутативность, а транзитивность следует из ассоциативности.

Функция f : M ® M, определённая на полурешётке M, называется дистрибутивной, если f(xÇy)=f(x)Ç f(y).

ЗАМЕЧАНИЕ В терминах подраздела 2.1.5 дистрибутивная функция – это гомоморфизм.

Нетрудно видеть, что дистрибутивная функция f монотонна:

x y Þ x = xÇy Þ f(x) = f(xÇy) = f(x) Ç f(y) Þ f(x) f(y).

Пример Пересечение в булеане монотонно, а разность – нет.

Полурешётка называется ограниченной, если у неё существуют верхняя и нижняя грань.

Поскольку естественный частичный порядок в полурешётке определён, определены и все другие понятия, построенные на его основе:

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

ТЕОРЕМА. Если L – ограниченная полурешётка конечной высоты, а f : L ® L – монотонная функция, то функция f имеет наименьшую неподвижную точку, которая может быть получена методом итераций из нижней грани.

Доказательство Поскольку полурешётка ограничена, ее нижняя грань 0 является наименьшим элементом. Поскольку полурешетка имеет конечную высоту, всякое линейно упорядоченное подмножество можно рассматривать как монотонную последовательность, который заканчивается наибольшим элементом (супремумом). В частности, последовательность áf ⁰(0), f ¹(0), f ²(0),… ñ монотонна в силу монотонности функции f и имеет супремум a = sup{f ⁿ(0) | n³0}, который является наименьшей неподвижной точкой (см. доказательство теоремы о наименьшей неподвижной точке в подразделе 1.8.5'). 

ЗАМЕЧАНИЕ Можно показать, что множество неподвижных точек монотонной функции на ограниченной полурешётке конечной высоты само образует ограниченную полурешётку конечной высоты.

Пример Рассмотрим конечное множество A = {a, …} и множество подмножеств этого множества 2^A. Ясно, что 2^A является ограниченной полурешёткой конечной высоты относительно пересечения. Рассмотрим f : 2^A ® 2^A, где f(X) := X+a. Наименьшей неподвижной точкой этой функции является {a}. Действительно, f(Æ)=a, f(a)=a, f(f(a))=a,…. Более того, все подмножества 2^A, содержащие элемент a, являются неподвижными точками функции f и образуют ограниченную полурешетку конечной высоты.