Множества

В настоящия курс няма да даваме точна дефиниция на понятието множество, а ще го разглеждаме като първично понятие, което се образува, когато някакви обекти се разглеждат, като едно цяло. Обектите събрани в множество се наричат елементи на множеството. Опитът е показал, че почти цялата математика може да се опише, чрез понятитето множество, поради което, в теорията на множествата, се разглеждат само множества, чиито елементи са множества. Обикновено множествата се означават с главни латински букви, а техните елементи с малки, макар че това правило не винаги се спазва, предвид обстоятелството, че елементите на множествата са също множества. Ако множеството $A$ е елемент на множеството $B$, казваме, че $A$ принадлежи на $B$, или че $B$ съдържа $A$, и записваме $A\in B$, или $B\ni A$. Ако $A$ не е елемент на $B$, записваме $A\notin B$. Ако всеки елемент на множеството $A$ е елемент на множеството $B$ казваме, че $A$ е подмножество на $B$ и записваме $A\subset B$. Ако множествата $A$ и $B$ имат общ елемент, казваме, че те се пресичат, в противен случай казваме, че те не се пресичат (са непресичащи се). За множествата се предполага, че изпълнават следните свойства (аксиоми).

1) Съществува множество без елемени, което наричаме празно множество, и което означаваме със символа $\emptyset$. При това $\emptyset\subset A$, за всяко множество $A$. (аксиома за празното множество)
2) Две множества $A$ и $B$ съвпадат, точно когато $A\subset B$ и $B\subset A$, при което записваме $A=B$ (в противен случай записваме $A\neq B$). (аксиома за идентичност)
3) Ако $A$ и $B$ са множества, то съществува множество, чиито елементи са точно $A$ и $B$, и което означаваме с $\{A,B\}$. (аксиома за сдвояване)
4) Ако $A$ е множество и $P(X)$ е твърдение, чиято истинност зависи от множеството $X$, то съществува множество, чиито елементи са всички $X\in A$, за които $P(X)$ е истина. Това множество означаваме с $\{X\in A|P(X)\}$ (аксиома за отделяне).
5) Ако $A$ е множество, то съществува множество, което означаваме с $\cup A$, чиито елементи са елементите на всеки елемент на $A$, т. е. $X\in \cup A$, точно когато съществува $Y\in A$, за което $X\in Y$ (аксиома за обединение). Множеството $\cup A$ се нарича обединение на $A$.
6) Ако $A$ е множество, то съществува множество, чиито елементи са подмножествата на $A$. Това множество се нарича степенно множество на $A$ и се означава с $\mathcal{P}(A)$.
7) Съществува индуктивно множество, т. е. съществува множество, което съдържа $\emptyset$ и заедно със всеки свой елемент $A$, съдържа и множеството $\cup\{A,\{A\}\}$, което се нарича наследник на $A$ (аксиома за безкрайността).
8) За всяко множество $A\neq\emptyset$ съществува елемент, който не съдържа никой елемент на $A$.
9) За всяко множество $A$, чиито елементи са непразни и две по две непресичащи се множества, съществува множество, което съдържа точно по един елемент от всеки елемент на $A$.

Горните аксиоми позоляват да се избегнат някои парадоксални изводи свързани със съществуването на множества.

Твърдение 1.1. Не съществува множество, чиито елементи са всички множества (множество от всички множества).
Доказателство. Да допуснем, че такова множество съществува и да го означим с $M$. Тъй като за всяко множество $X$ имаме $X\in M$, в частност това ще бъде изпълнено и за множествата $X$, за които $X\notin X$. От Аксиома 4) получаваме, че съществува множеството $$Y=\{X\in M|X\notin X\}.$$ За множеството $Y$ има две възможности, или $Y\in Y$, или $Y\notin Y$. И в двата случая получаваме противоречие с дефиницията на $Y$, т. е. множеството $Y$ не съществува. Следователно не съществува и $M$.

От аксиома 4) следват и следните свойства. За всяко множество $A\neq\emptyset$, същестува множество $\cap A$, което се нарича сечение на $A$, чиито елементи са елементите общи за всички елементи на $A$. т. е. по определение $X\in \cap A$ тогава и само тогава, когато $X\in Y$ за всички $Y\in A$. Множествата $\cup\{A,B\}$ и $\cap\{A,B\}$ означаваме съответно с $A\cup B$ и $A\cap B$, и ги наричаме обединение и сечение на $A$ и $B$, съответно. Ясно е, че $A$ и $B$ са непресичащи се, точно когато $A\cap B=\emptyset$. Разлика на множествата $A$ и $B$ наричаме множеството $A\setminus B=\{X\in A|X\notin B\}$. Ако $A\subset B$, казваме, че $B\setminus A$ е допълнение на $A$ до $B$. Наредена двойка с координати $A$ и $B$ се нарича множеството $\{\{A\},\{A,B\}\}$ и се означава с $(A,B)$. Множеството $\{(x,y)\in\mathcal P(\mathcal P(A\cup B))|x\in A, y\in B\}$ се нарича декартово произведение на $A$ и $B$ и се означава с $A\times B$.

Упражнения

1.1. Да се намери $\cup A$, ако а) $A=\{\emptyset,\{\emptyset\}\}$, б) $A=\emptyset$.
1.2. Намерете а) $\mathcal P(\emptyset)$, б) $\mathcal P(\{A\})$, в) $\mathcal P(\{A,B\})$.
1.3. Определете наредените двойки $(A,B)$, $(C,D)$, за които \newline $(A,B)\cap (C,D)\neq\emptyset$.
1.4. Покажете, че
а) $(a,b)=(c,d)$ тогава и само тогава, когато $a=c$ и $b=d$.
б) $(a,b)\in\mathcal P(\mathcal P({a,b}))$ и $a,b\in\cup(a,b)$.
в) ако $a\in A$ и $b\in A$, то $(a,b)\in\mathcal P(\mathcal P(A))$.
1.5. Покажете, че
а) $A\cup(B\cup C)=(A\cup B)\cup C$, $A\cap(B\cap C)=(A\cap B)\cap C$.
б) $A\cup B=B\cup A$, $A\cap B=B\cap A$.
в) $A\cup(B\cap C)=(A\cup B)\cap (A\cup C)$, $A\cap(B\cup C)=(A\cap B)\cup (A\cap C)$.
1.6. Покажете, че
а) $A\cup A=A$, $A\cap A=A$.
б) $A\cup \emptyset=A$, $A\cap \emptyset=\emptyset$, $A\setminus A=\emptyset$.
в) Ако $A\subset B$, то $A\cup B=B$ и $A\cap B=A$.
1.7. Покажете, че
а) $A\setminus B=A\setminus(A\cap B)$.
б) $A=(A\setminus B)\cup(A\cap B)$.
в) $(A\setminus B)\cap C=(A\cap C)\setminus B=(A\cap C)\setminus(B\cap C)$.
1.8. Покажете, че
a) $A\times B=\emptyset$ тогава и само тогава, когато $A=\emptyset$ или $B=\emptyset$,
б) $A\times (B\cup C)=(A\times B)\cup (A\times C)$,
в) $(A\cup B)\times C=(A\times C)\cup (B\times C)$,
г) $A\times (B\cap C)=(A\times B)\cap (A\times C)$,
д) $(A\cap B)\times C=(A\times C)\cap (B\times C)$,
e) $A\times (B\setminus C)=(A\times B)\setminus (A\times C)$,
ж) $(A\setminus B)\times C=(A\times C)\setminus (B\times C)$,
з) $A\times B\neq B\times A$.

Множество на естествените числа

Ествествените числа са числата, с които броим и номерираме. Както отбелязахме в предната секция, понятията в съвременната математика се основават на понятието множество. В настоящия параграф ще видим по какъв начин естествените числа могат да се дефинират, като множества с определени свойства.

Съгласно Аксиома 7) съществува индуктивно множество. От Аксиома 4) съществува множеството $\{x|x\in I$ за всяко индуктивно множество $I \},$ което наричаме множество на естествените числа и означаваме с $\mathbb{N}$. Непосредствно виждаме, че $\mathbb{N}\subset I$ за всяко индуктивно множество $I$. Действително, ако $n\in\mathbb{N}$, то $n\in I$ за всяко индуктивно множество $I$. Следователно $\mathbb{N}$ е “най-малкото“ индуктивно множество. Оттук и от Аксиома 2) на получаваме, че ако $A\subset\mathbb{N}$ е индуктивно, то $A=\mathbb{N}$. Това твърение е най-важното свойство на естествените числа и се нарича принцип на математическата индукция. С негова помощ се установяват много други свойства на естествените числа.

Забележка. Числата $0$, $1$, $2$, $3$ и т. н. могат да се дефинират по следния начин $0=\emptyset$, $1=\{\emptyset\}$, $2=\{\emptyset,\{\emptyset\}\}$, $3=\{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\}$ и т. н. Можем да забележим, че $1=\{0\}=0\cup\{0\}$, $2=\{0,1\}=1\cup \{1\}$, $3=\{0,1,2\}=2\cup\{2\}$ и т. н. В последствие ще видим, че всяко естествено число е множество, чиито елементи са всички предхождащи го естествени числа, и същевременно то е наследник на предхождащото го естествено число.

Твърдение 1.2. За всяко $n\in\mathbb{N}\setminus{\emptyset}$ съществува $k\in\mathbb{N}$, такова че $n=k\cup\{k\}$. С други думи, всяко естествено число, освен $\emptyset$, е наследник на някое естествено число.
Доказателство. Тъй като за всяко $k\in\mathbb{N}$ е вярно $k\cup{k}\neq\emptyset$, не съществува $k\in\mathbb{N}$, за което $\emptyset=k\cup{k}$.
Нека $A=\{n\in\mathbb{N}|$съществува $ k\in\mathbb{N},$ за което $n=k\cup\{k\}\}\cup\{\emptyset\}$. Тогава $\emptyset\in A$ и ако $n\in A$, то $n\cup\{n\}=(k\cup\{k\})\cup\{k\cup\{k\}\}$, и следователно $n\cup\{n\}\in A$. Тогава $A$ е индуктивно и от принципа на математическата индукция получаваме $A=\mathbb{N}$.

Множеството $A$ се нарича транзитивно, ако всеки елемент на $A$ е подмножество на $A$.

Твърдение 1.3. Всяко естествено число е транзитивно множество.
Доказателство. Нека $A$ е множеството от всички естествени числа, които са транзитивни множества, т. е. $A=\{x\in\mathbb{N}|x$ е транзитивно$\}$.Тогава $\emptyset\in A$ (тъй като елементите на $\emptyset$ множество притежават всяко свойство) и ако $n\in A$, то $n$ е транзитивно и $n\subset\cup\{n,\{n\}\}$. Нека $x\in\cup\{n,\{n\}\}$, тогава или $x\in n$, или $x\in\{n\}$. В първия случай $x\subset n$, тъй като $n$ е транзитивно, откъдето $x\subset n\subset \cup\{n,\{n\}\}$. Във втория случай, $x=n\subset\cup\{n,\{n\}\}$. Следователно $\cup\{n,\{n\}\}$ е транзитивно, т. е. $\cup\{n,\{n\}\}\in A$. Следователно $A\subset\mathbb{N}$ е индуктивно множество. От принципа на математическата индукция получаваме $A=\mathbb{N}$.

По аналогичен начин можем да установим, че $\mathbb{N}$ е транзитивно множество. т. е. всяко естествено число е подмножество на множеството от естествените числа.

Твърдение 1.4. Множеството $\mathbb{N}$ е транзитивно.
Доказателство. Нека $A$ е множеството от всички естествени числа, които са подмножества на $\mathbb{N}$ т. е. $A=\{n\in\mathbb{N}|n\subset \mathbb{N}\}$. Тогава $\emptyset\in A$, и ако $n\in A$, то $n\subset\mathbb{N}$. Нека $x\in\cup\{n,\{n\}\}$. Тогава или $x\in n$, или $x\in\{n\}$. В първия случай $x\in\mathbb{N}$, тъй като $n\subset \mathbb{N}$, a във втория $x=n\in\mathbb{N}$. Следователно $\cup\{n,\{n\}\}\subset\mathbb{N}$, т. е. $\cup\{n,\{n\}\}\in A$, което показва, че $A\subset \mathbb{N}$ е индуктивно. От принципа на индукцията получаваме $A=\mathbb{N}$.

Твърдение 1.5.
а) За всички $m,n\in\mathbb{N}$ имаме $m\in n$, точно когато $m\cup{m}\in n\cup{n}$,
б) За всяко $n\in\mathbb{N}$, $n\notin n$.
Доказателство.
а) Ако $m\cup\{m\}\in n\cup\{n\}$, то $m\cup\{m\}\in n$ или $m\cup\{m\}=n$. Тъй като $n$ е транзитивно (Твърдение 4), и в двата случая имаме $m\cup\{m\}\subset n$. От друга страна, тъй като $m\in m\cup\{m\}$, получаваме $m\in n$. Нека $m\in n$. Тогава множеството $A=\{n\in\mathbb{N}|m\cup\{m\}\in n\cup\{n\}$ за всяко $m\in n\}$ е индуктивно.
б) използвайки a) проверяваме, че $\{n\in\mathbb{N}|n\notin n\}$ е индуктивно.

Забележка. Принципът на математическата индукция често се прилага в следната форма: “Нека $P(X)$ е твърдение, такова че $P(\emptyset)$ е вярно и за всяко $k\in\mathbb{N}$ от верността на $P(k)$ следва верността на $P(k\cup\{k\})$. Тогава $P(n)$ е вярно за всяко $n\in\mathbb{N}$“. По същество първото изречение е формулировка на твърдението, че множеството $\{n\in\mathbb{N}|P(n)\}$ е индуктивно, а второто изречение е заключението в принципа на математическата индукция, че множеството $\{n\in\mathbb{N}|P(n)\}$ съвпада с $\mathbb{N}$.

В следващите параграфи ще продължим да развиваме свойствата на естествените числа.

Упражнения

1.9. Докажете, че следните условия са еквивалентни
а) $A\subset\mathcal P(A)$, б) $\cup A\subset A$,
в) ако $X\in A$, то $X\subset A$.
1.10. Докажете, че ако $A$ е транзитивно, то $A\cup {A}$ е транзитивно.
1.11. Докажете, че ако всеки елемент на $A$ е транзитивно множество, то $\cup A$ и $\cap A$ (при $A\neq\emptyset$) са транзитивни.
1.12. Докажете, че $A$ е транзитивно множество, тогава и само тогава, когато
a) $\cup(A\cup{A})=A$,
б) $\mathcal P(A)$ е транзитивно
Упътване. Проверете, че за всеки две множества $\cup(X\cup Y)=(\cup X)\cup(\cup Y)$

назад