Алгебраические системы замыканий

XH(Y)Y H(X)XH(H(Y)Y)(H(Y)Y)H(X)XH(Y)Y. То есть (X)(Y).

b) докажем обратное утверждение: если X(Y) влечёт (X)(Y) тогда (X) = H(X)X определяет оператор замыкания.

Для доказательства обратного утверждения, необходимо проверить выполнимость аксиом J. 1 – J. 3 оператора замыкания.

Для начала докажем вспомогательное утверждение о том, что YX* тогда и только тогда, когда XY*.

Доказательство:

∆ Докажем прямое утверждение.

Пусть YX*. Тогда, применив к нему свойство (7), получим Y*X**. По свойству (7) имеем включение XX**. Следовательно, получаем XX**Y* или XY*.

Докажем обратное утверждение.

Пусть XY*. Тогда X*Y**Y ▲

J. 1: пусть XY и Y(X), тогда по доказанному выше утверждению включение Y(X) равносильным образом можно заменить на X(Y). Получим, что XX(Y) или X(Y). Тогда по условию пункта b) задачи X(Y) влечёт (X)(Y). Следовательно, если XY, то (X)(Y).

J. 2: пусть XY и 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.

Пусть XAA, или XB (AA). Обозначим через J(X) пересечение всех предпорядков на A, содержащих X:

J(X) = {ρ – предпорядок на A: Xρ}.

Так как при пересечении бинарных отношений на множестве свойства рефлексивности и транзитивности сохраняются, то J(X) – наименьший предпорядок на A, содержащий X. Ясно, что AA является предпорядком на A. Поэтому система всех предпорядков на A является системой замыканий на этом множестве.

Остаётся проверить, будет ли система предпорядков алгебраической. Для этого возьмём произвольную пару (a, b)J(X), где XAA. Предпорядок J(X) получается из множества пар X добавлением пар вида (c, c), где cA, и его расширением по транзитивности: если уже получены пары (d, e) и (e, f), то добавляем и пару (d, f). При этом пара (a, b) в результате последовательного применения расширений по рефлексивности и транзитивности принадлежит конечному множеству пар FX. Следовательно, (a, b)J(F).

 Скачать реферат