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

Визначення 11.

Простір залежності

Z

називається кінцеве мірним, якщо будь-яке його незалежна множина кінцева.

Теорема 3.

Нехай

Z

- транзитивний простір залежності. Тоді будь-які два базиси в цьому просторі рівно потужні.

Доказ:

Розглянемо спочатку випадок кінцеве мірного простору

.

Нехай В, З — будь-які два базиси в А, їхнє існування забезпечується теоремою 2, і

, , , де різні елементи позначені різними буквами або постачені різними індексами. Застосуємо індукцію по max (r, s).

Якщо r = 0 або s = 0, то

або , і . Тому можна припускати, що r ≥ 1, s ≥ 1, без обмеження спільності будемо вважати, що r > s, так що насправді r > 1.

Припустимо, що базиси будуть рівне потужними для будь-якого t < r

По лемі про заміну множина

можна доповнити до базису D елементами базису З, скажемо

, t ≤ s < r.

Тепер перетинання D c У складається з n + 1 елемента, і D містить, крім того, ще t (< r) елементів, тоді як У містить, крім цього перетинання, ще r - 1 елементів, так що по припущенню індукції

, тобто .

Оскільки r > 1, звідси випливає, що t ≥ 1, і тому перетинання D із Із містить не менше ніж n+1 елементів. Використовуючи ще раз припущення індукції, знаходимо, що

й, отже, r = s і базиси В и С рівне потужні.

Далі, нехай В - кінцевий базис в.

Тоді й будь-який інший базис Із простору

буде кінцевим. Дійсно, У виражається через кінцеву множину елементів

у силу транзитивності буде що породжує й незалежною множиною в

, тобто .

Нарешті, якщо базиси В и С нескінченні. Кожний елемент із У залежить від деякої кінцевої підмножини базису З, і навпаки. Потужність множини всіх кінцевих підмножин усякої нескінченної множини дорівнює потужності самої множини. Тому потужності В и С збігаються.

Теорема 4.

Нехай

Z

- довільний простір залежності, тоді наступні умови еквівалентні

Z транзитивне;

для будь-якого кінцевого

;

кінцевих і Z

Z;

для будь-якого кінцевого

.

Доказ:

(i)

(ii) Справедливо по теоремі 3 і прикладу 7.

(ii)

(iii) Візьмемо

, так що - незалежно й . Допустимо, що твердження Z невірно. Тоді Z. Розглянемо . Маємо . Але Z, тому Z . По (ii) маємо . Але - протиріччя.

(iii)

(ii) Доведемо від противного. Нехай

. Можна вважати, що . Тоді по (iii) незалежно. Одержали протиріччя з максимальністю

(iii)

(i) Потрібно довести рівність

для довільного

.

Візьмемо

й покажемо, що Тому що , те Нехай існує , тоді незалежно й існує Z і Z . Розширюючи в можна припустити, що По (ii) , тобто . Тому по (iii) Z . бачимо, що . Виходить, . Одержуємо протиріччя з тим, що Отже, , те мережа .

Тепер досить показати, що

. Нехай , тоді залежно, розширюючи в можна припустити, що , крім того , тоді по (ii) . незалежно, тому . По (iii) Z . бачимо, що . Виходить, , одержали протиріччя з максимальністю . Отже, , зворотне включення очевидно, тому .