Вивчення поняття відносин залежності
Цей приклад показує, що існують не транзитивні простори залежності, у яких мінімальні множини, що породжують, незалежні, тобто є базисами.
Приклад 9.
Задамо на множині N натуральних чисел наступне відношення залежності:
Z
.
Одержуємо
нескінченну
строго зростаючий
ланцюжок оболонок
в
Z
. При
одержуємо
.
Таким чином,
маємо
.
Зауваження.
Поняття простору
залежності
можна й зручно
визначати через
базу залежності.
Саме, множина
B всіх мінімальних
залежних множин
простору залежності
Z
назвемо його
базою. Ясно,
що множини з
B не порожні,
кінцеві й не
втримуються
друг у другу.
Крім того, будь-яка
незалежна
множина містить
деяка множина
бази B. Простір
Z
має єдину базу
й однозначно
визначається
їй. Тому простору
залежності
можна задавати
базами.
Легко бачити, що вірно наступне твердження:
Непуста множина
B підмножин
множини
задає на
відношення
залежності
тоді й тільки
тоді, коли множини
з B не порожні,
кінцеві й не
включений друг
у друга.
У термінах бази B можна сформулювати умова транзитивності відповідного простору залежності.
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 є базисом.
3. Транзитивність
Особливий інтерес представляють транзитивні простори залежності. Важливим результатом є доказ інваріантності розмірності будь-якого транзитивного простору залежності.
Доведемо деякі
властивості,
справедливі
для транзитивних
просторів
залежності
Z
.
Властивість
1:
залежить від
.
Доказ:
![]()
залежить від
,
тобто
,
і
.
Розглянемо
,
тоді
![]()
![]()
- незалежно й
- залежно, а
,
одержуємо, що
,
тому
.
Маємо
.
По
визначенню
8 будь-яка підмножина
залежить від
Властивість
2: Якщо
залежить від
,
а
залежить від
,
те
залежить від
.
Доказ:
Запишемо умову,
використовуючи
властивість
1
,
а
,
тоді очевидно,
що
.
Властивість 3: Якщо X — мінімальна множина, що породжує, в A, те X - базис в A.
Доказ:
Нехай X — мінімальна множина, що породжує, в A. Покажемо, що воно не може бути залежним, тому що в цьому випадку його можна було б замінити власною підмножиною, що усе ще породжує A. Дійсно, у силу транзитивності відносини залежності, будь-яка множина, що породжує множина