One of the most common uses for the recursive definition of sets is to define the well-formed formulae in various mathematical systems. For example, in the study of logic we can define the well-formed formulae as follows:
1) Each primitive statement p, the tautology T0, and the contradiction F0 are well-formed formulae; and
2) If p, q are well-formed formulae, then so are
i) (¬p)
ii) (p ∨ q)
iii) (p ∧ q)
iv) (p → q)
v) (p ↔ q)
Using this recursive definition, we find that for the primitive statements p, q, r, the compound statement {{p ∧ (¬q)) → (r ∨ T0)) is a well-formed formula. We can derive this well- formed formula as follows:
Steps Reasons
1) p, q, r, T0.................................... Part (1) of the definition
2) (¬q)............................................. Step (1) and part (2i) of the definition
3) (p ∧ (¬q)).................................... Steps (1) and (2) and part (2iii) of the definition
4) (r ∨ T0)........................................ Step (1) and part (2ii) of the definition
5) ((p ∧ (¬q)) → (r ∨ T0))............. Steps (3) and (4) and part (2iv) of the definition
For the primitive statements p, q, r, and s, provide derivations showing that each of the following is a well-formed formula.
(a) ((p ∨ q) → (T0 ∧ (-r)))
(b) (((¬p) ↔ q) → (r ∧ (s ∨ F0)))