Задачі та вправи

І. Навести приклад множини Y, еквівалентної множині X={1,2,3,4,5}. Скільки взаємно однозначних відображень існує між Х та Y?

ІІ. Чи рівнопотужні множини: 1) N⁺ та N^-, 2) N^- та N⁺, 3) N та Z, 4) N⁺ та Q, 5) N та R?

III. Нехай А – незліченна множина й В – деяка зліченна підмножина множини А. Довести, що множина В\А незліченна.

ІV. Чи є зліченною: 1) множина усіх непарних цілих чисел; 2) множина усіх ірраціональних чисел?

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

1. Биркгоф Г., Барти Т. Современная прикладная алгебра. – М.: Мир, 1976. – 400 с.

2. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра, языки, програм-мирование. – К.: Наукова думка, 1989. – 328 с.

3. Капітонова Ю.В., Кривий С.Л., Летичевський О.А., Луцький Г.М., Печурін М.К. Основи дискретної математики. К.: Наукова думка, 2002. – 580 с.

4. Кук Г., Бейз Д. Компьютерная математика. – М.: Наука, 1990. – 400 с.

5. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математи-ческой логике и теории алгоритмов. – М.: Наука, 2001. – 234 с.

6. Столл Р. Множества. Логика. Аксиоматические теории. – М.:Просвещение, 1968. – 231 с.

Символи та позначення

N – множина усіх невід’ємних цілих чисел

N⁺ – множина усіх додатних цілих чисел

Z – множина усіх цілих чисел

Q – множина усіх раціональних чисел

R – множина усіх дійсних чисел

хА – х належить А

хА – х не належить А

АВ – А є підмножиною В

АВ – А є власною підмножиною В

АВ – А включає В

АВ – А не є підмножиною В

А=В – А та В рівні

(х) – для кожного х

Х  Y – з Х випливає Y

Х  Y – Х тоді й тільки тоді, коли Y

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

АВ – об’єднання А та В

АВ – перетин А та В

А\В – різниця А та В

А – доповнення А

АВ – симетрична різниця А та В

U – універсальна множина

В(Х) – булеан Х

<x,y> – упорядкована пара об’єктів (елементів) х та у

<x₁,…,x_n> – упорядкована n-ка (кортеж) об’єктів (елементів) x₁,…, x_n

АВ – декартів добуток А та В

А₁…А_n – декартів добуток А₁,…,А_n

Аⁿ – n-й декартів степінь А

xRy – <x,y>R

RA² – R є бінарне відношення на А

і_А – діагональ А

R^-1 – відношення, обернене до R

R₁R₂ – композиція R₁ та R₂

D(R) – область визначення R

R(R) – область значень R

F: AB – відображення А у В

F(а) – образ а при відображенні F

F^-1(а) – повний прообраз а при відображенні F

F(А) – образ множини А при відображенні F

F^-1(А) – прообраз множини А при відображенні F

А/R – фактор-множина А по R

R_r – рефлексивне замикання R

R_s – симетричне замикання R

R_t – транзитивне замикання R

R_rst – рефлексивно-симетрично-транзитивне замикання R

<A,R> – А частково упорядкована відношенням R

АВ – А та В рівнопотужні

А – потужність множини А

₀ – потужність множини N⁺

Предметний покажчик

Бієкція 31 Доповнення множини

Булеан множини 18 – абсолютне 9

Відношення 22 – відносне 9

– антисиметричне 34 Елемент

– антирефлексивне 35 – множини 3

– асиметричне 35 – максимальний 50

– бінарне 22 – мінімальний 50

– еквівалентності 41 – найбільший 50

– іррефлексивне 35 – найменший 50

– квазіпорядку 49 Замикання

– лінійного порядку 49 – рефлексивне 46

– обернене 25 – симетричне 46

– передпорядку 49 – транзитивне 46

– повного порядку 51 Індукції метод

– рефлексивне 35 – математичної 55

– симетричне 34 – трансфінітної 54

– строгого порядку 49 Кардинальне число 57

– тотожності 23 Канонічний розклад 45

– транзитивне 36 Кола Ейлера 11

– функціональне 27 Композиція відношень 25

– часткового порядку 48 Кортеж 20

– n-арне 23 Матриця 32

Відображення – діагональна 32

– множини А у множину В 28 – квадратна 32

– взаємно однозначне 31 – одинична 32

– ізоморфне 51 Множина 3

– ін’єктивне 31 – зліченна 57

– на 30 – континуальна 57

– сюр’єктивне 30 – лінійно упорядкована 49

– часткове 28 – повністю упорядкована 51

Відповідність взаємно однозначна 31 – порожня 7

Діагональ множини 23 – скінченна 57

Діаграми Венна 11 – скінченного індексу 44

Двоїстий вираз 15 – універсальна 11

Добуток – частково упорядкована 48

– декартів множин 20 Множини

– відношень 25 – еквівалентні 56

Доповнення відношення 24 – ізоморфні 51

Множини Перетин

– рівні 6 – відношень 24

– рівнопотужні 56 – множин 9

Об’єднання Підмножина 6

– відношень 24 – власна 7

– множин 8 Покриття 19

Область Потужність

– визначення відношення 28 – множини 57

– значень відношення 28 – континууму 57

Образ Предикат

– елементу 28 – n-арний 32

– множини 28 Прообраз

Операція – елементу 28

– бінарна 32 – – повний 28

– нульарна 32 – множини

– тернарна 32 Різниця

– унарна 32 – відношень 24

– n-арна 32 – множин 9

Пара – – симетрична 10

– обернена 34 Розбиття 20

– упорядкована 20 Фактор-множина 44

Перетворення множини 28 Функція 28

– n-арна 32