Hi all,
I am interested in proofs without using Goedel's completeness theorem.


* Does anyone have a reference to a proof of this theorem that uses Skolem Functions?
* How come Enderton's (Introduction to Logic) has a half a page proof (which looks OK to me) and Boolos (Computability And Logic) has a full chapter of it?


Thanks.



Compactness Theorem for First Order Logic
There's a proof of compactness using Skolem functions in the book "Elements of Mathematical Logic. Model Theory" by Kreisel and Krivine. (I'm assuming here that the English version matches the French, because the latter is the one I checked.) It presupposes the compactness theorem for propositional logic.


The proof runs as follows: Given a finitely satisfiable set $S$ of formulas, Skolemize them to get a set $S'$ of universal formulas that is satisfiable if and only if $S$ is. (Technical detail: If the vocabulary has no constant symbols, adjoin one, so that there are some closed terms for use in the next step.) Let $S''$ be the set of all the formulas you get from those in $S'$ by deleting the universal quantifiers and replacing the variables by closed terms in all possible ways. The formulas in $S''$ are propositional combinations of atomic sentences; by regarding the atomic sentences as propositional variables, we can view $S''$ as a set of formulas of propositional logic. Finite satisfiability of $S$ (in the sense of first-order logic) implies finite satisfiability of $S''$ (in the sense of propositional logic). By propositional compactness, there is a truth assignment satisfying $S''$. That truth assignment amounts to a description of a structure (in the first-order sense) in which every element is the value of some closed term. This structure satisfies $S'$ and therefore $S$.


