# Sets

## Sets and subsets

> *Definition*: a set is a collection of elements uniquely defined by these elements. 

Examples are $\mathbb{N}$, the set of natural numbers. $\mathbb{Z}$, the set of integers. $\mathbb{Q}$, the set of rational numbers. $\mathbb{R}$, the set of real numbers and $\mathbb{C}$ the set of complex numbers.

<br>

> *Definition*: suppose $A$ and $B$ are sets. Then $A$ is called a subset of $B$, if for every element $a \in A$ there also is $a \in B$. Then $B$ contains $A$ and can be denoted by $A \subseteq B$. 

The extra line under the symbol implies properness. A subset $A$ of a set $B$ which is not the empty set $\varnothing$ nor the full set $B$ is called a proper subset of $B$, denoted by $A \subsetneq B$. For example $\mathbb{N} \subsetneq \mathbb{Z}$.

<br>

> *Definition*: if $B$ is a set, then $\wp(B)$ denotes the set of all subsets $A$ of $B$. The set $\wp(B)$ is called the power set of $B$. 

Suppose for example that $B = {x,y,z}$, then $\wp(B) = \{\varnothing,\{x\},\{y\},\{z\},\{x,y\},\{x,z\},\{y,z\},\{x,y,z\}\}$.

<br>

> *Proposition*: let $B$ be a set with $n$ elements. Then its power set $\wp(B)$ contains $w^n$ elements.

??? note "*Proof*:"

    Let $B$ be set with $n$ elements. A subset $A$ of $B$ is completely determined by its elements. For each element $b \in B$ there are two options, it is in $A$ or it is not. So, there are $2^n$ options and thus $2^n$ different subsets $A$ of $B$.

<br>

> *Proposition*: suppose $A$, $B$ and $C$ are sets. Then the following hold:
> 
> 1. if $A \subseteq B$ and $B \subseteq C$ then $A \subseteq C$,
> 2. if $A \subseteq B$ and $B \subseteq A$ then $A = B$.

??? note "*Proof*:"

    To prove 1, suppose that $A \subseteq B$. Let $a \in A$, then $a \in B$ therefore $a \in C$.

    To prove 2, every element of $A$ is in $B$ and every element of $B$ is in $A$. As the set is uniquely determined by its elements $A = B$.

<br>

> *Definition*: let $P$ be a predicate with reference set $X$, then
> 
>$$
>   \big\{x \in X \;\big|\; P(x) \big\}
>$$
>
> denotes the subset of $X$ consisting of all elements $x \in X$ for which statement $P(x)$ is true.

## Operations on sets

> *Definition*: let $A$ and $B$ be sets.
>
> * The intersection of $A$ and $B$ $(A \cap B)$ is the set of all elements contained in both $A$ and $B$.
> * The union of $A$ and $B$ $(A \cup B)$ is the set of elements that are in at least on of $A$ or $B$.
> * $A$ and $B$ are disjoint if the intersection $(A \cap B)$ is the empty set $\varnothing$.

<br>

> *Definition*: suppose $I$ is a set (an index set) and for each element $i$ there exists a set $A_i$, then
> 
> $$
> \bigcup_{i \in I} A_i := \big\{x \;\big|\; \text{there is an } i \in I \text{ with } x \in A_i \big\},
> $$
>
> and
>
> $$
> \bigcap_{i \in I} A_i := \big\{x \;\big|\; \text{for all } i \in I \text{ there is } x \in A_i \big\}.
> $$
>

Implying unions and intersections taken over an index set. For example suppose for each $i \in \mathbb{N}$ the set $A_i$ is defined as $\{x \in \mathbb{R} \;|\; 0 \leq x \leq i \}$, then

$$
\bigcap_{i \in \mathbb{N}} A_i = \{0\},
$$

and

$$
\bigcup_{i \in \mathbb{N}} A_i = \mathbb{R}_{\geq 0}.
$$

<br>

> *Definition*: if $C$ is a collection of sets, then
>
> $$
> \bigcup_{A \in C} A := \big\{x \;\big|\; \text{there is an } A \in C \text{ with } x \in A \big\},
> $$
>
> and
>
> $$
> \bigcap_{A \in C} A := \big\{x \;\big|\; \text{for all } A \in C \text{ there is } x \in A \big\}.
> $$

<br>

> *Definition*: let $A$ and $B$ be sets. The difference of $A$ and $B$ $(A \backslash B)$ is the set of all elements from $A$ that are not in $B$. 
> 
>:  The symmetric difference of $A$ and $B$ $(A \triangle B)$ is the set consisting of all elements that are in exactly one of $A$ or $B$.
>
>:  If one is working inside a fixed set $U$ and only considering subsets of $U$, then the difference $U \backslash A$ is also called the complement of $A$ in $U$, denoted by $A^*$. In this case the set $U$ is called the universe.

## Cartesian products

Suppose $a_1, a_2, \dots, a_k$ are elements from some set, then the ordered k-tuple of $a_1, a_2, \dots, a_k$ is denoted by $(a_1, a_2, \dots, a_k)$

> *Definition*: the cartesian product $A_1 \times \dots \times A_k$ of sets $A_1, \dots , A_k$ is the set of all ordered k-tuples $(a_1, a_2, \dots, a_k)$ where $a_i \in A_i$ for $1 \leq i \leq k$.
> 
>:  If $A$ and $B$ are sets then
>
> $$
> A \times B = \big\{ (a,b) \;\big|\; a \in A,\; b \in B \big\}
> $$

Notice that for all $1 \leq i \leq k$ and $A_i = A$ then $A_1 \times \dots \times A_k$ is also denoted by $A^k$. 

## Partitions

> *Definition*: let $S$ be a nonempty set. A collection $\Pi$ of subsets is called a partition if and only if 
> 
> * $\varnothing \notin \Pi$,
> * $\bigcup_{X \in \Pi} X = S$,
> * for all $X \neq Y \in \Pi$ there is $X \cap Y = \varnothing$

For example the set $\{1,2, \dots , 10\}$ can be partitioned into the sets $\{1,2,3\}$, $\{4,5\}$ and $\{6,7,8,9,10\}$.

## Quantifiers

> *Definitions*: the universal quantifier "for all" is denoted by $\forall$ and the existential quantifier "there exists" is denoted by $\exists$.

<br>

> *Proposition* **- DeMorgan's rule**: the statement
>
> $$
>   \neg (\forall x \in X \;[P(x)])
> $$
>
> is equivalent with the statement
>
> $$
>   \exists x \in X \;[\neg (P(x))].
> $$
>
> The statement 
>
> $$
>   \neg (\exists x \in X \;[P(x)])
> $$
>
> is equivalent with the statement
>
> $$
> \forall x \in X \; [\neg (P(x))].
> $$

??? note "*Proof*:"

    will be added later.