Induction

We now know what $V$ is, the universe of all sets. We started this journey in order to build this universe and one of the guiding principles was that all objects in the universe are just pure sets. However, it is not completely clear what this means, so I went on to say that sets should be determined by their elements and nothing else. We had so far only one axiom that asserted this kind of "setness" of sets, that is the Axiom of Extensionality. Arguably, though, this is not enough. For example, nothing that I've said up to now can answer whether there exists a set $x$ which belongs to itself. Even more concretely, is there a set $x$ which is equal to $\{x\}$? I'm sure that you will find a prospect of such an object unusual, after all it would satisfy things like

$$x=\{x\}=\{\{x\}\}=\{\{\{x\}\}\}=\cdots .$$

Furthermore, say that $y$ also satisfies $y=\{y\}$, is then $y$ equal to $x$? If they're not equal, then $y$ is an element of $y$ which is different from all elements of $x$ and witnesses that $y\ne x$. However, the fact that $y$ is different from all elements of $x$ is true only because we assumed that $y\ne x$ to begin with!

I hope that I convinced you that sets of these kind are pathological. In a similar fashion, one can also argue that having a situation of the form $x\in y\in x$ would be pathological as well. The axiom that I'm going towards will eliminate this kind of anomalies and further fortify the "setness" of sets. To formulate it, let's say that a property $P(x)$ is inductive if for all sets $a$, the assumption that the property $P$ holds for all elements of $a$ necessarily implies that the property $P$ holds for $a$ itself. Intuitively, such a property propagates itself upwards, that is from elements to the set determined by those elements. Let's also say that a property $P(x)$ is universal if it holds for all sets. In terms of classes, we are simply saying that

$$\{x:P(x)\}=V.$$

Now, the new axiom that I want to introduce is Axiom of Induction and it states that every inductive property is universal. Intuitively, if a property propagates itself from elements of an arbitrary set to the set itself, then it propagates itself to all the sets. 

Let's see that this axiom implies that no set belongs to itself. We had in the previous post, in Russell's paradox, the class

$$R:=\{x:x\notin x\}.$$

We didn't know then if this class contains all the sets or not. Now, we can show that it actually does, that is that $R=V$. So, in attempt to show that the class $R$ is universal, we know that it suffices to just verify that it is inductive. Let's then verify that $R$ is inductive. We are given some set $a$ and we know that all elements of $a$ have the property $R$. It is our job to show that $a$ also has the property $R$. We will reason by contradiction, meaning that we will assume that $a$ doesn't have the property $R$ and then conclude an absurd statement from this assumption. Okay, we are assuming that $R(a)$ is false. Looking up the definition of $R$, we realise that this just means that $a\in a$. In words, we get that $a$ is an element of $a$. However, all the elements of $a$ have the property $R$, so in particular, the element $a$ also has the property $R$. But this is absurd:  we assumed to begin with that $a$ doesn't have the property $R$! Since we reached a contradiction, we see that $R$ is inductive and consequently, $R=V$.

Arguably, the axioms of Extensionality and Induction are two most important axioms since they determined the meaning of the quality of being a set. Other axioms only assert that sets of this or that kind exist. Very often, one has to look at restrictive universes where not all of these sets exist, thus giving up on some of the axioms. However, one virtually never gives up on Extensionality and Induction, making them essential to Set Theory. Later on, we will use Induction to establish a very special and conceptual stratification of the universe, so called Von Neumann hierarchy of sets. This hierarchy is crucial for the modern set-theoretic intuition and one more reason why Induction has a central role in Set Theory.