Section 1.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
Let be the ternary connective such that is equivalent to .
(a) Show that is complete.
(b) Show that no proper subset is complete.
Remark: is the ternary parity connective; the condition for is that for an odd number of ’s. is the binary parity connective. The function in the proof of Theorem 15B is the 3-place parity function.
(a) Note that is tautologically equivalent to . Together with we have a complete system of connectives.
(b) Now, similar to the previous exercise, we look for some properties of connectives such that the set of wffs satisfying each such property is closed under connectives, but not all connectives satisfy the property, in particular, and do not. To show that no proper subset is complete, for each connective in the set we need to find such property that all the other connectives satisfy it, but not the given one. In other words, there should be something unique in each connective that makes the set complete. In the previous exercises we have already listed some such properties.
is the only connective that is not evaluated to when all operands are evaluated to .
Similarly, is the only connective that is not evaluated to when all operands are evaluated to .
For we could proceed in two possible ways. First, similar to the first solution of Exercise 3, we could consider all wffs in two sentence symbols and using only, and show that we cannot construct any wffs tautologically equivalent to or . It seems that, eventually, we would have to show that the set of wffs generated by , under is the same as the one generated by , under , which is not complete according to Exercise 5. Second, the first solution suggests that we can apply ideas of Exercise 5. Namely, we can consider on the set of sentence symbols . Similar to Exercise 5, we call a wff in and even, if the number of truth assignments that evaluates the wff to is even. Then, all sentence symbols are even, is even ( ’s), is even ( ’s), and if for , and the number of truth assignments that evaluate , , to , where , is, respectively, , and ( , and are even), then is even as well ( ’s). Hence, the set of all even wffs in and contains the set of wffs generated by under , yet it does not cover all wffs in and , such as and . We conclude that is not complete.
is a bit harder as we did not use any property in the previous exercises that would distinguish from the set of others. Indeed, two properties used in Exercise 2 are already used for and . Another property used in Exercise 2, which is dependance on no more than 1 sentence symbol, satisfies the first two connectives only. The property used in Exercises 3 and 4 (self-duality) satisfies only. And the property used in Exercise 5 is already used. However, in this case the method of Exercise 3 (the first solution) is most applicable. We just note that the set of wffs is closed under in the sense that the application of any connectives from to any wffs that are tautologically equivalent to some wffs in , results in a wff that is again tautologically equivalent to one from . If the connective is or then the result is immediate, and if and are tautologically equivalent to some wffs from , then is also tautologically equivalent to some wff from (we need to consider cases such as being tautologically equivalent to , to , to itself, and to ). Hence, by induction, noting that all sentence symbols are in , we conclude that the set of wffs generated from using consists of wffs that are tautologically equivalent to one of those in , but since not all wffs are equivalent to one of those, the set is not complete.
Another way to see that is necessary for completeness, is to note that all connectives in are “increasing” in the sense that changing the truth assignment for any sentence symbol from to never results in changing of the evaluation of a wff built with these connectives from to (it may not change at all, or increase, but never decrease). This property is also inherited by wffs from sentence symbols, if the connectives used in the wff satisfy this property. And do satisfy this condition, while, for example, or do not.