0
$\begingroup$

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

$\endgroup$
6
  • 4
    $\begingroup$ How does weak Lowenheim-Skolemential completeness? At least the statement doesn't - we can have logics with the weak Lowenheim-Skolem property which don't have any good proof system (note that nothing in your statement of wLS has to do with proofs, and in particular you've referred to satisfiability instead of *consistency). $\endgroup$ Mar 15 '20 at 18:58
  • 3
    $\begingroup$ Löwenheim–Skolem does not entail completeness in any sense I can think of. The converse is not true either, though standard proofs of completeness of classical first-order logic also give Löwenheim–Skolem for free. $\endgroup$ Mar 15 '20 at 20:08
  • $\begingroup$ You guys are right that WLS does not literally entail completeness, nor vice versa. Nevertheless, earlier today in mathoverflow.net/questions/337144/… 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. $\endgroup$ Mar 15 '20 at 22:16
  • $\begingroup$ so so that information from the proof sufficed to give the completeness proof. (I was also confounded by the title of the page I just linked to.) $\endgroup$ Mar 15 '20 at 22:22
  • $\begingroup$ Se also pp. 50-51 in Paul Mancosu, The adventure of Reason: ... $\endgroup$ Mar 15 '20 at 23:09
2
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ You and Emil Jeřábek are right in that WLS does not literally entail completeness, nor vice versa. Nevertheless, earlier today in mathoverflow.net/questions/337144/… 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).'” $\endgroup$ Mar 16 '20 at 11:59
  • $\begingroup$ Clearly, 'implicitly proved' is here understood e.g. so so that information from the proof sufficed to give the completeness proof. $\endgroup$ Mar 16 '20 at 11:59
  • $\begingroup$ When it concerns the formulation of my question, I was also confounded by the title of the page I just linked to. $\endgroup$ Mar 16 '20 at 12:01
  • $\begingroup$ Memory and Google reveal that there are several authors who comment upon Gödels statement quoted above. See e.g. pp. 50-51 in Paul Mancosu, The adventure of Reason: ... Presumably the "implicit" connection between WLS and completeness has connections with WKL. $\endgroup$ Mar 16 '20 at 13:03
  • 1
    $\begingroup$ Tangential comment about $FOL_{\geq\omega_1}$: If I remember correctly, after it was proved that the set of validities is r.e., Keisler gave a nice, natural axiomatization for this logic. The key axiom said essentially that, if an uncountable set is partitioned into countably many pieces, then at least one of the pieces is uncountable. $\endgroup$ Mar 16 '20 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.