Навигация
2. Простір залежності
Теорема 1.
Нехай 
Z
- довільний простір залежності. Розглянемо наступні три твердження:
X — базис в A;
X — максимальна незалежна підмножина в A;
X — мінімальна множина, що породжує, в A.
Тоді 
й 
.
Доказ:
(i) 
(ii) Якщо X – базис, то по визначенню 6 X – незалежна підмножина, що породжує. Доведемо від противного, що воно максимальне. Нехай існують незалежні множини 
. Візьмемо 
, тоді 
незалежно, тому що будь-яка підмножина незалежної множини незалежно. Тому по визначеннях 3 і 5 
, звідки 
, одержали протиріччя з умовою. Тому X є максимальною незалежною підмножиною в A.
(ii) (i) Доведемо від противного, нехай 
не базис в 
, тобто . Тоді 
таке, що 
незалежно й лежить в , одержали протиріччя з максимальністю .
(ii) (iii) Якщо X — максимальна незалежна множина в A, те всякий елемент в
A або належить X, або такий, що 
залежно, а тому 
в тім і іншому випадку, тобто 
Оскільки 
, те X - множина, що породжує. Виходить, - базис простору .
Доведемо тепер, що воно мінімально. Нехай множина 
. Доведемо, що воно не є породжує для A. Візьмемо 
, але 
. Тоді 
незалежно, як підмножина множини X. Тому по визначеннях 3 і 5 
і 
, а це значить, що Y не є множиною, що породжує. Висновок: X – мінімальна множина, що породжує, в A.
(i) (iii) Справедливо, по доведеним вище твердженнях (i) (ii) і (ii) (iii). :
Визначення - позначення 10.
Для довільної множини простору залежності Z позначимо 
множину всіх максимальних незалежних підмножин, а через 
- множину всіх мінімальних підмножин, що породжують, цієї множини.
З теореми 1 випливає, що 
збігається із множиною всіляких базисів простору й 
для кожного 
.
Наступний приклад показує, що зворотне включення 
вірно не завжди.
Приклад 10.
Розглянемо дев'яти елементну множину 
, що записана у вигляді матриці 
. Залежними будемо вважати підмножини множини , що містять «прямі лінії»: стовпці, рядки або діагоналі матриці 
.
Розглянемо множини 
й 
, вони буде максимальними незалежними, тому що не містять прямих і при додаванні будь-якого елемента з , що не лежить у них, стають залежними. Тут максимальні незалежні множини містять різна кількість елементів.
Розглянемо ще одну множину 
, вона є мінімальним що породжує, тому що якщо виключити з нього хоча б один елемент, то воно вже не буде множиною, що породжує. Легко помітити, що залежно, тому не є базисом. Даний приклад ілюструє, що (iii)
(i) не вірно в загальному випадку, тобто для довільних просторів залежності.
Для будь-якого простору залежності Z виконуються наступні властивості:
Заміщення. Якщо 
Доказ:
Нехай 
, 
. Тому що 
залежить від 
, те залежить від незалежної підмножини 
множини , тобто 
залежно. Тепер, якби 
, те було б підмножиною множини й тому 
, що суперечило б нашому припущенню. Тому 
. Візьмемо 
. Тоді 
незалежно, тому що 
. Але 
залежно. Звідки 
.
Вкладеність. Об'єднання будь-якої системи вкладених друг у друга незалежних множин є незалежною множиною, тобто 
- незалежно, де 
також незалежні й 
Доказ:
Доведемо від противного. Припустимо, що залежно, тоді в ньому найдеться кінцева залежна підмножина 
:
. Маємо 
, одержали протиріччя з незалежністю 
.
Максимальність. Будь-яка незалежна множина втримується в максимальній незалежній множині.
Доказ:
Нехай - довільна незалежна множина в. Утворимо множину 
Z :
всіх незалежних множин, що містять . Відносно 
множина 
є впорядкованою множиною, що задовольняє по властивості вкладеності, умові леми Цорна. Тоді по лемі Цорна в існує максимальний елемент 
.
Теорема 2.
Будь-який простір залежності має базис.
Доказ:
Візьмемо порожню множину, вона незалежне. По властивості максимальності воно повинне втримуватися в деякій максимальній незалежній множині, що по теоремі 1 є базисом.
Похожие работы
ерел). Розділ 1. Соціологічні підходи до вивчення особистості та її місця в суспільстві 1.1 Зміст поняття «особистість» – соціологічне визначення Особистість як соціальна якість людини є предметом соціальних наук: філософії, соціології, психології та ін. Соціологія досліджує особистість як суб'єкт соціальних відносин, виділяючи в ній соціально-типові характеристики, які розвиваються ...
... тоді вони їй будуть заважати, а не допомагати. Отже, використання програм реабілітації сприяє усвідомленню дитиною необхідності позбавитися від хімічної залежності та скорішому одужанню, поверненню до нормального життя. 2.3 Психокорекційна робота Психологічна корекція базується на консультуванні і припускає цілеспрямований психологічний вплив на клієнта або пацієнта з метою приведення його ...
... полягає в конкретизації вивченого поняття завдяки виконанню вправ, які вимагають практичного застосування одержаних знань. 2. Перевірка ефективності формування комунікативно-мовленнєвих умінь молодших школярів 2.1 Відбір навчального матеріалу до вивчення частин мови в 3 класі Для формування загального поняття про частини мови у 3 класі навчальною програмою виділяється 4 години. При цьому ...
... які потребують впливу. У зв’язку з чим надається правова форма. Щодо процесуальних функцій правосуддя у цивільних справах, то вони не можуть існувати поза правовою формою. 2. Цивільні процесуальні правовідносини мають владний характер. Суд як орган правосуддя застосовує в межах процесуальних відносин норми права. Розпорядження суду є обов’язковими. Можна оскаржити судові рішення, але не можна ...
0 комментариев