Sets#

Definition: Set

A set is a collection of well-defined objects, called elements.

Notation

The notation \(a \in A\) means that \(a\) is an element of the set \(A\).

The notation \(a \notin A\) means that \(a\) is not an element of the set \(A\).

Note

A set can contain pretty much anything - numbers, letters, cars, sentences, people, colours and even other sets.
A set can contain either finitely many or infinitely many elements.

Definition: Singleton

A singleton is a set with exactly one element.

Definition: Equality

Two set are equal if they contain the same elements.

Axiom: Existence of an Empty Set

There exists a set with no elements.

\[ \exists A: \forall x:x \notin A \]

Notation

\[ \varnothing \qquad \emptyset \qquad \{\} \]

Theorem: Uniqueness of the Empty Set

There is only one empty set.

Proof

Let \(A\) and \(B\) be two empty sets. They have no elements and so the statement

\[ x \in A \iff x \in B \]

is vacuously true. Therefore, \(A = B\).

Theorem: Empty Set as Subset of all Sets

The empty set is a subset of all set.

Proof

Let \(A\) be a set.

Suppose that the empty set \(\varnothing\) is not a subset of \(A\). Then there must exist an element \(e \in \varnothing\) which is not an element of \(A\), i.e. \(e \notin A\). This is a contradiction, since the empty set contains no elements.

There are three main ways to represent and define sets.

The descriptive form uses words to describe a set. For example, the set \(S\) is the set of all odd natural numbers which are less than 12.

The set-builder form defines a set by specifying a condition that all of its members satisfies and looks like this:

\[ \text{set} = \{\text{ placeholder }|\text{ condition }\} \]

The placeholder is simply there so you can use it to more easily write the condition. The | character can be read as "such that". For example, specifying the aforementioned set \(S\) using set-builder notation will look like the following.

\[ S = \{s|s \text{ is an odd number and } 0 \lt s \lt 12\} \]

The final way to define a set is simply by listing all of its elements or listing enough of them, so that whoever is reading the definition can easily establish the pattern they follow. For example, the aforementioned set will be written as

\[ S = \{1,3,5,7,9,11\} \]

Subsets#

Definition: Subset

A set \(A\) is a subset of another set \(B\) if all elements of \(A\) are also elements of \(B\).

\[ a \in A \implies a \in B \]

Notation

If \(A\) is a subset of \(B\), we write \(A \subseteq B\). Some people also write \(A \subset B\), but this notation can be ambiguous.

If \(A\) is not a subset of \(B\), we write \(A \not\subseteq B\) or \(A \not \subset B\).

Definition: True Subset

A set \(A\) is a true subset / strict subset of another set \(B\) \(B\) if \(A \subseteq B\) and \(A \ne B\).

\[ (a\in A \implies a\in B) \land (\exists b \in B : b \notin A) \]

Notation

If \(A\) is a true subset of \(B\), we write \(A \subsetneq B\). Some people also write \(A \subset B\), but this notation can be ambiguous.

Definition: (Strict) Superset

A set \(A\) is a (strict) superset of another set \(B\) if \(B\) is a (strict) subset of \(A\).

Notation

\[ A \supseteq B \qquad A \supset B \]

Definition: Power Set

The power set of a set \(M\) is the collection of all subsets of \(M\).

\[ \{T \mid T \subseteq M\} \]

Notation

\[ \mathscr{P}(M) \qquad \mathcal{P}(M) \qquad \mathsf{P}(M) \qquad P(M) \qquad \mathbb{P}(M) \qquad 2^M \]

Definition: Indicator Function

Let \(S\) be a subset of a set \(X\).

The indicator function of \(S\) is the function \(\mathbf{1}_S: X \to \{0, 1\}\) defined as

\[ \mathbf{1}_S(x) = \begin{cases} 1 \qquad \text{if } x \in S \\ 0 \qquad \text{if } x \notin S \end{cases} \]

Operations#

Definition: Union

The union of two sets \(A\) and \(B\) is the set which contains exactly the elements which are in \(A\), in \(B\) or in both \(A\) and \(B\).

\[ \{x \mid x\in A \lor x\in B\} \]

Notation

\[ A \cup B \]

Definition: Intersection

The intersection of two sets \(A\) and \(B\) is the set of all elements which are both in \(A\) and in \(B\).

\[ \{ x \mid x\in A \land x \in B\} \]

Notation

\[ A \cap B \]

Definition: Disjoint Sets

We say that \(A\) and \(B\) are disjoint if their intersection is the empty set.

\[ A \cap B = \varnothing \]

Definition: Set Difference

The set difference \(A \setminus B\) of two sets \(A\) and \(B\) is the set which contains exactly the elements in \(A\) which are not elements of \(B\).

\[ \{x \mid x \in A \land x \notin B\} \]

Notation

\[ A \setminus B \qquad A - B \]

Definition: Complement

Let \(B\) be a subset of a set \(A\).

The complement of \(B\) in \(A\) is the difference \(A \setminus B\).

Definition: Symmetric Difference

The symmetric difference of two sets \(A\) and \(B\) is the set of all elements which are only in \(A\) and those elements which are only in \(B\):

\[ (A \cup B) \setminus (A \cap B) \]

Notation

\[ A \triangle B \qquad A \oplus B \]

Definition: Cartesian Product

Let \(A_1, \dotsc, A_n\) be non-empty sets.

The Cartesian product \(A \times \cdots \times A_n B\) is the set of all ordered pairs \((a_1, \dotsc, a_n)\) such that \(a_i \in A_i\):

\[ A\times B \overset{\text{def}}{=} \{(a; b)\mid a\in A \land b \in B\} \]

Theorem: Cardinality of the Set Union

The union of two finite sets \(A\) and \(B\) has cardinality

\[ |A\cup B| = |A|+|B|-|A \cap B| \]

Proof

TODO

Theorem: Commutativity of the Set Union

The union of two sets \(A\) and \(B\) is commutative:

\[ A\cup B = B \cup A \]

Proof

TODO

Theorem: Commutativity of Set Intersection

The intersection of two sets \(A\) and \(B\) is commutative:

\[ A \cap B = B \cap A \]

Proof

TODO

Theorem: Associativity of Set Intersection

The intersection of sets is associative:

\[ (A\cap B)\cap C = A\cap(B\cap C) \]

Proof

TODO

Theorem: Cardinality of the Cartesian Product

The Cartesian product of two finite sets \(A\) and \(B\) has cardinality

\[ |A \times B| = |B \times A| = |A|\cdot |B| \]

Proof

TODO

Theorem: Distributive Laws for Set Operations

The set operations have the following properties:

\[ A\cup (B\cap C) = (A\cup B) \cap (A\cup C) \]

\[ A\cap(B\cup C) = (A\cap B)\cup(A\cap C) \]

\[ A\setminus(B\cup C) = (A\setminus B)\cap (A\setminus C) \]

Proof

TODO