Monday, April 30, 2007

Up Yours, Loweheim-Skolem

Still plenty of time of get in other questions for this week. For those new to the Playground, we'll entertain any question at all, auto mechanics to quantum mechanics. If there is anything you've always wanted to know and have never figured out where to ask, let 'er rip here.

For our first question this week, Hanno asks,

How can Skolem regard the upward L-S theorem as 'nonsense?'

Follow up: In what sense can a mathematical proof recognized by multitudes of mathematicians be 'nonsensical?'
I am a bit hesitant to take this question on as I know even bringing up the Lowenheim-Skolem Theorem tends to get people a bit riled. But please, remember, under control people, this is a friendly blog, no ad hominems in the comments. Tomorrow, I promise, we'll talk about something less controversial, religion.

The entire matter is embedded in the late 19th/early 20th century project to find a logical foundation for arithmetic. In the mid-nineteenth century, we had non-Euclidean geometry pop up. It worried mathematicians because it was stranger than they were and it really worried philosophers because euclidean geometry was the template many used for true justified belief, it was the bedrock example of non-trivial things we knew to be true with absolute certainty. If the upstart non-Euclidean geometries could be shown to be inconsistent, that is, to give rise to contradictions, then they could not be true and would have to be rejected, leaving Euclid as necessarily true thereby saving centuries of philosophical thought on knowledge.

Of course, it wasn't to be. Felix Klein, Eugeno Beltrami, and Henri Poincare (twice) produced relative consistency proofs showing that the only way the non-Euclidean geometry could be inconsistent is if Euclid was as well -- something no one wanted to contemplate. But, then, where was the proof that Euclidean geometry itself won't give rise to a contradiction? David Hilbert showed that Euclidean geometry was consistent if arithmetic was, thereby kicking the mathematical can a bit down the intellectual road. But how do we know that arithmetic won't, somewhere, produce a contradiction?

This was a huge question and starting with folks like Gottlob Frege and Bertrand Russell, the hope was to show that ultimately, it all boiled down to logic which could be shown consistent. A half-step in the process translated arithmetic talk to set theory and the idea was to show that we could come up with a consistent set of axioms for set theory that would allow us to derive all of the results of arithmetic as a model, that is an interpretation of the axioms of our theory about sets.

It was at this juncture that Lowenheim and then a few years later in a more elegant fashion, Skolem, came up with what we now call the The Lowenheim-Skolem theorem which states,
If you have a countable first-order language L and a theory T in that language, if the T has a model then it has a countable model.
Huh? The idea is that if you take a language of the sort that was supposed to be strong enough in which to express the basic axioms of arithmetic, any set of possible axioms would have a model, an interpretation about a set of things with the same number of members as the counting numbers 1, 2, 3,...

To proceed, we need to realize that while the number of counting numbers is infinite, there are sets of numbers that are bigger. Gregor Cantor proved (if there is interest, we could talk about this later) that the number of real numbers is larger than the number of counting numbers. (The real numbers are all the rational numbers -- those that can be expressed as fractions or alternately terminating or repeating decimals -- and the irrational numbers -- numbers like pi that cannot be represented as a ratio of counting numbers and are representable as non-repeating decimals [pi goes on forever with no pattern or end].)

The Lowenheim-Skolem Theorem has a couple of variants and results -- the upward and downward versions -- which gave rise to what is called Skolem's paradox. The idea is that if we have set of axioms that gives us a model of arithmetic for the real numbers (remember, this is the question that motivated the whole project), then Skolem showed that this theory, which has as a central result "there is an uncountable set (that is, as set of numbers bigger than the counting numbers)," must have a countable model. But how can you satisfy a theory with a domain that only has a countable number of numbers when that very theory posits an uncountable number of numbers? Nonsense, says Skolem, even though he just proved it. Skolem thought that this unintended model undermined the standard approach to set theory. Mathematicians don't share Skolem's concerns, but philosophers take it quite seriously.

How can someone take a recognized proof to be nonsense? First of all, remember the times. there were all sorts of odd paradoxes and contradictions showing up around set theory at the time, so skepticism would not have been unwarranted. But secondly, the notion of nonsense could also tie to the interpretation of the theorem; that is, someone could argue that the theorem could not really do what it seems to do and that once we get inside and do some fancy logical footwork, we'll realize that things aren't as bad as we first thought. For a nice piece on the routes around Skolem's paradox and whether they work, here's Timothy Bays' chapter from Jacquette's Philosophy of Logic.

Alternatively, Skolem could have been using the phrase "doing logic" in the same way Hanno has been known to, that is, as referring to, shall we say, acts of a certain non-logical nature. Perhaps Skolem was saying that it was nonsense for Mrs. Skolem to argue that any axiomatic model of "doing logic" could thus be satisfied by sets of larger cardinality. Adds a whole new dimension to the "axiom of extension," if you know what I mean...

So there's my two cents. For the comments, remember please be polite. If you can't say anything nice, don't say anything at all.