Курсовая работа: Вивчення поняття відносин залежності
Доказ:
Візьмемо порожню множину, вона незалежне. По властивості максимальності воно повинне втримуватися в деякій максимальній незалежній множині, що по теоремі 1 є базисом.
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
- транзитивний простір залежності. Тоді будь-які два базиси в цьому просторі рівно потужні.
Доказ:
Розглянемо спочатку випадок кінцеве мірного простору .