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.

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:

if \(A \subseteq B\) and \(B \subseteq C\) then \(A \subseteq C\),

if \(A \subseteq B\) and \(B \subseteq A\) then \(A = B\).

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))]. \]

Proof:

will be added later.