86278 (612707), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Легко бачити, що вірно наступне твердження:

Непуста множина 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 виконуються наступні властивості:

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

Доказ:

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

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

Доказ:

Доведемо від противного. Припустимо, що залежно, тоді в ньому найдеться кінцева залежна підмножина : . Маємо , одержали протиріччя з незалежністю .

Максимальність. Будь-яка незалежна множина втримується в максимальній незалежній множині.

Доказ:

Нехай - довільна незалежна множина в. Утворимо множину Z : всіх незалежних множин, що містять . Відносно множина є впорядкованою множиною, що задовольняє по властивості вкладеності, умові леми Цорна. Тоді по лемі Цорна в існує максимальний елемент .

Теорема 2.

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

Доказ:

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

Доказ:

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

Нехай В, З — будь-які два базиси в А, їхнє існування забезпечується теоремою 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) маємо . Але - протиріччя.

Характеристики

Список файлов курсовой работы