Additions to First Order Logic

We began by discussing naive set theory. This is elegant, simple, intuitive, and generally lovely; the only problem is that it leads straight to disaster.

To get naive set theory, we make some small additions to first-order logic. First, we either add a predicate Set() to indicate that something is a set, or we distinguish between two styles of variables, one for anything at all and the other exclusively for sets. Our text chose the latter route, distinguishing between the variables $x, y, z, . . .$ which can range over anything at all, and the variables $a, b, c, . . .$ which range only over sets.

Next, we add a single new relation symbol to the language of first-order logic, namely the symbol $\in{}$ to represent set membership. Thus a sentence such as $c \in S$ indicates that the element $c$ is a member of the set $S$.

Third, we add axioms concerning the logical properties of the set membership relation. In naive set theory, we need to add only two axioms (or more precisely, one axiom and an axiom scheme).

Axiom 1.1 (Axiom of Extensionality)   $\forall a \forall b [ \forall x (x \in a \leftrightarrow x \in b ) \to a=b]$

Axiom 1.2 (Axiom of Comprehension)   $\exists a \forall x [x \in a \leftrightarrow P(x)]$

(Note that in the Axiom of Comprehension, $P(x)$ can be replaced by any formula expressible in first-order logic that contains $x$ as a free variable. Also note that $P(x)$ may also contain additional free variables $z_1, z_2, \ldots, z_n$, in which case the instance of the axiom schema must be prefixed by universal quantifiers $\forall z_1, \forall z_2, \ldots, \forall z_n$.)