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 $\Sigma$ be an effectively enumerable set of wffs. Assume that for each wff $\tau$ , either $\Sigma\vDash\tau$ or $\Sigma\vDash\neg\tau$ . Show that the set of tautological consequences of $\Sigma$ is decidable.
(a) Do this where “or” is interpreted in the exclusive sense: either $\Sigma\vDash\tau$ or $\Sigma\vDash\neg\tau$ but not both.
(b) Do this where “or” is interpreted in the inclusive sense: either $\Sigma\vDash\tau$ or $\Sigma\vDash\neg\tau$ or both.
Given $\tau$ , 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 $\Sigma_{n}$ be the first $n$ entries produced by the procedure that enumerates $\Sigma$ , including $\Sigma_{0}=\emptyset$ . Here we assume that $\Sigma_{n}$ ’s are defined as long as the procedure returns at least $n$ elements (it may run forever after all of the elements of $\Sigma$ are listed). $\Sigma_{0}$ is always defined. Starting from $k=0$ we test whether $\Sigma_{k}\vDash\tau$ or $\Sigma_{k}\vDash\neg\tau$ . If the answer of the first test is “yes” then we know that $\Sigma\vDash\tau$ , if the answer of the second test is “yes” then we know that $\Sigma\not\vDash\tau$ , otherwise we increase $k$ by $1$ and continue testing. According to the compactness theorem, if $\Sigma\vDash\gamma$ , then there is a finite subset $\Sigma'$ of $\Sigma$ that also tautologically implies $\gamma$ , in particular, every $\Sigma''$ such that $\Sigma'\subseteq\Sigma''\subseteq\Sigma$ will tautologically imply $\gamma$ , hence, our procedure will eventually return either “yes” or “no” (once we have enumerated all the members of $\Sigma'$ for either $\tau$ or $\neg\tau$ ). Also, importantly enough, if $\Sigma_{k}$ does not imply either $\tau$ or $\neg\tau$ , then there is at least one element of $\Sigma$ which was not yet enumerated, and, therefore, the procedure will not stuck at finding $\Sigma_{k+1}$ . In particular, the very first step tests whether $\tau$ or $\neg\tau$ is a tautology, and if not, then there is at least one element in $\Sigma$ . Alternatively, we could have just shown that $\Sigma$ must be infinite based on the assumption of (a).
(b) For any truth assignment $v$ that satisfies $\Sigma$ , $\overline{v}(\tau)$ and $\overline{v}(\neg\tau)$ are opposite, hence, $v$ cannot satisfy both $\tau$ and $\neg\tau$ . Therefore, we can be in one of the two following cases: either $\Sigma$ is not satisfiable at all, in which case all wffs are tautological consequences of $\Sigma$ , or $\Sigma$ is satisfiable and we are in the case of (a).
At first, I thought that the procedure should check whether $\Sigma$ 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 $\Sigma$ is satisfiable in a finite amount of time. If by listing all members of $\Sigma$ we, at some point, find that a finite subset of $\Sigma$ is unsatisfiable, then so is $\Sigma$ , but as long as we get all finite subsets satisfiable, there seems to be no way to be sure that the whole $\Sigma$ is satisfiable without considering every its member. The simplest example $\Sigma=\{A_{1},A_{2},\ldots\}$ . Having listed the first $n$ elements of $\Sigma$ , we can never be sure that, for example, the next element is not $\neg A_{1}$ . 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 $\Sigma$ itself is not an input to the procedure we are looking for. $\Sigma$ is decidable as long as there is a procedure that can decide whether any expression is in $\Sigma$ or it is not. We are not required to know the procedure. In our case, all $\Sigma$ ’s as stated in (b) fall into two classes. The first class contains all unsatisfiable $\Sigma$ ’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 $\Sigma$ . The second class contains all $\Sigma$ ’s that are satisfiable and (a) holds. For these $\Sigma$ ’s the procedure described in (a) will decide for any wff whether it belongs to such $\Sigma$ or not. Therefore, every $\Sigma$ satisfying (b) is decidable, we just don’t know which of the two procedures is the one that works for this particular $\Sigma$ .
P.S. Later, reading the book, I found a similar argument on page 144 (the very last paragraph).