7
$\begingroup$

Assume ZFC is consistent. Then its not true that every model $(M,\in')$ of ZFC has an element $x \in M$ such that $M$ believes that $x$ is a model of ZFC. Otherwise, by the semantic completeness theorem for first order logic, ZFC would prove its own consistency, thereby running afoul of Goedel's second incompleteness theorem.

However, it is true that every model $(M,\in')$ of ZFC has the property that there exists $A \subseteq M$ and $R \subseteq M^2$ such that $(A,R)$ is a model of ZFC. For example, take $A = M$ and $R = [\in'].$ This also shows that $A$ and $R$ can defined in the language of $(M,\in')$.

So firstly, is this analysis correct? I feel like I might be misusing the completeness theorem in the 1st paragraph, or at least misrepresenting it.

Secondly and more importantly, why doesn't the completeness theorem apply to these class-sized models $(A,R)$, thereby yielding a contradiction?

$\endgroup$
  • $\begingroup$ Just another one of these subtle points where theory and metatheory can be confused. $\endgroup$ – Asaf Karagila Nov 9 '13 at 12:46
  • $\begingroup$ (By the way, I noticed that over half of your questions which have been answered, do not have an accepted answer.) $\endgroup$ – Asaf Karagila Nov 9 '13 at 13:05
  • $\begingroup$ @AsafKaragila, well I've been more diligent about accepting answers the past 3 months or so, so I don't think its really a big deal. Its true that I should go back and accept past answers at some point, but I simply don't have the time at the moment. $\endgroup$ – goblin Nov 9 '13 at 13:17
5
$\begingroup$

I think you would actually use the soundness theorem, rather than the completeness theorem. So the false proof of the consistency of $\mathsf{ZF}$ would go something like this:

  1. Consider the class of all sets $V$ and the class of ordered pairs $\langle x, y \rangle$ where $x \in y$.

  2. Define a class function, $F$ from formulas over the language of $\mathsf{ZF}$ with parameters from $V$ to the set $\{0, 1\}$. Think of $F(\phi)$ as the truth value of $\phi$. We will write $V \models \phi$ to mean $F(\phi) = 1$ and $V \not \models \phi$ to mean $F(\phi) = 0$.

  3. Show (inside $\mathsf{ZF}$) that for each theorem $\phi$ of $\mathsf{ZF}$, $V \models \phi$, by checking the axioms of $\mathsf{ZF}$ hold and then applying the soundness theorem.

  4. Note that by the definition of $\models$, we can't have $V \models \bot$.

  5. Deduce that $\mathsf{ZF}$ is consistent.

I want to say that the part of this argument that fails is in fact 2. We can't define the "truth value" class function, so the parts that come afterwards, where we talk about $V \models \phi$ aren't even meaningful.

The way that we want to define the truth value function $F$ is as follows. We want to define it recursively on the structure of formulas. For example, we want $F(\phi \wedge \psi)$ to be one if both $F(\phi)$ and $F(\psi)$ are one, and zero otherwise. We want $F(\forall x \, \phi(x))$ to be one if $F(\phi(a)) = 1$ for every $a \in V$ and zero otherwise. However, we can't state this directly in the language of set theory.

If we were working over a set, instead of over $V$, then we could apply the recursion theorem to get a definition for $F$ based on the obvious inductive definition. However, this doesn't hold together when working with proper classes. I think the key point here is that because the formulas can have parameters from $V$, there is a proper class of them, and in particular the inductive clauses for quantifiers would be most problematic.

An alternative is work "outside" $\mathsf{ZF}$ and to define for each formula $\phi$ of $\mathsf{ZF}$, a separate formula of $\mathsf{ZF}$ to represent $V \models \phi$. However, this isn't sufficiently "internal" to prove the consistency of $\mathsf{ZF}$ inside $\mathsf{ZF}$. The general technique is however often useful for showing that a theory $T$ is consistent if a theory $T'$ is consistent (as opposed to showing that $T'$ proves that $T$ is consistent).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.