Intereting Posts

Variable leaving basis in linear programming – when does it happen?
Infinite products – reference needed!
Find all integral solutions to $a+b+c=abc$.
Evaluating the limit of $\sqrt{2+\sqrt{2+\sqrt{2+\cdots+\sqrt{2}}}}$ when $n\to\infty$
Is there a name for relations with this property?
To prove $f$ to be a monotone function
A nonsplit short exact sequence of abelian groups with $B \cong A \oplus C$
Constant rank theorem
How to solve $4\sin \theta +3\cos \theta = 5$
Is this *really* a categorical approach to *integration*?
Why the morphisms of vector spaces, over different fields is not interesting?
Centralizer of a given element in $S_n$?
Let G be a finite group with more than one element. Show that G has an element of prime order
Looking for examples of Discrete / Continuous complementary approaches
Example of Tetration in Natural Phenomena

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.

- How “Principia Mathematica” builds foundations
- Iff Interpretation
- Is there a Second-Order Axiomatization of ZF(C) which is categorical?
- Implication in mathematics - How can A imply B when A is False?
- Negation of quantifiers
- True or false or not-defined statements

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

- What philosophical consequence of Goedel's incompleteness theorems?
- The meaning of implication in logic
- Turing's 1939 paper on ordinal logic
- “This statement is false” - Propositional Logic
- Axiom of choice and calculus
- Upper and Lower bounds on proof length
- coproducts of structures
- Existence in ZF of a set with countable power set
- Negation of the Definition of Limit of a Function
- Well-ordering theorem and second-order logic

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.

- What are higher derivatives?
- Higher dimensional analogues of the argument principle?
- How to compute $\mathbb{Z}_n^*$, the unit group of the integers modulo $n$?
- Is there a General Formula for the Transition Matrix from Products of Elementary Symmetric Polynomials to Monomial Symmetric Functions?
- Detecting that a fraction is a repeating decimal
- Compute the Jacobson radical of $R=\mathbb{F}_3$ and find all simple $R$-modules.
- GCD Proof with Multiplication: gcd(ax,bx) = x$\cdot$gcd(a,b)
- Localization at an element is intersection of localizations at primes not containing the element
- Are products of powers of 2 and powers of 3 dense in the nonnegative reals?
- Find all the continuous functions such that $\int_{-1}^{1}f(x)x^ndx=0$.
- Period of a sequence defined by its preceding term
- Do trivial homology groups imply contractibility of a compact polyhedron?
- $\left|\frac{x}{|x|}-\frac{y}{|y|}\right|\leq |x-y|$, for $|x|, |y|\geq 1$?
- Is the axiom of choice really all that important?
- Nice expression for minimum of three variables?