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”

Thanks in advance

Solutions Collecting From Web of "Logic, set theory, independence proofs, etc"

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.