Тема 01

Множества. Операции с множества - дефиниции и свойства

Множество

Множеството е първично понятие. Това означава, че не можем да дадем точна дефиниция за същността му. Хубавото в случая, е че хората имат интуиция за това какво е множество - а именно съвкупност от елементи. Разбира се това обяснение е много общо, но ще трябва да се задоволим с него.¹

Множества могат да се задават по няколко начина:

A = {a, b, 1, cd, ябълка}	чрез изброяване на всички елементи
А = {x | x е просто от вида 5k + 3}	чрез задаване на условие, което елементите удовлетворяват
A = {1, 2, 3, …}	Като зададем първите няколко и останалите очевидно се вижда кои са :)

Елементите на едно множество са неповтарящи се. Тоест, множествата {1, 1, 2} и {1, 2} са всъщност едно и също множество.
Също така, елементите са несортирани: {1, 2} = {2, 1}.

Празно множество

Множеството, което не съдържа нито един елемент е специално и играе важна роля в доказателствата на… множество теореми.
Нарича се още "празното множество" и се бележи с $\varnothing$. Празното множество по дефиниция е подмножество на всяко друго(всеки елемент от него - тоест никой - принадлежи на всяко множество).

Подмножество

Дефиниция:
Казваме че:
A е подмножество на B, ако за всеки елемент x от A следва че x е и от B.

(1)

\begin{array} {l} A \subset B \iff \forall x \in A \Rightarrow x \in B\\ \end{array}

Казваме, че A е съществено подмножество на B ако А е нетривиално подмножество на B. Тоест, ако не се съвпада с B и ако не е празното множество.

А не е подмножество (знака за подмножество с черта отгоре) на B, ако съществува елемент x от A, такъв че x не е от B.

(2)

\begin{array} {l} A \overline\subset B \iff \exists x \in A \rightarrow x \notin B\\ \end{array}

Еквивалентност на множества

Дефиниция:
Казваме, че A = B(A и B са "еквивалентни", или още "съвпадат") когато двете множества се състоят от едни и същи елементи.

(3)

\begin{array} {l} \\ A = B \iff A \subset B \mbox{ u } B \subset A\\ \end{array}

Ще докажем тази очевидна теорема, защото тя ще помага много в бъдеще.

Доказателство:
Теоремата има 2 посоки. За щастие правата посока следва от дефиницията, защото 'еднакви елементи' всъщност значи, че всеки елемент от първото множество е и елемент от второто (т.е A ⊂ B), както и, че всеки елемент от второто е и елемент на първото (т.е B ⊂ A). С което правата посока е доказана :).
За да докажем 2рата посока ще използваме дефиницията.
Ще допуснем, че A ≠ B. Т.е без ограничение на общността ще считаме, че съществува елемент от A, който не е от B. (Без ограничение на общността означава, че доказателството върви аналогично, ако изберем и елемент от B, който не е в A). По дефиницията за подмножество обаче следва, че A не е подмножество на B, което противоречи на даденото (че A ⊂ B и B ⊂ A).

Основни операции с множества

Сега ще дефинираме основните операции с множества - обединение, сечение, разлика.
Тези операции приемат аргументи множества и връщат отново множество. Тоест, възможно е да дефинираме някакво множество като някаква операция с вече съществуващи множества.
Например, нека да си вземем обединението на всички множества, които никой никога не си е вземал, за да илюстрира свойство. Опа, изчезнаха. Е, нищо, да продължаваме с дефинициите.

Дефиниции:

Обединение

Обединение на две множества A и B наричаме такова множество C, което съдържа всички елементи както от A, така и от B.
Забележете, че в едно множество няма повтарящи се елементи. Ако нещо се среща и в двете множества, то се взема веднъж.
Бележи се по следния начин:

(4)

\begin{align} A \cup B &=& \{ x | x \in A\ \mbox{ or }\ x \in B\} \end{align}

Сечение

Сечение на две множества A и B наричаме такова множество C, което съдържа всички елементи, които принадлежат едновременно и на A, и на B.
Бележи се така:

(5)

\begin{align} A \cap B &=& \{ x | x \in A \mbox{ and } x \in B\} \end{align}

Разлика

Разлика на множествата A и B е множеството C, което съдържа всички елементи от A, които в същото време не са елементи от B.

(6)

\begin{align} A \setminus B &=& \{x | x \in A \mbox{ and } x \notin B\} \end{align}

Свойства на операциите с множества

Това са най-важните свойства, които се ползват при работа с множества (работа - т.е развиване на изрази с множества):

1. А ∪ B = B ∪ A (комутативност)
2. (A ∪ B) ∪ C = A ∪ (B ∪ C) (асоциативност)
3. А ∩ B = B ∩ A (комутативност)
4. (A ∩ B) ∩ C = A ∩ (B ∩ C) (асоциативност)
5. (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C)
6. (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C)
7. A \ (B ∪ C) = (A \ B) ∩ (A \ C)
8. A \ (B ∩ C) = (A \ B) ∪ (A \ C)

Доказателствата на тези свойства са лесни и се извършват последователно в две посоки. Първо приемаме, че някой елемент принадлежи на лявата част и доказваме, че принадлежи и на дясната. След това - обратното.
Да разгледаме например седмо свойство - ще докажем че всяка от двете страни е подмножество на другата:

(7)

\begin{array} {l} A \setminus (B \cup C) \subset (A \setminus B) \cap (A \setminus C) \\ \begin{eqnarray} \forall x \in A \setminus (B \cup C) &\Rightarrow& x \in A \mbox{ and } x \notin (B \cup C)\\ &\Rightarrow& x \in A \mbox{ and } x \notin B \mbox{ and } x \notin C\\ &\Rightarrow& x \in (A \setminus B) \mbox{ and } x \in (A \setminus C)\\ &\Rightarrow& x \in (A \setminus B) \cap (A \setminus C) \\ \end{eqnarray} \\ \end{array}

Останалите са, както казва всеки мързелив автор от шест хиляди години насам, за упражнение на читателя.

---

Автори: Искрен Чернев и Михаил Минков

Footnotes

1. Добре осмислете понятието "множество", нищо че е първично.