Talk:Löwenheim–Skolem theorem

From Wikipedia, the free encyclopedia

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)