Axiom of Schema Separation

A formula can be written as ${\psi(x,p)}$ . This is referencing all ${x}$ and ${p}$ for which ${\psi}$ is true. The Axiom of Schema Separation effectively builds a new set from an existing set. This may, in isolation, appear a circular way of building sets. This will be addressed later when we consider the axiom that claims the existence of the empty set ${\phi}$ .

Let ${X}$ be a set, ${x\in X}$ and ${p}$ a parameter. Then a new set ${Y}$ can be formed by selecting from ${X}$ all the values of ${x}$ and ${p}$ for which a given formula ${\psi}$ is true.

Axiom: The axiom of Schema of Separation

$\displaystyle Y = \{x\in X : \psi(x,p)\} \ \ \ \ \ (1)$

$\displaystyle \forall Y \; \forall{p}\; \exists X\;[x\in X \iff (y \in Y \; \land \; \psi(y,p))] \ \ \ \ \ (2)$

The formula ${\psi}$ must be written using ${\in}$ or ${=}$ in terms of first order predicate logic using connectives ${\land}$ , ${\lor}$ , ${\neg}$ , ${\implies}$ and ${\iff}$ and quantifiers ${\forall}$ and ${\exists}$ .

It follows from the Schema of Separation that we can define the intersection between two set and that this is a set.

Definition: Let ${A}$ and ${B}$ be sets. The intersection is:

$\displaystyle A \cap B = \{a \in A : a \in B\} \ \ \ \ \ (3)$

The set of the intersection is formed from elements that are in both ${A}$ and ${B}$ .

Definition: Let ${A}$ and ${B}$ be sets. The difference between ${A}$ and ${B}$ is:

$\displaystyle A-B = \{a \in A : a \notin B\} \ \ \ \ \ (4)$

The difference between two sets is a set that has all the elements that are in ${A}$ but are not in ${B}$ .

Definition: Let ${A}$ and ${B}$ be sets. The union of two sets is:

$\displaystyle A \cup B = \{a\in B \; \lor \; b\in B \} \ \ \ \ \ (5)$

The union of two sets is a set that has all the elements that are in ${A}$ and are in ${B}$ .

Definition: Let ${A}$ be a set. There exists an empty set ${\phi}$ .

$\displaystyle \phi = \{x : x \ne x \} \ \ \ \ \ (6)$

This defines a set that has no elements ${\phi = \{\}}$ .

The above definitions, as extensions to the Schema of Separation, construct new sets. But they still do so from existing sets. To help solve this situation we need the Axiom of Pairing.