Вивчення поняття відносин залежності
Властивість
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о:
.
Доказ:
Нехай
Тоді
И потім
.
Маємо