# Section 1.7: 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

Let
be an effectively enumerable set of wffs. Assume that for each wff
, either
or
. Show that the set of tautological consequences of
is decidable.

(a) Do this where “or” is interpreted in the exclusive sense: either
or
but not both.

(b) Do this where “or” is interpreted in the inclusive sense: either
or
or both.

Given
, we may want to first check whether it is a wff (Theorem 17B tells us that this is decidable). So, assume it is (otherwise return “no”).

(a) Let
be the first
entries produced by the procedure that enumerates
, including
. Here we assume that
’s are defined as long as the procedure returns at least
elements (it may run forever after all of the elements of
are listed).
is always defined. Starting from
we test whether
or
. If the answer of the first test is “yes” then we know that
, if the answer of the second test is “yes” then we know that
, otherwise we increase
by
and continue testing. According to the compactness theorem, if
, then there is a finite subset
of
that also tautologically implies
, in particular, every
such that
will tautologically imply
, hence, our procedure will eventually return either “yes” or “no” (once we have enumerated all the members of
for either
or
). Also, importantly enough, if
does not imply either
or
, then there is at least one element of
which was not yet enumerated, and, therefore, the procedure will not stuck at finding
. In particular, the very first step tests whether
or
is a tautology, and if not, then there is at least one element in
. Alternatively, we could have just shown that
must be infinite based on the assumption of (a).

(b) For any truth assignment
that satisfies
,
and
are opposite, hence,
cannot satisfy both
and
. Therefore, we can be in one of the two following cases: either
is not satisfiable at all, in which case all wffs are tautological consequences of
, or
is satisfiable and we are in the case of (a).

At first, I thought that the procedure should check whether
is satisfiable, and if not, then return “yes” for any wff, and if yes, then run the procedure of (a). However, I was not able to think of a way to decide whether an infinite set
is satisfiable in a finite amount of time. If by listing all members of
we, at some point, find that a finite subset of
is unsatisfiable, then so is
, but as long as we get all finite subsets satisfiable, there seems to be no way to be sure that the whole
is satisfiable without considering every its member. The simplest example
. Having listed the first
elements of
, we can never be sure that, for example, the next element is not
. Therefore, it seems that the set of all unsatisfiable sets of wffs is effectively enumerable, but its complement, the set of all satisfiable sets of wffs is not.

But then, I realized that we don’t need this. The thing is, that
itself is not an input to the procedure we are looking for.
is decidable as long as there is a procedure that can decide whether any expression is in
or it is not. We are not required to know the procedure. In our case, all
’s as stated in (b) fall into two classes. The first class contains all unsatisfiable
’s, and for each of them the procedure that always return “yes” (as long as the input expression is a wff, as noted in the beginning) is the one that will always decide whether a wff is in such
. The second class contains all
’s that are satisfiable and (a) holds. For these
’s the procedure described in (a) will decide for any wff whether it belongs to such
or not. Therefore, every
satisfying (b) is decidable, we just don’t know which of the two procedures is the one that works for this particular
.

P.S. Later, reading the book, I found a similar argument on page 144 (the very last paragraph).