Основе теорије скупова

Основе и нотација

Скупови су добро дефинисисане колекције елемената. Основна релација у теорији скупова је припадност. Пишемо $a\in A$ да би рекли да елемент $a$ припада скупу $A$ или да је $a$ елемент из скупа $A$. Празан скуп или скуп без елемената означаваћемо симболом $\emptyset$.

Кажемо да је $A$ подскуп скупа $B$, односно $A\subseteq B$, ако је сваки елемент $A$ елемент скупа $B$. Дакле, $A=B$ ако и само ако је $A\subseteq B$ и $B\subseteq A$. Специјални случај $\emptyset \subseteq A$, за сваки скуп $A$.

Базичне операције над два скупа $A$ и $B$:

Скуп $A\cup B$ се зове унија скупова $A$ и $B$, елементи уније су елементи скупа $A$ и скупа $B$.

Скуп $A\cap B$ се зове пресек скупова $A$ and $B$, елементи пресека су заједнички елемент скупова $A$ и $B$.

Скуп $A\smallsetminus B$ се зове разлика скупова $A$ и $B$, елементи разлике су сви елементи скупа $A$ који не припадају скупу $B$

Унија и пресек имају следећа својства:

Комутативност: $A\cup B=B\cup A$; $A\cap B=B\cap A$

Асоцијативност: $A\cup (B\cup C)=(A\cup B)\cup C$; $A\cap (B\cap C)=(A\cap B)\cap C$

Дистрибутивнност: $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$; $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$

Нотација: $\{a,b,c\}$ скуп чији су елементи $a,b,c$ ; $\{a\}$ скуп који има само један елемент $a$

Идемпотенција: $A\cup A=A;A\cap A=A$; $A\cup \emptyset =A$; $A\cap \emptyset =\emptyset$; $A\smallsetminus A=\emptyset$

Ако је $A\subseteq B$, тада је $A\cup B=B$; $A\cap B=A$

Ако је $a=b$ тада је $\{a,b\}=\{a\}$ и $\{a,b\}=\{b,a\}$

Дефиниција уређеног пара

Уређени пар се дефинише као $(a,b)=\{\{a\},\{a,b\}\}$ Својства уређеног пара: ако је $(a,b)=(c,d)$ онда је $a=c$ и $b=d$; ако је $a\neq b$ онда је($a,b)\neq (b,a)$.

Уређена тројка: $(a,b,c)=(a,(b,c))$ Уређена $n$-торка: $(a_{1},\dots ,a_{n})=(a_{1},(a_{2},\dots ,a_{n}))$.

Дефинифија картезијанског производа

Картезијски производ $A\times B$ два скупа $A$ и $B$ је скуп свих уређених парова $(a,b)$ таквих да је $a\in A$ и $b\in B$.

Картезијски производ $A_{1}\times \dots \times A_{n}$ скупова $A_{1},\dots ,A_{n}$ је скуп свих $n$-торки$(a_{1},\dots ,a_{n})$ за које је $a_{i}\in A_{i}$ за свако $1\leq i\leq n$.

Релације

Бинарна релација на скупу $A$ је скуп уређених парова елемената из $A$ који је подскуп скупа $A\times A$. У општем случају, $n$-арна релација дефинисана на $A$ је подскуп скупа $A^{n}$.

Својства бинарне релације

рефлексивност: $(a,a)\in R$ важи за свако $a\in A$

симетричност: $(b,a)\in R$ кад год је $(a,b)\in R$

транзитивност: $(a,c)\in R$ кад год је $(a,b)\in R$ и $(b,c)\in R$.

Ако је релација у исто време рефлексивна, симетрична и транзитивна онда се таква релација зове релација еквиваленције.

Ако је $R$ релација еквиваленције на скупу $A$ и $(a,b)\in R$ тада се каже да су $a$ и $b$ are $R$-еквивалентни. За свако $a\in A$ a класа еквиваленције, означена са $[a]R$, је скуп свих елемената скупа $A$ који су $R$-еквивалентни $a$. Скуп свих $R$-еквивалентних класа се зове скуп количник и означава се са $A/R$. Лако се може показати да је $A/R$ партиција скупа $A$, тј. ни један елемент из $A/R$ није празан, било која два елемента из $A/R$ су дисјунктна, а сваки $a\in A$ припада тачно једном елементу скупа $A/R$, тј. класи $[a]R$.

Ако је $R$ бинарна релација онда се често пише $aRb$ уместо $(a,b)\in R$.

За бинарну релацију $R$ дефинисану на скупу $A$ се каже да је антисиметрична ако је $a=b$ кад год је $aRb$ и $bRa$. Релација $R$ дефинисана на скупу $A$ и која је рефлекцивна, антисиметрична и транзитивна се зове (рефлексивни) парцијални поредак. Ако из $R$ одстранимо све парове $(a,a)$ за свако $a\in A$ тада ћемо добити строги рефлексивни поредак.

Функције

(Унарном, 1-арном) функцијом на скупу $A$ се назива бинарна релација $F$ на $A$ таква да за свако $a\in A$ постоји тачно један пар $(a,b)\in F$. Елемент $b$ се зове вредност релације $F$ у $a$, и означава са $F(a)$. Скуп $A$ је домен функције $F$. Ознака $F:A\rightarrow B$ се чита као $F$ је функција на домену $A$ и вредностима у скупу $B$. За $n\geq 2$, $n$-арна функција на $A$ је функција $F:A^{n}\rightarrow B$, за неко $B$.

Функција $F:A\rightarrow B$ се зове један-у-један функција ако за све елементе $a$ и $b$ из $A$ и $a\neq b$ важи да је $F(a)\neq F(b)$. Функција $F:A\rightarrow B$ је пресликавање скупа $A$ на скуп $B$ ако и само ако за свако $b\in B$ постоји неко $a\in A$ такво да је $F(a)=b$. Функција $F:A\rightarrow B$ је бијективна ако је један-у-један и на. Бијекција $F:A\rightarrow B$ успоставља један-у-један пресликавање елемената из $A$ у елементе из $B$. Функција идентичности на скупу $A$, записана као $Id:A\rightarrow A$, а коју чине сви парови $(a,a)$, где је $a\in A$ је пример тривијалне бијекције.

Ако су дате функције $F:A\rightarrow B$ и $G:B\rightarrow C$, кажемо да је композиција функција $F$ и $G$, записана као $G\circ F$, она функција $G\circ F:A\rightarrow C$ чији су елементи сви парови $(a,G(F(a)))$, где је $a\in A$. Ако су $F$ и $G$ бијекције, онда је $G\circ F$ бијекција.

Формуле

Формални језик теорије скупова је језик првог реда чији је једини не-логични симбол симбол бинарне релације припадности $\in$.

Ако је дата формула $\phi (x,y_{1},\dots ,y_{n})$ у језику теорије скупова и скупови $A,B_{1},\dots ,B_{n}$, онда се може формирати скуп свих елемената из $A$ који задовољава формулу $\phi (x,B_{1},\dots ,B_{n})$. Овај скуп се записује са $\{a\in A:\phi (a,B_{1},\dots ,B_{n})\}$. Следи неколико примера формуле

$\emptyset ={a\in A:a\neq a}$

$A=\{a\in A:a=a\}$

$A\setminus B={a\in A:a\notin B}$

$A\cap B=\{a\in A:a\in B\}$

Ако су $B$ и $C$ подскупови скупа $A$, онда важи формула

$B\cup C=\{a\in A:a\in B\lor a\in C\}$

Ако је дат подскуп $C\subseteq A\times B$ каже се да је пројекција $C$ (на прву координату) скуп

$\{a\in A:\exists b\in B((a,b)\in C)\}$

Ако су дати формула $\phi (x,y_{1},\dots ,y_{n})$ и скупови $B_{1},\dots ,B_{n}$, онда се не може формирати скуп свих скупова који задовољава формулу $\phi (x,B_{1},\dots ,B_{n})$. Нека је $\phi (x)$ формула и $x\notin x$. Ако би $A$ био скуп свих скупова који задовољава формулу $\phi$, тада $A\in A$ ако и само ако $A\notin A$. (Раселов парадокс, 1901).

Ординали

Ординале, који спадају у трансфинитне бројеве, а служе као типови уређења, је увео Кантор. Први ординал се диефинише као $\emptyset$. Ако је дат ординал $\alpha$ онда је следећи већи ординал, који се зове и непосредни следбеник ординала $\alpha$, скуп $\alpha \cup {\alpha }$. Коначни ординални бројеви су они ординали који се добију почевши са $\emptyset$ а затим се конструишу следећи ординали.

У теорији скупова природни бројеви су дефинисани као коначни ординали, тј.:

$0=\emptyset$

$1=\emptyset \cup \{\emptyset \}=\{\emptyset \}$

$2=\{\emptyset \}\cup \{\{\emptyset \}\}=\{\emptyset ,\{\emptyset \}\}$

$3=\{\emptyset ,\{\emptyset \}\}\cup \{\{\emptyset ,\{\emptyset \}\}\}=\{\emptyset ,\{\emptyset \},\{\emptyset ,\{\emptyset \}\}\}$

...

Примећује се да је $1=\{0\}$, $2=\{0,1\}$, $3=\{0,1,2\}$, ..., $n=\{0,1,2,\dots ,n-1\}$ тј. сваки природни број је скуп својих претходника.

За скуп $A$ се каже да је коначан ако постоји 1-у-1 пресликавање између неког природног броја $n$ и елемената скупа $A$, тј. бијекција $F:n\rightarrow A$, у ком се случају каже да скуп $A$ има $n$ елемената. За неки скуп се каже да је бесконачан ако није коначан.

Скуп свих коначних ординала ћемо означавати са $(\omega )$. На тај начин је $\omega$ скуп $N$, тј. скуп природних бројева при чему је $\omega$ први бесконачни ординал. Ординал $\omega$ није следбеник ни једног ординала и назива се гранични ординал. Техника рачунања ординала следбеника је већ описана. Треба уочити да је немогуће имати скуп свих ординала јер би у томе случају имали нови гранични ординал што је немогуће, јер смо већ дефинисали гранични ординал.

Као што је случај са коначним ординалима, сваки бесконачни ординал је скуп својих претходника. Последица ове чињенице је да је релација $\in$ релација стриктног добро дефинисаног поретка ординала, тј. за било која два ординала $\alpha$ и $\beta$ кажемо да је $\alpha <\beta$ ако и само ако је $\alpha \in \beta$.

Пребројиви и непребројиви скупови

Ако је $A$ коначан скуп онда постоји бијекција $F:n\rightarrow A$ између скупа природних бројева $N$ и скупа $A$. Сви коначни скупови су пребројиви, тј. $F(0)$ је први елемент скупа $A$, $F(1)$ други, итд. Било који бесконачни скуп $A$ је пребројив ако постоји бијекција $F:\omega \rightarrow A$ између скупа природниh бројева и скупа $A$. Лако је показати да је

• сваки бесконачни подскуп пребројивог скупа такође пребројив
• унија два пребројива скупа пребројив скуп
• Декартов производ два пребројива скупа пребројив скуп

Директна последица последње тврдње је да је скуп рационалних бројева $Q$ пребројив јер се сваки рационални број може да представи као количник два цела броја $m$ и $n$, $n\neq 0$, где је $m,n\in Z$ ($Z$ скуп целих бројева). Кантор је показао да је скуп реалних бројева $R$ непребројив.

Као што постоје непребројиви скупови тако постоје непребројиви ординали. Скуп свих коначних и пребројивих ординала је ординал, који се означава са $\omega _{1}$, и представља први непребројиви ординал.

Кардинални број, као трансфинитни број и тип бијективне коресподентности, је такође увео Кантор. Кардинални број коначног скупа $A$ је јединствани природни број $n$ дефинисан бијекцијом $F:n\rightarrow A$.

Код бесконачних скупова кардиналност је дефинисана бесконачним ординалом. Пошто су ординали добро уређени, можемо рећи да је кардиналност неког бесконачног скупа најмањи ординал који се бијекцијом пресликава у поменути скуп.

Кардиналност ординала $\alpha$ је најмањи ординал $\kappa$ који се бијекцијом пресликава на $\alpha$. При томе $\kappa$ се не може пресликати бијекцијом на неки мањи ординал. Ординални бројеви који се не могу бијекцијом пресликати на мањи ординал се зову кардинални бројеви.

Бесконачне кардиналне бројеве означавамо са $\aleph$. Најмањи бесконачни кардинални број је $\omega =\aleph _{0}$, следећи је $\omega _{1}=\aleph _{1}$ који је уједно и први непребројиви кардинал, затим $\omega _{2}=\aleph _{2}$, итд.

Извори

• Paul R. Halmos: Naive Set Thery. . New York: Springer Verlag. 1974. ISBN 9778-0-378-90104-6 . 
• A.K Shen, N. K. Vereshchagin: Basic Set Theory, AMS. 2002. ISBN 978-0-8218-2731-4.
• Aleksandar Perović, Aleksandar Jovanović, Boban Veličković: Teorija skupova. ISBN 978-86-7589-058-4 Matematički fakultet, Beograd