Транзитивність

3. Транзитивність

Особливий інтерес представляють транзитивні простори залежності. Важливим результатом є доказ інваріантності розмірності будь-якого транзитивного простору залежності.

Доведемо деякі властивості, справедливі для транзитивних просторів залежності  Z .

Властивість 1:  залежить від .

Доказ:

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

По визначенню 8 будь-яка підмножина  залежить від  

Властивість 2: Якщо  залежить від , а  залежить від , те  залежить від .

Доказ:

Запишемо умову, використовуючи властивість 1 , а , тоді очевидно, що .

Властивість 3: Якщо X — мінімальна множина, що породжує, в A, те X - базис в A.

Доказ:

Нехай X — мінімальна множина, що породжує, в A. Покажемо, що воно не може бути залежним, тому що в цьому випадку його можна було б замінити власною підмножиною, що усе ще породжує A. Дійсно, у силу транзитивності відносини залежності, будь-яка множина, що породжує множина X, буде так само породжувати й множина A. Отже, X - незалежна множина, що породжує, що по визначенню 6 є базисом.

Властивість 4:  для кожного .

Доказ: Потрібне із властивості 3.

Властивість 5 (про заміну.) :

Якщо X — незалежна множина й Y — множина, що породжує, в A, то існує така  підмножина множини Y,  що  й - базис для A.

Доказ:

Розглянемо систему J таких незалежних підмножин Z множини A, що .

Тому що X незалежно, те такі множини існують; крім того, якщо — деяке лінійно впорядкована множина множин з J, те його об'єднання  знову належить J, оскільки Z задовольняє умові , і якщо Z залежне, те деяка кінцева підмножина множини Z повинне було б бути залежним; ця підмножина втримувалося б у деякій множині  в суперечності з тим фактом, що всі  незалежні.

По лемі Цорна J має максимальний елемент М; у силу максимальності кожний елемент множини Y або належить М, або залежить від М, звідки . Цим доведено, що М — базис в A. Тому що , те М має вигляд , де  задовольняє умовам .■

Визначення 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 . бачимо, що . Виходить, , одержали протиріччя з максимальністю . Отже, , зворотне включення очевидно, тому .

(iv) (ii) У силу теорем 1 і 3 і доведена еквівалентності

(i) (ii).■

Далі будемо розглядати транзитивний простір залежності  Z .

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

Потужність максимальної незалежної підмножини даної множини  називається рангом цієї множини: .

Будемо розглядати кінцеві підмножини .

Мають місце наступні властивості.

Властивість 1^о:  Z .

Доказ: Z .

Властивість 2^о: Z .

Доказ: Z, візьмемо , тоді по властивості 1^о і . Зворотне твердження потрібне з визначення 13.

Властивості 3^о – 7^о сформульовані для .

Властивість 3^о: .

Доказ: Ясно, що , і тому що число елементів будь-якої підмножини не більше числа елементів самої множини, то дана властивість виконується.

Властивість 4^о: .

Доказ: потрібне з того, що незалежна підмножина в  можна продовжити до максимальної незалежної підмножини в ;

Властивість 5^о: .

Доказ:

Нехай  Тоді  И потім . Маємо  .

Властивість 6^о: .

Доказ: випливає із властивості 4⁰;

Властивість 7^о: .

Доказ:

.