Weak Skolem-Löwenheim and completeness

Question

In T. Skolem 1922 the author publishes a weak version of the Skolem-Löwenheim theorem which we call WLS and which according to Wikipedia says that every countable theory which is satisfiable in a model is also satisfiable in a countable model. My understanding is that WLS entails completeness in the sense of K. Gödel 1929. Does completeness entail WLS?

Edit:

Noah Schweber and Emil Jeřábek are right in that WLS does not literally entail completeness, nor vice versa. Nevertheless, earlier today in Equivalence between Lowenheim-Skolem Theorem and Godel Completeness I came across the following statement: “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 ¬A is satisfiable” (“provable” taken in an informal sense).'” Clearly, 'implicitly proved' is here understood e.g. so so that information from the proof sufficed to give the completeness proof.

When it concerns the formulation of my question, I was also confounded by the title of the page I just linked to.

Memory and Google reveal that there are several authors who comment upon Gödel's statement quoted above. See e.g. pp. 50-51 in Paul Mancosu, The adventure of Reason: ...

Presumably the "implicit" connections between WLS and completeness has connections with WKL.

References:

K. Gödel 1929: Über die Vollständigkeit des Logikkalküls, Doctoral dissertation, University Of Vienna

Skolem 1922: Einige Bemerkungen zu axiomatischen Begründung der Mengenlehre, 5th Scand. Math. Congress

Answer 1

For simplicity, below all languages are finite.

At least at an abstract enough level, neither implication holds. When we go a bit more into the details, there is some truth to "completeness yields WLS," but it's not too robust - and the other direction (contra your claim) I don't see at all.

---

It's easiest to argue that completeness does not entail WLS in any sense. Consider for example $FOL_{\ge\omega_1}$, first-order logic expanded by a quantifier "There are uncountably many." Trivially this does not have WLS; however, it turns out that its set of validities is r.e. and so is complete (or rather, admits a sound and complete "good proof system") in the strongest sense I can imagine.

The other direction is made more complicated by the lack of a clear meaning for "completeness" (this wasn't a serious issue in the previous paragraph since we had a counterexample even with respect to the strongest notion of completeness available). For example, there is a "completeness theorem" due to Barwise for the infinitary logic $\mathcal{L}_{\omega_1,\omega}$ (or rather, its "tame" fragments); does that count? Conversely, the narrowest notion of completeness - "has an r.e. set of validities" - is pretty limiting: it only makes sense for logics with countably many sentences, and even among those logics it's "presentation dependent" in the sense that it's not a property of the logic on its own but rather the logic together with a fixed numbering.

That said, contra your claim I don't see any notion of completeness which is implied by WLS. Put another way, a logic with WLS to which completeness might apply basically amounts to a sequence $(P_i)_{i\in\mathbb{N}}$ of subsets of the class of isomorphism types of countable structures; no complexity constraint is placed on the subsets themselves or the sequence as a whole. So there's nothing here which would give computational simplicity in any sense.

---

Of course - and Emil Jerabek pointed this out in a comment above - this doesn't address the possibility of a more nuanced connection: does a proof of WLS for FOL specifically naturally yield a proof of completeness for FOL specifically (and vice versa)?

Ironically, the direction you're asking about seems to me more solid than the direction you assert. Both Godel's and Henkin's proofs of completeness yield countable models, and so - by combining with the soundness theorem - yield WLS. (This also shows the importance of the "for FOL specifically" in the previous paragraph - consider $FOL_{\ge\omega_1}$.) However, I don't see a natural proof of WLS which yields completeness as a corollary (unless we cheat and prove WLS by going through completeness in the first place).