Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Елементи теорії множин II
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп'ютерна інженерія
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2003
Тип роботи:
Методичні вказівки
Предмет:
Дискретна математика
Частина тексту файла (без зображень, графіків і формул):
Міністерство Освіти і Науки України
Національний Університет “Львівська Політехніка”
Кафедра ЕОМ
Елементи теорії множин II
Методичні вказівки до практичних занять та самостійної роботи з курсу “Дискретна математика” для студентів базового напрямку 6.0915 “Комп’ютерна інженерія”
Затверджено на засіданні кафедри Електронних Обчислювальних Машин Протокол № 9 від 17 квітня 2003 року
Львів – 2003
Елементи теорії множин II : Методичні вказівки до практичних занять та самостійної роботи з курсу “Дискретна математика” для студентів базового напрямку 6.0915 “Комп’ютерна інженерія” / Укладачі: І. Мороз, Р. Попович – Львів: Національний університет “Львівська політехніка”, 2003, 13 с.
Укладачі: І. Мороз, старший викладач
Р. Попович, к.т.н., доцент
Відповідальний за випуск: Мельник А. О., професор, завідувач кафедри ЕОМ
Рецензенти: Ємець В. Ф., професор кафедри ЕОМ, д. фіз.-мат. н.
Юрчак І. Ю., доцент кафедри САПР, к. т. н.
Елементи теорії множин II
Відношення
Розглянемо декартовий добуток к-го степеня множини Х: Хк = Х ( Х ( ... ( Х. Довільну підмножину R множини Хк (R ( Хк) будемо називати к-арним відношенням, заданим на множині Х. Вважатимемо, що впорядковані елементи x1, x2, …, xn ( Х знаходяться між собою у відношенні R, коли (x1, x2, …, xn) ( R. Одномісні відношення, які ще називаються унітарними, відповідають підмножинам множини X. Надалі особливу увагу будемо приділяти бінарним відношенням (k = 2), які для стислості будемо називати просто відношеннями, якщо не обумовлено противного. Якщо на Х задано відношення R ( X 2, то запис x R х' означає, що x і х' знаходяться у відношенні R, тобто (x, х') ( R.
Областю визначення відношення R називаємо множину (R = {x | (( y : (x, y) ( R}, а областю значень - множину (R = {x | (( y : (y, x) ( R}. Для відношень звичайним чином визначені теоретико-множинні операції об’єднання, перетину і т.д. Доповненням відношення R ( X 2 вважаємо множину . Оберненим відношенням до відношення R називається відношення, задане множиною R-1 = {(x, y) | (y, x) ( R}. Образом множини Х відносно R називається множина R(Х) = {y | існує таке х ( Х, що (х, у) ( R} прообразом Х відносно R - множина R-1(Х) = {х | існує таке y ( Х, що (х, у) ( R}.
Розглянемо кілька прикладів найпростіших відношень:
1) на множині N відношення ( . Ясно, що впорядковані пари (3, 7) і (5, 5) належать цьому відношенню, а пара (4, 1) не належить;
2) на множині Р(Х) всіх підмножин множини Х = {1, 3, 5, 7, 9} відношення (. Пари підмножин ({1, 3}, {1, 3, 9}) і ({5, 7, 9}, {5, 7, 9}) належать цьому відношенню, а пара підмножин ({1, 5, 7}, {3, 5, 9}) не належить.
Кожному відношенню R на скінченній множині з n елементів X = {x1, x2, …, xn} можна поставити у відповідність матрицю А = (аij), i,j = де aij = 1, якщо xi R xj , і aij = 0 у протилежному випадку. Матриця А, яка складається з елементів 0 та 1, називається матрицею інцидентності відношення R.
Ця матриця однозначно задає відношення на скінченних множинах. Наприклад, - одинична матриця задає відношення рівності; - якщо в матриці на головній діагоналі знаходяться 0, а інші елементи рівні 1, то вона задає відношення нерівності. Якщо Х = {1, 2, 3, 4} і R – відношення (, то матриця інцидентності матиме вигляд
Відношення R на множині X називається:
1) рефлективним, якщо довільний елемент множини знаходиться у відношенні сам з собою, тобто для будь-якого х ( Х виконується х R х. Прикладами рефлективних відношень можуть бути ≤, ≥, = на множині натуральних чисел;
2) антирефлективним, якщо для будь-якого х ( Х пара (х, х) не належить до відношення R. Прикладами антирефлективних відношень можуть бути <, >, ≠ на множині раціональних чисел;
3) симетричним, якщо для довільних x, х' ( Х з того, що x R x випливає х' R x;
4) антисиметричним, якщо для довільних x, х' ( Х з того, що x R х' і х' R x, випливає x = х' (наприклад, ( на N, тому що з x ( х' і х' ( x випливає х' = x);
5) транзитивним, якщо для довільних x, х', х'' ( Х з того, що x R х' і х' R х'', випливає x R х'' (наприклад, відношення ( на множині Р(Х) чи відношення ( на множині N).
Наведемо деякі приклади відношень:
1) рефлективне, симетричне, не транзитивне
R = {(x, х') | x, х' ( R, | x - х' | ( 1};
2) рефлективне, антисиметричне, не транзитивне
R = {(x, х') | x, х' ( Z, x ( х' ( x2};
3) рефлективне, антисиметричне, транзитивне
R = {(x, х') | x, х' ( Q, x ( х'};
4) нерефлективне, антисиметричне, транзитивне
R = {(x, х') | x, х' ( R, x = х' = 0};
5) нерефлективне, симетричне, транзитивне
R = {(x, х') | x, х' ( R, x, х' > 0}.
Будь-якому відношенню R на множині Х можна поставити у відповідність відношення , що визначається так: x х' для x, х' ( X, якщо існують такі x1, x2, …, x( ( X, що x R x1, x1 R x2, ..., x( R x'. Відношення називається транзитивним замиканням відношення R. Якщо R транзитивне, то = R.
Розглянемо далі відношення, які мають особливе значення.
Відношення еквівалентності
Відношення R називається відношенням еквівалентності, якщо воно має наступні властивості:
а) рефлективності: (x, х) ( R при будь-якому х ( Х;
б) симетричності: з (x1, х2) ( R випливає (x2, х1) ( R;
в) транзитивності: якщо (x1, х2) ( R і (x2, х3) ( R, то (x1, х3) ( R;
Замість того, щоб писати (x1, х2) ( R, часто пишуть x1 ~ x2 або x1 ( x2(mod R) (читається так: x1 конгруентно x2 за модулем R) чи, простіше, (x1 ~ x2 або x1 ( x2, якщо немає необхідності ще раз вказувати, що мова йде про одне й те саме відношення R).
Приклади: 1) Беремо множину Z цілих чисел. Будуємо множину X = {(p, q) ( Z(Z | q ( 0} Відношення еквівалентності задаємо наступним чином: (p, q) ( (р', q') якщо рq' - р'q = 0.
2)(Визначимо на множині цілих чисел Z відношення еквівалентності так, що р(q, тоді і тільки тоді, коли p - q ділиться без остачі на деяке наперед задане число m. У теорії чисел таке відношення записується у вигляді р ( q(mod т).
3)(Нехай Х - множина прямих на площині. Визначимо відношення еквівалентності для прямих x1 і x2, покладаючи x1 ( x2, коли ці прямі паралельні чи співпадають.
4)(Х – множина всіх векторів на площині. Визначимо на X відношення еквівалентності ~, якщо ці вектори паралельні, однаково напрямлені й мають однакову довжину.
5)(У тій же множині Х (див.4) встановимо відношення еквівалентності ~, якщо і лежать на одній прямій, однаково напрямлені й мають однакову довжину.
6) Нехай Х – множина всіх студентів, які присутні на лекції з дискретної математики. Два студенти еквівалентні, якщо вони народилися в тому самому місяці року.
Відношення еквівалентності на множині Х породжує деяке розбиття цієї множини, блоки якого називаються класами еквівалентності. Будь-які два елементи з одного класу зв’язані відношенням еквівалентності, тобто еквівалентні; з різних класів - не еквівалентні.
Побудуємо розбиття множини Х, яке відповідає заданому відношенню еквівалентності на цій множині. Для x ( X позначимо через K(x) підмножину, що складається з елементів, еквівалентних x, тобто K(x) = {y | y ( X; y ~ x}.
Справедлива наступна теорема:
Теорема I. Два класи еквівалентності не перетинаються або співпадають.
Доведення. Припустимо, що перетин множин K(x) і K(х') непорожній, і візьмемо z ( K(x) ( K(х'). Клас еквівалентності K(x) утворений з елементів, еквівалентних одному зі своїх елементів x. Оскільки x і z еквівалентні, то за властивістю транзитивності отримуємо, що K(x) утворений також з елементів, еквівалентних z. Аналогічно K(х') утворений з елементів, еквівалентних z. Таким чином, K(х) і K(х') співпадають.
З наведеного доведення бачимо, що клас еквівалентності є множиною всіх елементів, еквівалентних довільному елементу з цього класу. Таким чином, клас еквівалентності визначає деяке розбиття множини Х, тобто деяку сім’ю непорожніх підмножин множини X, які попарно не перетинаються, а їх об’єднання рівне X. Якщо відомі ці підмножини, то відоме й відношення еквівалентності, бо х і х' еквівалентні тоді і тільки тоді, коли вони належать одному класу еквівалентності.
Навпаки, будь-яке розбиття множини X: Х =, де Xj непорожні і попарно не перетинаються, визначає деяке відношення еквівалентності, а саме x ( х', якщо існує такий індекс j ( J, що x ( Xj, х' ( Xj. У цьому випадку підмножини Xj є класами еквівалентності в цьому відношенні.
Зокрема, якщо відображення f : Х ( Y сюр’єктивне, то відношення x ~ y при f(x) = f(y) є відношенням еквівалентності на множині Х і підмножини f -1{z}, z ( Y, є класами еквівалентності.
Фактор-множина
Виходячи із сказаного кожен блок розбиття Xj є підмножиною множини X, що складається з елементів, еквівалентних деякому фіксованому елементу цієї підмножини. Тому можна розглянути і множину всіх класів еквівалентності, яку звичайно називають фактор-множиною за даним відношенням еквівалентності R і позначають наступним чином Х/R. Якщо через K(x) позначити клас еквівалентності елемента x, то K(x) є елементом фактор-множини та x ( K(x).
Відображення, що кожному елементу x ( X ставить у відповідність клас еквівалентності K(x), називається канонічною сюр’єкцією з X на X/R. Дійсно, вказане відображення є сюр’єктивним.
Навпаки, ми бачили раніше, що будь-яка сюр’єкція ( : X ( Y визначає деяке відношення еквівалентності R. Відображення, яке кожному z ( Y ставить у відповідність клас еквівалентності ( -1({z}) є бієкцією Y на X/R, що дозволяє розглядати Y як деяку "модель" фактор-множини X/R.
Можна дати просту інтерпретацію фактор-множини на прикладах відношень еквівалентності, наведених раніше (1, 2, 3, 4, 5):
1)°фактор-множина - це Q (раціональні числа), оскільки раціональне число звичайно визначається як сім’я пар (p, q), q ( 0, де при рq' - р'q = 0 дві пари (p, q) і (р', q') визначають те саме раціональне число;
2)°фактор- множина - це множина Zm цілих чисел, порівняних за модулем m;
3)°фактор- множина - це множина напрямлених прямих на площині;
4)°фактор- множина - це множина вільних векторів на площині. При цьому вільним вектором називається саме клас всіх еквівалентних векторів;
5)°фактор- множина - це множина “ковзних векторів” площини, які застосовуються в теоретичній механіці;
6)°фактор- множина - це множина місяців року. Вона може мати менше 12 місяців, бо в аудиторії може не виявитися студентів, які народилися в одному з місяців, скажімо в лютому.
Відношення порядку
(Бінарне) відношення R на множині Х називається відношенням порядку, якщо воно має властивості рефлективності, антисиметричності й транзитивності. Замість того, щоб писати (x, х') ( R, часто записують також х (R х' чи х ( х', якщо відношення порядку було зазначено заздалегідь і немає необхідності його повторювати. У цьому випадку х' ( x означає х ( х' і властивості рефлективності, транзитивності й антисиметричності запишуться відповідно у вигляді:
х ( х;
якщо х ( х' і х' ( х", то х ( х";
якщо х ( х' і х' ( х, то x = х'.
Розглянемо приклади відношень порядку:
1)°у множинах N натуральних чисел, Z цілих чисел, Q раціональних чисел відношення (x, х') ( R тоді і тільки тоді, коли х ( х', є відношенням порядку. Відношення (x, х') ( R тоді і тільки тоді, коли x ( х', також є відношенням порядку, яке протилежне до попереднього. Аналогічно можна розглядати відношення: х ( х', х < х', х' ( x, х' > x;
2)°у множині слів української мови існує відношення порядку, яке називається алфавітним, якщо домовитися ототожнювати омоніми;
3)°у множині Х = Р(Y) підмножин множини Y існує природне відношення порядку: А ( В, якщо А ( B;
4)°у множині Х = RY функцій, визначених на множині Y, з дійсними значеннями також існує природне відношення порядку: f ( g, якщо для кожного у ( Y виконується нерівність ((y( ( g(y). Зауважимо, що тут відношення f ( g означає, що яке б не було y, ((y( ( g(y) і хоча б для одного y, ((y( ( g(y). Вказане відношення зовсім не означає, що для кожного у виконується нерівність ((x( ( g(y);
5)°у множині N натуральних чисел існує наступне відношення порядку: a ( b, якщо a є дільником b;
6)°у довільній множині X відношення x ( х', якщо x = х', є відношенням порядку. Кажуть, що це - хаотичний порядок на X.
Множина Х з відношенням порядку ( називається повністю впорядкованою, якщо для будь-яких двох різних елементів x, х' з Х: або x ( х' або х' ( x. Інакше множина Х називається частково впорядкованою.
У розглянутих прикладах 1), 2) множина є повністю впорядкованою, а у прикладах 3) 6) – частково впорядкованою. У випадку, коли x і х' не задовольняють ніякому з двох зазначених співвідношень, кажуть, що вони не порівнянні. Так, у прикладі 3) - дві непорожні підмножини, що не перетинаються, не порівнянні; у прикладі 4) - не порівнянні постійні функції 0 і 10; у прикладі 5) - не порівнянні цілі числа 2 і 3; у прикладі 6) - два довільних різних елементи не порівнянні.
Нехай Х і Y - дві впорядкованих множини. Відображення ( : Х ( Y називається зростаючим, якщо з x ( x' випливає f(x) ( f(x'). Відображення ( : Х ( Y називається спадним, якщо з умови x ( x' випливає f(x') ( f(x).
Потужності. Кардинальні числа
Розглянемо відображення з N в N, яке кожному натуральному числу ставить у відповідність подвоєне число, тобто ізоморфізм γ(п) = 2п. Тоді можна сказати, що існує стільки парних натуральних чисел, скільки й натуральних, а також, що y випадку нескінченних множин може існувати бієктивне відображення деякої множини на її підмножину, яка відмінна від самої множини. Завдяки поняттю бієктивного відображення можна порівнювати між собою нескінченні множини.
Наведемо без доведення теорему.
Теорема 2 (Бернштейна). Нехай X та Y – дві довільні множини. Тоді 1) або існує ін’єкція X в Y, або існує ін’єкція Y в X (обидві обставини не виключають одна одну); 2) якщо існує одночасно ін’єкція X в Y та ін’єкція Y в X, то існує також бієкція X на Y.
Наслідок. Для заданих множин X та Y є тільки три можливості:
а) існує ін’єкція X в Y і не існує ін’єкція Y в X. В цьому випадку говорять, що Y має потужність строго більшу потужності X, або що X має потужність, строго меншу потужності Y;
б) існує ін’єкція Y в X і не існує ін’єкція X в Y. Тоді X має потужність строго більшу потужності Y або Y має потужність, строго меншу потужності X;
в) існує бієкція X в Y. У цьому випадку кажуть, що X і Y мають однакову потужність або рівнопотужні.
Якщо X рівнопотужна з Y, або її потужність строго менша, ніж Y, то кажуть, що X має потужність, меншу потужності Y.
Відношення ” X рівнопотужна Y “ є відношенням еквівалентності між множинами. Клас еквівалентності, тобто клас всіх множин рівнопотужних даній множині, називається потужністю або кардинальним числом. Скінченні кардинальні числа – це класи еквівалентності скінченних множин. Ці числа за визначенням є натуральними числами 0, 1, 2, ... . Слід відзначити, що ми приймаємо як первинне поняття натуральні числа, але їх строге математичне визначення досить складне. Як наслідок не легко apriori означити скінченні множини. Часто за визначенням вважають множину скінченною, якщо вона не рівнопотужна ніякій зі своїх підмножин, відмінних від самої множини, а потім доводять, що кардинальне число має властивості натуральних чисел. Нескінченне кардинальне число, тобто потужність нескінченної множини, називається трансфінітним кардинальним числом або трансфінітним числом.
У класі кардинальних чисел існує відношення такого порядку: якщо α є кардинальним числом якоїсь підмножини множини потужності β, то α ≤ β. Згідно з теоремою Бернштейна це відношення має властивість антисиметрії, а, значить, дійсно є деяким відношенням порядку. З цієї теореми випливає, що таке відношення порядку повне, тобто довільні два кардинальні числа можна порівняти. Якщо існує сюр’єкція ƒ : X → Y, то потужність Y менша потужності X. Дійсно, прообраз кожного елемента з Y не порожній, і якщо в кожному з цих прообразів ми виберемо по одному елементу, то отримаємо деяку підмножину множини X рівнопотужну Y. Наприклад, фактор-множина множини X за деяким відношенням еквівалентності має меншу потужність, ніж множина X. Не важко вибрати по одному елементу в кожній зі скінченого числа множин. Можливість такого вибору може бути введена як аксіома теорії множин – аксіома вибору або аксіома Цермело.
На множині кардинальних чисел можна визначити операції додавання, множення, піднесення до степеня так само, як і в множині натуральних чисел:
1) нехай α і β- два кардинальних числа, а X і Y - множини потужності відповідно α і β. Через α + β позначаємо потужність “суми” X і Y, тобто довільної множини, яка може бути утворена об’єднанням двох множин, рівнопотужних X і Y відповідно;
2) через α·β позначаємо потужність добутку X × Y. Це кардинальне число α об’єднань підмножин, що не перетинаються, і кожна з яких має потужність β;
3) через α β позначаємо потужність множини X Y всіх відображень з Y в X.
Теорема 3. Операції, визначені на множині кардинальних чисел, мають такі властивості:
1) асоціативність і комутативність додавання;
2) асоціативність і комутативність множення;
3) дистрибутивність множення відносно додавання;
4) (α β)∙(α γ) = α β + γ;
5) α γ∙β γ = (α∙β) γ;
6) (α β) γ = α β γ.
Властивості з теореми 3 створюють враження, що кардинальні числа (навіть транс-фінітні), мають усі властивості звичайних натуральних чисел. Проте теорема 4 показує, що це не так.
Теорема 4. Якщо α і β два кардинальних числа не дорівнюють 0 і якщо хоча б одне з них трансфінітне, то сума α + β і добуток α∙β дорівнюють більшому з них. Таким чином, можна зробити висновок, що для кардинальних нескінченних чисел визначити віднімання неможливо бо серед чисел, додавання яких до α дає α, фігурує не тільки 0, а й довільне скінчене число, і навіть α.
Теорема 5. Якою б не була множина X, множина її підмножин має потужність, строго більшу потужності X.
Неважко довести, що коли card X = α, то card P(X) = 2 α і для довільних α завжди 2 α > α. (наприклад, n ≥ 0, 2 n > n).
Перейдемо до двох найбільш важливих трансфінітних потужностей: потужності зчислених множини ν і потужності континууму γ.
Потужність зчисленних множин
Потужністю зчисленної множини ν називається потужність множини натуральних чисел N. Довільна множина, рівнопотужна N, називається зчисленною. Множина зчисленна, якщо існує хоча б одна бієкція цієї множини в множину N.
Теорема 6. ν - найменше трансфінітне кардинальне число.
Це означає, що довільна нескінченна множина X містить хоча б одну зчисленну підмножину.
Теорема 7. Для довільного скінченого числа т ≥ 1 виконуються рівності т∙ν = ν і ν т = ν. Результат випливає безпосередньо з теореми 5, згідно з якою т∙ν = ν при т ≤ ν і ν 2 = ν∙ν = ν, а це означає за індукцією ν т = ν.
Теорему 4 ми прийняли без доведення. Але рівність ν 2 = ν∙ν = ν, з якої випливає теорема 7, можна легко довести. Покажемо, що N ( N рівнопотужна N. Дійсно зі схеми, наведеної нижче
ми бачимо, що відображення , тобто f : N ( N → N є бієкцією.
На основі викладеного можна зробити такі висновки:
1) об’єднання скінченної або зчисленої множини скінченних чи зчислених підмножин множини X є скінченною або зчисленною множиною. Дійсно, нехай J - деяка підмножина N і підмножини A j, j ( J деякої множини X всі непорожні. Нехай f j : N → A j сюр’єкція. Тоді (j, п) → f j(n) буде сюр’єкцією J ( N → . Оскільки J ( N зчисленна, то скінченна або зчисленна;
2) множина Z всіх цілих чисел зчисленна (як об’єднання двох зчисленних множин). Множина Q раціональних чисел зчисленна. Дійсно відображення, яке ставить кожній парі (p, q), q ≠ 0 множини Z ( Z у відповідність раціональне число p / q, є сюр’єкцією підмножини Z ( Z на Q. Це означає, що Q не більш, ніж зчисленна, але так як вона містить N, то Q зчисленна;
3) множина алгебраїчних дійсних чисел зчислена. Алгебраїчним дійсним числом називають дійсний корінь деякого тотожньо не рівного нулю полінома з цілими коефіцієнтами. Оскільки тотожньо не рівний нулю поліном степеня ≤ m з цілими коефіцієнтами має т + 1 коефіцієнтів, які є довільними цілими числами і не всі дорівнюють нулю, то потужність множини цих поліномів дорівнює ν т + 1 = ν. Кожен такий поліном має не більше т алгебраїчних дійсних коренів, а значить, множину коренів поліномів степені ≤ т можна розглядати як об’єднання зчисленної множини скінченних множин. Така множина не більш ніж зчисленна, а так як вона нескінченна, то вона зчисленна. Так як т приймає всі значення, то множина всіх алгебраїчних чисел отримується як об’єднання зчисленного числа зчисленних множин, а значить є зчисленною множиною;
4) множина всіх точок простору R n з раціональними чи алгебраїчними координатами зчисленна, так як її кардинальне число дорівнює ν п = ν.
Потужність континууму
Теорема 8. Множина всіх дійсних чисел не є зчисленною.
Дійсно, доведемо, що навіть множина X = [0, 1] дійсних чисел, які задовольняють нерівність 0 ≤ x ≤ 1, не є зчисленною.
Доведення проведемо від протилежного. Припустимо, що X зчисленна й існує деяка бієкція N на Х, тобто елементи X можуть бути записані y вигляді деякої послідовності x1, x2, x3, …, елементи якої попарно різні. Крім того, розглянемо дійсне число ξ, яке визначимо так: перед комою поставимо 0, потім як j-й десятковий знак виберемо довільне ціле число між 1 і 8, яке відрізняється від j-го десяткового знака числа хj. Таким способом ми утворюємо нескінченний дріб, що визначає деяке число ξ. Для довільного натурального j маємо таке. Оскільки j-й десятковий знак числа ξ відрізняється від j-го десяткового знака числа хj і всі десяткові знаки числа ξ відрізняються від 0 і 9, то ξ ≠ хj (не допускаємо знаків 0 і 9, бо 0,102000... і 0,101999... одне і те ж саме число). Значить число ξ не збігається ні з одним з чисел послідовності x1, x2, x3, … Ми отримали суперечність. Це й доводить теорему.
Дійсні числа які не є алгебраїчними, називають трансцендентними. Так як множина алгебраїчних чисел зчисленна, а множина дійсних – незчисленна, то існують трансцендентні числа і навіть “більшість” дійсних чисел трансцендентні. Але не просто точно вказати трансцендентні числа. Можна, наприклад, довести (але це не очевидно), що числа е і π трансцендентні.
Будемо позначати через γ потужність множини X = [0, 1] і називати її потужністю континууму. Потужність континууму - це потужність множини дійсних чисел, оскільки є бієкцією ]0, 1[ на R.
Теорема 9. Мають місце рівності т∙γ = ν∙γ = γ∙γ = γ т = γν = γ, де т – довільне натуральне число.
Доведення просте. Всі кардинальні числа менші чи рівні γν і більші чи рівні γ, тому достатньо довести, що γν = γ. Легко переконатися, що γν = (2ν)ν = 2ν∙ν = 2ν = γ.
Зі сказаного випливає:
1) множина комплексних чисел має потужність континууму;
2) довільний векторний простір скінченого числа вимірів над полем дійсних чи комплексних чисел має потужність континууму. Дійсно, зафіксувавши базу, легко визначити бієкцію такого простору на R n, який має, згідно рівності γ n = γ, потужність континууму. Звідси випливає парадоксальний наслідок про існування бієкції R на площину R 2, так як множини R і R 2 рівнопотужні;
3) множини всіх послідовностей дійсних чисел і послідовностей комплексних чисел мають потужність континууму, так як їх кардинальне число дорівнює γ ν = γ.
4) множина X неперервних дійсних функцій дійсної змінної має потужність континууму;
5) множина всіх дійсних функцій дійсної змінної або навіть множина всіх функцій, що приймають тільки значення 0 і 1, має потужність, строго більшу за потужність континууму, тому що їх потужності рівні відповідно γγ і 2γ, а γγ = (2γ)γ =2γ γ = 2γ > γ.
З пп. 4, 5 випливає, що “більшість” функцій має не менше однієї точки розриву.
На завершення сформулюємо континуум-гіпотезу. Згідно цієї гіпотези, 2ν є кардинальним числом, яке іде одразу за ν. У загальному випадку узагальнена континуум-гіпотеза полягає в припущенні, що при довільному кардинальному числі α кардинальне число 2α іде безпосередньо за α. Доведено (П. Коен, 1968 р.), що континуум-гіпотеза не має рішення – її не можливо ані довести, ані спростувати, можна тільки прийняти її або протилежне їй твердження як аксіому.
Приклади розв’язання задач
1. Задано відношення R ( X ( X, X = N, (x, y) ( R, якщо x 2 – y 2 ділиться на 2. Дослідити відношення на рефлективність, антирефлективність, симетричність, антисиметричність, транзитивність.
Розв’язування: Очевидно, що відношення є рефлективним, бо для довільних x вираз x 2 x 2 завжди рівний нулю, а отже ділиться на 2. Оскільки R є рефлективне, то воно не може бути антирефлективним.
При аналізі на симетричність припустимо, що (x, y) ( R, і нехай (x 2 – y 2) / 2 = z. Тоді для (y, x), (y 2 – x 2) / 2 = -z, отже і (y, x) ( R. Звідси робимо висновок, що відношення R є симетричним, а отже воно не буде антисиметричним.
З умови належності пари (x, y) відношенню R випливає, що x та y повинні одночасно бути або парними або непарними числами. Для того, щоб (y, z) ( R, необхідно, щоб число z також було або парним або непарним одночасно з числом y, а, отже, і з числом x. Тому умова транзитивності (x R y і y R z ( x R z) виконується.
Так як, досліджене відношення R є рефлективним, симетричним та транзитивним, то це - відношення еквівалентності.
2. Знайти (R, (R, R-1, R○R, R○R-1, R-1○R, для відношення R = {(x, y)| x, y ( N i x ділить у}.
Розв’язування. Будемо вважати, що нуль ділить нуль. Наступні множини (R, (R та N співпадають ((R = (R = N), оскільки (х, х) ( R. Множина R-1 = {(x, y)| x, y ( N i y ділить x}. Композиція R○R = R, а R○R-1 = N2, тому що (х, у) ( R○R-1 це твердження, що існує z таке, що x ділить z i у ділить z. Але таке z легко знайти за довільними х та у. Треба взяти, наприклад, z = x(y. Множина R-1○R = N2, тому що (х, у) ( R-1○R це твердження, що існує z таке, що z ділить x і z ділить y. Треба взяти z = 1 для довільних x та y.
3. Довести, що для будь-яких бінарних відношень виконується рівність (R1 ( R2) 1 = R1 1 ( R2 1.
Розв’язування: (x, y) ( (R1 ( R2) 1 ( (x, y) ( (R1 ( R2) ( (x, y) ( R1 або (x, y) ( R2 ( (x, y) ( R1 1 або (x, y) ( R2 1 ( (x, y) ( R1 1 ( R2 1.
4. Оцінити потужність множини всіх можливих відображень множини натуральних чисел в множину цілих чисел (тобто N ( Z).
Розв’язування: Так як існує бієктивне відображення N ( Z, то задачу можна звести до оцінки всіх можливих відображень N ( N. Потужність множини всіх можливих відображень N ( N рівна νν, де ν –потужність зчисленної множини.
Література
1. Дискретна математика: Підручник / Ю. М. Бардачов, Н. А. Соколова, В. Є. Ходаков; за ред. В. Є. Ходакова. – К.: Вища школа, 2002. – 287 с.
2. Основи дискретної математики: Підручник / Ю. В. Капітонова, С. Л. Кривий, О. А. Летичевський, Г. М. Луцький, М. К. Печурін. – К.: Наукова думка, 2002. – 568с.
3. Луцький Г. М., Кривий С. Л., Печорін М. К. Основи дискретної математики. – К.: ВІПОЛ, 1995. – 252 с.
4. Бородін О. I., Потьомкін Л. В., Сліпенько А. К. Основні поняття сучасної алгебри. – К.: Вища школа, 1993. –112 с.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора