Osnove teorije skupova

Osnove i notacija

Skupovi su dobro definisisane kolekcije elemenata. Osnovna relacija u teoriji skupova je pripadnost. Pišemo $a\in A$ da bi rekli da element $a$ pripada skupu $A$ ili da je $a$ element iz skupa $A$. Prazan skup ili skup bez elemenata označavaćemo simbolom $\emptyset$.

Kažemo da je $A$ podskup skupa $B$, odnosno $A\subseteq B$, ako je svaki element $A$ element skupa $B$. Dakle, $A=B$ ako i samo ako je $A\subseteq B$ i $B\subseteq A$. Specijalni slučaj $\emptyset \subseteq A$, za svaki skup $A$.

Bazične operacije nad dva skupa $A$ i $B$:

Skup $A\cup B$ se zove unija skupova $A$ i $B$, elementi unije su elementi skupa $A$ i skupa $B$.

Skup $A\cap B$ se zove presek skupova $A$ and $B$, elementi preseka su zajednički element skupova $A$ i $B$.

Skup $A\smallsetminus B$ se zove razlika skupova $A$ i $B$, elementi razlike su svi elementi skupa $A$ koji ne pripadaju skupu $B$

Unija i presek imaju sledeća svojstva:

Komutativnost: $A\cup B=B\cup A$; $A\cap B=B\cap A$

Asocijativnost: $A\cup (B\cup C)=(A\cup B)\cup C$; $A\cap (B\cap C)=(A\cap B)\cap C$

Distributivnnost: $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$; $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$

Notacija: $\{a,b,c\}$ skup čiji su elementi $a,b,c$ ; $\{a\}$ skup koji ima samo jedan element $a$

Idempotencija: $A\cup A=A;A\cap A=A$; $A\cup \emptyset =A$; $A\cap \emptyset =\emptyset$; $A\smallsetminus A=\emptyset$

Ako je $A\subseteq B$, tada je $A\cup B=B$; $A\cap B=A$

Ako je $a=b$ tada je $\{a,b\}=\{a\}$ i $\{a,b\}=\{b,a\}$

Definicija uređenog para

Uređeni par se definiše kao $(a,b)=\{\{a\},\{a,b\}\}$ Svojstva uređenog para: ako je $(a,b)=(c,d)$ onda je $a=c$ i $b=d$; ako je $a\neq b$ onda je($a,b)\neq (b,a)$.

Uređena trojka: $(a,b,c)=(a,(b,c))$ Uređena $n$-torka: $(a_{1},\dots ,a_{n})=(a_{1},(a_{2},\dots ,a_{n}))$.

Definifija kartezijanskog proizvoda

Kartezijski proizvod $A\times B$ dva skupa $A$ i $B$ je skup svih uređenih parova $(a,b)$ takvih da je $a\in A$ i $b\in B$.

Kartezijski proizvod $A_{1}\times \dots \times A_{n}$ skupova $A_{1},\dots ,A_{n}$ je skup svih $n$-torki$(a_{1},\dots ,a_{n})$ za koje je $a_{i}\in A_{i}$ za svako $1\leq i\leq n$.

Relacije

Binarna relacija na skupu $A$ je skup uređenih parova elemenata iz $A$ koji je podskup skupa $A\times A$. U opštem slučaju, $n$-arna relacija definisana na $A$ je podskup skupa $A^{n}$.

Svojstva binarne relacije

refleksivnost: $(a,a)\in R$ važi za svako $a\in A$

simetričnost: $(b,a)\in R$ kad god je $(a,b)\in R$

tranzitivnost: $(a,c)\in R$ kad god je $(a,b)\in R$ i $(b,c)\in R$.

Ako je relacija u isto vreme refleksivna, simetrična i tranzitivna onda se takva relacija zove relacija ekvivalencije.

Ako je $R$ relacija ekvivalencije na skupu $A$ i $(a,b)\in R$ tada se kaže da su $a$ i $b$ are $R$-ekvivalentni. Za svako $a\in A$ a klasa ekvivalencije, označena sa $[a]R$, je skup svih elemenata skupa $A$ koji su $R$-ekvivalentni $a$. Skup svih $R$-ekvivalentnih klasa se zove skup količnik i označava se sa $A/R$. Lako se može pokazati da je $A/R$ particija skupa $A$, tj. ni jedan element iz $A/R$ nije prazan, bilo koja dva elementa iz $A/R$ su disjunktna, a svaki $a\in A$ pripada tačno jednom elementu skupa $A/R$, tj. klasi $[a]R$.

Ako je $R$ binarna relacija onda se često piše $aRb$ umesto $(a,b)\in R$.

Za binarnu relaciju $R$ definisanu na skupu $A$ se kaže da je antisimetrična ako je $a=b$ kad god je $aRb$ i $bRa$. Relacija $R$ definisana na skupu $A$ i koja je reflekcivna, antisimetrična i tranzitivna se zove (refleksivni) parcijalni poredak. Ako iz $R$ odstranimo sve parove $(a,a)$ za svako $a\in A$ tada ćemo dobiti strogi refleksivni poredak.

Funkcije

(Unarnom, 1-arnom) funkcijom na skupu $A$ se naziva binarna relacija $F$ na $A$ takva da za svako $a\in A$ postoji tačno jedan par $(a,b)\in F$. Element $b$ se zove vrednost relacije $F$ u $a$, i označava sa $F(a)$. Skup $A$ je domen funkcije $F$. Oznaka $F:A\rightarrow B$ se čita kao $F$ je funkcija na domenu $A$ i vrednostima u skupu $B$. Za $n\geq 2$, $n$-arna funkcija na $A$ je funkcija $F:A^{n}\rightarrow B$, za neko $B$.

Funkcija $F:A\rightarrow B$ se zove jedan-u-jedan funkcija ako za sve elemente $a$ i $b$ iz $A$ i $a\neq b$ važi da je $F(a)\neq F(b)$. Funkcija $F:A\rightarrow B$ je preslikavanje skupa $A$ na skup $B$ ako i samo ako za svako $b\in B$ postoji neko $a\in A$ takvo da je $F(a)=b$. Funkcija $F:A\rightarrow B$ je bijektivna ako je jedan-u-jedan i na. Bijekcija $F:A\rightarrow B$ uspostavlja jedan-u-jedan preslikavanje elemenata iz $A$ u elemente iz $B$. Funkcija identičnosti na skupu $A$, zapisana kao $Id:A\rightarrow A$, a koju čine svi parovi $(a,a)$, gde je $a\in A$ je primer trivijalne bijekcije.

Ako su date funkcije $F:A\rightarrow B$ i $G:B\rightarrow C$, kažemo da je kompozicija funkcija $F$ i $G$, zapisana kao $G\circ F$, ona funkcija $G\circ F:A\rightarrow C$ čiji su elementi svi parovi $(a,G(F(a)))$, gde je $a\in A$. Ako su $F$ i $G$ bijekcije, onda je $G\circ F$ bijekcija.

Formule

Formalni jezik teorije skupova je jezik prvog reda čiji je jedini ne-logični simbol simbol binarne relacije pripadnosti $\in$.

Ako je data formula $\phi (x,y_{1},\dots ,y_{n})$ u jeziku teorije skupova i skupovi $A,B_{1},\dots ,B_{n}$, onda se može formirati skup svih elemenata iz $A$ koji zadovoljava formulu $\phi (x,B_{1},\dots ,B_{n})$. Ovaj skup se zapisuje sa $\{a\in A:\phi (a,B_{1},\dots ,B_{n})\}$. Sledi nekoliko primera formule

$\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\}$

Ako su $B$ i $C$ podskupovi skupa $A$, onda važi formula

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

Ako je dat podskup $C\subseteq A\times B$ kaže se da je projekcija $C$ (na prvu koordinatu) skup

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

Ako su dati formula $\phi (x,y_{1},\dots ,y_{n})$ i skupovi $B_{1},\dots ,B_{n}$, onda se ne može formirati skup svih skupova koji zadovoljava formulu $\phi (x,B_{1},\dots ,B_{n})$. Neka je $\phi (x)$ formula i $x\notin x$. Ako bi $A$ bio skup svih skupova koji zadovoljava formulu $\phi$, tada $A\in A$ ako i samo ako $A\notin A$. (Raselov paradoks, 1901).

Ordinali

Ordinale, koji spadaju u transfinitne brojeve, a služe kao tipovi uređenja, je uveo Kantor. Prvi ordinal se diefiniše kao $\emptyset$. Ako je dat ordinal $\alpha$ onda je sledeći veći ordinal, koji se zove i neposredni sledbenik ordinala $\alpha$, skup $\alpha \cup {\alpha }$. Konačni ordinalni brojevi su oni ordinali koji se dobiju počevši sa $\emptyset$ a zatim se konstruišu sledeći ordinali.

U teoriji skupova prirodni brojevi su definisani kao konačni ordinali, tj.:

$0=\emptyset$

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

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

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

...

Primećuje se da je $1=\{0\}$, $2=\{0,1\}$, $3=\{0,1,2\}$, ..., $n=\{0,1,2,\dots ,n-1\}$ tj. svaki prirodni broj je skup svojih prethodnika.

Za skup $A$ se kaže da je konačan ako postoji 1-u-1 preslikavanje između nekog prirodnog broja $n$ i elemenata skupa $A$, tj. bijekcija $F:n\rightarrow A$, u kom se slučaju kaže da skup $A$ ima $n$ elemenata. Za neki skup se kaže da je beskonačan ako nije konačan.

Skup svih konačnih ordinala ćemo označavati sa $(\omega )$. Na taj način je $\omega$ skup $N$, tj. skup prirodnih brojeva pri čemu je $\omega$ prvi beskonačni ordinal. Ordinal $\omega$ nije sledbenik ni jednog ordinala i naziva se granični ordinal. Tehnika računanja ordinala sledbenika je već opisana. Treba uočiti da je nemoguće imati skup svih ordinala jer bi u tome slučaju imali novi granični ordinal što je nemoguće, jer smo već definisali granični ordinal.

Kao što je slučaj sa konačnim ordinalima, svaki beskonačni ordinal je skup svojih prethodnika. Posledica ove činjenice je da je relacija $\in$ relacija striktnog dobro definisanog poretka ordinala, tj. za bilo koja dva ordinala $\alpha$ i $\beta$ kažemo da je $\alpha <\beta$ ako i samo ako je $\alpha \in \beta$.

Prebrojivi i neprebrojivi skupovi

Ako je $A$ konačan skup onda postoji bijekcija $F:n\rightarrow A$ između skupa prirodnih brojeva $N$ i skupa $A$. Svi konačni skupovi su prebrojivi, tj. $F(0)$ je prvi element skupa $A$, $F(1)$ drugi, itd. Bilo koji beskonačni skup $A$ je prebrojiv ako postoji bijekcija $F:\omega \rightarrow A$ između skupa prirodnih brojeva i skupa $A$. Lako je pokazati da je

• svaki beskonačni podskup prebrojivog skupa takođe prebrojiv
• unija dva prebrojiva skupa prebrojiv skup
• Dekartov proizvod dva prebrojiva skupa prebrojiv skup

Direktna posledica poslednje tvrdnje je da je skup racionalnih brojeva $Q$ prebrojiv jer se svaki racionalni broj može da predstavi kao količnik dva cela broja $m$ i $n$, $n\neq 0$, gde je $m,n\in Z$ ($Z$ skup celih brojeva). Kantor je pokazao da je skup realnih brojeva $R$ neprebrojiv.

Kao što postoje neprebrojivi skupovi tako postoje neprebrojivi ordinali. Skup svih konačnih i prebrojivih ordinala je ordinal, koji se označava sa $\omega _{1}$, i predstavlja prvi neprebrojivi ordinal.

Kardinalni broj, kao transfinitni broj i tip bijektivne korespodentnosti, je takođe uveo Kantor. Kardinalni broj konačnog skupa $A$ je jedinstvani prirodni broj $n$ definisan bijekcijom $F:n\rightarrow A$.

Kod beskonačnih skupova kardinalnost je definisana beskonačnim ordinalom. Pošto su ordinali dobro uređeni, možemo reći da je kardinalnost nekog beskonačnog skupa najmanji ordinal koji se bijekcijom preslikava u pomenuti skup.

Kardinalnost ordinala $\alpha$ je najmanji ordinal $\kappa$ koji se bijekcijom preslikava na $\alpha$. Pri tome $\kappa$ se ne može preslikati bijekcijom na neki manji ordinal. Ordinalni brojevi koji se ne mogu bijekcijom preslikati na manji ordinal se zovu kardinalni brojevi.

Beskonačne kardinalne brojeve označavamo sa $\aleph$. Najmanji beskonačni kardinalni broj je $\omega =\aleph _{0}$, sledeći je $\omega _{1}=\aleph _{1}$ koji je ujedno i prvi neprebrojivi kardinal, zatim $\omega _{2}=\aleph _{2}$, itd.

Izvori

• 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