Множини. Операції над множинами

МІНІСТЕРСТВО  ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ  АВІАЦІЙНИЙ УНІВЕРСИТЕТ

КАФЕДРА ПРИКЛАДНОЇ ІНФОРМАТИКИ

 

 

 

 

 

 

 

 

 

 

 

 

Реферат

на тему: «Множини. Операції над множинами»

з дисципліни «Дискретна математика»

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Виконала

студентка УС-111

Жукова Вікторія Олегівна

 

 

 

 

 

Київ 2013

План

 

 

1. Інтуїтивне означення множини
2. Способи задання множин
3. Парадокс Рассела
4. Універсум. Підмножини.
5. Операції над множинами

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Інтуїтивне означення множини 

Поняття множини – одне з основних, якщо не основне, поняття математики. Воно не має точного визначення, і його слід віднести до аксіоматичних понять. Такими аксіоматичними поняттями, наприклад, в елементарній геометрії є поняття  точка, пряма, площина.

Часто приймається формулювання інтуїтивного поняття множини Георга Кантора, основоположника цієї теорії: «Довільне зібрання певних предметів нашої інтуїції чи інтелекту, які можна відрізнити один від одного і які уявляються як єдине ціле, називається множиною. Предмети, які входять до складу множини, називаються її елементами».

Суттєвим  пунктом канторівського розуміння  множини є те, що зібрання предметів  розглядається як один предмет («уявляється  як єдине ціле»). Основна увага  тут переноситься з окремих предметів  на зібрання предметів, що, в свою чергу, можна розглядати як предмети.

Що  стосується «предметів нашої інтуїції чи інтелекту», то це формулювання дає  значну свободу перш за все тим, що ніяк не обмежує природу предметів, які складають множину. Множина  може складатися, наприклад, з людей, точок площини, простих чисел, зірок  Всесвіту. Також це визначення дає  можливість розглядати множини, елементи яких з певних причин точно визначити  неможливо. У зв’язку з цим  згадаємо, що елементи будь-якої нескінченної множини, навіть теоретично, неможливо  зібрати в закінчену сукупність. 

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

Альтернативним  інтуїтивним визначенням множини  є також твердження математиків, які працювали під псевдонімом  Ніколо Бурбаки: «Множина утворюється  з елементів, що мають певні властивості, знаходяться у певних відношеннях  між собою чи з елементами інших  множин» або ж «Логічно кажучи, майже всю сучасну математику можна вивести з єдиного джерела: теорії множин».

Прикладами  множин є множина натуральних  чисел, множина парних чисел, множина  студентів у аудиторії, множина  дерев у лісі. 

Для позначення конкретних множин використовують великі літери A, S, X…Для позначення елементів множин загалом застосовують малі літери a, s, x…Для позначення того, що x є елементом множини S (тобто x належить S), будемо застосовувати запис x∈S, а запис x∉S означатиме, що елемент x не належить множині S. Символ ∈ називається символом належності.

Однозначно  визначена множина S, елементами якої є предмети x₁, x₂,…, x_n, будемо позначати S = {x₁, x₂,…, x_n}. Зокрема, {x} – так звана одинична множина, – є одноелементна множина, єдиним елементом якої є x. Якщо множина S скінченна, то кількість елементів в множині позначається |S|. Наприклад, для S = {a, b, c} |S| = 3. 

Порядок слідування елементів у множині  не має значення. Наприклад, {a, b, c} та {c, a, b} – це одна й та сама множина.

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

S = {S_i}_i∈_A

позначає, що S є сімейством, елементами якого є множини S_i, причому індекс i «пробігає» множину А.

Множина, яка складається з елементів  деякої множини S так, що ці елементи можуть входити до складу цієї множини в якій завгодно кількості екземплярів, будемо називати мультимножиною множини S і позначати її M(S). З точки зору теорії множин, множина і її мультимножина – це один і той самий об’єкт, і вони можуть між собою не розрізнятися. Але часто, особливо коли мова заходить про представлення множини в пам’яті ЕОМ, виникає потреба відрізняти мультимножину від множини.

 

1. Способи задання множин

Є кілька способів задання множин.

1. Вербальний (словесний) за допомогою опису характеристичних властивостей, які повинні мати елементи множин. Наприклад, S – множина студентів жіночої статі у цій аудиторії.
2. Список (перелік) усіх елементів (у фігурних дужках). Наприклад, S = {1,2,3}.
3. Предикатний (характеристичний) за допомогою характеристичного предикату – деякої умови, вираженої у формі логічного твердження або процедури, яка повертає логічне значення, і дозволяє перевіряти, належить чи ні будь-який даний елемент множині. Якщо для даного елемента ця умова виконується, то він належить визначеній множині, у протилежному випадку – не належить. Тобто множина задається у вигляді {x : P(x)} або {x | P(x)}, де P(x) – характеристичний предикат. Наприклад:
• S = {x | x – натуральне число};
• S = {x | x – парне число};
• S = {x | x – цифра десяткової системи}.

Переліком можна задавати тільки кінцеві множини. Нескінченні множини задаються  характеристичними предикатами.

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

 

2. Парадокс Рассела

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

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

Розглянемо множину А всіх множин X, що X не є елементом X, тобто  A = {X | X∉X}.

Якщо множина A існує, то ми маємо відповісти на запитання: А∈А? Нехай A не є елементом А, то за означенням А також є елементом А. З іншого боку, якщо А є елементом А, то А∉А. Отримали логічне протиріччя, яке відомо як парадокс Рассела. 

Цей парадокс відомий у популярній формі  як парадокс цирульника. В одному селищі цирульник зобов’язується голити всіх тих мешканців та тільки тих, які  не голяться самі. Як бути самому цирульнику: чи має він голити сам себе? Очевидно, що будь-яка відповідь приводить  до протиріччя.

Наведемо три способи запобігання  цьому парадоксу Рассела.

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

P(x) = x∈S & Q(x),

де S – відома, свідомо існуюча множина. Зазвичай при цьому використовується позначення {x∈S | Q(x)}. Для А така множина не зазначена, тому А – не є множиною.

2. Теорія типів. Об’єкти мають тип 0, множини елементів типу 0 мають тип 1, множини елементів типу 0 та 1 – тип 2 і т.д. А не має типу, тому не є множиною.
3. Явна заборона приналежності множини самій собі: X∈X – недозволений предикат. Відповідна аксіома має назву аксіома регулярності. 

Існування та аналіз парадоксів у теорії множин сприяли розвитку так званого конструктивізму – напрямку у математиці, в межах якого розглядаються тільки такі об’єкти, для яких відомі процедури (алгоритми) їх побудови. У конструктивній математиці виключаються ті поняття та методи класичної математики, які не задані алгоритмічно.

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

 

4.   Універсум. Підмножини.

У теорії множин використовується поняття порожньої  множини. Порожня множина – це множина, яка не містить елементів. Позначається вона символом ∅. Введення порожньої множини дає можливість оперувати будь-якою множиною без попереднього застереження, існує вона чи ні. Наприклад, множина S = {x | x – непарне число, що ділиться на 2} буде порожньою.

Означення 1.1. Множина A є підмножиною множини В, якщо кожний елемент А є елементом В, тобто якщо x∈A, то x∈В. Для позначення цього факту водиться знак «⊂» - символ включення (або «⊆»). При цьому множина В буде називатися надмножиною множини А.

Якщо  необхідно підкреслити, що множина В містить також інші елементи, крім елементів множини А, то використовують символ строгого включення: А⊂В. Зв’язок між символами ⊂ та ⊆ задається виразом

A⊂B ⇔ A⊆B & А≠В.

Зокрема кожна множина є підмножиною  самої себе. Якщо А не є підмножиною В, то пишуть А⊄В. Тобто існує елемент множини А, який не належить В.

Говорять, що множина А є власною підмножиною В, якщо A⊂B і А≠В. В такому випадку множина В буде власною надмножиною.

Означення 1.2. Універсум (універсальна множина) U – множина з такою властивістю, що всі множини, які розглядаються, є її підмножинами.

У теорії чисел універсум зазвичай співпадає  із множиною всіх цілих або натуральних  чисел. У математичному аналізі  універсум – множина всіх дійсних  чисел, або множина всіх точок n-вимірного простору. Треба зазначити, що універсум однозначно не визначений, якщо точно не вказана область визначення (предметна область). Звичайно, будь-яка множина, яка містить U, може бути використана як універсум.

За  визначенням, кожна з множин є  підмножиною універсуму. Порожня  множина є підмножиною будь-якої даної множини S, оскільки кожний елемент порожньої множини міститься в S (або не існує елементів порожньої множини, які б не належали S). 

Треба бути уважним, щоб розрізняти елементи множини та підмножини цієї множини. Наприклад, коли пишуть a∈{a,b,c}, це означає, що елемент a є членом множини, що складається з трьох елементів: a, b і c. Коли ж пишуть {a}⊂{a,b,c}, це означає, що множина, що складається з одного елемента a, є підмножиною множини, яка складається з трьох елементів: a, b і c.

Означення 1.3. Дві множини рівні, коли вони складаються з одних і тих самих елементів:

A=B ⇔ ∀x(x∈A⇔ x∈B).

Наприклад, {1,2,3} = {3,2,1}. 

Лема 1.1. Стверджується наступна рівність:

A⊂B & B⊂A ⇔ A=B.

Доведення. Необхідність. Розглянемо будь-який елемент x∈А. Множина А є підмножиною В, тому x∈В. З іншого боку, будь-який елемент x∈В (оскільки B⊂A) належить також множині А, тобто x∈А. За означенням рівності маємо А=В.

Достатність. Розглянемо будь-який елемент x∈А. Оскільки А=В, маємо x∈B. Тоді за означенням включення множин A⊂B. Розглянемо будь-який елемент x∈B. Якщо А=В, то x∈А.

За означенням включення В⊂А.

Лема 1.2. Стверджується наступна рівність (властивість транзитивності):

A⊂B & B⊂С ⇔ А⊂С.

Доведення. Якщо x∈А, то x∈В. Також якщо x∈В, то x∈С. Тобто якщо x∈А, то x∈С.

Отримали А⊂С.

Лема 1.3. Порожня множина єдина. 

Це можна довести виходячи з  означення рівності множин.

Ми вже зазначали раніше, що елементами множини можуть бути якісь інші множини.

Означення 1.4. Множину, елементами якої є всі підмножини А, називають множиною підмножин (булеаном) множини А і позначають Р(А). 

Так для триелементної  множини А = {a,b,c} маємо P(A) = {∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}. 

У разі кінцевої множини А, що складається з n елементів, її булеан Р(А) містить 2ⁿ елементів. Доведення ґрунтується на підсумовуванні всіх коефіцієнтів розкладу бінома Ньютона або на поданні підмножин n-розрядними двійковими числами, в яких 1 (або 0) відповідає елементам підмножин.

Слід підкреслити відмінності  між відношенням належності (∈) та відношенням включення (⊂). Відношення включення має властивість транзитивності, а відношення належності – ні. Наприклад, множина А = {{1}, {2,3}, {4}} у числі своїх елементів містить множину  {2,3}, тоді можна записати