Skupovi i skupovne operacije

Skup i element. Skup je jasno određena kolekcija objekata, a objekti koje sadrži nazivaju se njegovim elementima. Ako $x$ pripada skupu $A$, zapisujemo $x\in A$, a ako mu ne pripada, zapisujemo $x\notin A$. Skup bez elemenata je prazan skup i označava se sa $\varnothing$.

Podskup. 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$, onda je $A$ pravi podskup skupa $B$ i pišemo $A\subsetneq B$. Prazan skup je podskup svakog skupa, a svaki skup je podskup samog sebe.

Jednakost skupova. Dva skupa su jednaka ako imaju potpuno iste elemente. To se može proveriti tako što pokažemo da je svaki od njih podskup onog drugog:

$$A=B\iff A\subseteq B\land B\subseteq A.$$

Partitivni skup. Partitivni skup skupa $A$, u oznaci $\mathcal P(A)$, jeste skup svih podskupova skupa $A$. Na primer, ako je $A=\{a,b\}$, onda je

$$\mathcal P(A)=\{\varnothing,\{a\},\{b\},\{a,b\}\}.$$

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

Sadržaj

1. Podskup i partitivni skup
2. Skupovne operacije i intervali
3. Venovi dijagrami
4. Dekartov proizvod skupova

Uvod

Skupovi se najčešće označavaju velikim slovima, a njihovi elementi malim slovima. 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\}.$$

Dva skupa su jednaka ako imaju potpuno iste elemente, odnosno ako za svaki objekat $x$ važi:

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

Kod skupova zadatih svojstvom najpre rešavamo uslov, a zatim izdvajamo rešenja koja pripadaju navedenom brojnom skupu.

1. Podskup i partitivni skup

Podskup

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

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.

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	Identiteti
Komutativnost	$\begin{gathered}A\cup B=B\cup A\\A\cap B=B\cap A\end{gathered}$
Asocijativnost	$\begin{gathered}(A\cup B)\cup C=A\cup(B\cup C)\\(A\cap B)\cap C=A\cap(B\cap C)\end{gathered}$
Distributivnost	$\begin{gathered}A\cap(B\cup C)=(A\cap B)\cup(A\cap C)\\A\cup(B\cap C)=(A\cup B)\cap(A\cup C)\end{gathered}$
Idempotentnost	$\begin{gathered}A\cup A=A\\A\cap A=A\end{gathered}$
Neutralni elementi	$\begin{gathered}A\cup\varnothing=A\\A\cap U=A\end{gathered}$
Apsorbujući elementi	$\begin{gathered}A\cap\varnothing=\varnothing\\A\cup U=U\end{gathered}$
Komplement	$\begin{gathered}A\cup A^c=U\\A\cap A^c=\varnothing\\(A^c)^c=A\end{gathered}$
Apsorpcija	$\begin{gathered}A\cup(A\cap B)=A\\A\cap(A\cup B)=A\end{gathered}$
De Morganovi zakoni	$\begin{gathered}(A\cup B)^c=A^c\cap B^c\\(A\cap B)^c=A^c\cup B^c\end{gathered}$

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

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

Ovaj zapis je naročito koristan pri pojednostavljivanju složenijih skupovnih izraza.

3. Venovi dijagrami

Venov dijagram je grafički prikaz skupova i njihovih međusobnih odnosa. Skupove predstavljamo krugovima, a pravougaonik predstavlja univerzalni skup $U$.

Neka su

$$A=\{1,2,3,4\},\qquad B=\{3,4,5,6\},\qquad U=\{1,2,3,4,5,6,7,8\}.$$

1. Presek $A\cap B=\{3,4\}$ sadrži elemente koji pripadaju i skupu $A$ i skupu $B$.
2. Unija $A\cup B=\{1,2,3,4,5,6\}$ sadrži sve elemente koji pripadaju bar jednom od skupova.
3. Razlika $A\setminus B=\{1,2\}$ sadrži elemente skupa $A$ koji ne pripadaju skupu $B$.
4. Komplement $A^c=\{5,6,7,8\}$ sadrži elemente univerzalnog skupa koji ne pripadaju skupu $A$.

Preklapanje krugova pokazuje da skupovi imaju zajedničke elemente. Ako se krugovi ne preklapaju, skupovi su disjunktni i važi $A\cap B=\varnothing$.

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

Na dijagramu sa tri skupa pojavljuju se delovi koji pripadaju jednom, dvama ili svim trima skupovima.

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.

4. 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|.$$

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