Proof of induction principle

Theorem 1.1.3 (induction principle) of Dirk Van Dalen "Logic and Structure" states:

Let $A$ be a property, then $A(\phi)$ holds for all $\phi \in PROP$ if:

• $A(p_i)$, for all i;
• $A(\phi),A(\psi) \Rightarrow A(\phi \square \psi)$
• $A(\phi) \Rightarrow A(\neg \phi)$

I don't understand the little proof he gives. He writes let $X=\{\phi \in PROP | A(\phi) \}$, then X satisfies the conditions of the recursive definition of $PROP$. So $PROP \subseteq X$,i.e. for all $\phi \in PROP$ $A(\phi)$ holds.

• There must a definition before that theorem that says that $PROP$ is the smallest set that satisfies the given properties. Since $X$ satisfies the given properties, then certainly it is larger than the smallest set which satisfies these properties. Thus $PROP\subseteq X$. Commented Sep 27, 2014 at 17:16
• No problem. If no one posts an answer in a 'reasonable' amount of time, it would be good if you answered the question yourself so it doesn't come up as unanswered. Commented Sep 27, 2014 at 17:21
• Sure I'll do it Commented Sep 27, 2014 at 17:22

The proof comes from the fact that PROP is the smallest set of well-formed formulae. The proof van Dalen gives is correct, but too brief. As he defines $X=\{\phi \in PROP | A(\phi) \}$, then by the definition of PROP, which is the smallest set of well-formed formulae, it follows that $PROP \subseteq X$, otherwise it would be smaller than PROP itself.
For the sake of avoiding confusion, I feel it should be pointed out precisely in what sense PROP is the "smallest" set of well-formed formulae. For example, $\{10,11\}$ is certainly the smallest set of consecutive integers that add up to $21$, but that does not mean that it is a subset of $\{6,7,8\}$.