# Set theory and Model Theory

This question probably doesn't make any sense, but I don't see why, so I ask it here hoping someone will illuminate the matter:

There is this whole area of study in Set Theory about the consistency, independence of axioms, etc. In some of these you use model theory (e.g. forcing) to prove results about set theory.

My question is: What is the foundation of this model theory we are using? We are certainly using sets to talk about the models, what some may call sets in the "meta"-mathematics, that is to say, the "real" mathematics.

But then, all these arguments in the end in are all about the theory of sets as a theory, and not the theory of sets as a foundation of math, since we are using these sets in the meantime. So our set theory is not about the foundation of math.

Am I right?

-
The word got out that our resident logicians are pretty, pretty good! :P –  Mariano Suárez-Alvarez Apr 30 '10 at 2:18

Your worries arise from asymmetry between how you view ordinary mathematics and how you view logic and model theory.

If it is the business of logic and model theory to provide foundations for the rest of mathematics then, of course, logicians and model theorists will not be allowed to use mathematical methods until they have secured them. But how might they accomplish this? The more we think about it, the more it becomes obvious that "securing the foundations of mathematics", whatever that means, is a task for philosophers at best and a form of mysticism at worst.

It is far more fruitful to think of logic and model theory as just another branch of mathematics, namely the one that studies mathematical methods and mathematical activity with mathematical tools. They follow the usual pattern of "mathematizing" their object of interest:

• observe what happens in the real world (look at what mathematicians do)
• simplify and idealize the observed situation until it becomes manageable by mathematical tools (simplify natural language to formal logic, pretend that mathematicians only formulate and prove theorems and do nothing else, pretend that all proofs are always written out in full detail, etc.)
• apply standard mathematical techniques

As we all know well, the 20th century logicians were very successful. They gave us important knowledge about the nature of mathematical activity and its limitations. One of results was the realization that almost all mathematics can be done with first-order logic and set theory. The set-theoretic language was adopted as a universal means of communication among mathematicians.

The success of set theory has lead many to believe that it provides an unshakeable foundation for mathematics. It does not, at least not the mystical kind that some would like to have. It provides a unifying language and framework for mathematicians, which in itself is a small miracle. Always remember that practically all classical mathematics was invented before modern logic and set theory. How could it exist without a foundation so long? Was the mathematics of Euclid, Newton and Fourier really vacouous until set theory came along and "gave it a foundation"?

I hope this explains what model theorists do. They apply standard mathematical methodology to study mathematical theories and their meaning. They have discovered, for example, that however one axiomatizes a given body of mathematics in first-order logic (for example, the natural numbers), the resulting theory will have unintended and surprising interpretations (non-standard models of Peano arithmetic), and I am skimming over a few technical details here. There is absolutely nothing strange about applying model theory to the axioms known as ZFC.

Or to put it another way: if you ask "why are model theorists justified in using sets?" then I ask back "why are number theorists justified in using numbers?"

-
+1: Very well put Andrej! (Not really the right place to mention this since few will know what I'm talking about, but I also really liked your question regarding your colleague's wife.) –  François G. Dorais Apr 30 '10 at 7:49
The last line is great. –  Uri Andrews Apr 30 '10 at 8:11
I can't help to give -1 to the answer as it understates the importance of the problem of foundations and the role of mathematical logic in it (and I'm not even a logician or a philosopher!). –  Qfwfq Sep 19 '11 at 18:05
I disagree, naturally. Where exactly am I understating the "problem of foundations and the role of mathematical logic"? I am stating that it is not the role of mathematical logic to provide the sort of mystical, unshakeable foundations that many mathematicians think it ought to provide. That is a job for philosophers, if it is a job worth doing at all. If you read again, you will see that I praise the foundational achievements of modern logic. –  Andrej Bauer Sep 20 '11 at 14:56
-1 for the same reason as unknowngoogle. –  Joël Sep 28 '11 at 14:04

I totally agree with the answers already given but I still want to say something to your question, which emphasizes probably the formalist side. To cut a long story short the foundation of model theory, for which you were asking for, is ZFC (at least ZFC is one possibility), but this doesn't mean that one must not use model theory to investigate ZFC itself:

As you know, one can code the symbols of first order logic within set theory and, as a consequence, the whole model theory can be carried out in ZFC. Thus the Löwenheim-Skolem Theorem, the Compactness Theorem and so on are theorems of ZFC. (Note that when e.g. the Compactness Theorem talks about a “set of first order formulas”, it in fact talks about the set of the coded formulas, i.e. about a set of sets).

Now you can apply these results of model-theory to the coded axioms of ZFC (there is nothing wrong with that since ZFC is stated in first order logic and the set of the coded axioms is well defined); still everything is done in the frame ZFC.

The Theorem from logic, which states that if $T$ is a 'set' of formulas, $\psi$ another formula and $M$ a model such that $M \models T$ and $M \models \lnot \psi$, then T cannot prove $\psi$, is a theorem in ZFC (again $\psi$ and $T$ in this theorem are in fact coded, i.e. sets and moreover the metamathematical statement “there exits no proof from $T$ for $\psi$” is in fact a well defined statement about sets which mimics characteristics from proofs inside ZFC).

And this Theorem can now be used to state independence results about ZFC in ZFC. The only difficulty is that by Gödels celebrated result, one cannot prove inside ZFC the existence of a model of ZFC. Therefore one always assumes $Con(ZFC)$, i.e. the coded form of the assertion: “ZFC is consistent”, which is equivalent to “there exists a model of ZFC”. Then manipulate this given model to obtain a model for $ZFC+ \{ \varphi \}$ where $\varphi$ is an arbitrary interesting statement.

We can now prove things like: If ZFC is consistent then so is ZFC+ “Continuum Hypothesis fails” which is the famous result of Cohen shown by models but within ZFC.

-

The use of forcing in Set Theory is to investigate the Zermelo-Fraenkel axioms and their consequences. This is a perfectly valid use of Model Theory — the Completeness Theorem says that a statement φ is a consequence of ZFC if and only if φ is true in every model of ZFC. If one can produce a forcing poset that forces φ to be false, then we know that if ZFC is consistent then φ is not a consequence of ZFC since any suitable model can be extended to a model of ZFC in which φ is false. If another forcing forces φ to be true, then we know that φ is independent of ZFC.

I'm gathering from your question that you're a Platonist (I'm agnostic but I'll play along). This demonstration of independence via forcing says little about the truth of φ in the Platonic Universe. It only says that further information than the axioms of ZFC is needed to determine the truth of φ. However, these investigations over the past half-century have led to some insight on what statements are indeed true in the Platonic Universe. For example, see these two articles by Woodin (AMS Notices, 2001) where he discusses the status of the Continuum Hypothesis.

-
The thing is, aren't you using sets when you prove the Completeness Theorem? In the completeness theorem you are referring to theories which are sets of first order sentences, which themselves are made up of symbols from a set. Don't you need sets in the first place to do model theory? I mean, what are the foundations of model theory? –  Enrique Apr 30 '10 at 2:48
Sure, but that's not a problem. If you're indeed a Platonist then sets simply exist, the Completeness Theorem is true, and everyone is happy! (If my impression was wrong and you're not a Platonist, then explain and I'll adjust my answer accordingly.) –  François G. Dorais Apr 30 '10 at 2:52
In other words, from the Platonic view, sets exist and ZFC is simply what we know about them so far; ZFC is not a definition of sets (as it would be to a formalist) it's a fact of life. –  François G. Dorais Apr 30 '10 at 3:07
Here's a +1 from a dyed in the wool formalist. –  Harry Gindi Apr 30 '10 at 3:58
ok François, I think I see your point. –  Enrique Apr 30 '10 at 6:14

First of all, I would like to say that your question is not only justified, but actually most welcome: it shows the King naked. Who is the King? You can call him Semantics,or the mathematical theory of Truth (notice the capital letter) if you wish.

There is a widespread usage among logicians of sentences such as " the true universe of sets", the "set of natural numbers", and so forth, as if these entities were crystal clear and thus indisputable. They aren't, at least to me. But even if they are, even if there is such a thing as mathematical intuition which informs us on the world of platonic math (what my teacher aptly named PLATO's ATTIC), the fact is this: as soon as we SPEAK about them, they just become syntax, no more no less (ie part of a frame syntactic theory which grounds them).

Model theory is a great branch of mathematics, no doubts about it. But it is formalized mathematics, and grounded in ZFC. Does that mean that all its results are empty, especially in the model theory of ZFC? I say absolutely no. Instead, it bespeaks of the uncanny capability of a powerful theory such as ZFC to "reflect" upon itself and the rest of mathematics. The king is naked, but a king nevertheless. Long live the king!

PS I just discovered the recent work of Joel D. Hamkins and a few others on the Multiverse: finally some people from the set theory ranks are moving away from a dogmatic and monolitic notion of truth (the ghost-like "true universe of sets" and its equally ghostly eternal properties) towards a new dynamic and contextual one. I think this is a beginning of a new era, if I am not mistaken....

-
I must say that I have never in my studies heard any of my teachers speak of this "One universe of sets!", if it was mentioned at all (depending on the course of course) then it was mentioned as "a universe of sets" and nothing more. –  Asaf Karagila May 30 '11 at 18:53
I don't understand the reasoning behind this: "even if there is such a thing as mathematical intuition which informs us on the world of platonic math, the fact is this: as soon as we SPEAK about them, they just become syntax, no more no less." Would my speaking about you make you "just become syntax, no more no less"? Platonists would regard syntax and whatever we say about these objects as merely a help to communicating about them, not as having any influence on their platonic existence or nature. –  Andreas Blass May 30 '11 at 21:28
I will not become syntax, but what you write about me, regardless of whether I am really there, IS syntax and nothing but syntax. If you formalize me in a suitable frame theory,say ZFC, and then argue about my properties, you may be guided by your inner knowledge of what I am, but at the end of the day, the validity of your arguments is purely a syntactical matter. Moreover: you may be admitted to Plato's attic, and I may not, but if your reasoning is syntactically correct I will have to agree with your deductions assuming your premises. –  Mirco Mannucci May 30 '11 at 23:37

Do I remember the following correctly? Using a coding of formal logic (and ZFC itself) in ZFC the following is correct: If ZFC can prove that coded-ZFC coded-proves a coded-theorem, then ZFC proves the theorem.

In other words, working in the world of ZFC-coded model theory, your theorem's are still correct in the 'real' world -- whatever you philosophical inclination for 'real'.

-
No I think that this direction is the false one. It's the other way round: If ZFC proves a statement then ZFC proves that the 'coded ZFC proves the coded statement'. If your suggested direction would be true it would cause trouble with Gödels Incompleteness Theorem. –  Stefan Hoffelner Apr 30 '10 at 8:48