Тест числові множини. Способи завдання множин

Тест по темі «Безліч»

Інструкція:

1 варіант

1. Визначити яке з множин є підмножиною А = (10, 20, 30, 40, 50, 60)

a) (10, 20, 30, 40, 50, 60, 70) б) (10) в) (10, 35)

2. Яке з множин визначає, якщо А = (1, 2, 3, 4, 5), B = (3, 4, 5, 6, 7)

a) (1, 4, 5) б) (1, 2, 3, 4, 5) в) (1, 2, 3, 4, 5, 6, 7)

, Якщо A = (1, 3, 5, 7, 9), B = (1, 2, 3, 4)

а) (1, 3, 5, 7) б) (1, 2, 3, 4, 5, 7, 9) в) (1, 3)

4. Безліч трикутників розбили на підмножини різнобічних трикутників, рівнобедрених трикутників і рівносторонніх трикутників. Чи відбулося розбиття множини трикутників на класи?

а) так б) немає

5. На якому малюнку зображено об'єднання множин А і В ()?

Тест по темі «Безліч»

Тест з вибором правильної відповіді.

Інструкція:Виберіть букву з правильною відповіддю і занесіть її в бланк відповідей.

2 варіант

1. Визначити яке з множин є підмножиною

А = (5, 15, 25, 35, 45, 55)

a) (55) б) (5, 25, 50) в) (25, 55, 75)

2. Яке з множин визначає, якщо А = (2, 4, 6, 8, 10), B = (8, 10, 12, 14)

a) (2, 4, 6, 8, 10, 12, 14) б) (8, 10, 12, 14) в) (8, 10)

3. Яка з множин визначає
, Якщо A = (2, 4, 6, 8, 10), B = (2, 4, 8, 9)

а) (2, 4, 6, 8, 10) б) (2, 4, 8, 9) в) (2, 4, 8)

4. Безліч всіх кутів розбили на підмножини прямих, тупих і гострих. Чи відбулося розбиття множини кутів на класи?

а) так б) немає

5. На якому малюнку зображено перетин множин А і В (
)?

Федеральне агентство з освіти

чуваська державний університетім. І.М. Ульянова

Алатирський філія

Факультет управління та економіки

Кафедра вищої математики та інформаційних технологій

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

з дисципліни: Математична логіка

Елементи теорії множин

виконав студент

1 курсу

групи - АФТ 61-06

Науковий керівник

проф. Мерлін А.В.

Вступ

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

до другої половини XIXстоліття поняття «безлічі" не розглядалося як математичний (безліч книг на полиці, безліч людських чеснот і т. д. - все це чисто побутові мовні звороти). Положення змінилося, коли німецький математик Георг Кантор (рис. 1) розробив свою програму стандартизації математики, в рамках якої будь-який математичний об'єкт повинен був опинятися тих чи інших «безліччю».

Наприклад, натуральне число, по Кантору, слід розглядати як безліч, що складається з єдиного елемента іншої множини, званого «натуральним поруч» - який, в свою чергу, сам є безліч, що задовольняє так званим аксіомам Пеано. При цьому загальному поняттю«Безлічі», що розглядався їм як центрального для математики, Кантор давав мало що визначають визначення на кшталт «безліч є багато, мислиме як єдине», і т. Д. Це цілком відповідало умонастрою самого Кантора, підкреслено називав свою програму не "теорією множин» (цей термін з'явився значно пізніше), а вченнямпро множини ( Mengenlehre).

Програма Кантора викликала різкі протести з боку багатьох сучасних йому великих математиків. Особливо виділявся своїм непримиренним ставленням до неї Леопольд Кронекера, який вважав, що математичними об'єктами можуть вважатися лише натуральні числа і те, що до них безпосередньо зводиться (відома його фраза про те, що «бог створив натуральні числа, а все інше - справа рук людських» ). Проте, деякі інші математики - зокрема, Готлоб Фреге і Давид Гільберт - підтримали Кантора в його намірі перевести всю математику на теоретико-множинний мову.

Однак незабаром з'ясувалося, що установка Кантора на необмежену сваволю при оперуванні з множинами (виражений їм самим в принципі «сутність математики полягає в її свободі») є спочатку порочної. А саме, було виявлено ряд теоретико-множинних антиномій: виявилося, що при використанні теоретико-множинних уявлень деякі твердження можуть бути доведені разом зі своїми запереченнями (а тоді, згідно з правилами класичної логіки висловлювань, може бути «доведено» абсолютно будь-яке твердження!). Антиномії ознаменували собою повний провал програми Кантора.

І все ж Кантор вважається засновником теорії множин, і зробив великий внесок у сучасну математику. Йому належить така характеристика поняття «безліч»: Безліч - це об'єднання певних, різних об'єктів, званих елементами множини, в єдине ціле.

Глава 1. Множини

1.1 Елементи і безлічі

Поняття множини і елемента безлічі відносяться до понять, які не визначним явно, таким, як, наприклад, точка і пряма. Слова «сукупність», «сімейство», «система», «набір» і т.п. - синоніми слова «безліч». Це пов'язано з тим, що деякі поняття в математиці повинні бути вихідними, служити тими «цеглинками», з яких складається загальна теорія. Ми визначаємо тільки, як співвідносяться ці вихідні поняття, не кажучи про природу аналізованих об'єктів. Людське мислення влаштовано так, що світ представляється що складається з окремих «об'єктів». Філософам давно ясно, що світ - єдине нерозривне ціле, і виділення в ньому об'єктів - це не більше ніж довільний акт нашого мислення, що дозволяє сформувати доступну для раціонального аналізу картину світу. Але як би там не було, виділення об'єктів і їх сукупностей - природний (або навіть єдино можливий) спосіб організації нашого мислення, тому не дивно, що він лежить в основі головного інструменту опису точного знання - математики.

Можна сказати що безліч -це будь-яка певна сукупність об'єктів. Об'єкти, з яких складено безліч, називаються його елементами.Елементи безлічі різні і відрізняються один від одного. Прикладами множин можуть бути: безліч людей, тварин, рослин на нашій планеті, а також безліч N натуральних чисел 1, 2, 3, ..., безліч Р простих чисел 2, 3, 5, 7, 11, ... Безліч Z цілих чисел: ..., -2, -1, 0, 1, 2, ..., безліч Rвещественних чисел і т.д. Безліч, що не містить елементів, називається порожнім. Позначення: Æ.Пустое безліч є підмножиною будь-якої множини. Потужність порожнього безлічі дорівнює нулю. Поняття порожнього безлічі (подібно поняттю «нуль») виникає з потреби, щоб результат будь-якої операції над множинами був також безліччю.

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

Якщо об'єкт х є елементом множини М, то кажуть, що х належить М. Позначення: хÎМ. В іншому випадку говорять, що х не належить М. Позначення: хÏМ. Зауважимо, що елементи множини самі можуть бути множинами. Наприклад, безліч груп студентів складається з елементів (груп), які, в свою чергу, складаються зі студентів.

Нехай дано два безлічі А і В (рис 1.1.1), тоді:

підмножина – поняття частини в теорії множин. МножествоC є підмножиною множини B (рис. 1.1.1, позначається CÌB) в разі, якщо кожен елемент множестваC є також і елементом безлічі B. Наприклад, безліч всіх парних чисел є підмножиною множини всіх цілих чисел. Якщо C є підмножиною B, то B називається надмножествомC.

Зазвичай безлічі позначають прописними буквами латинського алфавіту, а елементи множин - малими літерами.

Поняття множини, елемента і приналежності, які на перший погляд видаються інтуїтивно ясними, при найближчому розгляді таку ясність втрачають. По-перше, проблематична Відмінність елементів. Наприклад, символи «е» і «а», які зустрічаються на цій сторінці, - це один елемент множини Аабо два різних елемента? По-друге, проблематична можливість (без додаткових зусиль) вказати, чи належить даний елемент даного безлічі. Наприклад, чи є число +86958476921537485067857467 простим?

Безлічі, як об'єкти, можуть бути елементами інших множин. Безліч, елементами якого є множини, зазвичай називається класомабо сімейством.

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

1.2 Способи завдання множин

Ірраціональність чисел поставила нас перед необхідністю працювати з нескінченними множинами. Але насправді з нескінченністю доводиться стикатися постійно, наприклад будь-яка геометрична фігура - безліч точок: відрізок, окружність, трапеція, конус ... - всі ці фігури містять нескінченну кількість точок. Виходячи з цього, виникає необхідність завдання множин, для зручності роботи з ними. Щоб задати безліч, потрібно вказати, які елементи йому належать. Це можна зробити різними способами. Зазначимо дві найбільш уживані форми завдання (визначення) множин

Перерахування елементів, тобто вказівка всіх елементів безлічі, які прийнято укладати в фігурні дужки. Якщо елементи: Ò, Â, Á, À, w - належать множині М, то записується М = (Ò, Â, Á, À, w);

Характеристичне властивість, коли серед елементів якого-небудь безлічі виділяються за допомогою висловлювання, елементи, що володіють деяким властивістю (що характеризує це безліч). Нехай P (x) - якесь властивість числа x. Тоді запис (x | P (x)) означає безліч всіх таких чисел, які мають властивість P (x). Наприклад, безліч (x | x2 - 3x + 2 = 0) є сукупність коренів рівняння x2 - 3x + 2 = 0, тобто це множина складається з двох елементів: 2 і 1; (X | 3 12 і x<3} = Æ;

Однак при завданні множин як одним, так і іншим способом можуть виникнути проблеми. Наприклад, нехай безліч А складається з російських слів «стіл», «світ» і символу «$» в стандартній символіці, тобто А = (стіл, світ, $). Безліч А ^, що складається з таких же символів, але на англійській мові, буде іншим А ^ = (table, peace, $). Так що потрібно бути точним у перерахуванні (тобто завданні множин шляхом перерахування). І ще один приклад, пов'язаний з будь-яким підручником або книгою. Існує багато примірників якоїсь книги, якщо мається на увазі конкретна книга (наприклад, що належить певній людині), отримаємо один варіант, якщо малися на увазі всі екземпляри, що вийшли з друкарні (наприклад, тираж 100 тис. Книг) - інший варіант, якщо ж мати на увазі тільки збереглися до теперішнього моменту - третій варіант. Тому необхідно бути точним при завданні множин перерахуванням.

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

Якщо безліч Yсуществует, то ми повинні мати можливість відповісти на наступне питання: YÎY? Нехай YÎY, тоді має виконуватися властивість, що задає безліч Y, тобто YÏY. Нехай YÏY, то, оскільки виконується властивість, що задає Y, приходимо до того, що YÎY, а це суперечить припущенню. Виходить непереборні логічне протиріччя. Ось три способи уникнути цього парадоксу.

1. Обмежити використовувані характеристичні предикати видом

P (x) = xÎA & Q (x),

де A - відоме, свідомо існуюче безліч (універсум). Зазвичай при цьому використовують позначення (xÎА | Q (x)). Для Yуніверсум не вказано, а тому Yмножеством не є;

2. Теорія типів. Об'єкти мають тип 0, безлічі мають тип 1, безлічі множин - тип 2 і т. Д. Yне має типу і безліччю не є;

3. Характеристичне властивість P (x) задано у вигляді обчислюваної функції (алгоритму). Спосіб обчислення значення властивості XÎXне заданий, а тому Yмножеством не є.

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

1.3 Кількість елементів у множині

Потужність безлічі - це узагальнення поняття кількості (числа елементів безлічі), яке має сенс для всіх множин, включаючи нескінченні.

Існують великі, є менші нескінченні множини, серед них рахункова безліч є найменшим.

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

Рахункова безліч є «найменшим» нескінченним безліччю, т. Е. В будь-якому нескінченній множині знайдеться рахункова підмножина.

властивості:

1. Будь-яка підмножина рахункового безлічі звичайно або лічильно;

2. Об'єднання кінцевого або рахункового числа рахункових множин лічильно;

3. Пряме твір кінцевого числа рахункових множин лічильно;

4. Безліч всіх кінцевих підмножин рахункового безлічі лічильно;

5. Безліч всіх підмножин рахункового безлічі континуально і, зокрема, не є рахунковим.

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

властивості

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

· Для нескінченних множин потужність безлічі може збігатися з потужністю його власного підмножини, наприклад

Z (безліч цілих чисел) = (-3, -2, -1,0,1,2,3 ...);

N (безліч натуральних чисел) = (1,2,3,4,5,6,7 ...);

0,1, -1,2, -2,3, -3 ... цілих чисел стільки ж, скільки і натуральних

1,2, 3,4, 5, 6, 7…

· Теорема Кантора гарантує існування більш потужного безлічі для будь-якого даного: Безліч всіх підмножин множини A могутніше A, або | 2A | > | A |.

· За допомогою Канторова квадрата можна також довести наступне корисне твердження: Декартово твір нескінченної кількості A з самим собою рівнопотужності A.

Дотримуючись Кантору, потужність безлічі називається кардинальним числом і позначається потужність такого безлічі A через | A | (Сам Кантор використовував позначення). Іноді зустрічається позначення.

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

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

Для потужностей, як і в разі кінцевих множин, є поняття: рівність, більше, менше. Тобто для будь-яких множин A і B можливо тільки одне з трьох:

1. | A | = | B | або A і B рівнопотужні;

2. | A | > | B | або A могутніше B, т. е. A містить підмножина, рівносильне B, але A і B НЕ рівнопотужні;

3. | A |< | B | или B мощнее A, в этом случае B содержит подмножество, равномощное A, но A и B не равномощны.

Ситуація, в якій A і B НЕ рівнопотужні і ні в одному з них немає частини, рівнопотужності іншому, неможлива. Це випливає з теореми Цермело. Інакше це означало б існування непорівнянних між собою потужностей (що в принципі можливо, якщо не брати аксіому вибору).

Ситуація, в якій | A | > | B | і | A |< | B |, невозможна по теореме Кантора - Бернштейна.

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

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

Глава 2. Операції над множинами

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

2.1 Порівняння множин

безліч елемент аксіоматичний приналежність

Безліч A міститься у великій кількості B (безліч B включає безліч A), якщо кожен елемент A є елемент B:

Якщо і, то A називається власним підмножиною В. Зауважимо, що. За визначенням.

Два безлічі називаються рівними, якщо вони є підмножинами один одного:

Теорема про порівнянні множин. Для будь-яких множин A і B існує одна і тільки одна з наступних можливостей: | A | = | B |, | A |<|B|, |A|>| B |.

2.2 Основні операції над множинами

Нижче перераховані основні операції над множинами:

· Об'єднання:

· Перетин:

· Різниця:

· Симетрична різниця:

· Додаток:

Операція доповнення має на увазі деякий універсум (безліч U, яке містить A):

Для кращого розуміння сенсу цих операцій використовуються діаграми Ейлера - Венна, на яких представлені результати операцій над геометричними фігурамияк множинами точок.

Об'єднанням двох множин AÈB (рис. 2.2.1) - називають третьою безліч, кожен елемент якого належить хоча б одному з множин A і B

Перетином множин А∩В (рис 2.2.2), є безліч, що складається з усіх тих елементів, які належать одночасно всіма даними безлічам.

Різницею множин A \ B = A - B (рис. 2.2.3) - називається така безліч, кожен елемент якого належить множині A, але не належить множині B.

Симетрична різниця ADB (рис. 2.2.4)

Доповнення до безлічі A називається безліч всіх елементів, що не входять в безліч A (рис 3.2.5)

2.3 Властивості операцій над множинами

Нехай заданий універсум U . Тоді для всіх A, B, CÌ Uвиконуються наступні властивості (табл. 2.3.1):

Властивості операцій над множинами

Для об'єднання (È)	Для перетину (Ç)
ідемпотентність
A È A = A	A Ç A = A
комутативність
A È B = B È A	A Ç B = B Ç A
асоціативність
A È (BÈC) = (A È B) ÈC	A Ç (BÇC) = (A Ç B) ÇC
дистрибутивність
A È (BÇC) = (A È B) Ç (A È C)	A Ç (BÈC) = (A Ç B) È (A Ç C)
поглинання
(A Ç B) ÈA = A	(A È B) ÇA = A
властивості нуля
A ÈÆ = A	A ÇÆ = Æ
властивості одиниці
A È U = U	A Ç U = U
інволютивними
= A
Закони де Моргана

властивості доповнення

Вираз для різниці

Вираз для симетричної різниці

У справедливості перерахованих властивостей можна переконатися різними способами. Наприклад, намалювати діаграми Ейлера для лівої і правої частин рівності і переконатися, що вони збігаються, або ж провести формальне міркування для кожного рівності. Розглянемо для прикладу першу рівність: A È A = А.Візьмемо довільний елемент х,належить лівій частині рівності, х Î A È A. За визначенням операції об'єднання È маємо х Î A È х Î A.В будь-якому випадку х Î A . Взявши довільний елемент з безлічі в лівій частині рівності, виявили, що він належить множині в правій частині. Звідси по визначенню включення множин отримуємо, що A È A Ì А.нехай тепер х Î A . Тоді, очевидно, вірно х Î A È х Î A . Звідси по визначенню операції об'єднання маємо х Î A È A. Таким чином, А Ì A È A. Отже, за визначенням рівності множин, A È A = А. Аналогічні міркування неважко провести і для інших рівностей.

Доведемо властивість дистрибутивности для операції об'єднання на діаграмах Ейлера-Венна (рис 2.3.1):

A È (BÇC) = (A È B) Ç (A È C)

Глава 3. Аксіоматична теорія множин

3.1 Наївна теорія множин

На початку XX векаБертран Рассел, вивчаючи наївну теорію множин, прийшов до парадоксу (з тих пір відомому як парадокс Рассела). Таким чином, була продемонстрована неспроможність наївною теорії множин і пов'язаної з нею канторовской програми стандартизації математики. А саме, було виявлено ряд теоретико-множинних антиномій: виявилося, що при використанні теоретико-множинних уявлень деякі твердження можуть бути доведені разом зі своїми запереченнями (а тоді, згідно з правилами класичної логіки висловлювань, може бути «доведено» абсолютно будь-яке твердження!). Антиномії ознаменували собою повний провал програми Кантора.

Після виявлення антиномії Рассела частина математиків (наприклад, Л. Е. Я. Брауер і його школа) вирішила повністю відмовитися від використання теоретико-множинних уявлень. Інша ж частина математиків, очолена Д. Гильбертом, зробила ряд спроб обґрунтувати ту частину теоретико-множинних уявлень, яка здавалася їм найменш відповідальною за виникнення антиномій, на основі свідомо надійної финитной математики. З цією метою були розроблені різні аксиоматизации теорії множин.

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

В даний час найбільш поширеною аксіоматичної теорією множин є ZFC - теорія Цермело - Френкеля з аксіомою вибору. Питання про несуперечності цієї теорії (а тим більше - про існування моделі для неї) залишається невирішеним.

3.2 Аксіоми теорії множин

Зараз у нас є всі засоби, щоб сформулювати систему аксіом теорії множин ZFC, в рамках якої можна викласти все загальноприйняті в сучасній математиці способи міркувань і не проходить жоден з відомих теоретико-множинних парадоксів. Ця система дозволяє будувати все математичні об'єктивиходячи з порожньої множини. Уявімо систему аксіом, Цермело - Френкеля (ZF).

1.Аксіома існування порожнього безлічі: Існує порожня множина Æ;

2.Аксіома існування пари: Якщо існують безлічі а й b, то існує безліч (a, b);

3.Аксіома суми: Якщо існує безліч X, то існує безліч ÈX = (a | aÎb для деякого bÎX);

4.Аксіома нескінченності: Існує безліч w = (0, 1, ..., n, ...), де 0 = Æ, n + 1 = nÈ (n);

5.Аксіома безлічі всіх підмножин: Якщо існує безліч А, то існує безліч:

Р (А) = (B | BÍA);

6. Аксіома заміни: Якщо P (x, у) - деяка умова на безлічі x , у, Таке, що для будь-якого безлічі xсуществует не більше одного безлічі у, Що задовольняє Р (х, у), то для будь-якого безлічі аіснує безліч (b | P (c, b) для деякого з Î а);

7. Аксіома екстенсіональності:

Два безлічі, що мають однакові елементи, рівні, будь-яка множина визначається своїми елементами:

8. Аксіома регулярності:

Будь-яке непорожня множина xімеет елемент а Î х, для якого

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

Покажемо, як аксіоматика ZF дозволяє визначати теоретико-множинні операції.

1. Визначимо безліч AÈ В, виходячи з множин А до В. За аксіомі існування пари утворюється безліч (А, В). За допомогою аксіоми суми отримуємо безліч È (A, B), яке за визначенням збігається з безліччю AÈB.

2. Перетин А Ç В множин А і В визначається по аксіомі заміни за допомогою наступного властивості Р (х, у): х = у і х Î А. Маємо безліч (b | P (c, b) і з Î В) = (b | з = bі з Î А і з ÎВ) = (c | з Î А і з ÎВ).

3. Покажемо, що з аксіом 5 і 6 слід існування безлічі А2 = ((a, b) | a, bÎ А) для будь-якого безлічі А. Так як (a, b) = ((a), (a, b) ), то А2 ÍP (Р (А)). Нехай властивість Р (х, у) означає, що існують такі a, bÎ А, що x = ((а), (а, b)) і y = х. Тоді безліч А2 одно (b | P (c, b), cÎ Р (Р (А))) і по аксіомі 6 воно існує.

Система аксіом ZFC утворюється з ZF додаванням однієї з наступних двох еквівалентних аксіом, які, з одного боку, є найменш «очевидними», а з іншого - найбільш змістовними,

1. Аксіома вибору.

Для будь-якого непорожньої безлічі А існує таке відображення j: Р (А) \ (Æ) ®A, що j (Х) ÎX | для всіх XÍ А, X¹Æ.

2. Принцип повного упорядкування. Для будь-якого непорожньої безлічі А існує бінарне відношення £ на А, для якого (A, £) цілком упорядкована множина.

В системі ZFC справедливий принцип трансфінітної індукції, що є узагальненням принципу повної індукції: якщо (A, £) - цілком упорядкована множина, Р (х) - деяка властивість, то справедливість властивості Р (х) на всіх елементах х Î А випливає з того, що для будь-якого zÎ А здійсненність властивості Р на елементах у, де у< z, влечет выполнимость P(z):

Глава 4. Подання множин в ЕОМ

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

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

4.1 Реалізація операцій над підмножинами заданого універсуму U

нехай універсум U- кінцевий, і число елементів в ньому перевершує розрядності ЕОМ: | U | < n. Элементы универсума нумеруются: U = (U1 ... un). Підмножина А універсуму Uпредставляється кодом (машинним словом або бітової шкалою) С, в якому

1, якщо u1 ÎА

0, якщо un ÏА

де С [i] - це i-й розрядкоду С;

Код перетину множин А і В є поразрядное логічне твір коду безлічі А і коду безлічі В. Код об'єднання множин А і В є поразрядное логічна сума коду безлічі А і коду безлічі В. В більшості ЕОМ для цих операцій є відповідні машинні команди. Таким чином, операції над невеликими множинами виконуються досить ефективно. Якщо потужність універсуму перевершує розмір машинного слова, але не дуже велика, то для подання множин використовуються масиви бітових шкал. У цьому випадку операції над множинами реалізуються за допомогою циклів за елементами масиву.

4.2 Генерація всіх підмножин універсуму

У багатьох переборних алгоритмах потрібно послідовно розглянути всі підмножини заданої множини. У більшості комп'ютерів цілі числа представляються кодами в двійковій системі числення, причому число 2k - 1 представляється кодом, що містить k одиниць. Таким чином, число 0 є поданням порожнього безлічі Æ, число 1 є поданням підмножини, що складається з першого елемента, і т.д. Наступний тривіальний алгоритм перераховує все підмножини n-елементного безлічі.

Алгоритм генерації всіх підмножин n-елементного безлічі:

Вхід: n³ 0 - потужність множини;

вихід:послідовність кодів підмножин i;

for i from 0 to 2n - 1;

yield i ;

end for ;

Алгоритм видає 2n різних цілих чисел, отже, 2n різних кодів. Зі збільшенням числа збільшується кількість двійкових розрядів, необхідних для його подання. Найбільше (з генеруються) число 2n - 1 вимагає свого уявлення рівно n розрядів. Таким чином, всі підмножини генеруються, причому рівно по одному разу. Недолік цього алгоритму полягає в тому, що порядок генерації підмножин ніяк не пов'язаний з їх складом. Наприклад, слідом за підмножиною з кодом 0111 буде перераховано підмножина з кодом 1000.

4.3 Подання множин впорядкованими списками

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

elem = record ;

i : info ; (Інформаційне поле);

n : n(Покажчик на наступний елемент);

end record ;

При такому поданні трудомісткість операції Î складе О (n), а трудомісткість операцій Ì, Ç, È складе О (n × m), де n і m - потужності беруть участь в операції множин.

Якщо елементи в списках впорядкувати, наприклад, за зростанням значення поля i, то трудомісткість всіх операцій складе О (n). Ефективна реалізація операцій над множинами, представленими у вигляді упорядкованих списків, заснована на вельми загальний алгоритм, Відомому як алгоритм злиття. Алгоритм типу злиття паралельно переглядає два безлічі, представлених впорядкованими списками, причому на кожному кроці просування відбувається в ту безліч, в якому поточний елемент менше.

висновок

Курсовий проект виконаний на тему «Елементи теорії множин». У ньому розглянуті питання:

Безлічі: елементи і множини, способи завдання множин, кількість елементів у множині;

Операції над множинами: порівняння множин, основні операції над множинами, властивості операцій над множинами;

Аксіоматична теорія множин: наївна теорія множин, аксіоми теорії множин;

Подання множин в ЕОМ: Реалізація операцій над підмножинами заданого універсуму U , Генерація всіх підмножин універсуму, Подання множин впорядкованими списками;

На підставі знайденої інформації (навчальна література, Internet), я виділив основні пункти, які найбільш повно і точно дають уявлення про теорію множин. При виконанні роботи були наведені приклади множин, а також і ті приклади, які призводять до суперечностей при різному способіїх завдання. При дослідженні властивостей операцій над множинами я довів одне з властивостей (дистрибутивность) за допомогою діаграм Ейлера-Венна. І я вважаю, що в останньому розділі необхідно було вказати на зв'язок між множинами і їх поданням на ЕОМ, особливо це важливо, на мій погляд, для спеціальності математика-програміста.

Після виконаної роботи можна зробити такий висновок:

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

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

1. Дискретна математика для програмістів / Ф.А.Новіков. - СПб .: Пітер, 2002. - 304 с.

2. Жолкіїв С.Ю. Математика та інформатика для гуманітаріїв: Підручник. - М .: Гардарики, 2002. - 531 с.

3. Судоплатов С.В., Овчинникова О.В. елементи дискретної математики: Підручник. - М .: ИНФРА-М, Новосибірськ: Изд-во НГТУ, 2002. - 280 с. - (Серія « Вища освіта»)

4. Шипачов Вадим Олександрович В.С. Вища математика. Учеб. Для вузів. - 4-е изд., Стер. - М .: вища школа. 1998. - 479 с.

5. Матеріал з Вікіпедії - вільної енциклопедії. Георг Кантор (http://www.peoples.ru/science/mathematics/kantor/)

Тест: Основи теорії множин Безліч, що не містить жодного елемента.

відповідь:

порожня множина

Безліч, що містить кінцеве число елементів.

відповідь:

кінцеве безліч

Безліч, яке не є ні кінцевим, ні порожнім.

відповідь:

безліч

Безліч річок в Росії.

порожнє

Безліч людей, що живуть на Марсі.

кінцеве

Безліч точок на окружності.

нескінченне

безліч натуральних чисел

безліч цілих чисел

безліч раціональних чисел

безліч дійсних чисел

комутативність

АІB = BІA

асоціативність

AИ (B∩C) = (AІB) ∩ (AІC)

дистрибутивність

(AІB) ИC = AИ (BІC)

Способи завдання множин:

перерахування всіх елементів безлічі

за допомогою кіл Ейлера

вказівка характеристичного властивості елементів безлічі

вказівка першого і останнього елементів безлічі

доповненням множини

універсальним безліччю

рівним

підмножиною

Безліч А - підмножина безлічі D

Безліч D - підмножина множини A

Безліч А і безліч D рівні

Безліч А - ступінь безлічі D

(0;1)

(3;1)

(2;0)

(1;0)

безліч студентів факультету, що мають домашній персональний комп'ютер

порожня множина

безлічі А і В рівні

Нехай безліч M = (- 1; 1) являє собою інтервал, а безліч N = [- 1; 0] - відрізок числової осі, тоді безліч K = M З N, як числовий проміжок дорівнюватиме ...

K = [- 1, 1]

K = (- 1,0]

K = (- 1,0)

K = (- 1, 1]

		(-1;0)
		(1;1)
		(0;1)
		(-1;1)

симетрична різниця

доповнення

рівнопотужності

Виберіть вірні твердження:

Нескінченні незліченні безлічі є менш потужними, ніж нескінченні незліченні безлічі.

Нескінченні незліченні безлічі є більш потужними, ніж нескінченні рахункові безлічі.

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

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

безлічі А і В складаються з однакових елементів

безлічі А і В рівні

безліч А включає в себе безліч В

безліч А - підмножина безлічі У

Спростіть, якщо А = В, А∩С =∅ :

(((AІB) ∩ (C∩C)) \ (B∩A) ∩B)) ΔA = ...

порожня множина

Спростіть, якщо А = В, А∩С =∅ :

((D \ (A∩B)) ∩ ((CІC) ∩B) = ...

порожня множина

Спростіть, якщо А = В, А∩С =∅ :

(C∩B) Δ ((AІB) І (C∩A)) = ...

порожня множина

X = (1,5); Y = (1,2,4); Z = (2,5)

Знайти безліч: XІ (Y∩Z)

{1,2,4,5}

{1,2,5}

{1,4,5}

{1,2,4}

Нехай дано такі множини:

X = (1,2,3,4,5); X = (1,5); Y = (1,2,4); Z = (2,5)

Знайти безліч: (XІY) ∩ (XІZ)

{1,2,4,5}

{1,5}

{1,2,5}

{2,5}

A = (5, 7, 9) І (5,12, 15)

Виконайте дії і визначте потужність отриманого безлічі:

B = {5, 7, 9, 12} З{5,12, 15}

Виконайте дії і визначте потужність отриманого безлічі:

A = (5, 7, 9) З{5, 57, 59}

Виконайте дії і визначте потужність отриманого безлічі:

B = {5, 7, 9} І{5, 57, 59}

Виконайте дії і визначте потужність отриманого безлічі:

{1, 2, 3}\ {2, 3}

Виконайте дії і визначте потужність отриманого безлічі:

{1, 2, 3}\ {4, 5}

x ≤ 3

x  (1, 2, 3)

1 < x < 5

x  (2, 3, 4)

3 < x ≤ 6

x  (4, 5, 6)

2 ≤ x ≤ 4

1 ≤ x< 4

Скільки учнів вирішили всі завдання?

В олімпіаді з математики для абітурієнтів взяло участь 40 учнів, їм було запропоновано вирішити одну задачу з алгебри, одну з геометрії і одну з тригонометрії. З алгебри вирішили задачу 20 осіб, з геометрії - 18 осіб, з тригонометрії - 18 осіб.

З алгебри і геометрії вирішили 7 осіб, з алгебри та тригонометрії - 9 осіб. Жодної задачі не вирішили 3 людини.

Скільки учнів вирішили тільки два завдання?

З алгебри і геометрії вирішили 7 осіб, з алгебри та тригонометрії - 9 осіб. Жодної задачі не вирішили 3 людини.

Скільки учнів вирішили тільки одну задачу?

Першу або другу контрольні роботи з математики успішно написали 33 студента, першу або третю - 31 студент, другу або третю - 32 студента. Не менше двох контрольних робіт виконали 20 студентів.

Скільки студентів успішно вирішили тільки одну контрольну роботу?

У класі 35 учнів. Кожен з них користується хоча б одним з видів міського транспорту: метро, автобусом і тролейбусом. Всіма трьома видами транспорту користуються 6 учнів, метро та автобусом - 15 учнів, метро і тролейбусом - 13 учнів, тролейбусом та автобусом - 9 учнів.

Скільки учнів користуються тільки одним видом транспорту?

відповідь:

Нехай A = (1,2,3,8) і B = (a, b, c)