Misplaced Pages

Revision as of 22:49, 7 June 2005

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 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."?

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?

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

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 Misplaced Pages except for Model theory.

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)