Here is a rough overview of the basics of AbstractSetTheory, in particular ZFC and how we construct things like numbers and functions.
What is 'abstract' about Abstract Set Theory?
We never worry about, or ask about, what sets actually are. In the formal language of SetTheory, there is only one non-logical symbol: ∈. Abstract set theory is all about the relation ∈. We begin with a set of a priori assumptions about properties that any sensible notion of ∈ should satisfy. We call these axioms. There are a few different sets of axioms for Set Theory, but the most common is ZFC (Zermelo-Fraenkel with the AxiomOfChoice).
Axioms
- Extensionality: two sets are equal if and only if they have the same elements.
- Regularity: every non-empty set contains an element \(y\) disjoint from \(x\).
- Schema of Comprehension: Given a set \(X\) and a formula \(\phi(x)\), the set \(\{x\in X:\phi(x)\}\) exists.
- Pairing: if \(x\) and \(y\) exist, then there is a set containing both \(x\) and \(y\).
- Union: the union over the elements of a set exists. That is, if \(X = \{ x_1, x_2, \ldots \}\) then the set \(\bigcup X = x_1 \cup x_2 \cup \ldots\) exists.
- Replacement: informally if \(f(x)\) is a function definable by a formula \(\phi\), \(A\) is a set, and \(f(x)\) exists for all \(x\in A\), then the set \(\{ f(x) : x\in A\}\) exists.
- Infinity: there is a set containing \(\varnothing\) and closed under the successor operation \(x \rightarrow x \cup \{x\}\).
- Power set: if \(x\) is a set, then so is the set of all subsets of \(x\), which we call the power set of \(x\) and denote it by \(\mathscr{P}(x)\).
- Choice (AC): the cartesian product of a collection of nonempty sets is nonempty.
- Or equivalent to AC: for every set \(X\) there is a binary relation on \(X\) which makes \(X\) well-ordered.
Relations and functions
Given sets \(X\) and \(Y\), the cartesian product of \(X\) and \(Y\), denoted \(X\times Y\) is the set of all pairs \((x,y)\) such that \(x\in X\) and \(y\in Y\). That is: \(X\times Y=\{(x,y) : x\in X, y\in Y\}\). Similarly we define the cartesian product of many sets \(X_1\times X_2\times X_3\times\cdots\). The cartesian product of an infinite collection of sets \(\{ X_i : i\in I\}\) where \(I\) is an infinite index set, is more fiddly to define (essentially elements of the cartesian product of an infinite collection of sets are functions \(f:I\rightarrow\bigcup\{X_i:i\in I\}\) such that for all \(i\in I\) we have \(f(i)\in X_i\)).
A \(n\)-ary relation on a set \(X\) is a subset of \(X\times X\times\cdots\times X\) where the cartesian product is of \(n\) copies of \(X\).
A function \(f:X\rightarrow Y\) is a relation \(R(x,y)\) on \(X\times Y\), such that \(R\) associates an element of \(X\) to at most one element of \(Y\). That is, if \(R(x,y)\) and \(R(x,z)\) then necessarily \(y=z\). When \(R(x,y)\) defines a function, we use the notation \(f(x)=y\).
Properties of functions
A function is injective if different inputs give different outputs. That is, if \(f(x)=z\) and \(f(y)=z\) then \(x=y\).
A function is surjective if its codomain is equal to its range. That is, if \(f:X\rightarrow Y\) then for all \(y\in Y\) there is \(x\in X\) with \(f(x)=y\).
A function is bijective if it is both injective and surjective.
Ordinals
We can construct the natural numbers by identifying \(0\) with the empty set \(\varnothing\), and the proceeding to define the successor \(S(x)=x\cup\{x\}\). This way we get an ordinal for each natural number \(n\in\mathbb{N}\). These are the finite ordinals. We can take the union of all finite ordinals to get the first infinite ordinal, which we denote \(\omega\). We call these limit ordinals. Once we have \(\omega\), we can construct \(S(\omega\)), which we denote \(\omega+1\), and then \(\omega+2\) and so on. Then we can take the union of all the \(\{\omega+n:n\in\omega\}\) to get \(\omega+\omega\), which we denote \(2\omega\). In this way, we can create bigger and bigger ordinals. Either using the successor operation or taking unions to produce limit ordinals. Ordinals are well-ordered. That is, a set of ordinals does not contain an infinite descending sequence.
Cardinals
The cardinality of a set is the 'number' of elements in it. It can be infinite. Two sets have the same cardinality, that is, they are equinumerous if, and only if, there exists a bijective function between them.
The Schröder-Bernstein Theorem says that if there exists an injection \(f:X\rightarrow Y\) and an injection \(g:Y\rightarrow X\) then there exists a bijection \(h:X\rightarrow Y\).
We denote the cardinality of a set \(X\) by \(\|X\|\), and we identify \(\|X\|\) with the smallest ordinal \(\alpha\) such that \(X\) is equinumerous with \(\alpha\). The cardinal of the set of all finite ordinals is denoted \(\aleph_0\), (aleph null), and (assuming AC) is the smallest infinite ordinal.
If we assume the Axiom of Choice, or equivalently, the well-ordering principle, then every set is equinumerous with some ordinal, and so the cardinals are linearly ordered.
Countability
A set is countable if either it is finite or else its cardinality is \(\aleph_0\). Equivalently, a set X is countable if it is the image of some function from \(\omega\). That is, if \(X=\{f(x):x\in\omega\}\).
The power set \(\mathscr{P}(X)\) of a set \(X\) is always of a larger cardinality than \(X\), as can be proved by Cantor's Diagonal Argument. The real numbers \(\mathbb{R}\) are at least as large as the power set \(\mathscr{P}(\mathbb{N})\) of the natural numbers, so are strictly larger (in cardinality terms), than \(\mathbb{N}\).