Skip to main content

Section 5.2 Bounded comprehension

We also want to be able to carve out pieces of our sets defined by suitable formulas. So if \(X\) is a set, and \(\phi(x)\) is some formula of set theory (any sentence of predicate calculus along with \(\in\) in which the only free variable is \(x\)), then the axioms of set theory allow us to form a set

\begin{equation*} A = \left\{x\in X : \phi(x)\right\}\text{.} \end{equation*}

Thus \(A\) is the set whose elements are all and only those elements \(x\in X\) such that \(\phi(x)\) obtains.

It's important that sets defined by formulas are carved out of existing sets. This is called bounded comprehension. With an unbounded comprehension axiom, we would be able to build the following:

\begin{equation*} R\coloneq\left\{X : \neg(X\in X)\right\}\text{.} \end{equation*}

You may have seen this: this \(R\) creates some challenges, since \(R \in R\) if and only if \(R \notin R\text{.}\) This is the example that Bertrand Russell cooked up, just to ruin Gottlob Frege's day.