Set Theory
Table of Contents
The basic idea in set theory is to model all mathematical objects as sets. A set is a collection of elements, with no concept of ordering, so the set \(\{1, 2\} = \{2, 1\}\). The only relevant information about a set is which objects are inside the set. The notation we use for an element being in a set is \(\in\). So the notation \(1 \in S\) means that the number \(1\) is in the set \(S\).
Every set has a cardinality. The cardinality is a fancy word for size. So the set \(\{1, 2\}\) has a cardinality of 2.
Operations on Sets
Given a set \(A = \{a_1, ..., a_n\}\) and a set \(B = \{b_1, ..., b_m\}\), there are a number of binary operations you can use on sets:
Union \(\cup\)
The union \(A \cup B = \{a_1, ..., a_n, b_1, ..., b_m\}\) is the set containing all the elements which are in \(A\) or \(B\).
Intersection \(\cap\)
The union \(A \cap B = \{c_1, ..., c_k\}\) is the set containing all the elements \(c_i\) which are in \(A\) and \(B\).
Difference
The difference \(A - B\) is the set of all elements that are in \(A\) but not in \(B\).
Cartesian Product
The Cartesian product of two sets \(A = \{a_1, a_2\}\) and \(B = \{b_1, b_2, b_3\}\) is the set: \[\begin{align}A \times B = \{ &(a_1, b_1), (a_1, b_2), (a_1, b_3), \\ &(a_2, b_1), (a_2, b_2), (a_2, b_3)\}\end{align}\]
Notice that the cardinality of \(A\), \(|A| = 2\) and \(|B| = 3\), and also \(|A\times B| = 6 = 2\times 3\). So the cardinality of the product of the sets is the product of the cardinalities of the sets.
Subsets
A set \(S\) where every element \(s \in S\) is also in some other set \(T\), is called a subset of \(T\). So if \(s \in S\) implies that \(s \in T\), then we write \(S \subseteq T\).
Relations
A relation between two sets \(A\) and \(B\) is a subset of \(A \times B\)
Functions
A function \(f\) from \(A\) to \(B\) is a subset of the relation \(A\times B\), with the constraint that if \((a,b_1) \in f\) and \((a, b_2) \in f\), then \(b_1 = b_2\). This condition allows us to talk about the value \(f(a)\) in an unambiguous way. That is, there is only one unique value \(f(a)\) which will be in the right hand side of the pair \((a, f(a))\). The notation we use for \(f\) is: \[f : A \to B\]