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