Foundation and epsilon-induction

1. Introduction

Either by examining the sets created in the first few levels of the cumulative hierarchy or from other means, via considering the idea of constructions of sets perhaps, we conclude that we do not expect sets to have infinite descending sequences

x_{0} ∋ x_{1} ∋ x_{2} ∋ x_{3} ∋ x_{4} ∋ \dots

at least for sets in the cumulative hierarchy of constructed sets. The axioms of Zermelo-Fraenkel set theory are intended to represent axioms true in this hierarchy, so we expect to have an axiom stating there can be no such descending sequence.

Unfortunately, the statement that there is no such descending sequence is not first order, but second order. This is analogous to the fact that there are nonstandard structures satisfying all first order sentences of arithmetic true in $ℕ$ . However, the example of arithmetic provides at least one clue as to a powerful axiom scheme true in all structures without infinite descending chains: induction. Applied to set theory we have the axiom scheme of $\in$ -induction.

Axiom Scheme of $\in$ -Induction: For all first order formulas $ϕ (x, \overline{a})$ of the language $L_{\in}$ , $\forall \overline{a} (\forall x (\forall y \in x ϕ (y) \to ϕ (x)) \to \forall x ϕ (x, \overline{a}))$ .

We are not going to adopt this as an axiom scheme for Zermelo Fraekel because it will follow from other axioms, and it will be instructive to see how that happens. We will, however, adopt the following special case of $\in$ -Induction.

Axiom of Foundation: $\forall x (\exists y y \in x \to \exists y (y \in x \land \neg \exists z (z \in x \land z \in y)))$ .

Other ways of saying this include: if $x$ is nonepty there is a set $y \in x$ such that $y \cap x = \emptyset$ ; and if $x$ is nonepty there is an $\in$ -minimal $y \in x$ i.e. one with no $z \in x$ having $z \in y$ .

Proposition.

The axiom of fountation follows from the axiom scheme of $\in$ -induction.

Proof.

Indeed by the contrapositive of the axiom of $\in$ -induction for the formula $ϕ (x, a)$ which is $x \notin a$ you should find that either $a = \emptyset$ or $\exists x \in a \forall y \in x y \notin a$ , as required.

2. Applications

We look at some of the applications of the axiom of foundation combined with some of the other axioms already proposed.

Proposition.

For no set $x$ does $x \in x$ .

Proof.

Consider the $\in$ -least $y$ in $\{x\}$ . Of course it must be $x$ , but then my $\in$ -minimality we have $x \notin x$ .

Proposition.

For all sets $x, y$ we have $x \cup \{x\} = y \cup \{y\}$ implies $x = y$ .

Proof.

If $x \cup \{x\} = y \cup \{y\}$ and $x \neq y$ then $x \in y$ and $y \in x$ since both are in $x \cup \{x\} = y \cup \{y\}$ . Now look at the $\in$ -minimal element of $\{x, y\}$ . If this is $x$ then $y \notin x$ and if this is $y$ then $x \notin y$ . Either way we get a contradiction.

Often the empty set is denoted $0$ rather than $\emptyset$ . The operation $s (x) = x \cup \{x\}$ is called the successor of $x$ . (It exists by application of pair set and sum set axioms.) Clearly $0$ is not the successor of any set, and by the previous proposition the successor operation is 1-1. This already shows that there are infinitely many sets. The next axiom uses the idea of successor to state that there is an infinite set.