Xreferat.com » Рефераты по математике » Вивчення поняття відносин залежності

Вивчення поняття відносин залежності

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о: Вивчення поняття відносин залежності.

Доказ:

Нехай Вивчення поняття відносин залежності Тоді Вивчення поняття відносин залежності И потім Вивчення поняття відносин залежності. Маємо Вивчення поняття відносин залежності Вивчення поняття відносин
    <div class=

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: