Set Theory

Alexander Neville

2023-01-04

A set is a collection of different items; a set contains elements. A set can be simply expressed by enumerating its elements, typically inside \(\{\),\(\}\) curly brackets. \(\{2,4,6,8\}\) and \(\{\text{Alex}, \text{Benjamin}, \text{John}\}\) are examples of sets.

Membership & Equality

The symbol \(\in\) denotes set membership, so if \(x\) is a member of set \(A\) this can be written \(x \in A\). The notation \(x \notin A\) means that \(x\) is not an element of \(A\). Two sets are equal when they contain the same elements, formally:

\[ A = B \iff (\forall x.x \in A \iff x \in B)\]

Subsets

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

\[ B \subseteq A \iff (\forall x.x \in B \implies x \in A)\]

Any set is a subset of itself \(A \subseteq A\). If \(B \subseteq A\) and \(A \neq B\), then \(B\) is a proper subset of \(A\), written \(B \subset A\).

\[ B \subset A \iff (\forall x.x \in B \implies x \in A) \land \neg (A = B) \]

Two sets are equal if and only if they are subsets of each other.

\[ A = B \iff (A \subseteq B \land B \subseteq A)\]

Set Operations

Some common set operations:

Set Cardinality

Every finite set \(A\) has a natural number cardinality \(|A|\), its size or number of elements. The empty set is written \(\emptyset\) or \(\{\}\) and has a cardinality of \(0\). \(\{\emptyset\}\) is not the empty set, as \(1 \neq \{1\}\) it is the singleton set, with cardinality \(1\).

Set Builder Notation

Enumeration of a subset's elements is inconvenient for large subsets. A subset can be constructing concisely by selecting items from another set according to logical conditions in set-builder notation. The \(|\) symbol is read "such that".

\[\{n \in \mathbb{N} \text{ } | \text{ }n \ge 10\} = \{10, 11, 12, \ldots\}\] \[\{n^2 \text{ } | \text{ } n\in \mathbb{N}, n^3 \ge 8\} = \{4, 9, 25, \ldots\}\]

Product of Sets

A tuple is a finite, ordered sequence of elements. An ordered pair is a 2-tuple, while an ordered triple is a 3-tuple, in general an n-tuple has \(n\) elements. The ordered pair \((a, b)\) does not equal \((b,a)\) unless \(a=b\); order matters surprisingly. The product of two sets is the set of all ordered pairs.

\[A \times B \stackrel{\text{def}}{=} \{(x,y) | x \in A, y \in B\}\]

Every lists of sets has a product. The product of \(\emptyset\) is \(\{()\}\).

\[A \times B \times C \stackrel{\text{def}}{=} \{(x,y,z) | x \in A, y \in B, z \in C\}\]

Special Sets

Subset Algebra

For any set \(S\), \(\mathcal{P}S\) is the set of all subsets of \(S\). If \(A\) and \(B\) are elements of \(\mathcal{P}S\) they are both subsets of \(S\), called the common or ambient set. Operations on \(A\) and \(B\) include \(A \cup B\) and \(A \cap B\) and also the complement of \(A\) relative to \(S\), written \(\overline{A}\).

\[\overline{A} \stackrel{\text{def}}{=} S \setminus A\]

The axioms that these operations have:

Any set equipped with the operations \(\land\), \(\lor\), \(\neg\) and two constants \(\top\) and \(\bot\) forms a boolean algebra. Every power set forms a boolean algebra assigning \(\emptyset = \bot\) and the ambient set \(S = \top\).

See Also

Or return to the index.