Characterizations of non-wellfounded models? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T11:08:59Z http://mathoverflow.net/feeds/question/3462 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/3462/characterizations-of-non-wellfounded-models Characterizations of non-wellfounded models? Scott Cramer 2009-10-30T18:18:35Z 2009-12-29T22:35:13Z <p>My question is whether there are any characterizations of non-wellfounded models of set theory. A wellfounded model is one that does not have any \epsilon-descending infinite sequences. I'm not asking about models that satisfy ZF-Foundation, but rather ones that satisfy ZF, but are not wellfounded in V. For example, taking the ultrapower by an ultrafilter which is not countably complete produces such a model. </p> <p>I would assume that the reason one does not work with non-wellfounded models is the inability to collapse them, and therefore the inability to study their structure in relation to V. And perhaps there is a theorem which says that "anything is possible" when it comes to these models, and therefore it's a hopeless cause to understand them. </p> http://mathoverflow.net/questions/3462/characterizations-of-non-wellfounded-models/3489#3489 Answer by Grigor for Characterizations of non-wellfounded models? Grigor 2009-10-30T23:29:50Z 2009-10-30T23:29:50Z <p>What do you mean by characterization? We don't really have a characterization of well founded models of set theory, do we? </p> <p>Of course, any consistent extension of ZFC has ill founded models. </p> http://mathoverflow.net/questions/3462/characterizations-of-non-wellfounded-models/3948#3948 Answer by Apollo for Characterizations of non-wellfounded models? Apollo 2009-11-03T16:02:49Z 2009-11-03T16:02:49Z <p>You may want to look at Peter Aczel, Jon Barwise, <em>Non-Well-founded Sets</em> where they describe doing set-theory replacing the Axiom of Foundation by the Anti-Foundation Axiom. There, certain kinds of non-well-founded sets are postulated to exist and they give means to determine if two sets are the "same" set. (For example given A={A} and B={C}, C={B}, is A=B? (I think the answer is yes, shown by a bi-simulation argument.)</p> http://mathoverflow.net/questions/3462/characterizations-of-non-wellfounded-models/10075#10075 Answer by Joel David Hamkins for Characterizations of non-wellfounded models? Joel David Hamkins 2009-12-29T22:35:13Z 2009-12-29T22:35:13Z <p>There is a large body of work studying ill-founded models of set theory. The goal is to provide a robust model theory for models of set theory, usually focussing on the countable models. Much of this theory grows out of the study of nonstandard models of arithmetic, and many tools and theorems from models of arithmetic generalize to the study of models of ZFC. </p> <p>Let me give a few examples. If M is a model of ZF, one can form the <em>standard system</em> of M by looking at the trace on the standard &omega; of all the reals of M. It is easy to see that Ssy(M) is a Boolean algebra, closed under Turing reducibility and if T is an infinite binary tree coded in Ssy(M), then there is a path through T coded in Ssy(M). Any set of reals with those three properties is called a <em>Scott</em> set, in honor of Dana Scott, who proved the following amazing characterization:</p> <p><b>Theorem.</b>(Scott) If ZFC is consistent, then every countable Scott set arises as the standard system of a model of ZFC.</p> <p>Scott's theorem is usually stated for models of PA, but the proof for ZFC is identical. It remains a big open question whether Scott's theorem holds for all uncountable Scott sets. The answer is known for Scott sets of size &omega;<sub>1</sub>, and so under CH the problem is solved, but it remains open when CH fails. </p> <p>A key definition is that a model M of ZFC is <em>computably saturated</em> if it realizes every finitely consistent computable type over M. All such models are &omega;-nonstandard. It turns out that M is computably saturated if and only if it is (isomorphic to) a model that is an element of an &omega;-nonstandard model of ZFC. Furthermore, these models have interesting closure properties.</p> <p><b>Theorem.</b> Any two countable computably saturated models of ZFC with the same standard system and same theory are isomorphic. </p> <p><b>Theorem.</b> Every countable computably saturated model M of ZFC is isomorphic to a rank initial segment V<sub>&alpha;</sub> of itself. </p> <p>Much of the analysis of models of PA, such as that in the book by Jim Schmerl (UConn) and Roman Kossak (CUNY) extends to models of ZFC. Ali Enayat has also done a lot of interesting work along these lines. </p> <p>Here is another interesting theorem having to do with nonstandard ZFC models. Let ZFC* be any finite fragment of ZFC. If there is a (very small) large cardinal, then one can use full ZFC in this theorem (e.g. it suffices is there some uncountable &theta; with L<sub>&theta;</sub> satisfying ZFC). The theorem is interesting in the case that there are nonconstructible reals. </p> <p><b>Theorem</b>. Every real x is an element of a model of ZFC*+V=L. Furtheremore, one can find such a model whose ordinals are well-founded at least to &alpha;, for any desired countable ordinal &alpha;.</p> <p>Proof. First, the statement of the theorem is definitely true in L, since every real in L is in some large L<sub>&theta;</sub>. Second, the complexity of the statement is &Sigma;<sup>1</sup><sub>1</sub> in x and a real coding &alpha;. Thus, by Shoenfield's Absoluteness theorem, it is true in V. QED</p> <p>Thus, even when x is non-constructible, it can still exist in a model of V=L! This is quite remarkable. (This theorem was shown to me by Adrian Mathias, but I'm not sure to whom it is originally due.)</p>