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