Section 1.2: Problem 8 Solution
Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.
James R. Munkres
(Substitution) Consider a sequence of wffs. For each wff let be the result of replacing the sentence symbol by , for each .
(a) Let be a truth assignment for the set of all sentence symbols; define to be the truth assignment for which . Show that . Use the induction principle.
(b) Show that if is a tautology, then so is . (For example, one of our selected tautologies is . From this we can conclude, by substitution, that is a tautology, for any wffs and .)
(a) Let be the set of all sentence symbols. Let be the set of all wffs such that . Then, by assumption, all sentence symbols are in (here we assume that if there is a sentence symbol different from all , then , though, I think, what is meant here is that ’s form the set of all sentence symbols, as was defined earlier in the text). Now, if , then , where, by definition, and , and, similarly, , where, by definition, is valuated according to the truth tables. One thing to mention here is that we used equalities and which simply mean that the substitution in a formula is equivalent to the substitution in its components, which is easy to accept or show using induction. Finally, by the induction principle, we conclude that , and .
(b) ( is a tautology) iff (every truth assignment on implies ) THEN (here is where iff does not work) (every truth assignment on implies , where is defined as in (a)) iff ( is a tautology). To see that the other direction does not work, consider, for example, the wff , which is not a tautology, together with the substitution . Then, , which is a tautology.