Skupovi
Skup je osnovni pojam u modernoj matematici, što znači da se ovaj pojam ne definiše.
Ipak, skup možemo zamisliti kao kolekciju različitih elemenata. Cela moderna matematika je bazirana na ovom konceptu, pa je izuzetno važno znati i razumeti teoriju skupova.
Skupovi se uobičajeno obeležavaju velikim latiničnim slovima $A, B, C...$. Elementi skupa se pišu unutar zagrada $\lbrace$ i $\rbrace$.
Skup može biti određen:
1. nabrajanjem njegovih elemenata $A=\lbrace 1,2,3,4,5 \rbrace$
2. zadavanjem pravila koje zadovoljavaju elementi skupa $A=\lbrace x\in \mathbb{N} \vert x<6\rbrace$
Skup koji ne sadrži elemente naziva se prazan skup i obeležava se sa $\emptyset$ or $\lbrace \rbrace$.
Relacije između skupova
Jednaki skupovi
Skupovi $A$ i $B$ su jednaki ako i samo ako sadrže jednake elemente; ako su svi elementi prvog skupa jednaki elementima drugog skupa, i obrnuto.
$A=B \overset{def}{\Leftrightarrow} (\forall x)(x\in A \Leftrightarrow x\in B)$
Pošto je relacija jednakosti skupova tranzitivna, refleksivna i simetrična ona je relacija ekvivalencije.
Podskup
Skup $A$ je podskup skupa $B$ ako i samo ako je svaki element skupa $A$ ujedno i element skupa $B$.
$A \subseteq B \overset{def}{\Leftrightarrow} (\forall x)(x \in A \Rightarrow x \in B)$
Skup $B$ je nadskup skupa $A$, označavamo $B \supseteq A$.
Ako je skup $A$ podskup skupa $B$ i ako skup $B$ sadrži najmanje jedan element koji nije element skupa $A$, onda kažemo da je skup $A$ pravi podskup skupa $B$ i obeležavamo $A \subset B$, ili da je skup $B$ pravi nadskup skupa $A$, što pišemo $B \supset A$.
Relacija $\subset$ je tranzitivna: $(A \subset B) \wedge (B \subset C) \Rightarrow A \subset C$.
Prazan skup je podskup svakog skupa.
Operacije sa skupovima
Unija skupova
Unija skupova $A$ i $B$ je skup svih elemenata koji pripadaju najmanje jednom od skupova $A$ ili $B$.
$A \cup B \overset{def}{=} \lbrace x \vert x \in A \vee x \in B \rbrace$
Operacija unije skupova je:
1. idempotentna: $A\cup A=A$
2. komutativna: $A \cup B = B \cup A$
3. asocijativna: $(A \cup B) \cup C = A \cup (B \cup C)$
Presek skupova
Presek skupova $A$ i $B$ je skup koji sadrži sve elemente koji pripadaju i skupu $A$ i skupu $B$.
$A \cap B\overset{def}{=}\lbrace x \vert x\in A \wedge x\in B \rbrace$
Operacija presek skupova je:
1. idempotentna: $A\cap A=A$
2. komutativna: $A \cap B = B \cap A$
3. asocijativna: $(A \cap B) \cap C = A \cap (B \cap C)$
Razlika skupova
Razlika skupova $A$ i $B$ je skup svih elemenata skupa $A$ koji ne pripadaju skupu $B$.
$A \setminus B \overset{def}{=} \lbrace x \vert x \in A \wedge x \notin B \rbrace$
Simetrična razlika
Simetrična razlika skupova $A$ i $B$ je skup svih elemenata koji pripadaju samo jednom od skupova $A$ i $B$.
$A \bigtriangleup B \overset{def}{=} (A \setminus B) \cup (B \setminus A)$
Očigledno je da je operacija $\bigtriangleup$ komutativna.
Komplement skupa
Neka je skup $A \subset B$. Komplement skupa $A$ u odnosu na skup $B$ je skup svih elemenata skupa $B$ koji ne pripadaju skupu $A$.
$C_B(A)\overset{def}{=}\lbrace x\vert x\in B \wedge x\notin A\rbrace$
Partitivni skup
Partitivni skup skupa $A$ je skup svih podskupova skupa $A$, uključujući prazan skup i sam skup $A$.
$P(A) \overset{def}{=} \lbrace B \vert B \subset A \rbrace$
Primer: Partitivni skup skupa $A=\lbrace 1,2,3 \rbrace $ je skup $P(A)=\lbrace \emptyset ,\lbrace 1 \rbrace , \lbrace 2\rbrace, \lbrace 3 \rbrace , \lbrace 1,2 \rbrace , \lbrace 1,3 \rbrace , \lbrace 2,3 \rbrace , \lbrace 1,2,3 \rbrace \rbrace $
Dekartov proizvod
Dekartov proizvod skupova $A$ i $B$ je skup svih uređenih parova $(x,y)$ takvih da je $x$ element skupa $A$, a $y$ element skupa $B$.
$A \times B \overset{def}{=} \lbrace(x,y) \vert x \in A \wedge y \in B \rbrace $
Osobine operacija sa skupovima
Distributivni zakon
$A \cup (B \cap C)=(A \cup B)\cap (A \cup B)$
$A \cap (B \cup C)=(A \cap B)\cup (A \cap B)$
Zakon apsorpcije
$A\cup(A\cap B)=A$
$A\cap(A\cup B)=A$
De Morganovi zakoni
$C_U(A\cup B)=C_U(A)\cap C_U(B)$
$C_U(A\cap B)=C_U(A)\cup C_U(B)$
Relacije i funkcije
Relacije
Ako su $A$ i $B$ dva neprazna skupa onda svaki podskup $\rho$ skupa $A\times B$ se zove binarna relacija u skupu $A\times B$.
Ako je $(a,b)\in \rho$, onda kažemo da su $a$ i $b$ u relaciji i zapisujemo $a\rho b$.
Funkcije
Binarnu relaciju $f\subset X\times Y$ zovemo funkcija ako i samo ako za svaki element $x\in X$ postoji tačno jedan $y\in Y$ takav da je $(x,y)\in f$, tj. $(\forall x\in X)(\exists !y\in Y)(x,y)\in f$
Simbolički zapis: $f:X\longmapsto Y$ or $X\overset{f}{\longmapsto} Y$
Ako je $(x,y)\in f$, pišemo $f(x)=y$. Element $x$ zovemo original, a $y$ slika.
Skup $X$ zovemo domen, a skup $Y$ kodomen funkcije $f$.
Postoje tri specijalna tipa funkcija koja imaju poseban značaj u matematici: injekcija, surjekcija i bijekcija.
Injekcija
Funkcija $f:X\longmapsto Y$ je injektivna ili "1-1" funkcija ako i samo ako za svaki element $x\in X$ postoji tačno jedan element $y\in Y$ za koji je $f(x)=y$.
$f:X\overset{1-1}{\longmapsto}Y\overset{def}{=}(\forall x_1,x_2\in X)(x_1\neq x_2\Rightarrow f(x_1)\neq f(x_2))$
Surjekcija
Funkcija $f:X\longmapsto Y$ je surjekcija ili "na" funkcija ako i samo ako za svaki element $y\in Y$ postoji element $x\in X$ za koji je $f(x)=y$.
$f:X\overset{onto}{\longmapsto}Y\overset{def}{=}(\forall y\in Y)(\exists x\in X)(f(x)=y)$
Bijekcija
Funkcija $f:X\longmapsto Y$ je bijekcija ako je surjekcija i injekcija.