Intereting Posts

Group of order 15 is abelian
Continuous and bounded variation does not imply absolutely continuous
Simple problem on restricted partition
How many essential ways: $n$ balls in $k$ bins, where $k$ can vary and there are $\geq 2$ balls in each bin?
Proof by Induction: $\sum_0^nx^i=(1-x^{n+1})/(1-x)$
Center of a free product
Lifting cohomology-killing maps through the 3-sphere
Proof to sequences in real analysis
Find all values of $p$ such that $ax^2+bx+c \equiv 0 (\bmod p)$ have solution
Finding the area under the curve $y=3-3\cos(t),x=3t-3\sin(t)$
What is the limit $\lim\limits_{n \to \infty} \frac{n^{\sqrt{n}}}{2^n}$?
How can one write $z^{-1}$ as a Stieltjes function?
Factorial, but with addition
Help to understand a proof by descent?
Expressing a positive integer as a sum of positive integers

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.

- Definition of Substitution (Equality vs Equivalence relations)
- What are $\Sigma _n^i$, $\Pi _n^i$ and $\Delta _n^i$?
- First-order logic without equality
- True or false or not-defined statements
- Countable axiom of choice: why you can't prove it from just ZF
- Every $n$-ary logical connective has a DNF

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

- Example of non-isomorphic structures which are elementarily equivalent
- Is there more than one infinitessimal among the hyperreal numbers
- What's the difference between a negation and a contrapositive?
- Given an infinite poset of a certain cardinality, does it contains always a chain or antichain of the same cardinality?
- Good books on mathematical logic?
- Can it be shown that ZFC has statements which cannot be proven to be independent, but are?
- Using the Fitch system, how do I prove $((p \implies q) \implies p)\implies p$?
- Why is Skolem normal form equisatisfiable while the second order form equivalent?
- Bijection between power sets of sets implies bijection between sets?
- Is there a statement whose undecidability is undecidable?

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.

- prove: A finitely generated abelian group can not be isomorphic to a proper quotient group of itself.
- Euler-Lagrange, Gradient Descent, Heat Equation and Image Denoising
- Prove that every bounded sequence in $\Bbb{R}$ has a convergent subsequence
- Quotient space of unit sphere is Hausdorff
- Bayesian Network, Sprinkler Example
- Expansion of $(1+\sqrt{2})^n$
- Approximating measures by open sets and compact sets.
- Category of Field has no initial object
- Finding the intersection point of many lines in 3D (point closest to all lines)
- Complex ($\mathbb C$) least squares derivation
- In $K$, is the power of any prime also primary?
- Sum of two truncated gaussian
- Why is the ratio test for $L=1$ inconclusive?
- Is $\mathrm{GL}_n(\mathbb C)$ divisible?
- Find the volume between two paraboloids