Комбінаторика

Поняття множини. Операції над множинами. Об’єднання і переріз двох множин. Різниця і доповненя множин. Множини з відношеннями. Прямий (декартів) добуток множин. Бінарні відношення. Відношення еквівалентності. Відношення порядку. Предикати.
Краткое сожержание материала:

33

Розділ I. Елементи теорії множин

§1.1. Поняття множини

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

Об'єкти, із яких складається множина, називаються її елементами. Множини позначається великими буквами, а її елементи малими. Те, що елемент а належить множені А записується так а А. Запис а є А або а А означає, що елемент а не належить множені А.

Окремі найважливіші множини мають загальноприйняте позначення

· N - множина натуральних чесел (1, 2, 3, 4…)

· Z - множина цілих чисел (…-3, -2, -1, 0, 1, 2, 3…)

· Q - множина раціональних чисел (Z + дробові числа)

· I - множина всіх ірраціональних чисел

· R - множина дійсних чисел ( Q + ірраціональні чисела)

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

Множина, яка містить скінчену кількість елементів називається скінченою.

Запис A={a₁, a₂, a₃… a_n} означає, що множина А скінчена і містить n елементів. Множина Х={x₁, x₂… , x_n….} - є незкінченою. Множина, яка не містить жодного елементу називаєтся порожньою і позначається символом .

Приклади: Множина дійсних коренів рівняння x²+1=0, множина усіх цілих чисел, що діляться на 4, але не діляться на 2.

Нехай P(x) - деяка властивість (закон, правило, форма) числа х, тоді запис

{x| P(x)} означає множину всіх тих чисел х, для яких виконується властивість Р(х). Наприклад:

1. {x|x є R, x² + 3x + 4 =0} множина тих дійсних чисел х, які є розв'язками рівняння x² + 3x + 4 =0.

2. А={x| x є z, |x|?100} - множина тих цілих чисел модуль яких не більший за 100, тобто елеменетами множини А є цілі числа по порядку від -100 до +100.

Множину можна подати у вигляді відрізку на числовій осі:

x

-3 -2 -1 0 1 2 3 4 5 6

мал.1.1

А={x| x є R, 2 ? x < 5} A=[2,5)

Числові проміжки позначаються так:

Нехай а і b - дійсні числа, причому а<b.

Розглянемо числові множини.

· [a; b] = {x|a ? x ? b } - закритий відрізок, сегмент;

· (a; b) = {x|a < x < b } - відкритий інтервал;

· (a; b] = {x|a < x ? b } - напівінтервал, напіввідкритий інтервал,

· [a; b) = {x|a ? x < b } - напівсегмент;

· (- ?; + ?) = {x|- ? < x < + ? } - нескінченно відкритий інтервал.

Введемо інтервал, що називається околом точки. Нехай х₀ - довільне дійсне число. Околом точки х₀ називається будь-який інтервал (б; в), що містить цю точку, тобто б < x₀ < в. Так околом точки x₀ = 1 є інтервал ( - 0,5; 1,5), (0,2) і т. д.

Інтервал ( x₀ - Е, x₀ + Е ), де Е > 0 називається Е - околом точки х₀, при цьому точку х₀ називають центром, а число Е - радіусом околу. Цей окіл буде досить малий, якщо число Е теж буде мале.

Нехай задано дві множини А і В. Якщо кожен елемент множини А є елементом мнгожини В, то множину А називають підмножиною множини В і пишуть АВ (А міститься в В).

Наприклад N Z. Очевидно, що кожна множина є своєю підмножиною, а порожня множина є підмножиною будьякої множини.

Якщо множини А і В містять одні і ті ж елементи, тобто АВ і ВА, то їх називають рівними і пишуть А=В.

Множину, різні підмножини якої доводиться розглядати в процесі вивчення якогось питання, називають універсальною множиною.

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

А не має спільних елементів з В і С , а В і С мають спільні елементи.

мал.1.2

§1. 2 Операції над множинами. Об'єднання і переріз двох множин.

Об'єданням двох множин А і В, називається множина А U В, елементи якої належать хочаб одній із цих множин.(мал.1.3)

мал.1.3

Об'єдання декількох множин.

A_i = A₁ U A₂ U A₃ U…U A_n

A_i ={x | x є А₁ або х є А₂ або х є А₃ або …х є А_n }

Перерізом двох множин А і В називається множина А ? В елементи якої належать як і множині А, так і множені В. (мал.1.4)

А ? В={x | х є А і х є В}

A_i={x | x є А₁ і х є А₂, х є А₃…х є А_n}

мал.1.4

Властивості об'єдання і перерізу множин:

1. Комутативний (переставний) закон

А U B = В U А;

А ? В = В ? А;

2. Асоціативний (сполyчний) закон.

А ? (В ? С) = (А ? В) ? С

А U (В U С) = (А U B) U С

3. Дистрибутивний (розподільний) закон.

А U (В ? С)=(А U B) ? (А U С)

А ? (В U С)=(А ? В) U (А ? С)

4. А U Ш = А.

5. А ? Ш = Ш.

Ці закони легко довести за допомогою діаграм. Доведемо 3-й дистрибутивний закон:

А U (В С) = (А U B) ? (А U С)

А U (В U С) (А U B) ? (А U С)

мал.1.5 мал.1.6

А ? (В U С)=(А ? В) U (А ? С)

А ? (В U С) (А ? В) U (А ? С)

мал.1.7 мал.1.8

§1. 3 Різниця і доповненя множин.

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

Різницею множин А та В називається множина А\В, яка складається зусіх тих елементів, які належать множині А і не належать В.(мал.1.9)

А \ В = {x | x є A I x ў B}

мал.1.9

Властивості різниці :

· А \ В ? В \ А - не комутативна .

· А \ (В \ С) ? (А \ В) \ С - не асоціативна

· А U Ш = А.

· А ? Ш = Ш.

· (B U C) \ A=(B \ A) U (C \ A) - дисрибутивний закон віднімання відносно об'єдання;

· (B ? C) \ A = (B \ A) ? (C \ A) - дистрибутивний закон віднімання відносно перерізу;

Якщо А є В, то різницю В \ А називають доповненням множини А до множини В і записують - = В \ А

мал.1.10

Отже, доповненням до підмножини А в множину В називається множина всіх елементів із множини В, які не належать А

Властивості доповнення, якщо АВ

Для довільних підмножин А і В універсальної множини М, доповнення до множин А і В дорівнюють перерізу множин , а доповнення до перізу множин А і В дорівнює об'єднанню їх доповнень .

Доведемо це...