# Logic, set theory, independence proofs, etc

I have some big troubles trying to understand specific set theory stuff.

Especially when we demonstrate something about set theory we always have to keep our demonstration in set theory, typically not using second order logic.

For example to demonstrate Löwenheim-Skolem we have to quantify over formulas to explicitly build a countable model. This is a second-order proof, and we usually don't mind doing that. But if one want to show "$\mathrm{ZFC} + \mathrm{Con}(\mathrm{ZFC}) \vdash \exists M$ countable model of ZFC", this should not be possible anymore.

So here are my questions :

• Can "$\mathrm{ZFC} + \mathrm{Con}(\mathrm{ZFC}) \vdash \exists M$ countable model of ZFC"
• If yes, how? Since we have to quantify over formulas.
• Can "$\mathrm{ZFC} + \mathrm{Con}(\mathrm{ZFC}) \vdash \exists M$ countable and transitive model of ZFC"

-

First of all you have to ask yourself what does it means when we say $Con(ZFC)$. Can we talk about $ZFC$ as an object inside set theory? Doesn't that require to talk about every formula since Replacement and Separation are schemata of formulas?

The answer lies in the following observation: In $ZFC$ we cannot quantify over metamathematical formulas, that is formulas as objects outside of the universe of set. What we can do though is assign a set to every formula. Then for every formula we have an object in the universe that represents the metamathematical formula. We usually symbolize this as $\ulcorner\phi\urcorner$.

Through this and because of the inductive construction of formulas we can create a formula $Form(x)$ that says "$x$ is a formula" and is true exactly when there is a formula that is assigned to $x$. Furthermore we can create a formula $ZFC(x)$ that says that "$x$ is a formula of $ZFC$". We can create formulas such as $Pr(x)$ that says that using a specific system of logical axiom and inference rules $ZFC$ proves $x$ (through this we can create the sentence $Con(ZFC)$). Also given a set $M$ and a binary relation $E\subset M\times M$ we can create a formula $Sat(M,E,x)$ that says $(M,E)\models x$. Then we can prove about the formulas as objects inside the universe the Lowenheim-Skolem theorem, the completeness theorem, the compactness theorem and every other metamathematical result. $ZFC$ as you know is enough to prove the completeness theorem and so we have that: $$ZFC\vdash Con(ZFC)\iff \exists M\textrm{countable model of}\ ZFC$$

But is it the same? Are the results about these objects that we call formulas inside the universe the same as the results about the metamathematical formulas? The result we can obtain is a schema of theorems that state: $$\phi^{(M,E)}(a_1,\ldots,a_n)\iff(M,E)\models \ulcorner\phi(a_1\ldots,a_n)\urcorner$$

Notice the following: The left hand side refers to the relativization of the metamathematical formula (hence it's a schema of theorems). Now the right-hand side, the formula I wrote in the previous paragraphs that talks about the satisfiability of a formula is definable only when $M$ is a set. Indeed if we could define satisfiability about classes then we would have a truth definition which contradicts Tarski's theorem. It should be noted that we can define satisfiability in classes when we bound the number of alternating quantifiers of formulas: We can define satisfiability for $\Delta_0$ formulas, and for every natural number $n$ we can define the satisfiability of $\Sigma_{n}$ formulas.

For your last question, I am not certain, though I am under the impression that the existence of a transitive model of $ZFC$ is stronger than the consistency of $ZFC$. This is because the set-model that exists due to the consistency may be not standard and may contain infinite descending $\in$-sequences while it thinks that it's well founded (I am aware of such constructions: for example apply Łoś's theorem using a non-principal ultrafilter that is not $\sigma$-complete). Then it would be impossible to apply Mostowski's collapse to get the standard transitive model.

Edit: Keep in mind that Mostowski's theorem has as requirements that the binary relation is well founded in the universe. So given a model $(M,E)$ we may have $x_{n+1} E x_n$ for every $n\in\omega$ but if the set with extension $\{x_n\ :n\in\omega\}$ is not in $M$ the axiom of foundation will not be violated. In such a case it would be impossible to apply Mostowski's theorem.

Edit2: Here's the model I described above. Take a non-principal ultrafilter $\mathcal{U}$ on $\omega$ (that is $\mathcal{U}\subset\mathcal{P}(\omega)$). Of course $\mathcal{U}$ is not $\sigma$-complete since if it was it would be principal. Now take the ulraproduct of the universe modulo $\mathcal{U}$: The universe will be $V^\omega/\mathcal{U}$ that contains equivalence classes of functions $f:\omega\to V$ defined as $[f]:=\{g:\omega\to V : \{n\in\omega : f(n)=g(n)\}\in\mathcal{U}\}$. There is a slight problem here, namely that these may be classes but it can be solved using Scott's trick to turn these classes into sets. Next we define: $$[f]=[g]\iff \{n\in\omega : f(n)=g(n)\}\in\mathcal{U}$$ $$[f]E[g]\iff \{n\in\omega : f(n)\in g(n)\}\in\mathcal{U}$$

So we have a model $(V^\omega/\mathcal{U},E)$. For every formula $\phi$ you can prove the following result using Łoś's theorem: $$(V^\omega/\mathcal{U},E)\models\phi([f_1],\ldots,[f_n])\iff\{m\in\omega : \phi(f_1(m),\ldots,f_n(m))\}\in\mathcal{U}$$

Take note here that this is a schema of theorems. Still it is enough to show in ZFC that the model satisfies foundation since it's one singular axiom.

Now take the functions $f_n(m)=m-n$ (in case $m-n<0$ let $f_n(m)=0$). Since $\mathcal{U}$ is non-principal it contains the Fréchet filter and thus for every $n\in\omega$ the set $\{m\in\omega: m\geq n\}\in\mathcal{U}$. Observe that $f_{n+1}(m)\in f_n(m)$ for every $m>n$. Thus $\{m\in\omega: f_{n+1}(m)\in f_n(m)\}\in\mathcal{U}$ and therefore $[f_{n+1}]E[f_n]$. This is true for every natural number $n$ while the model satisfies the axiom of foundation.

Given an inaccessible cardinal $\kappa$ we can create the above construction in $V_\kappa$ and have the fact that $(V_\kappa^\omega/\mathcal{U},E)\models ZFC$ as a theorem while at the same time we have that there is an infinite descending $E$-sequence.

-
Firstable, thank you very much for such a complete answer ! ok apparently this is just a comment spot, so I ll continue 'with another answer' – Archimondain Mar 21 '11 at 0:23
Ok apparently this is the spot to answer your answer, so I continue here. What you describe at the end seems weird to me. Since Con(ZF) implies Con(ZF)+foundation, can't we work using the model in which fundation is true ? and then do a Mostowski collapse ? (I assume that is what you mean by 'collapsing lemma'). I have another related question, but it is much more complexe ans require another answer. – Archimondain Mar 21 '11 at 0:32
@Archimondain: Yes by the collapsing lemma I mean Mostowski's collapse (I'll edit that, I don't know why I called it like that). The model may think that it satisfies foundation but that doesn't mean that it is well-founded. For example even if the model (let's call it $M$) contains sets $x_n$ such that $x_{n+1}\in x_n$, the set $\{x_n : n\in\omega\}$ may not be in $M$ and so $M$ would satisfy foundation. – Apostolos Mar 21 '11 at 0:38
@Archimondain: Just become someone denies having a drinking problem it doesn't mean they don't have one. If you work within the model, it may fiercely deny that it is drunk - however started in a larger universe which already hung the intervention banner. – Asaf Karagila Mar 21 '11 at 0:52
@Archimondain: This is true only if the model $(M,E)$ has as $E$ the real $\in$. But this may not be the case at all. The consistency admits the existence of a model of ZFC. This doesn't mean that the membership relation in that model is the real $\in$. It is possible that this $E$ is a very different relation and it may not be well founded. – Apostolos Mar 21 '11 at 2:01