Section 1.2: Problem 10 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
Say that a set of wffs is equivalent to a set of wffs iff for any wff , we have iff . A set is independent iff no member of is tautologically implied by the remaining members in . Show that the following hold.
(a) A finite set of wffs has an independent equivalent subset.
(b) An infinite set need not have an independent equivalent subset.
(c) Let ; show that there is an independent equivalent set . (By part (b), we cannot hope to have in general.)
(a) We can show it either by removing dependent wffs from the set, or by induction. Let us use the induction principle. If then it is vacuosly independent (indeed, it does not contain any formula, not to say the one that would be tautologically implied by the others) and equivalent to itself. A more interesting case to consider is when , i.e. it has one formula only. If is not a tautology, then is independent and equivalent to itself. Now, if is a tautology, then the empty subset of is independent. For any wff , iff for any truth assignment , iff for any truth assignment , iff for any truth assignment such that , (this “such that” does not actually restrict the choice of ) iff . That is, is equivalent to . The induction step. Assume that we have wffs in and that for all lower numbers of wffs in we have already shown the existence of an independent equivalent subset. If all wffs in are not tautologically implied by the others, then is independent and equivalent to itself. Suppose, now, that is tautologically implied by . Then, by assumption, there is an independent subset of which is equivalent to . We need to show that it is also equivalent to . For a wff , iff iff for any truth assignment that satisfies , iff for any truth assignment that satisfies , (again, by saying this, we do not restrict the choice of , as satisfies iff it satisfies ) iff .
The fact that we repeatedly used here is that if , then iff . The other solution we indicated uses this fact to show that by removing dependent formulas one by one we still have a subset which is equivalent to the initial set.
(b) Remark: Whether we prove (a) by induction, as we did, or by removing dependent formulas one by one, the proof would not work in the infinite case. The induction principle shows a statement for finite numbers (I am not talking about the generalized induction principle, which is not applicable in this case), and the second method would leave us with an infinite subset after each step.
Of course, we could have tried to generalize the statement at the end of (a) to the following, if then iff , and then consider the subset of all dependent wffs in , and take . This is something that we did for the case where there is one formula in only. In general, however, there are at least two problems with this. First, there might be wffs in that are dependent on each other. For example, if there are two tautologically equivalent wffs in , then both will be included to leaving nothing tautologically implying either one in . But even if we take special care of this case, there is a more general problem. It might happen, that there is an infinite sequence of wffs in such that each wff in the sequence is dependent on the following, leaving us with no subset (finite or infinite) that would be independent and that would tautologically imply the rest.
The simplest example, I can think of, is when , where , and . Each is tautologically implied by (and any for ). At the same time, the only independent subsets of are the empty set and . The empty subset does not tautologically imply any , while does not tautologically imply . And, of course, it is clear that if and are equivalent, then each tautologically implies any formula in the other one.
(c) Here we consider the infinite case, the finite case is covered in (a). However, now we don’t have the subset restriction. Therefore, we may combine ’s to form new formulas. So, suppose we have which is equivalent to and independent. The fact that it is equivalent to implies that all ’s are true iff all ’s are true. The independence means that for any there should be a truth assignment such that while for all .
Looking at the example in (b), we note that is satisfied by one truth assignment only, namely, the one that sets all sentence symbol values to . This suggests, that as we could have simply consider . However, there are too many ways to obtain the sequence from the initial one, so it by itself does not provide a further clue.
But let us try something similar. First, for each formula we want to ensure that it is not tautologically implied by the others, this means that there should be a truth assignment such that while all other . This is necessary and sufficient to show the independence of . Second, to show the equivalence of and , we need to ensure that all wffs in are evaluated to iff all wffs in are evaluated to . Let us try to make the first requirement stronger, that is, for every truth assignment such that , we require for . Note, that this is equivalent to the requirement that whenever , for all . Indeed, in this case, if we assume that two formulas are evaluated to , then one index should be larger than the other one, meaning that the corresponding formula should have been evaluated to . Of course, this, by itself, is not enough to ensure that is independent, as we would further have to assume that for every there is at least one truth assignment such that . Given this new requirement, for equivalence, we require that if all wffs in are evaluated to , then all wffs in are evaluated to , but if there is at least one wff in that is evaluated to , then there is exactly one wff in that is evaluated to . To pick which one is evaluated to , we may try to require that it is the one with the minimum index such that is evaluated to .
To sum up, given wffs , we want to construct a sequence such that the condition (*) holds: given any truth assignment , if and only if and for all . It is easy to see that this requirement is sufficient to guarantee the equivalence of and and independence of , as long as for each there is at least one truth assignment such that . We will get to this latter condition later. Given the condition (*), is evaluated to iff is evaluated to , i.e. we can try to take . Next, is evaluated to iff is evaluated to and is evaluated to , i.e. we take . Next, is evaluated to iff is evaluated to and both and are evaluated to , i.e. we take . Continuing this way, we conclude that our approach leads to . Note that for any assignment , iff and iff for , and iff the condition (*) holds. This by itself guarantees the equivalence of and . As was noted above, we need something more to guarantee the independence of . The problem is that might never be evaluated to , meaning that whenever all previous ’s are true, is true as well. The problem here may come from two different issues. First, it could be the case that is tautological. Second, it could be the case that whenever is false, for some , is false. Overall, we do not have to consider each different case separately. Indeed, we just note that in this case (as constructed) is tautological. Further, for any set of wffs and any set of tautologies, is tautologically equivalent to ( iff , similar to Exercise 4(a), where is iff all wffs in are and is , iff , since is a tautology). Now, we can simply exclude all tautologies . Note, that in this case a) there is at least one truth assignment such that , and, hence, for , , b) if all ’s are then all ’s are , c) if is the least index such that is , then the initial is not a tautology, hence, not excluded, and is evaluated to . Therefore, we have independence and equivalence.
Two special cases to consider, just for fun. First, the example of (b). After obvious transformations we get , which takes the form of and is evaluated to iff is evaluated to while is evaluated to , implying that is just tautologically equivalent to , something different from what we came up in (b) using different reasoning. Note, that unlike our solution in (b), here, if one formula is false, then all others are true. Second, suppose that there is such that no truth assignment satisfies it. Then, for every , is a tautology, i.e. excluded. Hence, we may assume that is the lowest index with the property. Since is never satisfied, by itself, it tautologically implies any other formula (p. 23), moreover, due to this, also tautologically implies any other formula, hence, one way to obtain an equivalent independent set of wffs is to just take one formula . is independent, as is not tautologically implied by the empty set, and it is equivalent to as both tautologically imply any formula. Note, that in this case . However, our method may produce a more complicated system of equations. For example, suppose that is not a tautology and is satisfied by at least some truth assignments, and . As we noted, we can just consider , in which case . However, according to our more general method, all ’s are removed from for , and , . Since is not satisfied by any truth assignments, is tautologically equivalent to . That is, essentially, we obtain an equivalent set of wffs , which is, as , not satisfied by any truth assignments (hence, tautologically implies any formula, and is equivalent to ), and independent, since we assumed that is not a tautology and is satisfied by at least one truth assignment. Note that (assuming that ).