# Equivalence between Lowenheim-Skolem Theorem and Godel Completeness

In papers published 1920 and 1922, Skolem offered two separate proofs of a result due to Lowenheim. On this basis we can distinguish a strong and a weak version of the Lowenheim-Skolem theorem as follows:

The weak (1922) version states that if a closed formula $$\phi$$ of quantification theory is satisfiable, then it is satisfiable in a countable domain. This version does not require the Axiom of Choice; a model of $$\phi$$ is built up from below using numerals to instantiate the variables.

The (1920) "subdomain" version states that if $$\phi$$ is satisfiable in an (infinite) domain D, then it is satisfiable in a countable subdomain D' of D, where the predicates retain the same meaning in D' as in D (modulo the restriction).

Skolem (1922) gives no formal proof procedure. However, the level-by-level construction of the denumerable model implicitly supplies an effective procedure for refuting a formula in a finite number of steps. This occurs if we reach a level for which no satisfying truth-value assignment exists for the approximation to the formula considered at that level, thus implying the formula's negation. This explains why Godel (Coll. Wrks. Vol 1, p. 52) writes that Skolem's weak theorem implies completeness: "Skolem...could justly claim...that, in his 1922 paper, he implicitly proved: 'Either A is provable or $$\neg$$A is satisfiable” (“provable” taken in an informal sense).'

What about the subdomain version? In this version, Skolem starts with $$\phi$$ in normal form (i.e. $$\forall x \exists y\psi$$, where $$\psi$$ quantifier-free) and uses the axiom of choice to find witnesses $$f(x)$$ for the existential quantifier, taken from a domain D in which $$\phi$$ is assumed to be satisfied. Let $$a$$ be an arbitrary element from D. The proof continues by closing $$a$$ under the following operation. Consider all the classes $$X\subseteq$$D such that $$a \in X$$ and if $$x \in X$$, then $$f(x) \in X$$. Skolem then applies a result from Dedekind's chain theory to conclude that the intersection of all such classes $$X$$ must be denumerable (cf. Dedekind 1888).

By omission, Godel implies that this subdomain version cannot be interpreted so as to yield completeness. I assume this is because the method Skolem uses does not, as in the weak version, implicitly describe a refutation procedure for $$\phi$$ since the assumption of $$\phi$$'s satisfiability in D is crucial in the description of the submodel.

Question:

(a) Is that the correct reading?

(b) Does it mean that the weak version, in order to provide a refutation procedure, does not make use of the antecedent in its statement?

## Main references

1. Skolem 1920, Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit mathematischer Sätze nebst einem Theoreme über dichte Mengen, Videnskapsselskapet Skrifter, translated in (3) as Logico-combinatorical investigations in the satisfiability or provabilitiy of mathematical propositions: A simplified proof of a theorem by L. Löwenheim and generalizations of the theorem

2. Skolem 1922, Einige Bemerkungen zu axiomatischen Begründung der Mengenlehre, 5th Scand. Math. Congress, translated in (3) as Some remarks on axiomatized set theory

3. Jean van Heijenoort (ed.) 1977, From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931, Harvard University Press

• The statement 'Either A is provable or ¬A is satisfiable” is a relation between provability and satisfiablility. The statement "if a closed formula ϕ of quantification theory is satisfiable, then it is satisfiable in a countable domain" says nothing about provability. So I think you need to get clearer on just what each person is saying. – Colin McLarty Jul 28 '19 at 23:50
• @ColinMcLarty Thanks for the heads up. I have modified the post and question accordingly. – Mallik Jul 29 '19 at 3:19
• An interesting and thoughtful question! Small suggestion, though: it would be very helpful to give full references to the Skolem papers (and ideally also links, if you can find them online), since their details are central to the question. – Peter LeFanu Lumsdaine Jul 29 '19 at 7:37
• @PeterLeFanuLumsdaine Thank you for filling those in! – Mallik Jul 29 '19 at 14:11
• Your reference "Coll. Wrks. Vol 1, p. 52" is wrong. May you rectify it, please, and also advice here as you do it? – Frode Alfson Bjørdal Mar 15 at 22:50

## 1 Answer

On Question (a), yes this is correct. On Question (b), almost yes. If you drop the assumption that ϕ is satisfiable, then Skolem has given a sound and complete procedure for refuting a formula in a finite number of steps. However it is not (and cannot be) also effective. If the formula is in fact not refutable then the procedure may run forever without showing at any finite point that the formula is not refutable.

It is easy to prove tree/tableaux methods like this cannot be sound, complete, and effective: some formulas have only infinite interpretations, and the tree cannot construct such in a finite number of steps. What is harder is to show there is no sound, complete, effective procedure for refutability at all.