Вивчення поняття відносин залежності (стр. 6 из 8)
(iv) 
(ii) У силу теорем 1 і 3 і доведена еквівалентності
(i) (ii).■
Далі будемо розглядати транзитивний простір залежності 
Z 
.
Визначення 12.
Потужність максимальної незалежної підмножини даної множини 
називається рангом цієї множини: 
.
Будемо розглядати кінцеві підмножини
.Мають місце наступні властивості.
Властивість 1о: 
Z
.Доказ:
Z 
.Властивість 2о:
Z 
.Доказ: Z, візьмемо 
, тоді по властивості 1о
і 
. Зворотне твердження потрібне з визначення 13.Властивості 3о – 7о сформульовані для 
.
Властивість 3о:
.Доказ: Ясно, що
, і тому що число елементів будь-якої підмножини не більше числа елементів самої множини, то дана властивість виконується.Властивість 4о:
.Доказ: потрібне з того, що незалежна підмножина в
можна продовжити до максимальної незалежної підмножини в 
;Властивість 5о:
.Доказ:
Нехай
Тоді 
И потім 
. Маємо 
.Властивість 6о:
.Доказ: випливає із властивості 40;
Властивість 7о:
.Доказ:
.4. Зв'язок транзитивних відносин залежності з операторами замикання
Транзитивне відношення залежності також може бути описане за допомогою алгебраїчного оператора замикання деякого типу. Для початку сформулюємо визначення використовуваних понять.
Визначення 13.
Множина E підмножин множини A називається системою замикань, якщо 
E і система E замкнута щодо перетинань, тобто ∩D 
E для кожної непустої підмножини D 
E
Визначення 14.
Оператором замикання на множині A називається відображення J множини B (A) у себе, що володіє наступними властивостями:
J. 1. Якщо 
, то J(X) 
J(Y);
J. 2. X J(X);
J. 3. JJ(X) = J(X), для всіх X, Y 
B (A).
Визначення 15.
Оператор замикання J на множині A називається алгебраїчним, якщо для будь-яких 
і 
тягне 
для деякої кінцевої підмножини 
множини 
.
Визначення 16.
Система замикань називається алгебраїчної, якщо тільки відповідний оператор замикання є алгебраїчним
Слід зазначити теорему про взаємозв'язок між системами замикань і операторами замикань.
Теорема 5.
Кожна система замикань E на множині
визначає оператор замикання J на 
за правилом J(X) = ∩{Y 
E | Y 
X}. Обернено, кожний оператор замикання J на 
визначає систему замикань E 
J 
.Наступна теорема показує зв'язок транзитивного відношення залежності й алгебраїчного оператора замикання.
Теорема 6.
Для будь-якого транзитивного відношення залежності 
Z відображення 
є алгебраїчним оператором замикання на А із властивістю заміщення.
Обернено, будь-який алгебраїчний оператор замикання на А із властивістю заміщення виходить таким способом з деякого транзитивного відношення залежності Z на А.
Доказ:
Будемо називати підмножину Т множини A замкнутим, якщо 
.
Покажемо спочатку, що замкнуті підмножини утворять систему замикань. Якщо
, де 
- сімейство замкнутих множин, то нехай 
- така незалежна підмножина множини B, що 
залежно; оскільки 
для всіх 
, маємо 
, звідки 
, тобто В замкнуто.Нехай
, те по визначенню 3 
Z 
кінцеве, таке що 
залежно. У першому випадку 
, а в другому 
. І оскільки 
замкнуто в силу транзитивності, одержуємо алгебраїчний оператор замикання.