Proof of induction principle

Question

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.

Answer 1

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.

Answer 2

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\}$.

However, when it comes to being a set of all propositional formula, all the conditions are of the form "you must contain these things" and "if you contain these things you must also contain these things". Because of this very particular form (there are mathematically more precise ways to formulate it), it is the case that there does exist a set, namely PROP, such that if you satisfy the conditions, you must contain PROP as a subset.