Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

From Model Theory article from wikipedia : "A theory is satisfiable if it has a model $ M\models T$ i.e. a structure (of the appropriate signature) which satisfies all the sentences in the set $T$". In structure definition there is also requirement for "container of a structure" to be set.

As we assume then, every model have to lay inside of some set-container. This obviously give us in serious trouble, as for set theory, there is no model of this type, and even maybe cannot be. One of possible explanations why set theory cannot be closed inside set ( which will lead us to some well known paradoxes) is opinion that "there can be no end to the process of set formation" so we have "structure" which cannot be closed inside itself which is obviously rather well state.

As we know that not every theory may have a model (see set-theory) then some question arises:

  • What are the coses (other than pure practical - if they are set we know how to work with them) of putting so strong requirements for model to be set?

  • Is there any way to weaken this requirement?

  • Are there any "explorations" of possible extension of model theory with fundamental objects other than sets?

I presume that some categorical point of view may be useful here, but is there any? I am aware about questions asked before, specially here 8731, but it was asked in context of category theory which is of course valid point of view but somehow too fine. I would like to ask in general.

And last one, philosophical question: is then justified, that condition for a theory to have model in set universe is some kind of anthropomorphic point of view - just because we cannot build any other structures in effective way we build what is accessible for us way but it has no objective nor universal meaning? Is true that model theory is only a "universal algebra+logic" in universe of the set, or it justifications may be extended to some broader point of view? If yes: which one?

I have hope that this question is good enough for mathoverflow: at least please try to deal wit as kindly request for references.


Remark: Well formulated point from n-CathegoryCafe discussion: "In the centre of Model Theory there is " fundamental existence theorem says that the syntactic analysis of a theory [the existence or non-existence of a contradiction] is equivalent to the semantic analysis of a theory [the existence or non-existence of a model]."

In fact the most important point is: may it be extended on non "set container" universes?


I would like to thank everyone who put here some comments or answers. In is the most interesting that in a light of answer of Joel David Hamkins it seems that for first order theories (FOT) consistency is equivalent to having set model. It is nontrivial, because it is no matter of somehow arbitrary definition of "having model" but it is related to constructive proof of Completeness Theorem of Gödel. From ontological point of view it then states that for FOT there is no weaker type of consistency than arising from model theory based on sets, and in some way it is maximal form of consistency simultaneously. Then there is no way to extend for FOT equivalence to non-set containers, which is nontrivial part - the only theories which are consistent in FOT are those which has a set models and this statement is proved not using set theoretical constructions in nonconstructive ways. So it was important to me, and I learn a lot from this even if for specialist it is somehow maybe obvious. I have hope that I understand it right;-)

@Tran Chieu Minh: thank You for pointing to interesting discussion, I will try to understand the meaning of Your remarks here and there.

share|improve this question
1  
Not exactly an answer, but I think I asked one question which is philosophically similar. mathoverflow.net/questions/11974/… –  Tran Chieu Minh Feb 18 '10 at 10:27
3  
I don't see the trouble. There is no contradiction in assuming that set theory has a model M which is a set. M then contains all "sets" (in the sense of the theory you are trying to modelize) but not all usual sets (for example it cannot contain all its own subsets by reasons of cardinality). Things become much clearer if instead of set theory you call it widgit theory and call your elements widgits, so there is no risk of confusion with the usual sets. –  Andrea Ferretti Feb 18 '10 at 10:51
    
@Andrea: I am only hobbyist but I think You cannot point such structure effectively. If a ZFC has a model which is set, then the model is inside "original" ZFC. Then ""by a result known as the completeness theorem, the statement that ZFC has any models at all is equivalent to the statement that ZFC is consistent" So we have proof inside ZFC that it is consistent, which is in contradiction to many logics theorems specially Tarski undefinability Theorem as true sentences in ZFC have to exist in model of it, which is then part of original ZFC –  kakaz Feb 18 '10 at 11:08
2  
That is of course true. You cannot show in ZFC that ZFC has a model, or equivalently, that the axioms of ZFC are consistent. But if you assume that the axioms of ZFC are consistent, you also have to assume that there exists a model of it. –  Michael Greinecker Feb 18 '10 at 11:26
2  
"Consistent" means that a contradiction cannot be deduced from it. –  Gerald Edgar Feb 18 '10 at 18:27
show 5 more comments

5 Answers 5

up vote 25 down vote accepted

You seem to believe that it is somehow contradictory to have a set model of ZFC inside another model of ZFC. But this belief is mistaken.

As Gerald Edgar correctly points out, the Completeness Theorem of first order logic asserts that if a theory is consistent (i.e. proves no contradiction), then it has a countable model. To be sure, the proof of the Completeness Theorem is fairly constructive, for the model is built directly out of the syntactic objects (Henkin constants) in an expanded language. To re-iterate, since you have mentioned several times that you find something problematic with it:

  • Completeness Theorem. (Goedel 1929) If a theory is consistent, then it has a model that is a set.

The converse is much easier, so in fact we know that a theory is consistent if and only if it has a set model. This is the answer to your question.

More generally, if a theory is consistent, then the upward Lowenheim-Skolem theorem shows that it has models of every larger cardinality, all of which are sets. In particular, since the language of set theory is countable, it follows that if ZFC is consistent, then it has models of any given (set) cardinality.

The heart of your confusion appears to be the mistaken belief that somehow there cannot be a model M of ZFC inside another structure V satisfying ZFC. Perhaps you believe that if M is a model of ZFC, then it must be closed under all the set-building operations that exist in V. For example, consider a set X inside M. For M to satisfy the Power Set axiom, perhaps you might think that M must have the full power set P(X). But this is not so. All that is required is that M have a set P, which contains as members all the subsets of X that exist in M. Thus, M's version of the power set of X may be much smaller than the power set of X as computed in V. In other words, the concept of being the power set of X is not absolute between M and V.

Different models of set theory can disagree about the power set of a set they have in common, and about many other things, such as whether a given set is countable, whether the Continuum Hypothesis holds, and so on. Some of the most interesting arguments in set theory work by analyzing and taking advantage of such absoluteness and non-absoluteness phenomenon.

Perhaps your confusion about models-in-models arises from the belief that if there is a model of ZFC inside another model of ZFC, then this would somehow mean that we've proved that ZFC is consistent. But this also is not right. Perhaps some models of ZFC have models of ZFC inside them, and others think that there is no model of ZFC. If ZFC is consistent, then these latter type of models definitely exist.

  • Incompleteness Theorem. (Goedel 1931) If a (representable) theory T is consistent (and sufficiently strong to interpret basic arithmetic), then T does not prove the assertion "T is consistent". Thus, there is a model of T which believes T is inconsistent.

In particular, if ZFC is consistent, then there will be models M of ZFC that believe that there is no model of ZFC. In the case that ZFC+Con(ZFC) is consistent, then some models of ZFC will have models of ZFC inside them, and some will believe that there are no such models.

A final subtle point, which I hesitate to mention because it can be confusing even to experts, is that it is a theorem that every model M of ZFC has an object m inside it which M believes to be a first order structure in the language of set theory, and if we look at m from outside M, and view it as a structure of its own, then m is a model of full ZFC. This was recently observed by Brice Halmi, but related observations are quite classical. The proof is that if M is an ω-model, then it will have the same ZFC as we do in the meta-theory and the same proofs, and so it will think ZFC is consistent (since we do), and so it will have a model. If M is not an ω-model, then we may look at the fragments of the (nonstandard) ZFC inside M that are true in some Vα of M. Every standard fragment is true in some such set in M by the Reflection Theorem. Thus, by overspill (since M cannot see the standard cut of its ω) there must be some Vα in M that satisfies a nonstandard fragment of its ZFC. Such a model m = VαM will therefore satisfy all of the standard ZFC. But M may not look upon it as a model of ZFC, since M has nonstandard axioms which it thinks may fail in m.

share|improve this answer
2  
If I could, I would add another +1 (or more) for the "final subtle point"! –  François G. Dorais Feb 18 '10 at 15:04
    
@Joel:"Perhaps you believe that if M is a model of ZFC, then it must be closed under all the set-building operations that exist in V" No I know that, model of ZFC in V may be not closed in V. But I have idea that if it is model inside some V and then is a set in the meaning that meets ZFC axioms, then it is also a set in the meaning of some other model of ZFC for which V is a "closed structure", then a set. So as such structure would exist it will lead to contradiction. I know that: "Thus, M's version of the power set of X may be much smaller than the power set of X as computed in V" Thank You –  kakaz Feb 18 '10 at 15:07
    
So if I well understand, at least for first order theory completeness and "to be implemented as a set" is completely equivalent, assuming that by "set" we mean abstract implementation of ZFC axioms. –  kakaz Feb 18 '10 at 15:23
    
Thanks for accepting my answer, although I sense that you are not fully satisfied, for which I am sorry. You had asked for something weaker than having a set model, but the completeness theorem shows that if there is no set model, then the theory is actually inconsistent. Thus, there is very little room for a weaker notion; you would inevitably be pushed to consider non-set "models" that in some sense satisfy an inconsistent theory... –  Joel David Hamkins Feb 18 '10 at 16:23
    
Thanks for that remark. Maybe there is possibility to extend such structure in other nonstandard-logic like paraconsistent one for example or higher order theories, which as far as I know gives some serious problems. However I learn a lot from Your answer and I wish to thank You a lot, because gives me a point of view which I may use in order to learn something from literature: it gives some kind of anchor or order in looking for other phenomena;-) –  kakaz Feb 18 '10 at 16:38
show 1 more comment

The fundamental reason why models in model theory are required to be sets is that for such models $M$ there exists the satisfaction relation $M\models\phi[e]$ between formulas $\phi$ and evaluations $e$, obeying Tarski’s definition. This is not possible in general for class models in ZFC (or NBG)—for example, the existence of a satisfaction relation for $(V,\in)$ would imply the consistency of ZFC, which is not provable in ZFC.

There are other reasons for sticking to set models (for example, various constructions of models, in particular those using the compactness theorem, tend not to work for proper classes), but this is the most important one. On the other hand, in some parts of model theory it is convenient to work inside a “monster model” which may be a proper class (at least metaphorically, i.e., large enough so that it behaves as if it were a proper class for all arguments we want to employ it in), but one has to be careful when working in such a setup.

share|improve this answer
4  
Continuing your first paragraph, it might be good to point out that stronger theories of classes, like Kelly-Morse, allow you to define satisfaction for proper class models. Thus, they also allow you to prove that any theory that has a class model is consistent and (provided the vocabulary is a set) therefore also has set models. A sloppy formulation addressed to the original question is: Once the notion of class-sized model makes sense, these models exist for the same theories as set-sized models. –  Andreas Blass Jul 2 '11 at 18:56
add comment

In some cases one takes a proper class as the model. But in fact if a theory (with finitely many symbols) is consistent then it has a countable model, and thus a model which is a set.

share|improve this answer
    
I m only a hobbyist so then I do not understand Your answer. Do You state that what You say is true because You have a proof of statement: "if theory is consistent => has a model as a set" or it is true because "consistent" use model definition which requires model to be a set? Is requirement for model to be a set necessary or not? I am asking on possible extension of meaning "consistent" on universes which are not set, not about way of application known definition of model object ( which has to be a set from definition!). So is Your answer true in that context? –  kakaz Feb 18 '10 at 11:17
    
"if a theory (with finitely many symbols) is consistent then it has a countable model" - then we have to have "set" model of ZFC, but it lead us to a troubles, do not? See comments above. –  kakaz Feb 18 '10 at 11:20
2  
L\"ovenheim-Skolem theorem; compactness theorem ... hobbyists should look them up before contributing to this thread, perhaps... –  Gerald Edgar Feb 18 '10 at 13:13
    
@Gerard: I have read about them, but it is not so simple. But it refers to theories which have infinite models so then has models of any cardinality. It then states something about models which necessary are sets. So from formal point of view You cannot have models which are not sets. Is the "set container" necessary for model theory itself? Are there any formulation of model theory and fundamental theorem of syntactic-semantic equivalence which allows us to not use sets as structures? Sorry but You do not understand what I am asking about. It is not so easy. –  kakaz Feb 18 '10 at 13:48
2  
You do realize that this "hobbyist who should look things up before contributing to the thread" is the person who started the thread? –  Steven Gubkin Feb 18 '10 at 14:54
add comment

Gerald's answer is quite correct. This began as a comment justifying it, but because of length considerations I'm leaving it as an answer instead.

A model of ZFC is not a perfect replica of the category of sets crammed into a single set (in fact, to the extent that such a statement makes any sense at all, there is no such thing). Rather it is a set $M$ together with a binary relation, $\in$, such that the axioms of ZFC set theory -- i.e., a certain family of first order statement in the (countable) language of sets -- holds in $(M,\in)$.

There are a lot of things that such a model $M$ will not tell you about the category of sets. However, assuming -- as we generally do -- that there really is a category of sets satisfying each of the axioms of ZFC, then it follows from Godel's Completeness Theorem that it must have a model $M$ as above. This is a nontrivial result. Moreover, since the language of sets is countable it follows from Skolem-Lowenheim that models of ZFC exist of all infinite cardinalities.

To be fair, Skolem himself found this consequence -- the existence of a countable model of set theory -- to be somehow problematic ("Skolem's Paradox"). But modern set theorists and logicians simply don't feel this way: they have gotten used to the statement, which is not paradoxical in the strict logical sense (there is no contradiction) but rather merely sounds strange when you first hear it.

In much the same way, Tarski's motivation for the Banach-Tarski paradox was to exhibit the absurdity of the Axiom of Choice (AC). But nowadays 99.9% of all mathematicians are happy with AC, and the study of "paradoxical decompositions" is a flourishing subfield of geometric group theory.

As Joel David Hamkins explained to me previously here on MO, you could consider class-valued models of a theory and, depending upon taste, it may sometimes be convenient to do so. But again it is not necessary to do so because of Godel Completeness.

share|improve this answer
    
It looks like my answer came in less than a minute before Joel's. He is the expert here: further questions should be directed to him. –  Pete L. Clark Feb 18 '10 at 14:29
    
Thanks, Pete! (I posted mine, and saw that you had just posted.) In any case, it seems that we've got three totally correct answers here. –  Joel David Hamkins Feb 18 '10 at 14:38
1  
Regarding Skolem's Paradox, I would like to emphasize that Skolem's Paradox was formulated a decade before Gödel's Completeness, Compactness, and Incompleteness Theorems. In fact, a revisionist interpretation of Skolem's Paradox is that it is in fact a slightly weak version of Gödel's Second Incompleteness Theorem. –  François G. Dorais Feb 18 '10 at 14:55
add comment

I think that this question was down-rated too quickly. It appears to me that modulo the confusion which was pointed out by previous posts there are some valid point that need to be addressed.

I just post my opinion. I don't think I have enough knowledge to give justification for them. I hope this will give some more fuel for the discussion.

1) I don't think there is truly much essential point to require a model to be a set in the sense of the Platonic concept of set i.e. to require that $ a \in b$ means $a$ is an element of $b$ in the real sense. An arbitrary interpretation of "is an element" will work. I think the more important requirement here is the requirement of "closed system" i.e. relations are defined everywhere, functions defined everywhere and won't give you an outside element. So being a set is a sufficient condition to capture this notion of "closed system" (in a philosophical sense). But it is not necessary.

2) That points out some way to weaken the requirement.

3) I don't know. I gave you the link to my previous question. I think Angus Macyntyre did suggest something like that. I have not find time to sit down and read all of them properly. My belief is that at least a category theory language is possible, but I don't know whether it can be extended to other kind of objects or not.

share|improve this answer
1  
The aim of asking this question is not to discuss about ZFC at all, but about model theory and models. Unfortunately ZFC is incorporated in it, so probably my question is a idea of looking for "new model theory" which do not use set theory at all - clearly without direct answer. But from answer of Joel D.Hamkins we see, that at least for first order theories consistency is equivalent to having a model as a set, which for me is very interesting and definite statement which is far from being obvious, even if You heard about theorems mentiuoned in comments/answers. –  kakaz Feb 18 '10 at 17:12
1  
It is maybe worth pointing out that this model must not only be a set, but in fact an ordered pair $(M,E)$ such that $M$ is a set and $E$ is a binary relation in $M$ which is going to be the interpretation of the symbol $\in$. So if we take, for example, the axiom of pairing, namely $(\forall x)(\forall y)(\exists z)(\forall u)(u\in z\iff u=x\vee u=y)$ (this is the assertion that given sets $x$ and $y$, there exists the set $\{x,y\}$), we have that this set model must satisfy it: but with the intended interpretation, this doesn't mean that given $x,y\in M$, we must have that $\{x,y\}\in M$. –  David FernandezBreton Mar 6 '11 at 7:49
    
This only means that given $x,y\in M$, there must be an element $z\in M$, such that the only elements which bear the relation $E$ with $z$ are $x$ and $y$ (this is, we have $(x,z)\in E$, $(y,z)\in E$ and there is no other $u$ such that $(u,z)\in E$). So $M$ doesn't really needs to contain the unordered pair $\{x,y\}$, it just needs to contain something that $M$ will believe" that is the unordered pair. Similarly, $M$ must contain something that it thinks" is the powerset of any of its elements, etc. From this point of view, the fact that there is a model of set theory which is itself a set –  David FernandezBreton Mar 6 '11 at 7:55
    
...looks less paradoxical, since this set model won't actually be the universe of all sets, it's only going to be certain set with certain binary relation (which the model itself will "think" is the membership relation) that satisfies the axioms. Of course, we expect the "actual" universe of sets to satisfy the axioms as well, but this and the set models for set theory can differ in some other statements that don't follow from the axioms (so for instance, we can have a set model satisfying $CH$ while the "real" universe of sets maybe don't satisfy $CH$). –  David FernandezBreton Mar 6 '11 at 7:59
    
So there's no problem here since even if the set model satisfies the ZFC axioms, it need not be an exact copy of the "real" universe of sets... sorry about the really really long comment, but I felt it inappropriate to post a new answer so many time after the question was done. –  David FernandezBreton Mar 6 '11 at 8:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.