Non-standard models of finite set theory - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T01:59:17Z http://mathoverflow.net/feeds/question/63887 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/63887/non-standard-models-of-finite-set-theory Non-standard models of finite set theory Hans Stricker 2011-05-04T06:49:49Z 2011-05-07T04:15:10Z <p>It is well known how the intended model and <a href="http://en.wikipedia.org/wiki/Non-standard_model_of_arithmetic#Structure_of_countable_non-standard_models" rel="nofollow">how the (countable) non-standard models of arithmetic look like</a>.</p> <p>It's also well known how the intended model of set theory with the axiom of infinity replaced by its negation (ZF-Inf) looks like: $\langle V_\omega;\in\rangle$, the hereditarily finite sets with the $\in$-relation.</p> <blockquote> <p>But how do (countable) non-standard models of ZF-Inf look like?</p> </blockquote> http://mathoverflow.net/questions/63887/non-standard-models-of-finite-set-theory/63892#63892 Answer by SJR for Non-standard models of finite set theory SJR 2011-05-04T08:44:00Z 2011-05-07T04:15:10Z <p>Any positive integer can be written uniquely as a sum of distinct powers of 2. PA knows this, in the sense that one can write down a formula $\phi(x,y)$ meaning in the standard model that the $x$-th bit in the binary expansion of $y$ is 1. Moreover we can construct $\phi$ so that PA will prove all the expected facts about the $x$-th bit in the binary expansion of $y$.</p> <p>If $M$ is any model of PA, then by taking $\phi(x,y)$ as the membership relation "$x\in y$" we get a model of ZF-Inf. This is worked out in detail in Chapter 1 of "Metamathematics of First Order Arithmetic" by Hajek and Pudlak. In fact the authors carry this out not just for PA but for the subtheory <code>$\text{I}\Sigma_0(\text{exp})$</code>. </p> <p>(Added) I expected that every model $M$ of ZF-Inf would arise in this way, by applying the above construction to the model of PA consisting of the ordinals of $M$. But it seems this is not so... See Ali's answer below.</p> http://mathoverflow.net/questions/63887/non-standard-models-of-finite-set-theory/63918#63918 Answer by Ali Enayat for Non-standard models of finite set theory Ali Enayat 2011-05-04T14:15:27Z 2011-05-07T00:43:07Z <p>Models of ZF-Infinity that arise from models of PA via binary bits - a method first introduced by Ackermann in 1940 to interpret set theory in arithmetic- end up satisfying the statement TC := "every set has a transitive closure". </p> <p>It is known that the strengthened theory ZF-Infinity+TC is bi-interpretable with PA, which in particular means that every model of ZF-Infinity+TC is an "Ackermann model" of a model of PA.</p> <p>However, TC is essential: there are models of ZF-Infinity that do NOT satisfy TC; and therefore such models cannot arise via Ackermann coding on a model of PA. </p> <p>It is also known that there are "lots of" nonstandard model of ZF-Infinity [i.e., models not isomorphic to the intended model $V_{\omega}$] that are ${\omega}$-models [i.e., they have no nonstandard integer]. </p> <p>It is possible for a nonstandard ${\omega}$-model of ZF-Infinity to have a computable epsilon relation. Indeed, there is an analogue of Tennenbaum's theorem here: all computable models of ZF-Infinity are ${\omega}$-models.</p> <p>For more detail on the above, and references on the subject of finite set theory, you can consult the following paper:</p> <p><a href="http://academic2.american.edu/~enayat/ESV%20%28May19,2009%29.pdf" rel="nofollow">http://academic2.american.edu/~enayat/ESV%20%28May19,2009%29.pdf</a></p> <p>Ali Enayat</p> <p>PS. In light of the comments about TC to my posting, it is worth pointing out that even though TC is not provable in ZF-Infinity, the theory ZF-Infinity is "smart enough" to interpret ZF-Infinity + TC via the inner model of sets whose transitive closure exists as a set [as opposed to a definable class; cf. the aforementioned paper for more detail]. </p> <p>Therefore the relation of TC to ZF-Infinity is analogous to the relation between Foundation (Regularity) to ZF without Foundation since ZF is interpretable in ZF without Foundation via an inner model.</p>