______________________ ...... __________
a1a2a3an-1an
Неважко переконатись, що a£b, a,bÎM тоді і тільки тоді, коли в діаграмі частково впорядкованої множини M існує складений зі стрілок шлях, що веде з вершини a у вершину b. Верхня грань для {a,b} - це елемент, в який ведуть шляхи з a і з b. Нижня грань {a,b} - це елемент, з якого існують шляхи і в a, і в b.
Частково впорядкована множина не є решіткою тоді, коли
1) деяка пара елементів не має верхньої або нижньої грані;
2) для деякої пари елементів найменша верхня (або найбільша нижня) грань не існує.
Наприклад, перші дві множини B і 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 називається повною решіткою, якщо для будь-якої непорожньої підмножини AÍM в множині M існують найменша верхня грань sup A і найбільша нижня грань inf A. Очевидно, що довільна повна решітка є решіткою, але не будь-яка решітка є повною решіткою. Якщо M - повна решітка, то найменша верхня грань усієї множини M (sup M) називається одиницею даної решітки і позначається 1, а найбільша нижня грань множини M (inf M) називається нулем решітки і позначається 0. Вибір цих назв для sup M і inf M пояснюється такими властивостями елементів 1 і 0.
Для довільного елемента aÎM виконується
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, b(M) і P з прикладу 1.19 є повними решітками. Одиницями цих решіток будуть відповідно (1,1,1), M і {M}, а нулями - (0,0,0), Æ і { {a} | aÎM }.
2. Множина N натуральних чисел не є повною решіткою, оскільки будь-яка її нескінченна підмножина на має найменшої верхньої грані.
3. Множина всіх дільників натурального числа n, частково впорядкована за відношенням "ділить", є повною решіткою. Одиницею в такій решітці є число n, а нулем - число 1.
15. Парадокси теорії множин
Слово "парадокс" грецького походження і перекладається українською мовою - несподіваний, дивний. Вживають це слово у відношенні до висловлювання (положення, ідеї), яке суттєво різниться від загальноприйнятого традиційного уявлення з даного приводу. Вживання терміна "парадокс" стосовно до тих суперечностей, які були виявлені різними математиками в теорії множин Г.Кантора, є наївною спробою зменшити їхнє значення і надати їм характеру логічних курйозів, штучних, неприродних конструкцій. Більш точно суть явища передає назва, "антиномії теорії множин", оскільки термін антиномія є синонімом терміна суперечність. Але за традицією, будемо називати сформульовані нижче положення парадоксами.
Парадокс Б.Рассела. Для будь-якої множини M коректним є питання: чи множина M належить собі як окремий елемент, тобто чи є множина M елементом самої себе, чи ні? Наприклад, множина всіх множин є множиною і тому належить сама собі, а множина всіх будинків у місті не є будинком, множина студентів в аудиторії не є студентом.
Отже коректно поставити сформульоване питання і щодо множини всіх множин, які не будуть власними елементами. Нехай M - множина всіх тих множин, що не є елементами самих себе. Розглянемо питання: а сама множина M є елементом самої себе чи ні? Якщо припустити, що MÎM, то з означення множини M випливає MÏM. Якщо ж припустимо, що MÏM, то з того ж таки означення дістанемо MÎM.
Близьким до парадокса Рассела є так званий "парадокс цирульника": цирульник - це мешканець міста, який голить тих і тільки тих мешканців міста, які не голять самі себе. Проводячи міркування, аналогічні тим, що були зроблені в парадоксі Рассела, дійдемо висновку, що цирульник голить себе в тому і тільки в тому випадку, коли цирульник не голить сам себе.
А от парадокс, що був відомий самому автору теорії множин Г.Кантору. Розглянемо об’єднання всіх мислимих множин і позначимо його U. Тоді за теоремою 1.8 потужність множини b(U) всіх підмножин множини U має більшу потужність, ніж сама множина U. Однак це парадоксально, оскільки за означенням множина È є множиною, яка містить всі множини (зокрема, і множину b(U) ).
Багато хто з математиків на початку ХХ ст. не надавали цим парадоксам особливого значення, оскільки в той час теорія множин була відносно новою галуззю математики і не зачіпала інтересів більшості математиків. Однак їхні більш відповідальні та проникливі колеги зрозуміли, що виявлені парадокси стосуються не тільки теорії множин і побудованих на ній розділів класичної математики, але мають безпосереднс відношення до логіки взагалі, тобто до головного інструменту математики.
Зокрема, парадокс Рассела може бути переформульований в термінах логіки і таким чином доданий до відомих з давніх часів логічних парадоксів (парадокса брехуна, парадокса всемогутньої істоти тощо).
Гостро постало питання про обгрунтування засад математики. На початку ХХ ст. виникли три основні напрямки досліджень з обгрунтування сучасної математики. Коротко подамо суть кожного з цих напрямків.
1.Логіцизм. Основною тезою логіцизму є положення, що першоосновою математики є логіка, а математика - це лише частина логіки. Тобто всі математичні істини складають власну підмножину множини всіх логічних істин.
Головні ідеї та методи логіцизму були вперше викладені у великій праці А.Уайтхеда і Б.Рассела "Принципи математики", яка вийшла на початку другого десятиріччя ХХ ст.
Незважаючи на те, що в рамках логіцизму проблема обгрунтування математики не була остаточно розв'язана, все ж було зроблено чимало для з'ясування деяких важливих сторін логічної структури математики.
2.Iнтуїціонізм. Основними засадами інтуїціонізму є такі принципи:
1) В основу математики кладеться поняття натурального числа, причому система натуральних чисел вважається інтуїтивно відомою.
2) Усі інші математичні об’єкти будуються на основі натуральних чисел суто конструктивно за допомогою скінченного числа застосувань скінченної кількості конкретних операцій.
Доведення існування математичного об’єкта зводиться до побудови конкретного алгоритму, тобто визнаються лише конструктивні доведення існування математичних об’єктів. Зокрема, не визнається доведення існування математичних об’єктів методом від супротивного.
3) Закон виключеного третього незастосований до нескінченних множин. (Закон виключеного третього - це логічна аксіома, за якою з двох тверджень "A" і "не A" тільки одне є істинним).
4) Визнається абстракція потенційної нескінченності і відкидається абстракція актуальної нескінченності.
Обгрунтування математики в рамках інтуіціонізму натрапляє на дві основні перешкоди: значну частину важливих розділів математики не вдається побудувати засобами інтуїціонізму, або ж така побудова має досить громіздкий і штучний вигляд, який не задовольняє переважну більшість як математиків-теоретиків, так і практиків.
Подальшим кроком у розвитку інтуїціонізму є конструктивний напрям (або конструктивізм), який розвивається на основі уточненого поняття алгоритму.
3. Формалізм. Засновником формалізму вважають Д.Гільберта. Цей напрям є дальшим поглибленням аксіоматичного методу в математиці. Основою будь-якої аксіоматичної теорії є список неозначуваних (первинних) понять і список аксіом, тобто положень, які приймаються за вихідні і істинність яких початково декларується. Додатково означаються логічні правила, за допомогою яких з одних тверджень (зокрема, з аксіом) дістають інші.
Гільберт і його послідовники вважали, що кожен розділ математики можна повністю формалізувати, тобто за допомогою формальних виразів (формул) подати всі аксіоми, а всі математичні (логічні) доведення звести до суто формальних перетворень над формулами.
Саме на основі ідей формалізму Е.Цермело у 1908 році побудував першу формальну аксіоматичну теорію множин (так звану систему Цермело-Френкеля, або ZF). Пізніше було запропоновано багато видозмін і вдосконалень ZF та інших аксіоматичних теорій множин.
Якщо проаналізувати всі парадокси теорії множин, то можна зробити висновок, що всі вони обумовлені необмеженим застосуванням так званого принципу абстракції (або принципу згортання), згідно з яким для будь-якої властивості P(x) існує відповідна множина елементів x, які мають властивість P(x). Якщо відкинути це припущення, то всі відомі парадокси теорії множин стають неможливими. Так з парадоксів Рассела і Кантора випливало б, що не існують множина множин, які не є елементами самих себе, і множина всіх множин.
В усіх існуючих аксіоматичних теоріях множин неможливість антиномій грунтується на обмеженнях принципу згортання.
СПИСОК ЛIТЕРАТУРИ
Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра, языки, программирование.- Киев, 1974.
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера.- 2-е изд., перераб. и доп.- М., 1988.