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\}$.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}