Теория на Множествата - Тема 1

Увод


страницата се нуждае от дописване/преглеждане


Основни понятия и записване

Всички латински букви, малки и главни ще означават множества. Всички гръцки букви ще означават свойства. Свойство - това е нещо, което елементите (т.е множествата) или имат, или нямат.

запис значение
$x = A$ равенство на множества (и малката и главната буква са множества!)
$x \in y$ принадлежност на едно множество към друго множество
$\lnot (x = A)$ с този странен знак ще бележим отрицание. В случая - отрицание на равенството, т.е $x \ne A$
$\varphi = \lnot(x \in y)$ както казахме с гръцки букви ще означаваме свойствата - в случая това е свойство за непринадлежност към $y$
$\varphi \And \psi$ логическо и, още конюнкция. Т.е това е ново свойство, което е истина, ако и двете свойства $\varphi, \psi$ са истина
$\varphi \lor \psi$ логическо или, още дизюнкция. Т.е това е ново свойство, което е истина, ако поне едно от двете свойства $\varphi, \psi$ е истина
$(\varphi \Longrightarrow \psi) \iff (\lnot \varphi \lor \psi)$ това е свойство на импликацията (следва) - Ако от $\varphi$ следва $\psi$, то или $\varphi$ не е изпълнено, или е изпълнено $\psi$ (защото е изпълнено $\varphi$, от което то следва)
$\forall x\varphi$ този запис означава, че за всяко $x$, $\varphi$ е истина. Това е различно от, всички $x$, за който е изпълнено $\varphi$
$\exists x\varphi$ този запис означава, че съществува $x$, за което $\varphi$ е изпълнено

Логически аксиоми

Сега ще напишем няколко аксиоми, който взимаме от логиката. Без тези аксиоми не може да се свърши никаква смислена работа.

без скоби със скоби
$x = x$
$x = y \Rightarrow y = x$ $(x = y) \Rightarrow (y = x)$
$x = y \And y = z \Rightarrow x = z$ $((x = y) \And (y = z)) \Rightarrow (x = z)$
$x = x' \And x' \in y \Rightarrow x \in y$ $((x = x') \And (x' \in y)) \Rightarrow (x \in y)$
$x \in y \And y = y' \Rightarrow x \in y'$ $((x \in y) \And (y = y') \Rightarrow (x \in y')$

Аксиоматика на Цермело-Френкел

Ще разгледаме аксиоматиката на тези двама симпатяги. Тя е доста основна и 'проста', но пък за сметка на това е доста непротиворечива :-)

Аксиома 0 (съществуване)

Аксиома 0:
Има поне едно множество.
$\exists x(x = x)$

Тъй като за всяко множество $x$ е изпълнено, че $x = x$, то горният запис твърди точно, че съществува поне едно множество, като не прави никакви догадки какво точно трябва да е то.

Аксиома 1 (обемност)

Аксиома 1(Аксиома за обемност):
Ако 2 множества имат едни и същи елементи, то те са равни.

(1)
\begin{align} \forall x\forall y (\forall z(z \in x \iff z \in y) \Rightarrow x = y) \end{align}

Можем да изпуснем $\forall x\forall y$, защото пишем общи твърдения.
Следствие:

(2)
\begin{align} \forall x \forall y (x = y \Rightarrow \forall z(z \in x \iff z \in y)) \end{align}

Това следствие гласи, че ако 2 множества са равни, то и елементите им са еднакви (обратното е аксиомата, затова може да го запишем с $\iff$). T.e това е обратната посока на аксиомата. Доказателството (в правата посока) става, чрез допускане на противното.

Аксиома 2 (отделяне)

Аксиома 2(Аксиомна схема за отделянето / Аксиома за ограничена абстракция):
Нека ($\bar u = u_1, u_2, \cdots, u_n$).
Нека $\varphi(x, \bar u)$ е теоретикомножествено свойство (т.е. това е израз в който има $\in$ и $=$, в който участват $x, u_1, u_2, \cdots, u_n$; ако израза е истина, значи $x$ притежава това свойство, иначе не; пример $\varphi(x,\bar u) = (x \in u_1) \And (u_2 \in x)$).
Нека $A$ е множество. Тогава съществува множество, чиито елементи са точно онези елементи на $A$, за които $\varphi(x,\bar u)$. С други 'думи':

(3)
\begin{align} \forall A\forall u_1\forall u_2 \cdots \forall u_n \exists B\forall z(z \in B \iff \varphi(z, \bar u) \And z \in A) \end{align}

Твърдение
Нека фиксираме $\varphi, A, \bar u$. Тогава съществува единствено $B$, такова че $\forall z(z \in B \iff \varphi(z, \bar u) \And z \in A)$.
Т.е твърдим, че множеството за което се говори във горната аксиоматична схема е единствено (при фиксирани $\varphi, A, \bar u$).

Доказателство:
Ще допуснем, че има 2 множества, изпълняващи условията и ще докажем че са равни.
Нека $B_1, B_2$ са такива множества, за който

(4)
\begin{eqnarray} & & \forall z(z \in B_1 \iff \varphi(z, \bar u) \And z \in A)\\ & & \forall z(z \in B_2 \iff \varphi(z, \bar u) \And z \in A)\\ \end{eqnarray}

Ще докажем, че $B_1 = B_2$.
Нека $z$ e произволно множество. Ще докажем, че $z \in B_1 \iff z \in B_2$. Нека $z \in B_1$ (другото е симетрично). Следователно (от дефиницията на $B_1$) $\quad \varphi(z, \bar u)) \And (z \in A)$. Следователно (от дефиницията на $B_2$) $\quad z \in B_2$.

(5)
\begin{align} ((z \in B_2) \iff ((\varphi(z, \bar u)) \And (z \in A))) \Rightarrow z \in B_2 \end{align}

Т.е доказахме, че $z \in B_1 \Rightarrow z \in B_2$. С аналогични разсъждения за $B_2$ стигаме до $z \in B_2 \Rightarrow z \in B_1$, т.е че $z \in B_1 \iff z \in B_2$. Понеже разсъждавахме за произвлоно $z$, тогава твърдението е вярно за всяко $z$.

(6)
\begin{align} \forall z(z \in B_1 \iff z \in B_2) \overset{\underset{\mathrm{Ax1}}{}}\Longrightarrow B_1 = B_2 \end{align}

Ще въведем малко по-олекотен запис, позволяващ построяване на свойство по Ax2. Ще записваме

(7)
\begin{align} B = \{ z | z \in A \And \varphi(z, \bar u) \} \end{align}

Твърдение(за съществуване и единственост на празното множество):
Съществува множество, в което няма никакви елементи. Формално:

(8)
\begin{align} \exists A\forall x(x \notin A) \end{align}

Доказателство:
Съгласно Ax0 (за съществуването) съществува поне едно множество. Нека вземем едно такова множество и да го означим със $C$.
Нека отбележим теоретикомножественото свойство $x \ne x$ със $\varphi (x)$.
Съгласно Ax2 (за отделянето) има единствено множество $B : \forall z(z \in B \iff z \in C \And \varphi (z))$.

(9)
\begin{eqnarray} B &=& \{ z | z \in C \And \varphi(z) \} \\ B &=& \{ z | z \in C \And z \ne z \} \\ \end{eqnarray}

Ще докажем, че $\forall x(x \notin B)$.
Нека $x$ е произволно (множество). Допускаме, че $x \in B$. Тогава $x \in C \And x \ne x$. И двете са верни, следователно е вярно и само второто - $x \ne x$. Абсурд!
Допуснатото е невярно! Следователно $x \notin B$. Tъй като разсъждавахме за произволно $x$, то твърдението е вярно и за всяко $x$! T.e $\forall x(x \notin B)$.

Сега ще докажем, че множество отговарящо на тези свойства е единствено. Т.е

(10)
\begin{align} \forall A_1\forall A_2 (\forall x(x \notin A_1) \And \forall x (x \notin A_2) \Longrightarrow A_1 = A_2) \end{align}

Нека $A_1, A_2$ са 2 произволни множества, такива че:

(11)
\begin{eqnarray} & & \forall x (x \notin A_1) \quad (\star) \\ & & \forall x (x \notin A_2) \quad (\star\star) \end{eqnarray}

Нека $z$ е произволно множество. Ще докажем, че $z \in A_1 \iff z \in A_2$ (от където по Ax1(за обемността) ще следва че множествата са равни). Твърдението което искаме да докажем е равносилно на:

(12)
\begin{align} z \notin A_1 \iff z \notin A_2 \end{align}

(1) Нека $z \notin A_1$. От $\star\star \Rightarrow z \notin A_2$ (обърнете внимание че не използвахме даденото $z \notin A_1$). T.e $z \notin A_1 \Rightarrow z \notin A_2$.
(2) Нека $z \notin A_2$. От $\star \Rightarrow z \notin A_1$ (обърнете внимание че не използвахме даденото $z \notin A_2$). T.e $z \notin A_2 \Rightarrow z \notin A_1$.
Тогава:

(13)
\begin{align} (z \notin A_1 \iff z \notin A_2) \iff (z \in A_1 \iff z \in A_2) \overset{\underset{\mathrm{Ax1}}{}}\iff A_1 = A_2 \end{align}

Доказахме съществуване и единственост на празното множество. Може да си мислим че това е 0-местна операция, т.е константа. За в бъдеще ще го отбелязваме със $\varnothing$.

Аксиома 3 (чифт)

Аксиома 3(Аксиома за чифта):
За всеки 2 множества $a$ и $b$, съществува множество A, такова че $a$ и $b$ са му елементи.

(14)
\begin{align} \forall a\forall b\exists A(a \in A \And b \in A) \end{align}

Твърдение:
За всеки 2 множества $a$ и $b$ има единствено множество $A$, такова че само $a$ и $b$ са му елементи:

(15)
\begin{align} \forall a\forall b\exists A(x \in A \iff x = a \lor x = b) \end{align}

Доказателство:
Първо ще докажем съществуване.
Нека $a$ и $b$ са произволни множества. Тогава според Ax3(аксиома за чифта) имаме $\exists B : a \in B \And b \in B$. Нека си вземем едно такова множество $B$. Образуваме си теоретикомножествено свойство: $\varphi(z, a, b) : z = a \lor z = b$. Тогава според Ax2 (аксиома за отделянето):

(16)
\begin{align} C = \{ u | u \in B \And \varphi(u, a, b) \} \end{align}

Твърдим, че $\forall x( x \in C \iff x = a \lor x = b \}$.
Нека $x$ е произволно множество.
(1) Нека $x \in C$
Тогава $x \in B \And \varphi(x, a, b)$ т.е. $x \in B \And x = a \lor x = b$. Т.е $(x \in C) \Rightarrow (x = a \lor x = b)$
(2) Нека $x = a \lor x = b$
(а) $x = a$ тогава $a \in B$, от построението на $B$.$\quad (a \in B \And x = a)$ следователно $x \in B$. Тоест $x \in B \And \varphi(x, a, b)$. (второто е от условието на случая)
(б) $x = b$ тогава $b \in B$ oт построението на $B$. $\quad (b \in B \And x = b)$ следователно $x \in B$. Тоест $x \in B \And \varphi(x, a, b)$. (второто е от условието на случая)
От (а) и (б) получаваме $(x = a \lor x = b) \Rightarrow (x \in B \And \varphi(x, a, b))$.
Т.е $(x = a \lor x = b) \Rightarrow x \in C$.
От (1) и (2) получаваме $(x \in C) \iff (x = a \lor x = b)$
Тъй като направихме разсъждението за произволно $x$, то важи за всяко $x$:

(17)
\begin{align} \forall x (x \in C \iff x = a \lor x = b) \end{align}

Единствеността се доказва тривиално със Ax1(за обемността).

Това единствено множество ще означаваме с $\{ a, b \}$.
Ако $a = b$, чифта $\{ a, a \}$ ще означаваме с $\{ a \}$. Наричаме го синглетон на $a$. (от английски singleton).

Съществува ли теоретико множествено свойство $\varphi(x)$, което описва синглетоните (т.е те го имат, останалите множества го нямат).

(18)
\begin{eqnarray} & & \exists a(x = \{ a \})\\ & & \exists a\exists A(\forall z (z \in A \iff z = a) \And x = A)\\ & & \exists a\forall z (z \in x \iff z = a) \end{eqnarray}

Сега вече може да си образуваме следната редица: празното множество, синглетона на празното множество, синглетона на синглетона на празното множество…

(19)
\begin{align} \varnothing \quad \{ \varnothing \} \quad \{\{ \varnothing \}\} \cdots \end{align}

Интересен е въпросът дали тези множества са различни :-)
Твърдение

(20)
\begin{align} \varnothing \ne \{ \varnothing \} \end{align}

Ще използваме аксиомата за обемност: $\varnothing \in \{ \varnothing \} \And \varnothing \notin \varnothing$ Следователно са различни!

По аналогичен начин може да се докаже за всяка двойка такива множества, че са различни.

До момента може да образуваме безкрайно много множества, и все пак не можем да образуваме множества, с повече от 2 елемента. Следващата аксиома ще ни помогне за образуването на множества с повече от 2 елемента.

Аксиома 4 (обединение)

Аксиома 4(аксиома за обединението):
За всяко множество $A$, съществува множество $B$, такова че всички елементи, на елементите на $A$ са негови елементи (на $B$).

(21)
\begin{align} \forall A\exists B\forall x \forall y(x \in y \And y \in A \Rightarrow x \in B) \end{align}

Означение(за единственост):
Нека $A$ е множество и $\varphi(A)$ е теоретикомножествено свойство. Ще въведем означението $\exists !A(\varphi(A)$, което е съкращение за следната формула:

(22)
\begin{align} \exists A (\varphi(A)) \And \forall A_1 \forall A_2 (\varphi(A_1) \And \varphi(A_2) \Rightarrow A_1 = A_2) \end{align}

Твърдение(единственост на обединението):
Множеството от аксиома 4 е единствено.

(23)
\begin{align} \forall A\exists !B \forall x(x \in B \iff \exists y(x \in y \And y \in A)) \end{align}

Многократно показахме подобни доказателства. В това няма нищо специално.
Това множество ще отбелязваме за кратко: $\cup A$.

(24)
\begin{align} \forall x(x \in \cup A \iff \exists y(x \in y \And y \in A)) \end{align}

Твърдение:
Не съществува множество на всички множества.
Доказателство:
Допускаме противното. Нека $B_0$ е такова множество (т.е. $\forall x (x \in B_0)$). Тогава конструираме:

(25)
\begin{align} R = \{ x | x \in B_0 \And x \notin x \} \end{align}

Изпълнено е точно едно от двете: $R \in R$ или $R \notin R$. Допуснете първо едното, после и дгугото и ще стигнете до противоречие и в двата случая.

Твърдение: За всяко множество съществува елемент, който не принадлежи на него.

(26)
\begin{align} \forall A \exists x (x \notin A) \end{align}

Доказателство: Допускаме противното. Т.е че съществува множество, което съдържа всички елементи. Противоречие с горното твърдение :)

С помощта на тази аксиома и подходящо свойство, можем да отделим от обединението само тези елементи, които са елементи на всички елементи на дадено множество.
Дефиниция(сечение)

(27)
\begin{align} \cap А \leftrightharpoons \{x | x \in \cup A \And \forall z( z \in A \Rightarrow x \in z)\} \end{align}

Познатите ни означения за обединение и сечение на две множества могат да се въведат така:

(28)
\begin{align} x \cup y \leftrightharpoons \cup \{x, y\} \end{align}
(29)
\begin{align} x \cap y \leftrightharpoons \cap \{x, y\} \end{align}

Така ако имаме множества $x, y$ и $z$ можем да образуваме множеството $\{x,y,z\} = \{x,y\}\cup\{z\}$. Ако $n$ е естествено число можем да образуваме множество с $n$ елемента.

Така ако им

Аксиома 5 (степенно множество)

Дефиниция(подмножество):
Нека $A$ и $B$ са множества. Казваме, че $A$ е подмножество на $B$ и означаваме $A \subseteq B$, ако е изпълнено:

(30)
\begin{align} \forall x (x \in A \Rightarrow x \in B) \end{align}

Тоест $A$ е подмножество на $B$ тогава и само тогава, когато всеки елемент на $A$ е също и елемент на $B$. Можем да използваме съкратеният запис за да правим теоретикомножествени свойства.

Свойства: За произволни $x, y, z$ и $w$ са изпълнени:

(31)
\begin{align} \varnothing \subseteq x \end{align}
(32)
\begin{align} x \subseteq x \end{align}
(33)
\begin{align} (x \subseteq y \And y \subseteq z) \Rightarrow x \subseteq z \end{align}
(34)
\begin{align} (x \subseteq y \And z \subseteq w) \Rightarrow x \cup z \subseteq y \cup w \end{align}
(35)
\begin{align} (x \subseteq y \And z \subseteq w) \Rightarrow x \cap z \subseteq y \cap w \end{align}
(36)
\begin{align} (x \subseteq y \And y \subseteq x) \Rightarrow x = y \end{align}

Аx5(Аксиома за степенното множество):
За всяко множество $A$, съществува множество, сред чиито елементи са всички подмножества на $A$.

(37)
\begin{align} \forall A \exists B \forall x ( x \subseteq A \Rightarrow x \in B) \end{align}

Твърдение:

(38)
\begin{align} \forall A \exists! B\forall x(x \in B \iff x \subseteq A) \end{align}

Доказва се аналогично на досегашните доказателства за единственост.

Нека бележим $B$ от аксиомата като $\mathcal P (A)$, т.е:

(39)
\begin{align} \mathcal P(A) = \{ x | x \subseteq A \} \end{align}

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

Свойства на степенното множество:

  • $\varnothing \in \mathcal P (A)$
  • $A \in \mathcal P (A)$
  • $A \subseteq B \Rightarrow \mathcal P (A) \subseteq \mathcal P (B)$
  • $\cap \mathcal P (A) = \varnothing$
  • $\cup \mathcal P (A) = A$

Твърдение:
Не съществува множество $A$, такова че $\mathcal P (A) \subseteq A$.
Доказателство:
Допускаме че съществува. Нека вземем едно такова множество и го кръстим $A_0$.

(40)
\begin{align} R_A = \{ x | x \in A_0 \And x \notin x \} \end{align}

Получаваме противоречие като проверим дали $R_A \in R_A$.

Дефиниция:
Множества, за който $A \subseteq \mathcal P(A)$ се наричат транзитивни.
За всяко транзитивно множество $z$ са в сила:

(41)
\begin{eqnarray} & &\forall y(y \in z \Rightarrow y \subseteq z)\\ & &\forall y(y \in z \Rightarrow \forall x (x \in y \Rightarrow x \in z))\\ & &\forall x \forall y (x \in y \And y \in z \Rightarrow x \in z) \end{eqnarray}

Бележим $\mathrm{Trans} (A)$ (това е просто теоретикомножествено свойство, което записваме така за по кратко - няма нищо общо с функции).

Пример за транзитивни множества са $\varnothing,\ \{ \varnothing \},\ \{ \varnothing, \{ \varnothing \} \}$.
Разбира се има множества, който не са транзитивни: $\{ \{ \varnothing \} \}$.

Свойства на транзитивните множества:

  • $\mathrm{Trans}(x) \Rightarrow \mathrm{Trans}(\cup x)$

Доказателство:
Нека $y \in \cup x$. Ще докажем, че $y \subseteq \cup x$.

(42)
\begin{eqnarray} (y \in \cup x) &\longrightarrow& (\exists z (z \in x \And y \in z)) \\ &\longrightarrow& (\exists z (z \subseteq x \And y \in z))\\ &\longrightarrow& y \in x\\ &\longrightarrow& y \subseteq \cup x \end{eqnarray}
  • Нека $x$ е множество съставено само от транзитивни множества: $\forall y(y \in x \Rightarrow \mathrm{Trans}(y))$. Тогава $\mathrm{Trans}(\cap x)$

Доказателство:
Нека $z \in \cap x$ е произволно. Тогава за произволно $y \in x$ имаме, че $z \in y$, защото $z$ e елемент от сечението, т.е. е елемент на всяко от множествата. От $\mathrm{Trans}(y)$ следва $z \subseteq y$. Тъй като това е вярно за произволно $y$, значи е вярно за всички. Тогава $z \subseteq \mathrm{Trans}(\cap x)$.

Дефиниция: $S(x) \rightleftharpoons x \cup \{ x \}$
Дефинираме формулна операция събиране с 1.
Твърдение: $\mathrm{Trans}(x) \Rightarrow \mathrm{Trans}(S(x))$.
Доказателство:
Нека $\mathrm{Trans}(x)$ и $y \in S(x)$. Тогава $y \in x \lor y \in \{ x \}$
1 сл) $y \in x$. От транзитивността на $x$ получаваме $y \subseteq x \subseteq S(x)$, т.е $y \subseteq S(x)$.
2 сл) $y \in \{ x \}$, следователно $y = x \subseteq S(x)$, т.е $y \subseteq S(x)$
Така в двата случая получихме, че $y \subseteq S(x)$, с което твърдението е доказано.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License