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

Курсова робота

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

Зміст

Введення

1. Визначення й приклади

2. Простір залежності

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

4. Зв'язок транзитивних відносин залежності з операторами замикання

5. Матроїди

Висновок

Список літератури

Введення

 

Метою курсової роботи є вивчення поняття відносини залежності, розгляд відносини залежності на різних множинах.

Поставлена мета припускає рішення наступних задач:

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

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

Сформулювати й довести властивості й теореми як для довільних, так і для транзитивних просторів залежності.

Розглянути теорему про зв'язок транзитивного відношення залежності й алгебраїчного оператора замикання.

Вивчити поняття матроїда, привести приклади матроїдів.

Розглянути жадібний алгоритм і його зв'язок з матроїдами.

На підставі поставлених цілей і задач кваліфікаційна робота розбивається на 5 параграфів.

У першому параграфі наведені основні визначення й розглянуті деякі приклади відносини залежності.

У другому - розглядаються довільні простори залежності, їхньої властивості й деяких теорем.

Третій – присвячений транзитивним і кінцеве мірним просторам залежності. Тут розглянуті властивості транзитивних просторів залежності й доведені теореми, які підтверджують існування базису й інваріантність розмірності в будь-якому кінцеве мірному транзитивному просторі залежності.

У четвертому параграфі формулюються основні визначення дотичного оператора замикання й розглянута теорема про подання транзитивного відношення залежності за допомогою алгебраїчного оператора замикання.

П'ятий параграф присвячений матроїдам, прикладам матроїдів і їхньому застосуванню при вивченні теоретичною основою аналізу «жадібних» алгоритмів.

Основною літературою при написанні кваліфікаційної роботи стали монографії: Кона П. «Універсальна алгебра» [2] і Куроша О. Г. «Курс вищої алгебри» [3].

1. Визначення й приклади

 

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

Множина Z підмножин множини A назвемо відношенням залежності на A, якщо виконуються наступні аксіоми:

 

Z₁:  Z ;

Z₂:  Z  Z ;

Z₃:  Z ( Z - звичайно).

 

Підмножина множини A називається залежною, якщо вона належить Z, і незалежною у противному випадку.

Легко переконатися в незалежності аксіом Z₁ - Z₃..

Модель 1: . Думаємо Z = B (А) для будь-якої множини .

Модель 2: . Нехай Z =  при .

Модель 3: . Нехай Z =  для нескінченної множини .

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

Простором залежності назвемо пари  Z , де Z – відношення залежності на A.

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

Елемент  називається залежним від множини , якщо а Î X або існує така незалежна підмножина Y множини X, що  залежно, тобто  Z  Z ).

З визначення 1 випливає, що якщо елемент  залежить від множини , то він залежить від деякої кінцевої підмножини .

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

Множина всіх елементів, що залежать від X, називається оболонкою множини X і позначається через .

Ясно, що  й включення  тягне включення їхніх оболонок: .

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

Якщо  = A, то X називається множиною, що породжує, множини A.

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

 Незалежна підмножина, що породжує, множини A називається базисом множини A.

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

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

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

Відношення залежності Z на A будемо називати транзитивним відношенням залежності, якщо  .

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

 Транзитивним простором залежності назвемо простір залежності, у якому відношення залежності має властивість транзитивності.

Як теоретико-множинний постулат будемо використовувати наступний принцип, еквівалентний відомій аксіомі вибору.

Лема Цорна.

Непуста впорядкована множина, у якому кожне лінійно впорядкована підмножина має верхню грань, має максимальний елемент.

Далі доцільно розглянути деякі приклади відносини залежності:

Приклад 1.

Поняття лінійної залежності у векторному просторі V над полем . Система векторів векторного простору V називається лінійно залежної, якщо існує кінцева лінійно залежна її підсистема, у противному випадку – лінійно незалежної.

Поняття лінійної залежності в кінцеве мірних векторних просторах дається в курсі алгебри. Кінцева система векторів V називається лінійно залежної, якщо існують елементи поля  одночасно не рівні нулю й такі, що лінійна комбінація . Множина лінійних комбінацій множини  векторів векторного простору V з коефіцієнтами з поля P називається лінійною оболонкою цих векторів і позначається . При цьому  - є підпростором у просторі V, породженим . Одержуємо транзитивне відношення залежності.

Приклад 2.

Нехай поле  є розширенням основного поля Р, а  мінімальне підкольце утримуючі елементи  й поле Р. Підкольце  складається із всіх елементів поля, які виражаються через елементи  й елементи поля Р за допомогою додавання, вирахування й множення: це будуть усілякі багаточлени від  з коефіцієнтами з поля Р. Тоді, якщо для всякого елемента  існує єдиний запис у вигляді багаточлена від  як невідомих з коефіцієнтами з поля Р, тобто якщо різні багаточлени від  будуть різними елементами підкольца , те система елементів , буде називатися алгебраїчно незалежної над полем Р, у противному випадку алгебраїчно залежної. Довільна множина елементів поля Р називається залежним, якщо воно містить кінцеву залежну підмножину. У першому випадку кільце  ізоморфно кільцю багаточленів . Відношення алгебраїчної залежності над полем Р є транзитивним відношенням залежності.

Приклад 3.

Нехай на множині A задане рефлексивне й симетричне бінарне відношення  (називане відношенням подібності). Підмножина X множини A будемо вважати залежним, якщо воно містить два різних елементи, що перебувають у відношенні .

Оболонкою множини  служить множина

У цьому випадку можна підсилити аксіому  відносини залежності в такий спосіб:

 

 Z  Z.

 

 Тоді оболонкою множини  буде множина всіх елементів, що перебувають відносно подібності хоча б з одним елементом із множини .

Уведене відношення залежності буде транзитивним тоді й тільки тоді, коли відповідне бінарне відношення  буде транзитивне, тобто є відношенням еквівалентності на .

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

Приклад 4.

Розглянемо чотирьох елементну множину .

Назвемо підмножину  множини  залежним тоді й тільки тоді, коли  або .

 

Z .

 

Розглянемо підмножину  множини , по уведеному визначенню воно буде незалежно. Розглянемо оболонку множини   й знайдемо оболонку оболонки нашої множини . Таким чином, ми одержали, тобто розглянуте нами відношення залежності не є транзитивним.

Приклад 5.

Розглянемо довільну множину  й . Множина  будемо вважати залежним, якщо  B (А)\ B (В), тобто , але . Таким чином, одержали наступний транзитивний простір залежності:  B (А)\ B (В. Оболонкою  буде множина .

Зокрема можна розглянути 2 випадки:

, тобто всі множини незалежні, тоді  .

 B (А) , тобто всі множини, крім порожнього, будуть залежними, у цьому випадку  .

Приклад 6.

Розглянемо довільну множину  і його непусту кінцеву підмножину . Уведемо на множині А наступне відношення залежності

Z B (А) .

 

Таким чином, залежними будуть всі надмножини множини .

Якщо , то .

Якщо , то .

Якщо , то .

Одержуємо транзитивний простір залежності.

Приклад 7.

Підпростір простору залежності  Z . Розглянемо , де діє те ж відношення залежності Z. Тоді одержимо індукований простір залежності  Z  B . У цьому випадку залежними будуть тільки ті підмножини множини, які були залежні в просторі  Z . І якщо простір  Z транзитивне, те транзитивним буде й підпростір .

Приклад 8.

Нехай  і Z = . Такий простір залежності  Z не транзитивне, тому що  й . Простір А має два базиси  й, які є і єдиними мінімальними множинами, що породжують в.

Цей приклад показує, що існують не транзитивні простори залежності, у яких мінімальні множини, що породжують, незалежні, тобто є базисами.

Приклад 9.

Задамо на множині N натуральних чисел наступне відношення залежності:

Z .

 

Одержуємо нескінченну строго зростаючий ланцюжок оболонок в  Z . При  одержуємо

.

Таким чином, маємо .

Зауваження.

Поняття простору залежності можна й зручно визначати через базу залежності. Саме, множина B всіх мінімальних залежних множин простору залежності  Z назвемо його базою. Ясно, що множини з B не порожні, кінцеві й не втримуються друг у другу. Крім того, будь-яка незалежна множина містить деяка множина бази B. Простір  Z має єдину базу й однозначно визначається їй. Тому простору залежності можна задавати базами.

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

Непуста множина B підмножин множини  задає на  відношення залежності тоді й тільки тоді, коли множини з B не порожні, кінцеві й не включений друг у друга.

У термінах бази B можна сформулювати умова транзитивності відповідного простору залежності.