Вивчення поняття відносин залежності (стр. 3 из 8)

Цей приклад показує, що існують не транзитивні простори залежності, у яких мінімальні множини, що породжують, незалежні, тобто є базисами.

Приклад 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

виконуються наступні властивості:

Заміщення. Якщо

Доказ:

Нехай

, . Тому що залежить від , те залежить від незалежної підмножини множини , тобто залежно. Тепер, якби , те було б підмножиною множини й тому , що суперечило б нашому припущенню. Тому . Візьмемо . Тоді незалежно, тому що . Але залежно. Звідки .