Talk:Löwenheim–Skolem theorem

confusing

The article here and the articles around it (First-order logic Second-order logic) I find terribly confusing.

We have:

"The Lowenheim-Skolem theorem states that any "model" M has a countably infinite submodel N that satisfies exactly the same set of first-order sentences that M satisfies. A "model", in this sense, consists of an underlying set (often also denoted) "M" and a set of relations on the underlying set M and a set of functions (sometimes taking several arguments) from M into itself."

My first difficulty is what "first order" sentences are. It says under First-order logic that "first-order logic is strong enough to formalize all of set theory and thereby virtually all of mathematics." But it also says " It [FOL] is a stronger theory than sentential logic, but a weaker theory than arithmetic, set theory, or second-order logic." Yet under Second-order logic we have "second-order logic differs from first-order logic in that it allows quantification over subsets of a domain, or functions from the domain into itself, rather than only over individual members of the domain."

I have difficulty in understanding how "first-order logic is strong enough to formalize all of set theory and thereby virtually all of mathematics." But also that FOL by implication does not allow "quantification over subsets of a domain". These statements seem to contradict each other. If FOL does not allow quantification over subsets of a domain, how can it "formalize all of set theory and thereby virtually all of mathematics."?

Individuals are subsets of the domain and they are obviously quantified over in FOL. What is meant is that quantification over predicates and functions taken as subsets of the domain is not permitted. In any case, FOL is capable of formalizing set theory but certainly not all of mathematics. E.g. it cannot formalize finitude, which is a consequence of the Löwenheim-Skolem theorem (and essentially Konig's lemma). Nortexoid 01:05, 8 Jun 2005 (UTC)

This article attempts to explain the apparent paradox further down. "An optimist might attempt to reduce second-order logic to first-order logic in the following way. Expand the domain from the set of all real numbers to the union of that set with the set of all sets of real numbers. Add a new binary predicate to the language: the membership relation. Then sentences that were second-order become first-order. "

OK. That sounds to just like set theory. But it then continues

"But notice that the domain was asserted to include all sets of real numbers. That requirement has not been reduced to a first-order sentence! But might there be some way to accomplish the reduction? The classic Löwenheim-Skolem theorem entails that there is not. That theorem implies that there is some countably infinite subset of R, whose members we will call internal numbers, and some countably infinite set of sets of internal numbers, whose members we will call "internal sets", such that the domain consisting of internal numbers and internal sets satisfies all of the first-order sentences satisfied by the domain of real-numbers-and-sets-of-real-numbers. In particular, it satisfies a sort of least-upper-bound axiom that says, in effect:

     Every nonempty internal set that has an internal upper bound has a least internal upper bound. 

Countability of the set of all internal numbers (in conjunction with the fact that those form a densely ordered set) necessarily implies that that set does not satisfy the full least-upper-bound axiom. Countability of the set of all internal sets necessarily implies that is not the set of all subsets of the set of all internal numbers (since Cantor's theorem implies that the set of all subsets of a countably infinite set is an uncountably infinite set). "

But if Cantor's theorem is expressed within set theory itself, which is (if I understand this) simply FOL plus signs for sets, what is Cantor's Theorem saying?

Cantor's theorem is saying exactly what it states. I suppose you mean, how are we to interpret the first-order sentence that there are uncountably many members of the powerset of the naturals (or the reals) if that sentence has a denumerable model. Different people give different interpretations. Nortexoid 01:05, 8 Jun 2005 (UTC)

On this subject generally, in an article by Peter Suber (who is also normally very good), I find that "the Skolem paradox only afficts first order theories". So does it afflict set theory or not? Is set theory a first or second order theory? Also, [in correspondence] Harvey Friedman told me that there was effectively no difference between second order systems and set theory. I may have misunderstood this. He said there was a huge amount of confusion among philosophers about the difference between second ordeer logic and set theory. It certainly confuses the h-ll out of me.

Skolem's paradox only affects first-order theories because second-order ones don't have the Löwenheim-Skolem (nor compactness) property. Yes, it affects first-order axiomatizations of set theory, but not second-order ones.

There is effectively no difference between second-order theories and set theory. You can formalize set theory in second-order systems but you have an entirely different model theory than that of first-order theories--e.g. completeness does not hold. Nortexoid 01:05, 8 Jun 2005 (UTC)

Finally, regarding the "move" to 2nd order, it seems to me that any sentence of the form

the smallest x such that [….] that is greater than any y such that [….]

is happily first order, and also completely set-free, once we have made an appropriate substitution into the […] bit. The difficult bit is capturing the part that says "a sentence *of this form*" i.e. to say it has a "form" at all, we allude to the fact that any appropriate formula can be substituted into […], i.e. we quantify over "formulas". Is that what really makes it second order?

There is nothing here about Skolem's Paradox. Or anywhere in Wikipedia except for Model theory.

The whole part you quoted above that mentions upper bounds is about the paradox. According to the LS theorem, any first-order set theory will have a countable model if it has any model at all. But the powerset of the countable naturals is a set in this theory and by Cantor's theorem (which holds in this theory) it is uncountable. So obviously such an axiomatization of set theory fails fully to capture certain notions such as 'set' and 'uncountable'. Nortexoid 01:05, 8 Jun 2005 (UTC)

In summary, is there any modification to these articles that would resolve the confusion? And to add, Michael, for it surely you who will read this, that your articles are generally superlative, and among the best in Wikepedia! I remain a fan. Dean.

User: dbuckner

Thank you.

I'm not sure I can write very clearly about Skolem's paradox. Just as there are countable models of the reals that are not "internally" countable, so there are countable models of ZFC that "internally" look as if they contain all sets. Michael Hardy 00:52, 9 Jan 2004 (UTC)

Change of notation for signature: $\sigma \rightarrow a$

The notation on this page used 'sigma' as the arity function, whilst the article on 'signature' used 'sigma' as the name of the signature itself and the arity function was called 'a' -- I've changed the notation in this article to conform with the article signature Zero sharp 04:21, 24 September 2007 (UTC)

merge

I think the article on the upward L-S theorem should be merged here. — Carl (CBM · talk) 16:14, 16 November 2007 (UTC)

I agree. --Hans Adler (talk) 23:00, 16 November 2007 (UTC)

Also agree, not clear why there were ever two (articles, not theorems). Zero sharp (talk) 05:08, 22 November 2007 (UTC)

I merged them. Please feel free, as always, to rearrange and fix my prose. — Carl (CBM · talk) 01:37, 25 November 2007 (UTC)

I am sorry Carl, I forgot to leave a note that I was rewriting this article in user space. Now you have obviously put quite a bit of work into merging the two original versions. I have replaced the article with my version nevertheless, but feel free to revert. --Hans Adler (talk) 10:18, 25 November 2007 (UTC)

If you do revert, the complete text (and quite a lot of other stuff) is also here: User:Hans Adler/Model theory and universal algebra. --Hans Adler (talk) 10:22, 25 November 2007 (UTC)

AC and Skolem 1923

Gregory Moore writes in Zermelo's Axiom of Choice, page 251f:

Not until Gödel [1930] did mathematical logicians carefully and uniformly observe the distinction between a syntactic notion such as consistency (no contradiction can be derived) and the curresponding semantic notion of satisfiability. [...]

Löwenheim studied sentences in which quantifiers ranged over relations as well as sentences in which the quantifiers were restricted to individuals. In addition, he permitted his sentences to contain denumerable strings of quantifiers and of relations. Despite this wealth of expressive power, he formulated a theorem which revealed a severe limitation in the strength of first order logic: if a first order sentence A is true in every finite domain, but not in every domain, then A is false in some denumerable domain. [...]

Löwenheim's [1915] proof [...] relied on a distributive law which stated that a sentence $\forall x\,\exists y\,A(x,y)$ is true in a domain if and only if ${\exists }y_{\lambda }\,\forall x\,A(x,y_{\lambda }(x))$ is true there, where $\lambda$ ranges over all individuals of the domainl. (To Löwenheim, the quantifier $\mathbf {\exists } y_{\lambda }$ was a possibly uncountable sequence of individual existential quantifiers, one for each individual in the given domain.) [...]

Skolem [retained] countably many quantifiers in a given sentence, [but] circumvented Löwenheim's second order semantics through the introduction of new first order relations -- in effect, Skolem functions. Yet Skolem continued to obscure the boudnary between [...] consistency and satisfiability by stating L's result in the following form:

A 1st order sentence is either contradictory or else satisfiable in a countable domain.

[...] What he actually proved was

If a first order sentence is satisfiable in a set M, it is satisfiable in a countable subset of M.

[...] By 1922, Skolem [...] criticized Zermelo's system [...] Furthermore, he proved without using AC a weaker version of the LS theorem:

If a countable family of sentences is satisfiable, then it is satisfiable in the domain $\mathbb {N}$ of natural numbers. [...] concluded that Z's system could be satisfied in $\mathbb {N}$ [...] known as the Skolem paradox.

So there are several issues here:

1. Single sentences, or countable theories
2. strictly first order, or allowing infinitely many quantifiers, and/or second order quantifiers
3. Do we want just any countable model, or a countable submodel of a given model?

Concerning the axiom of choice, we know now that

• Clearly some version of the axiom of choice is needed to get a countably infinite substructure of any infinite structure (never mind elementarity -- ZF does not prove that any infinite set contains a copy of the natural numbers)
• No AC is needed if we want to show that any countable consistent 1st order theory has a countable model. The usual (Henkin) proof of Gödel's completeness theorem gives such a model, and does not use AC. (Neither does Gödel's original proof, I think.)

Aleph4 (talk) 11:14, 12 December 2007 (UTC)

Assessment comment

The comment(s) below were originally left at Talk:Löwenheim–Skolem theorem/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

I believe this should be merged into Löwenheim-Skolem theorem, since nowadays model theorists rarely think of the upward and downward LS theorems as two separate theorems. --Hans Adler 21:37, 13 November 2007 (UTC)

Substituted at 18:28, 17 July 2016 (UTC)

Copyright infringement or violation?

The current lead of this article very similarly matches text on page 160 of the book "A Functorial Model Theory: Newer Applications to Algebraic Topology " by Cyrus F. Nourani. At present At least one similar sentence existed in this article before the publication of the book. Needs more investigation. Jason Quinn (talk) 13:29, 27 February 2020 (UTC)