Увод
страницата се нуждае от дописване/преглеждане
Основни понятия и записване
Всички латински букви, малки и главни ще означават множества. Всички гръцки букви ще означават свойства. Свойство - това е нещо, което елементите (т.е множествата) или имат, или нямат.
запис | значение |
---|---|
$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 множества имат едни и същи елементи, то те са равни.
Можем да изпуснем $\forall x\forall y$, защото пишем общи твърдения.
Следствие:
Това следствие гласи, че ако 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)$. С други 'думи':
Твърдение
Нека фиксираме $\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$ са такива множества, за който
Ще докажем, че $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$.
Т.е доказахме, че $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)Ще въведем малко по-олекотен запис, позволяващ построяване на свойство по Ax2. Ще записваме
(7)Твърдение(за съществуване и единственост на празното множество):
Съществува множество, в което няма никакви елементи. Формално:
Доказателство:
Съгласно Ax0 (за съществуването) съществува поне едно множество. Нека вземем едно такова множество и да го означим със $C$.
Нека отбележим теоретикомножественото свойство $x \ne x$ със $\varphi (x)$.
Съгласно Ax2 (за отделянето) има единствено множество $B : \forall z(z \in B \iff z \in C \And \varphi (z))$.
Ще докажем, че $\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)Нека $A_1, A_2$ са 2 произволни множества, такива че:
(11)Нека $z$ е произволно множество. Ще докажем, че $z \in A_1 \iff z \in A_2$ (от където по Ax1(за обемността) ще следва че множествата са равни). Твърдението което искаме да докажем е равносилно на:
(12)(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$.
Тогава:
Доказахме съществуване и единственост на празното множество. Може да си мислим че това е 0-местна операция, т.е константа. За в бъдеще ще го отбелязваме със $\varnothing$.
Аксиома 3 (чифт)
Аксиома 3(Аксиома за чифта):
За всеки 2 множества $a$ и $b$, съществува множество A, такова че $a$ и $b$ са му елементи.
Твърдение:
За всеки 2 множества $a$ и $b$ има единствено множество $A$, такова че само $a$ и $b$ са му елементи:
Доказателство:
Първо ще докажем съществуване.
Нека $a$ и $b$ са произволни множества. Тогава според Ax3(аксиома за чифта) имаме $\exists B : a \in B \And b \in B$. Нека си вземем едно такова множество $B$. Образуваме си теоретикомножествено свойство: $\varphi(z, a, b) : z = a \lor z = b$. Тогава според Ax2 (аксиома за отделянето):
Твърдим, че $\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$:
Единствеността се доказва тривиално със Ax1(за обемността).
Това единствено множество ще означаваме с $\{ a, b \}$.
Ако $a = b$, чифта $\{ a, a \}$ ще означаваме с $\{ a \}$. Наричаме го синглетон на $a$. (от английски singleton).
Съществува ли теоретико множествено свойство $\varphi(x)$, което описва синглетоните (т.е те го имат, останалите множества го нямат).
(18)Сега вече може да си образуваме следната редица: празното множество, синглетона на празното множество, синглетона на синглетона на празното множество…
(19)Интересен е въпросът дали тези множества са различни :-)
Твърдение
Ще използваме аксиомата за обемност: $\varnothing \in \{ \varnothing \} \And \varnothing \notin \varnothing$ Следователно са различни!
По аналогичен начин може да се докаже за всяка двойка такива множества, че са различни.
До момента може да образуваме безкрайно много множества, и все пак не можем да образуваме множества, с повече от 2 елемента. Следващата аксиома ще ни помогне за образуването на множества с повече от 2 елемента.
Аксиома 4 (обединение)
Аксиома 4(аксиома за обединението):
За всяко множество $A$, съществува множество $B$, такова че всички елементи, на елементите на $A$ са негови елементи (на $B$).
Означение(за единственост):
Нека $A$ е множество и $\varphi(A)$ е теоретикомножествено свойство. Ще въведем означението $\exists !A(\varphi(A)$, което е съкращение за следната формула:
Твърдение(единственост на обединението):
Множеството от аксиома 4 е единствено.
Многократно показахме подобни доказателства. В това няма нищо специално.
Това множество ще отбелязваме за кратко: $\cup A$.
Твърдение:
Не съществува множество на всички множества.
Доказателство:
Допускаме противното. Нека $B_0$ е такова множество (т.е. $\forall x (x \in B_0)$). Тогава конструираме:
Изпълнено е точно едно от двете: $R \in R$ или $R \notin R$. Допуснете първо едното, после и дгугото и ще стигнете до противоречие и в двата случая.
Твърдение: За всяко множество съществува елемент, който не принадлежи на него.
(26)Доказателство: Допускаме противното. Т.е че съществува множество, което съдържа всички елементи. Противоречие с горното твърдение :)
С помощта на тази аксиома и подходящо свойство, можем да отделим от обединението само тези елементи, които са елементи на всички елементи на дадено множество.
Дефиниция(сечение)
Познатите ни означения за обединение и сечение на две множества могат да се въведат така:
(28)Така ако имаме множества $x, y$ и $z$ можем да образуваме множеството $\{x,y,z\} = \{x,y\}\cup\{z\}$. Ако $n$ е естествено число можем да образуваме множество с $n$ елемента.
Така ако им
Аксиома 5 (степенно множество)
Дефиниция(подмножество):
Нека $A$ и $B$ са множества. Казваме, че $A$ е подмножество на $B$ и означаваме $A \subseteq B$, ако е изпълнено:
Тоест $A$ е подмножество на $B$ тогава и само тогава, когато всеки елемент на $A$ е също и елемент на $B$. Можем да използваме съкратеният запис за да правим теоретикомножествени свойства.
Свойства: За произволни $x, y, z$ и $w$ са изпълнени:
(31)Аx5(Аксиома за степенното множество):
За всяко множество $A$, съществува множество, сред чиито елементи са всички подмножества на $A$.
Твърдение:
(38)Доказва се аналогично на досегашните доказателства за единственост.
Нека бележим $B$ от аксиомата като $\mathcal P (A)$, т.е:
(39)Разбира се горният запис не е много валиден, тъй като не казваме от кое множество филтрираме елементите, но аксиомата е точно заради това - сигурни сме, че такова множество съществува.
Свойства на степенното множество:
- $\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$.
Получаваме противоречие като проверим дали $R_A \in R_A$.
Дефиниция:
Множества, за който $A \subseteq \mathcal P(A)$ се наричат транзитивни.
За всяко транзитивно множество $z$ са в сила:
Бележим $\mathrm{Trans} (A)$ (това е просто теоретикомножествено свойство, което записваме така за по кратко - няма нищо общо с функции).
Пример за транзитивни множества са $\varnothing,\ \{ \varnothing \},\ \{ \varnothing, \{ \varnothing \} \}$.
Разбира се има множества, който не са транзитивни: $\{ \{ \varnothing \} \}$.
Свойства на транзитивните множества:
- $\mathrm{Trans}(x) \Rightarrow \mathrm{Trans}(\cup x)$
Доказателство:
Нека $y \in \cup x$. Ще докажем, че $y \subseteq \cup x$.
- Нека $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)$, с което твърдението е доказано.