Skupovi i skupovne operacije

Skup je jasno određena kolekcija objekata, a objekti koje sadrži nazivaju se njegovim elementima.

Skupovi se najčešće označavaju velikim slovima, a elementi malim slovima.

Ako objekat $x$ pripada skupu $A$, zapisujemo $x\in A$. Ako mu ne pripada, zapisujemo $x\notin A$.

Skup možemo zadati nabrajanjem elemenata:

$$A=\{1,2,3,4\},$$

ili navođenjem svojstva koje njegovi elementi ispunjavaju:

$$A=\{x\in\mathbb N\mid 1\leq x\leq 4\}.$$

Znak $\mid$ u ovom zapisu čita se „takav da”. U zadacima u kojima je $\mathbb N=\{1,2,3,\ldots\}$, prethodna dva zapisa predstavljaju isti skup.

Redosled elemenata nije važan, a ponavljanje elementa ne menja skup. Zato je

$$\{1,2,3\}=\{3,2,1,2\}.$$

Skup bez elemenata naziva se prazan skup i označava se sa $\varnothing$ ili $\{\}$.

Dva skupa su jednaka ako imaju potpuno iste elemente:

$$A=B\iff (\forall x)(x\in A\iff x\in B).$$

Sadržaj

1. Podskupovi i partitivni skup
2. Skupovne operacije i intervali
3. Skupovni zakoni, jednakosti i jednačine
4. Venovi dijagrami
5. Dekartov proizvod skupova

1. Podskupovi i partitivni skup

Skup $A$ je podskup skupa $B$ ako svaki element skupa $A$ pripada i skupu $B$:

$$A\subseteq B\iff (\forall x)(x\in A\Rightarrow x\in B).$$

Ako je $A\subseteq B$ i $A\ne B$, tada je $A$ pravi podskup skupa $B$, što zapisujemo $A\subsetneq B$.

Prazan skup je podskup svakog skupa, a svaki skup je podskup samog sebe:

$$\varnothing\subseteq A, \qquad A\subseteq A.$$

Partitivni skup skupa $A$, u oznaci $\mathcal P(A)$, jeste skup svih podskupova skupa $A$.

Ako konačan skup $A$ ima $n$ elemenata, njegov partitivni skup ima $2^n$ elemenata:

$$|A|=n\Rightarrow |\mathcal P(A)|=2^n.$$

Razlog je to što pri formiranju podskupa za svaki od $n$ elemenata imamo dve mogućnosti: da ga uključimo ili da ga ne uključimo.

2. Skupovne operacije i intervali

Unija skupova

Unija skupova $A$ i $B$ sadrži sve elemente koji pripadaju bar jednom od ta dva skupa:

$$A\cup B=\{x\mid x\in A\lor x\in B\}.$$

Ako neki element pripada obema skupovima, u uniji ga zapisujemo samo jednom.

Presek skupova

Presek skupova $A$ i $B$ sadrži elemente koji istovremeno pripadaju i skupu $A$ i skupu $B$:

$$A\cap B=\{x\mid x\in A\land x\in B\}.$$

Ako skupovi nemaju zajedničkih elemenata, njihov presek je prazan i kažemo da su skupovi disjunktni.

Razlika skupova

Razlika $A\setminus B$ sadrži elemente koji pripadaju skupu $A$, ali ne pripadaju skupu $B$:

$$A\setminus B=\{x\mid x\in A\land x\notin B\}.$$

Redosled skupova je važan. U opštem slučaju $A\setminus B$ i $B\setminus A$ nisu jednaki.

Komplement skupa

Kada je određen univerzalni skup $U$, komplement skupa $A$ čine svi elementi skupa $U$ koji nisu u skupu $A$:

$$A^c=U\setminus A.$$

Komplement zato zavisi od izbora univerzalnog skupa.

Složeni skupovni izrazi

Kod izraza sa više operacija prvo računamo ono što je u najdubljim zagradama, a zatim korak po korak prelazimo ka spoljašnjem delu izraza. Tako se smanjuje mogućnost da pomešamo skupove nad kojima se operacija izvršava.

Intervali kao skupovi

Interval je skup realnih brojeva između zadatih granica. Uglasta zagrada znači da granična tačka pripada intervalu, a obla zagrada da ne pripada.

Interval	Uslov za $x$
$[a,b]$	$a\leq x\leq b$
$[a,b)$	$a\leq x<b$
$(a,b]$	$a<x\leq b$
$(a,b)$	$a<x<b$

Uz $-\infty$ i $+\infty$ uvek se piše obla zagrada, jer beskonačnost nije realan broj koji može pripadati intervalu.

Skupovne operacije sa intervalima određujemo poređenjem njihovih granica. Presek sadrži zajednički deo, unija obuhvata sve tačke koje pripadaju bar jednom intervalu, a razlika uklanja tačke drugog intervala iz prvog.

3. Skupovni zakoni, jednakosti i jednačine

Osnovni skupovni zakoni

Skupovne izraze možemo preuređivati pomoću zakona koji odgovaraju zakonima logičkih operacija. U sledećim formulama $U$ označava univerzalni skup.

Zakon	Jednakosti
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)$
Distributivnost	$A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$, $A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$
Idempotentnost	$A\cup A=A$, $A\cap A=A$
Neutralni elementi	$A\cup\varnothing=A$, $A\cap U=A$
Apsorbujući elementi	$A\cap\varnothing=\varnothing$, $A\cup U=U$
Komplement	$A\cup A^c=U$, $A\cap A^c=\varnothing$, $(A^c)^c=A$
Apsorpcija	$A\cup(A\cap B)=A$, $A\cap(A\cup B)=A$
De Morganovi zakoni	$(A\cup B)^c=A^c\cap B^c$, $(A\cap B)^c=A^c\cup B^c$

Razliku možemo zapisati pomoću preseka i komplementa:

$$A\setminus B=A\cap B^c.$$

Ovaj zapis je naročito koristan pri dokazivanju složenijih jednakosti.

Dokazivanje jednakosti skupova

Da bismo dokazali $X=Y$, možemo pokazati da svaki element skupa $X$ pripada skupu $Y$ i obrnuto. To zapisujemo kao niz ekvivalencija:

$$x\in X\iff x\in Y.$$

Drugi način je da dokažemo dve inkluzije, $X\subseteq Y$ i $Y\subseteq X$.

Skupovne jednačine

U skupovnoj jednačini nepoznata je ceo skup. Rešenje često nije jedinstveno, pa treba odrediti sve skupove koji ispunjavaju zadati odnos.

Za jednačinu oblika $A\cup X=B$ rešenje postoji samo ako je $A\subseteq B$. Tada mora da važi

$$B\setminus A\subseteq X\subseteq B.$$

Za jednačinu $A\cap X=B$ neophodno je da bude $B\subseteq A$. Pri rešavanju u univerzalnom skupu $U$ tada važi

$$B\subseteq X\subseteq B\cup A^c.$$

4. Venovi dijagrami

Venov dijagram prikazuje skupove kao oblasti unutar pravougaonika koji predstavlja univerzalni skup. Preklapanje oblasti predstavlja presek, a svi delovi obuhvaćeni nacrtanim skupovima predstavljaju njihovu uniju.

Broj elemenata unije dva skupa

Broj elemenata konačnog skupa $A$ označavamo sa $|A|$. Kada saberemo $|A|$ i $|B|$, elemente preseka prebrojali smo dva puta. Zato ih jednom oduzimamo:

$$|A\cup B|=|A|+|B|-|A\cap B|.$$

Broj elemenata koji pripadaju samo skupu $A$ jednak je

$$|A\setminus B|=|A|-|A\cap B|.$$

Broj elemenata unije tri skupa

Za tri konačna skupa važi princip uključivanja i isključivanja:

$$\begin{aligned} |A\cup B\cup C| ={}&|A|+|B|+|C|\\ &-|A\cap B|-|A\cap C|-|B\cap C|\\ &+|A\cap B\cap C|. \end{aligned}$$

Trostruki presek na kraju dodajemo zato što smo ga u prvom redu prebrojali tri puta, a zatim ga kroz tri preseka oduzeli tri puta.

U tekstualnim zadacima često je preglednije popunjavati disjunktne oblasti dijagrama sledećim redosledom:

1. Upisati broj elemenata u preseku sva tri skupa.
2. Odrediti delove koji pripadaju tačno dvama skupovima.
3. Odrediti delove koji pripadaju samo jednom skupu.
4. Sabiranjem svih disjunktnih oblasti izračunati uniju.
5. Ako postoje elementi van unije, dodati i oblast izvan sva tri skupa.

5. Dekartov proizvod skupova

Dekartov proizvod skupova $A$ i $B$ jeste skup svih uređenih parova $(a,b)$ u kojima je prva komponenta iz skupa $A$, a druga iz skupa $B$:

$$A\times B=\{(a,b)\mid a\in A\land b\in B\}.$$

Parovi su uređeni, pa je $(a,b)=(c,d)$ samo ako je $a=c$ i $b=d$. U opštem slučaju zato važi

$$A\times B\ne B\times A.$$

Oznaka $A^2$ predstavlja proizvod skupa sa samim sobom:

$$A^2=A\times A.$$

Ako su $A$ i $B$ konačni skupovi, onda je

$$|A\times B|=|A|\cdot|B|.$$

Grafičko predstavljanje

Ako su elementi skupova brojevi, Dekartov proizvod možemo prikazati u koordinatnom sistemu. Prvi element uređenog para određuje položaj na horizontalnoj osi, a drugi položaj na vertikalnoj osi.

• Ako su $X$ i $Y$ konačni skupovi, $X\times Y$ prikazuje se konačnim brojem tačaka.
• Ako su $X$ i $Y$ intervali, $X\times Y$ predstavlja pravougaonu oblast. Uključene granice crtaju se punom linijom, a isključene isprekidanom linijom.

Na primer, za

$$X=\{-1,0,1,2\}, \qquad Y=\{1,2\},$$

proizvod $X\times Y$ čini osam tačaka, jer postoje četiri izbora za prvu i dva izbora za drugu koordinatu.

Ako je

$$X=[-1,1], \qquad Y=[1,2],$$

onda je

$$X\times Y=\{(x,y)\mid -1\leq x\leq 1\land 1\leq y\leq 2\},$$

što je zatvoren pravougaonik u koordinatnoj ravni.

Određivanje činilaca proizvoda

Ako je zadat neprazan skup $A\times B$, skup $A$ dobijamo prikupljanjem svih prvih komponenti, a skup $B$ prikupljanjem svih drugih komponenti.

Ako je $A\times B=\varnothing$, ne možemo na ovaj način jednoznačno odrediti oba skupa. Znamo samo da je bar jedan od njih prazan.

Skupovne operacije i Dekartov proizvod

Dekartov proizvod je distributivan prema uniji, preseku i razlici:

$$(A\cup B)\times C=(A\times C)\cup(B\times C),$$ $$(A\cap B)\times C=(A\times C)\cap(B\times C),$$ $$(A\setminus B)\times C=(A\times C)\setminus(B\times C).$$

Analogni zakoni važe kada se operacija nalazi u drugom činiocu proizvoda.

Skup čiji su elementi već uređeni parovi može učestvovati u svim skupovnim operacijama. Ako formiramo proizvod dva takva skupa, elementi novog proizvoda jesu uređeni parovi uređenih parova. Na primer, ako su $E_1=\{(1,1)\}$ i $E_2=\{(1,2),(2,1)\}$, onda je

$$E_1\times E_2=\{((1,1),(1,2)),((1,1),(2,1))\}.$$