Навигация
Зв'язок транзитивних відносин залежності з операторами замикання
26967
знаков
0
таблиц
0
изображений
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 
кінцеве, таке що
залежно. У першому випадку 
, а в другому 
. І оскільки 
замкнуто в силу транзитивності, одержуємо алгебраїчний оператор замикання.
Цим доведено, що замкнуті підмножини утворять алгебраїчну систему замикань.
Виконання властивості заміщення потрібне з відповідної властивості просторів залежності.
Обернено, нехай 
- алгебраїчний оператор замикання із властивістю заміщення.
Будемо вважати залежним, якщо 
для деякого 
, і незалежним у противному випадку.
Тому що оператор алгебраїчний, то звідси випливає, що всяка залежна множина має кінцеву залежну підмножину, і оскільки очевидно, що всяка множина, що містить залежну підмножину, саме залежно, у такий спосіб одержуємо відношення залежності. Умова транзитивності виконується по визначенню, і це показує, що ми маємо транзитивне відношення залежності.
Тепер для будь-яких , 
маємо 
тоді й тільки тоді, коли 
для деякої кінцевої підмножини 
множини . Вибираючи мінімальним, можемо припускати, що незалежно. Звідси випливає, що 
й, отже, 
.
Обернено, якщо , те знову 
для деякої кінцевої незалежної підмножини множини . Це означає, що залежно, тобто 
для якогось 
.
У силу властивості заміщення одержуємо, що й 
, тому 
.
Зауваження. Існують алгебраїчні оператори замикання, що не володіють властивістю заміщення. Для приклада візьмемо нескінченну циклічну напівгрупу 
.
Нехай 
і 
. Тоді 
, 
, але 
.
Похожие работы
ерел). Розділ 1. Соціологічні підходи до вивчення особистості та її місця в суспільстві 1.1 Зміст поняття «особистість» – соціологічне визначення Особистість як соціальна якість людини є предметом соціальних наук: філософії, соціології, психології та ін. Соціологія досліджує особистість як суб'єкт соціальних відносин, виділяючи в ній соціально-типові характеристики, які розвиваються ...
... тоді вони їй будуть заважати, а не допомагати. Отже, використання програм реабілітації сприяє усвідомленню дитиною необхідності позбавитися від хімічної залежності та скорішому одужанню, поверненню до нормального життя. 2.3 Психокорекційна робота Психологічна корекція базується на консультуванні і припускає цілеспрямований психологічний вплив на клієнта або пацієнта з метою приведення його ...
... полягає в конкретизації вивченого поняття завдяки виконанню вправ, які вимагають практичного застосування одержаних знань. 2. Перевірка ефективності формування комунікативно-мовленнєвих умінь молодших школярів 2.1 Відбір навчального матеріалу до вивчення частин мови в 3 класі Для формування загального поняття про частини мови у 3 класі навчальною програмою виділяється 4 години. При цьому ...
... які потребують впливу. У зв’язку з чим надається правова форма. Щодо процесуальних функцій правосуддя у цивільних справах, то вони не можуть існувати поза правовою формою. 2. Цивільні процесуальні правовідносини мають владний характер. Суд як орган правосуддя застосовує в межах процесуальних відносин норми права. Розпорядження суду є обов’язковими. Можна оскаржити судові рішення, але не можна ...
0 комментариев