Verzamelingenleer

Een verzameling is een collectie van objecten, die elementen heten. Verzamelingen worden vaak genoteerd met hoofdletters, elementen vaak met kleine letters. De elementen van verzamelingen kunnen zelf ook verzamelingen zijn.

Als $a$ een element is van $A$, noteren we $a \in A$. Anders $a \notin A$.

De cardinaliteit van een verzameling $A$ is het aantal elementen van $A$, notatie $|A|$. Zo geldt bijvoorbeeld $|\{2,4,6,8\}|=4$.

De lege verzameling, notatie $\emptyset$, is de verzameling die geen elementen bevat: $\emptyset = \{\}$.

Notatie

Een verzameling $A$ kan op verschillende manieren genoteerd worden (dit is telkens dezelfde verzameling):

1. Opsomming: $A=\{2,4,6,8,10,12,14,16,18,20\}$
2. Puntjes: $A=\{2,4,6,...,20\}$
3. Bewering: $A=\{2x : x \in \Z \land 1 \leq x \leq 10\}$

Van verzamelingen maken de volgorde en dubbele elementen niet uit. Zo is ${1,2,3} = {1,3,2} = {1,2,1,3,1}$.

Deelverzamelingen

Een verzameling $A$ is een deelverzameling van verzameling $B$ als alle elementen van $A$ ook elementen zijn van $B$, notatie $A \subseteq B$.

Twee verzamelingen $A$ en $B$ zijn gelijk, notatie $A=B$, als $A$ en $B$ precies dezelfde elementen hebben, oftewel $A \subseteq B$ en $B \subseteq A$.

De verzameling $A$ is een strikte deelverzameling van $B$ als $A \subseteq B$ en $A \neq B$. Dit noteer je als $A \subset B$.

Machtsverzameling

De machtsverzameling van $A$, notatie $\mathcal P(A)$, is de verzameling van alle deelverzamelingen van $A$. Dus $\mathcal P(A) = \{B : B \subseteq A\}$.

Er geldt: $|\mathcal P(A)|=2^{|A|}$.

Operaties

Op twee verzamelingen $A$ en $B$ kun je operaties uitvoeren.

Vereniging

De vereniging van $A$ en $B$, notatie $A \cup B$, bevat alle elementen die in $A$ of in $B$ zitten (inclusief).

$$A \cup B = \{x : x \in A \lor x \in B\}$$

Doorsnede

De doorsnede van $A$ en $B$, notatie $A \cap B$, bevat alle elementen die in $A$ en in $B$ zitten.

$$A \cap B = \{x : x \in A \land x \in B\}$$

Verzamelingen $A$ en $B$ heten disjunct als $A \cap B = \emptyset$.

Verschil

Het verschil van $A$ en $B$, notatie $A \backslash B$, bevat alle elementen die wel in $A$ zitten, maar niet in $B$.

$$A \backslash B = \{x : x \in A \land x \notin B\}$$

Er geldt: $A \cap B \subseteq A \cup B$.

Complement

De universele verzameling, notatie $U$, is de verzameling waar alle verzamelingen (van interesse) deelverzameling van zijn.

Het complement van $A$, notatie $\overline A$, bevat alle elementen die wel in $U$ zitten, maar niet in $A$.

$$\overline A = \{x : x \in U \land x \notin A\}$$

Er geldt: $\overline{\overline A} = A$ en $A \cap \overline B = A \backslash B$.

Voorbeeld

Carthesisch product

Een geordend paar van $x$ en $y$, notatie $(x,y)$, is een "gesorteerde verzameling". Er geldt namelijk: $(a,b)=(c,d) \iff (a=c \land b=d)$.

Het carthesisch product van verzamelingen $A$ en $B$, notatie $A \times B$, is de verzameling met alle geordende paren van $A$ en $B$:

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

Er geldt: $|A \times B| = |A| \cdot |B|$.

Geïndiceerde verzamelingen

De vereniging van verzamelingen $A_1,A_2,...,A_n$ wordt genoteerd als notatie $A_1 \cup A_2 \cup ... \cup A_n$, of:

$$\bigcup^n_{i=1} A_i = \{x : x \in A_i \text{ voor een } i \text{ waarvoor } 1 \leq i \leq n\}$$

De doorsnede van verzamelingen $A_1,A_2,...,A_n$ wordt genoteerd als notatie $A_1 \cap A_2 \cap ... \cap A_n$, of:

$$\bigcap^n_{i=1} A_i = \{x : x \in A_i \text{ voor elke } i \text{ waarvoor } 1 \leq i \leq n\}$$

Indexverzameling

We nemen een indexverzameling $I$ en we nemen aan dat $S_{\alpha}$ een verzameling is voor elke $\alpha\in I$, notatie $\{S_\alpha\}_{\alpha\in I}$.

Nu is de vereniging $\bigcup_{\alpha \in I} S<em>\alpha = \{x : x \in S</em>\alpha \text{ voor een } \alpha \in I\}$.

En de doorsnede is $\bigcap_{\alpha \in I} S<em>\alpha = \{x : x \in S</em>\alpha \text{ voor iedere } \alpha \in I\}$.

Partities

Laat $S$ een verzameling met deelverzamelingen van $A$ zijn, ofwel $S \subseteq \mathcal P(A)$. Dan is $S$ paarsgewijs disjunct precies als $x \cap y = \emptyset$ voor alle $x,y \in S$ met $x \neq y$.

Een partitie van een verzameling $A$ is een verzameling $S$ met deelverzamelingen van $A$ waarvoor geldt:

1. $\emptyset \notin S$
2. Voor elke $x,y \in S$ met $x \neq y$ geldt $x \cap y = \emptyset$ ($S$ is paarsgewijs disjunct)
3. $\bigcup_{x \in S} x = A$