# 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
).