1

Stuart Shapiro mentioned in his book Thinking about Mathematics that Lowenheim-Skolem theorem showed the "relativity" of a model in mathematics. What does it actually mean? What does the phrase "to relativize an oracle" mean?

EDIT: In order to clarify the confusion, I found the phrase "relativize an oracle" from different context, NOT from the book.

  • A little more context would be useful. Could you provide some text from the book? – stoicfury Aug 6 '13 at 5:27
2

I do not have this book, so I cannot know what the phrase "to relative an oracle" is supposed to mean, but I can explain the relativity of models in mathematics that results from this theorem.

In a given universe U of set theory, consider a theory T and an infinite model M of T. According to that theorem, the cardinal of M may be any infinite cardinal (countable or uncountable, as viewed by U).

Now let us change the viewpoint, and consider the universe U with the system M inside it, from the outside : U is just a model of set theory among others. If U is a countable model of set theory, then M will be countable too when viewed from outside U, even if it was uncountable when viewed by U.

Set theory also admits models U where the set N of natural numbers it contains, is uncountably infinite (when viewed from outside). In this case M will also be uncountable when viewed from outside (as it contains a copy of this uncountable N), even if it is countable when viewed by U.

I also wrote a site on the foundations of mathematics, that contains these issues.

  • Like the diagram in that website! – Sniper Clown Aug 6 '13 at 0:29
0

Relativity of a model and relative to an oracle are two distinct mathematical notions coming from different areas of mathematics. They're not connected.

A theory can be presented in axiomatic form. One then attempts to constuct a model to show that this theory actually models something. Now one would hope that for certain theories there is a unique model. After all, one doesn't want, several models of ordinary arithmatic. For example, the Peano Axioms models arithmtic, and there is the usual standard model of arithmatic, but there are also non-standard models too. In the reference, they rely on the compactness theorem in logic to show this. A different construction uses ultraproducts, now the model produced by this method is uncountable, but by using the Lowenheim-Skolem theorem one can produce countable models. So the Lowenheim-Sklem theorem is not used directly to show that there multiple models of arithmetic. This is actually show via other means.

Compoutation is modelled by the turing model (or there lambda calculus which is provably equivalent), but it cannot answer all questions. An oracle is attached which gives answers to a specific class of questions for which no mechanism or algorithm is explained. For example, the halting problem for Turing Machines in not solvable by a turing machine. One can stipulate an Oracle that does indeed answer these questions.

There is a link between computation and countable non-standard models of arithmetic. This is the operations of addition & multiplication are not computable (Tennenbaums Theorem).

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.