Section 1.7: Compactness and Effectiveness

Compactness Theorem

A set of wffs is satisfiable iff every finite subset is satisfiable.

Given a set $\Sigma$ of wffs that is finitely satisfiable, extend it recursively by including each possible wff (there are countably many) or its negation depending on which one makes the extended set finitely satisfiable at each step. Then, the resulting set $\Delta$ contains $\Sigma$ and all wffs or their negations, and is finitely satisfiable. Now, for each sentence symbol $A$ we assign $v(A)=T$ iff $A$ is in the extended set (i.e. $v(A)=F$ iff $\neg A$ is in the extended set; both $A$ and $\neg A$ cannot be there, as it would make $\{A,\neg A\}$ an unsatisfiable finite subset of $\Delta$ ). Then, $v$ satisfies a wff iff it is in $\Delta$ .

If $\Sigma\vDash\tau$ , then there is a finite subset $\Sigma_{0}\subseteq\Sigma$ s.t. $\Sigma_{0}\vDash\tau$ .

In fact, the corollary is equivalent to the Compactness Theorem, that is the truth of the latter can be shown if the truth of the corollary is assumed.

Effectiveness and Computability

A set of expressions $E$ is called decidable iff there is an effective procedure that, given an expression, will decide whether it belongs to $E$ or not.

A set of expressions $E$ is called effectively enumerable (semidecidable) iff there is an effective procedure that, given an expression, produces a positive answer iff it belongs to $E$ .

A set of expressions $E$ is effectively enumerable iff there is an effective procedure that lists all the members of $E$ .
The Parsing Algorithm of Section 1.3 ensures that the set of wffs is decidable.
(Kleene’s Theorem) A set of expressions $E$ is decidable iff both it and its complement are effectively enumerable.
- The class of effectively enumerable sets is closed under union and intersection.
- The class of decidable sets is closed under union, intersection and complementation.

A function $f$ is effectively computable (or simply computable) iff there is an effective procedure that, given any $x\in\mbox{dom}f$ , produces $f(x)$ .

Decidability of tautological consequences

The truth table procedure of Section 1.2 ensures that there is an effective procedure to decide whether $\Sigma\vDash\tau$ for a finite $\Sigma$ .
- In particular, the set of tautological consequences of a finite set $\Sigma$ is decidable.
- The set of tautologies is decidable.
If $\Sigma$ is infinite, even if decidable itself, the set of its tautological consequences may not be decidable.
- If $\Sigma$ is effectively enumerable, the set of its tautological consequences is effectively enumerable as well (follows from compactness).
- If $\Sigma$ is effectively enumerable, and such that for any $\tau$ , $\Sigma\vDash\tau$ or $\Sigma\vDash\neg\tau$ (in either exclusive or inclusive meaning of “or”), then the set of its tautological consequences is decidable.

Completeness

These facts are more important for the first-order logic and will reappear in Section 2.4.

Define a deduction from $\Sigma$ to be a finite sequence $<\alpha_{1},\ldots,\alpha_{n}>$ of wffs such that for each $k\le n$ one of the following holds: $\vDash\alpha_{k}$ , $\alpha_{k}\in\Sigma$ , or there are $i,j<k$ : $\alpha_{i}=(\alpha_{j}\rightarrow\alpha_{k})$ ( $\alpha_{k}$ is obtained by modus ponens from

and $\alpha_{j}$ ).

$\Sigma\vDash\alpha_{n}$ .
If $\Sigma\vDash\tau$ , there is a deduction $<\ldots,\tau>$ from $\Sigma$ .

Subpages

Section 1.7: Compactness and Effectiveness

Section 1.7: Compactness and Effectiveness

Compactness Theorem

Effectiveness and Computability

Decidability of tautological consequences

Completeness