Section 2.5: Problem 7 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
The completeness theorem tells us that each sentence either has a deduction (from ) or has a counter-model (i.e., a structure in which it is false). For each of the following sentences, either show there is a deduction or give a counter-model.
(a) This sentence is not valid. Let where . Then, for any , and , therefore, , , and .
(b) This sentence is valid. We need to show that . By the deduction and generalization theorems, it is sufficient to show that . By axiom group 2, MP and contraposition, it is sufficient to show that . By MP and contraposition rules, using the axiom of group 2 , we have . And, using the axiom of group 1 and MP, we have .
(c) This sentence is not valid. The example of a structure in which it is false is the same as in (a) where . For any , , , , and , therefore, , , , , , and .
(d) This sentence is valid. We need to show that , or, equivalently, (here we use the following definition of : means ). By the generalization theorem, it is sufficient to show that which we denote as . For this, it is sufficient to show that where is a term substitutable for in . Indeed, by axiom group 2, , and, using MP and contraposition, we have . Now, is substitutable for in , and is simply , a tautology.