Множини і відношення

Тоді (2,3.75,-4)<(2.1, 24,0), але кортежі (1,4,-1.7 ) і (2,2,4) непорівнювані.

Аналогічно може бути введено частковий порядок на множинах Nⁿ, Zⁿ і Qⁿ.

5. Зафіксуємо строгий порядок розташування символів у довільному скінченному алфавіті A={a₁,a₂,...,a_n}, наприклад, покладемо, що a₁<a₂<...<a_n. Тоді природним чином означається так званий лексикографічний порядок на множині A всіх слів довжини m в алфавіті A. А саме, вважаємо a_i1a_i2... a_in < a_j1a_j2...a_jn тоді і тільки тоді, коли a_is = a_js при s=1,2,...,k-1 і a_ik < a_jk для певного k.

Лексикографічний порядок можна поширити на множину A всіх слів в алфавіті A, якщо доповнити алфавіт A додатковим ("порожнім") символом b і вважати, що b<a_i, i=1,2,...,n. При порівнюванні двох слів різної довжини спочатку слово меншої довжини доповнюється справа такою кількістю "порожніх" символів b, щоб зрівнятися по довжині з другим словом, після чого обидва слова порівнюються за правилом порівнювання слів однакової довжини.

Нехай A = {a,b,c} і a<b<c, тоді aac<aba, abbc<abcb, ab<abab, b<cba тощо.

Лексикографічний порядок лежить в основі впорядкування всіх словників, енциклопедій, індексів (предметних або іменних покажчиків), довідників, списків, таблиць тощо.

6. В множині N натуральних чисел відношення "ділить" є відношенням часткового порядку. Маємо 4 28, 11 132, 5 5, 1 n для будь-якого nN. Пари 7 і 22, 13 і 35 непорівнювані.

Нехай M частково впорядкована множина і A деяка непорожня підмножина множини M. Верхньою гранню підмножини AM в множині M називається елемент bM такий, що ab всіх aA. Елемент b називається найбільшим елементом множини M, якщо b - верхня грань множини M.

Відповідно, елемент c частково впорядкованої множини M називається нижньою гранню підмножини AM, якщо ca для будь-якого aA. Елемент c - найменший в множині M, якщо c - нижня грань самої множини M.

Таким чином, вважається, що найбільший і найменший елементи, а також верхня та нижня грані (якщо вони існують), є порівнюваними з усіма елементами даної множини M або підмножини A відповідно.

Елемент xM називається максимальним в множині M, якщо не існує елемента aM такого, що x<a. Відповідно, елемент nM називається мінімальним у множині M, якщо не існує елемента aM такого, що a<n. Очевидно, якщо в частково впорядованій множині M існує найбільший елемент, то він же є єдиним максимальним елементом множини M. Аналогічно, найменший елемент множини M - єдиний мінімальний елемент даної множини. Зауважимо також, що частково впорядкована множина M може не мати найбільшого (найменшого) елемента і в той же час мати один або декілька максимальних (мінімальних) елементів. У лінійно впорядкованій множині поняття найбільшого і максимального (найменшого і мінімального) елементів збігаються.

Приклад 1.18. 1. У множині Z цілих чисел множина N натуральних чисел має найменший елемент (число 1) і не має найбільшого елемента.

2. У довільній множині M з тривіальним порядком i_M (відношенням рівності) кожен елемент aM є одночасно максимальним і мінімальним елементом. Найбільший і найменший елементи в множині M відсутні.

3. Булеан (A) множини A з відношенням часткового порядку містить найменший елемент - порожню множину і найбільший елемент - саму множину A. У множині D всіх непорожніх підмножин множини A (тобто в множині (A)\{}) не існує найменшого елемента, але всі одноелементні множини {a}, aA є мінімальними елементами множини D.

4. У множині N натуральних чисел, частково впорядкованій за відношенням "ділить", число 1 є найменшим елементом, а найбільшого елемента не існує. Якщо ж множину N доповнити числом 0, тобто розглянути множину невід'ємних цілих чисел із відношенням часткового порядку "ділить", то окрім найменшого елемента (як і раніше, число 1) з'являється найбільший елемент - число 0.

Лінійно впорядкована множина (ланцюг) M називається цілком впорядкованою множиною, якщо кожна непорожня підмножина AM має найменший елемент.

Зокрема, множина N натуральних чисел з традиційним відношенням порядку є цілком впорядкованою, а множина Z цілих чисел - не є цілком впорядкованою, оскільки будь-яка її нескінченна підмножина від'ємних чисел не має найменшого елемента.

Якщо M - частково впорядкована множина, то множина L всіх її ланцюгів (тобто лінійно впорядкованих підмножин множини M) є також частково впорядкованою за відношенням теоретико-множинного включення. Максимальні елементи множини L називають максимальними ланцюгами множини M.

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

Теорема Куратовського-Цорна або лема Цорна. Якщо в частково впорядкованій множині M будь-який ланцюг має верхню (нижню) грань, то множина M має максимальний (мінімальний) елемент.

Теорема Хаусдорфа. Будь-який ланцюг частково впорядкованої множини M міститься в деякому максимальному ланцюзі множини M.

Теорема Цермело. Будь-яку множину M можна цілком впорядкувати.

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

Аксіома вибору. Якщо дано множину M, то існує функція w:( (M)\{}) M, яка кожній непорожній підмножині AM ставить у відповідність певний елемент a = w(A) цієї підмножини, aA.

Iнакше кажучи, функція w обирає по одному елементу з непорожніх підмножин множини M.

Зокрема, аксіомою вибору ми неявно користувались при доведенні теореми 1.2.

Будь-яке твердження T відносно елементів деякої цілком впорядкованої множини M можна доводити, використовуючи так звану трансфінітну індукцію, яка є узагальненням відомого методу математичної індукції.

База індукції. Доводимо справедливість твердження T для найменшого елемента множини M.

Iндукційний крок. Робимо припущення, що твердження T виконується для будь-якого елемента a такого, що a<b і доводимо справедливість твердження T для елемента b.

Якщо виконуються умови бази і індукційного кроку, то твердження T справедливе для довільного елемента aM.

Припустімо, що це не так. Нехай в множині M існують елементи, для яких не виконується твердження T і KM - сукупність усіх таких елементів. Множина M цілком впорядкована, отже K має найменший елемент bK. Зі справедливості умови бази індукції випливає, що b не є найменшим елементом у множині M. Це означає, що в множині M існують елементи a<b і для всіх таких елементів a виконується твердження T. Згідно з індукційним кроком твердження T повинно виконуватись і для елемента b, що призводить до суперечності.

14. Решітки

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

Точною верхньою гранню підмножини A частково впорядкованої множини M (позначається supA) називають найменшу з верхніх граней підмножини A. Відповідно, точною нижньою гранню підмножини A частково впорядкованої множини M (позначається infA) називають найбільшу з нижніх граней підмножини A.

Частково впорядкована множина M називається решіткою (структурою), якщо для будь-якої пари елементів a,bM (тобто для будь-якої двоелементної підмножини множини M ) існують sup{a,b} і inf{a,b}.

Приклад 1.19. 1. Будь-яка лінійно впорядкована множина M (наприклад, числові множини N, Z, Q і R з традиційними відношеннями порядку) є решіткою. Якщо a,bM, то sup{a,b} = max(a,b) і inf{a,b} = min(a,b).

2. Розглянемо множину N натуральних чисел з відношенням часткового порядку "ділить". Для a,bN означимо sup{a,b} = НСК(a,b) і inf{a,b) = НСД(a,b) (НСК - найменше спільне кратне, НСД - найбільший спільний дільник). Тоді sup{12,32 }=96, inf{12,32}= 4, inf{16,27}=1.

3. Частково впорядкована за відношенням включення множина (M) всіх підмножин множини M є решіткою: sup{A,B}=AB і inf{A,B}= AB, A,BM.

4. Розглянемо множину R кортежів дійсних чисел довжини n з відношенням часткового порядку, означеним у прикладі 1.17(4), тобто (a₁,a₂,...,a_n)(b₁,b₂,...,b_n) тоді і тільки тоді, коли a_ib_i, i=1,2,...n. Частково впорядкована у такий спосіб множина R є решіткою:

sup{( a₁,a₂,...,a_n),( b₁,b₂,...,b_n)} = (c₁,c₂,...,c_n),

де c_i = max(a_i,b_i ), i=1,2,...n,

inf{( a₁,a₂,...,a_n),( b₁,b₂,...,b_n)} = (d₁,d₂,...,d_n),

де d_i = min(a_i,b_i ), i=1,2,...,n.

Аналогічно можуть бути перетворені на решітки множини кортежів Nⁿ, Zⁿ, Qⁿ і Bⁿ, де B = {0,1 } - множина двійкових цифр.

Множина P = {R₁,R₂,...,R_m} всіх можливих розбиттів деякої скінченної множини M може бути перетворена в решітку в такий спосіб. Вважаємо, що розбиття R_i={A_i1,A_i2,..., A_ik} і R_j={A_j1,A_j2,...,A_jk} знаходиться у відношенні R_i < R_j, якщо кожен клас A_it, t=1,2,...,k розбиття R_i міститься в деякому класі A_jt розбиття R_j. Наприклад, для M ={1,2,3,4,5} розбиття R'={{1,2},{3},{4,5}} менше розбиття R''={{1,2,3},{4,5}} і менше розбиття R'''={{1,2},{3,4,5}}, а розбиття R'' і R''' непорівнювані.

Мінімальним елементом частково впорядкованої множини P є розбиття { {a} | aM}, а максимальним елементом - {M}. Тоді sup{R_i,R_j} = R_k, де R_k - розбиття, в якому елементи a,bM входять в один клас тоді і тільки тоді, коли існує такий cM, що кожна з пар елементів a і c та c і b належить одному класу або в R_i, або в R_j ; inf{R_i,R_j} = R_l, де R_l - розбиття, в якому елементи a,bM належать одному класу тоді і тільки тоді, коли вони належать одному класу і в R_i, і в R_j.

Наприклад,

sup{R'',R'''} = {{1,2,3,4,5}}, sup{R',R''} = {{1,2,3},{4, 5}},

inf{R'',R'''} = {{1,2},{3},{4,5}}, inf{R',R''} = {{1,2},{3},{4,5}}.

Оскільки за теоремою 1.10 існує взаємно одозначна відповідність між усіма розбиттями даної множини M і всіма відношеннями еквівалентності на M, то множина всіх відношень еквівалентності на M може бути перетворена в решітку.

Скінченну частково впорядковану множину M зручно зображати у вигляді діаграми або структурного графа, вершини якого відповідають елементам множини M. З вершини a проводимо стрілку у вершину b, якщо a b і не існує такого c, що a c і c b. Стрілки (петлі), що відповідають діагональним парам (a,a) не проводимо.

Приклад 1.20. 1. На рис.1.6 зображено діаграми для чотирьох частково впорядкованих множин:

а) множини двійкових кортежів B³;

б) булеана (M) множини M = {a,b,c} з відношенням включення ;

в) множини натуральних чисел C={2,5,7,10,28,70} з відношенням "ділить";

г) множини D={a,b,c,d} з відношенням часткового порядку R={(a,a),(b,b),(c,c), (d,d),(a,c),(b,c),(a,d), (b,d)}.

2. Діаграма будь-якої скінченної лінійно впорядкованої множини M={a₁,a₂,...,a_n}, a_i a_i+1, i=1,2,...,n-1 має вигляд

______________________ ...... __________

a₁ a₂ a₃ a_n-1 a_n

Неважко переконатись, що ab, a,bM тоді і тільки тоді, коли в діаграмі частково впорядкованої множини M існує складений зі стрілок шлях, що веде з вершини a у вершину b. Верхня грань для {a,b} - це елемент, в який ведуть шляхи з a і з b. Нижня грань {a,b} - це елемент, з якого існують шляхи і в a, і в b.

Частково впорядкована множина не є решіткою тоді, коли

1) деяка пара елементів не має верхньої або нижньої грані;

2) для деякої пари елементів найменша верхня (або найбільша нижня) грань не існує.

Наприклад, перші дві множини B і (M) з прикладу 1.20 є решітками, тому що для їхніх діаграм не виконується жодна з наведених умов. Множина C не є решіткою, оскільки, наприклад, для пар {2,5}, {5,7}, {7,10} не існують нижні грані, а пари {10, 28} і { 28,70} не мають верхніх граней. Пара елементів {a,b} ({c,d}) множини D має дві верхні (дві нижні) грані c і d (відповідно a і b), однак не має найменшої верхньої (найбільшої нижньої) грані, оскільки елементи c і d (a і b) непорівнювані між собою.

Частково впорядкована множина M називається повною решіткою, якщо для будь-якої непорожньої підмножини AM в множині M існують найменша верхня грань sup A і найбільша нижня грань inf A. Очевидно, що довільна повна решітка є решіткою, але не будь-яка решітка є повною решіткою. Якщо M - повна решітка, то найменша верхня грань усієї множини M (sup M) називається одиницею даної решітки і позначається 1, а найбільша нижня грань множини M (inf M) називається нулем решітки і позначається 0. Вибір цих назв для sup M і inf M пояснюється такими властивостями елементів 1 і 0.

Для довільного елемента aM виконується

sup {1,a} = 1, sup {0,a} = a, a 1,

inf {1,a} = a, inf {0,a} = 0, a 0. (1.10)

Очевидно, що елементи 0 і 1 є відповідно найменшим і найбільшим елементами повної решітки M.

Приклад 1.21. 1. Решітки B, (M) і P з прикладу 1.19 є повними решітками. Одиницями цих решіток будуть відповідно (1,1,1), M і {M}, а нулями - (0,0,0), і { {a} | aM }.

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

Множина всіх дільників натурального числа n, частково впорядкована за відношенням "ділить", є повною решіткою. Одиницею в такій решітці є число n, а нулем - число 1.

15. Парадокси теорії множин

Слово "парадокс" грецького походження і перекладається українською мовою - несподіваний, дивний. Вживають це слово у відношенні до висловлювання (положення, ідеї), яке суттєво різниться від загальноприйнятого традиційного уявлення з даного приводу. Вживання терміна "парадокс" стосовно до тих суперечностей, які були виявлені різними математиками в теорії множин Г.Кантора, є наївною спробою зменшити їхнє значення і надати їм характеру логічних курйозів, штучних, неприродних конструкцій. Більш точно суть явища передає назва, "антиномії теорії множин", оскільки термін антиномія є синонімом терміна суперечність. Але за традицією, будемо називати сформульовані нижче положення парадоксами.

Парадокс Б.Рассела. Для будь-якої множини M коректним є питання: чи множина M належить собі як окремий елемент, тобто чи є множина M елементом самої себе, чи ні? Наприклад, множина всіх множин є множиною і тому належить сама собі, а множина всіх будинків у місті не є будинком, множина студентів в аудиторії не є студентом.

Отже коректно поставити сформульоване питання і щодо множини всіх множин, які не будуть власними елементами. Нехай M - множина всіх тих множин, що не є елементами самих себе. Розглянемо питання: а сама множина M є елементом самої себе чи ні? Якщо припустити, що MM, то з означення множини M випливає MM. Якщо ж припустимо, що MM, то з того ж таки означення дістанемо MM.

Близьким до парадокса Рассела є так званий "парадокс цирульника": цирульник - це мешканець міста, який голить тих і тільки тих мешканців міста, які не голять самі себе. Проводячи міркування, аналогічні тим, що були зроблені в парадоксі Рассела, дійдемо висновку, що цирульник голить себе в тому і тільки в тому випадку, коли цирульник не голить сам себе.

А от парадокс, що був відомий самому автору теорії множин Г.Кантору. Розглянемо об'єднання всіх мислимих множин і позначимо його U. Тоді за теоремою 1.8 потужність множини (U) всіх підмножин множини U має більшу потужність, ніж сама множина U. Однак це парадоксально, оскільки за означенням множина є множиною, яка містить всі множини (зокрема, і множину (U) ).

Багато хто з математиків на початку ХХ ст. не надавали цим парадоксам особливого значення, оскільки в той час теорія множин була відносно новою галуззю математики і не зачіпала інтересів більшості математиків. Однак їхні більш відповідальні та проникливі колеги зрозуміли, що виявлені парадокси стосуються не тільки теорії множин і побудованих на ній розділів класичної математики, але мають безпосереднс відношення до логіки взагалі, тобто до головного інструменту математики.

Зокрема, парадокс Рассела може бути переформульований в термінах логіки і таким чином доданий до відомих з давніх часів логічних парадоксів (парадокса брехуна, парадокса всемогутньої істоти тощо).

Гостро постало питання про обгрунтування засад математики. На початку ХХ ст. виникли три основні напрямки досліджень з обгрунтування сучасної математики. Коротко подамо суть кожного з цих напрямків.

1. Логіцизм. Основною тезою логіцизму є положення, що першоосновою математики є логіка, а математика - це лише частина логіки. Тобто всі математичні істини складають власну підмножину множини всіх логічних істин.

Головні ідеї та методи логіцизму були вперше викладені у великій праці А.Уайтхеда і Б.Рассела "Принципи математики", яка вийшла на початку другого десятиріччя ХХ ст.

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

2. Iнтуїціонізм. Основними засадами інтуїціонізму є такі принципи:

1) В основу математики кладеться поняття натурального числа, причому система натуральних чисел вважається інтуїтивно відомою.

2) Усі інші математичні об'єкти будуються на основі натуральних чисел суто конструктивно за допомогою скінченного числа застосувань скінченної кількості конкретних операцій.

Доведення існування математичного об'єкта зводиться до побудови конкретного алгоритму, тобто визнаються лише конструктивні доведення існування математичних об'єктів. Зокрема, не визнається доведення існування математичних об'єктів методом від супротивного.

3) Закон виключеного третього незастосований до нескінченних множин. (Закон виключеного третього - це логічна аксіома, за якою з двох тверджень "A" і "не A" тільки одне є істинним).

4) Визнається абстракція потенційної нескінченності і відкидається абстракція актуальної нескінченності.

Обгрунтування математики в рамках інтуіціонізму натрапляє на дві основні перешкоди: значну частину важливих розділів математики не вдається побудувати засобами інтуїціонізму, або ж така побудова має досить громіздкий і штучний вигляд, який не задовольняє переважну більшість як математиків-теоретиків, так і практиків.

Подальшим кроком у розвитку інтуїціонізму є конструктивний напрям (або конструктивізм), який розвивається на основі уточненого поняття алгоритму.

3. Формалізм. Засновником формалізму вважають Д.Гільберта. Цей напрям є дальшим поглибленням аксіоматичного методу в математиці. Основою будь-якої аксіоматичної теорії є список неозначуваних (первинних) понять і список аксіом, тобто положень, які приймаються за вихідні і істинність яких початково декларується. Додатково означаються логічні правила, за допомогою яких з одних тверджень (зокрема, з аксіом) дістають інші.

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

Саме на основі ідей формалізму Е.Цермело у 1908 році побудував першу формальну аксіоматичну теорію множин (так звану систему Цермело-Френкеля, або ZF). Пізніше було запропоновано багато видозмін і вдосконалень ZF та інших аксіоматичних теорій множин.

Якщо проаналізувати всі парадокси теорії множин, то можна зробити висновок, що всі вони обумовлені необмеженим застосуванням так званого принципу абстракції (або принципу згортання), згідно з яким для будь-якої властивості P(x) існує відповідна множина елементів x, які мають властивість P(x). Якщо відкинути це припущення, то всі відомі парадокси теорії множин стають неможливими. Так з парадоксів Рассела і Кантора випливало б, що не існують множина множин, які не є елементами самих себе, і множина всіх множин.

В усіх існуючих аксіоматичних теоріях множин неможливість антиномій грунтується на обмеженнях принципу згортання.

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

Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра, языки, программирование.- Киев, 1974.

Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера.- 2-е изд., перераб. и доп.- М., 1988.

Кук Д., Бейз Г. Компьютерная математика.- М.,1990.

Калужнин Л.А. Введение в общую алгебру.- М.,1973.

Столл Р.Р. Множества. Логика. Аксиоматические теории.- М.,1968.

Шрейдер Ю.А. Равенство, сходство, порядок.- М.,1971.

Шиханович Ю.А. Введение в современную математику.- М.,1965.

Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов.- М.,1975.

Размещено на Allbest.ru