Алгебраические системы замыканий (стр. 7 из 8)
Решение:
a) докажем прямое утверждение: если (X) = H(X) 
X определяет оператор замыкания тогда X 
(Y) влечёт (X) (Y).
Пусть X (Y), то есть X H(Y)
Y. Так как по условию (Y) = H(Y) Y – оператор замыкания, то для него выполняются аксиомы J. 1 – J. 3. Применим аксиому J. 1 к X H(Y) Y и аксиому J. 3 к ((Y)):X H(Y)
Y 
H(X) X H(H(Y) Y) (H(Y) Y) 
H(X) X H(Y) Y. То есть (X) (Y).b) докажем обратное утверждение: если X (Y) влечёт (X) (Y) тогда (X) = H(X) X определяет оператор замыкания.
Для доказательства обратного утверждения, необходимо проверить выполнимость аксиом J. 1 – J. 3 оператора замыкания.
Для начала докажем вспомогательное утверждение о том, что Y
X* тогда и только тогда, когда X Y*.Доказательство:
∆ Докажем прямое утверждение.
Пусть Y
X*. Тогда, применив к нему свойство (7), получим Y* 
X**. По свойству (7) имеем включение X X**. Следовательно, получаем X X** Y* или X Y*.Докажем обратное утверждение.
Пусть X
Y*. Тогда X* Y** Y ▲J. 1: пусть X
Y и Y (X), тогда по доказанному выше утверждению включение Y (X) равносильным образом можно заменить на X (Y). Получим, что X X (Y) или X (Y). Тогда по условию пункта b) задачи X (Y) влечёт (X) (Y). Следовательно, если X Y, то (X) (Y).J. 2: пусть X
Y и Y (X) по утверждению, значит, X (X).J. 3: по J. 2 X
(X). Применим к нему свойство (7), получим (X) (X). Применим это же свойство к X (Y) 
(X) (Y), получим (X) (Y) (X) (Y). Далее по утверждению Y (X) 
(Y) (X). Получили (Y) (X) (Y). При этом (Y) (X) (по утверждению). Следовательно, мы получаем обратное включение (X) (X). Тем самым получили, что (X) = (X).Следовательно, (X) = H(X) 
X – оператор замыкания.
Задача 3. Показать, что множество всех предупорядоченностей ρ на множестве A является алгебраической системой замыканий. Верно ли это для множества всех упорядоченностей?
Решение:
Непустое множество
назовём предупорядоченным, если введенное на нём бинарное отношение ρ рефлексивно и транзитивно. Такое отношение ρ называется отношениемпредпорядканаA.ПустьX
A 
A, илиX 
B (A A). Обозначим через J(X) пересечение всех предпорядков на A, содержащих X:J(X) =
{ρ – предпорядок на A: X ρ}.Так как при пересечении бинарных отношений на множестве свойства рефлексивности и транзитивности сохраняются, то J(X) – наименьший предпорядок на A, содержащий X. Ясно, что A
A является предпорядком на A. Поэтому система всех предпорядков на A является системой замыканий на этом множестве.Остаётся проверить, будет ли система предпорядков алгебраической. Для этого возьмём произвольную пару (a, b)
J(X), где X A A. Предпорядок J(X) получается из множества пар X добавлением пар вида (c, c), где c A, и его расширением по транзитивности: если уже получены пары (d, e) и (e, f), то добавляем и пару (d, f). При этом пара (a, b) в результате последовательного применения расширений по рефлексивности и транзитивности принадлежит конечному множеству пар F X. Следовательно, (a, b) J(F).