12
$\begingroup$

It seems that the Godel's Condensation Lemma is typically used to show that certain constructible sets will appear by some stage of the construction of $L$. For example in the proof that CH holds in $L$, GCL is used to show that if $X \subset \omega$ is contructible, then $X \in L_{\omega_{1}}$.

Does anyone know if there are combinatorial arguments for these sorts of facts; i.e. arguments that don't use GCL or results from model theory? How would one prove $L \models$CH to someone who did not know the Lowenheim-Skolem theorem?

$\endgroup$
3
  • $\begingroup$ I strongly suspect that there is no such argument, but I've upvoted because if there is one I'd love to hear it. $\endgroup$ Commented Jun 26, 2014 at 21:02
  • $\begingroup$ You can make it "Reductio ad Previousium" where you argue that if $L\models\lnot\sf CH$, then all the previous proofs were wrong, and that's impossible. ;-) $\endgroup$
    – Asaf Karagila
    Commented Jun 26, 2014 at 22:00
  • $\begingroup$ You can also use the Condescension Lemma for a very quick proof. For example, "Q: Why does $L$ satisfy $\sf CH$?", "A: Pfft, if you have to ask, you wouldn't get it anyway". $\endgroup$
    – Asaf Karagila
    Commented Jun 26, 2014 at 22:06

2 Answers 2

4
$\begingroup$

It's been 25 years since I struggled through it, but I clearly remember that Godel's book Consistency of the Axiom of Choice and of the Generalized Continuum Hypothesis with the Axioms of Set Theory gets this result combinatorially --- exactly how, I have long forgotten. I only learned about the much, much easier Lowenheim-Skolem proof later on.

I've been told that Godel wrote his book that way, in machine language, essentially, because he didn't want any philosophical doubts people might have about logic to affect their reception of his theorem.

$\endgroup$
5
  • $\begingroup$ Wow! It would be great if someone could summarize the argument he used. $\endgroup$ Commented Jun 27, 2014 at 1:08
  • $\begingroup$ Yeah, I actually thought I had a copy of the book but I couldn't find it just now. I'll go look again. $\endgroup$
    – Nik Weaver
    Commented Jun 27, 2014 at 1:15
  • $\begingroup$ ... no luck, it is nowhere to be found. $\endgroup$
    – Nik Weaver
    Commented Jun 27, 2014 at 2:36
  • $\begingroup$ If I remember correctly, Gödel avoided formalizing first-order logic by using what are now called the Gödel operations, a collection of functions that suffice to construct, from a given set, all the sets first-order-definable over it. If you look at the Gödel functions you'll see that some of them correspond to the first-order quantifiers and connectives, and others take care of bookkeeping, like permuting the arguments of a relation. $\endgroup$ Commented Jun 27, 2014 at 2:37
  • $\begingroup$ @AndreasBlass That's familiar, then. I suppose that one can replace the Lowenheim-Skolem argument just by closing under the operations, which one can do without increasing the cardinality, and then arguing that the Mostowski collapse is also closed under the operations and hence is some $L_\beta$. $\endgroup$ Commented Jun 27, 2014 at 12:18
1
$\begingroup$

Not an answer, but too long for a comment: here is how I would explain (not prove) that $L\models CH$ to someone who has not seen Lowenheim-Skolem (actually, I would really prefer to just show them Lowenheim-Skolem - it's easy and beautiful! - but suppose for some reason I can't).

There's a proof of a related claim which does not use Lowenheim-Skolem (well, it uses the key idea). We can define a "baby $L$" for second-order arithmetic: for $\eta\in ON$, we define $M_\eta$ recursively as

  • $M_0=(\omega, \{\})$,

  • $M_\lambda=(\omega, \bigcup_{\alpha<\lambda}M_\alpha$),

  • $M_{\alpha+1}=\Pi^1_2-Def(M_\alpha)$,

where $\Pi^1_2-Def(N)$ is the set of subsets of the first-order part of $N$ which are $\Pi^1_2$-definable over $N$.

Now the "$L\models CH$"-like claim is that this construction terminates at level $\omega_1$ and results in at most $\omega_1$-many reals; that is, $$M_{\omega_1}=M_{\omega_1+1}=\bigcup_{\eta\in ON} M_\eta \quad\mbox{and}\quad \vert \mathbb{R}^{M_{\omega_1}}\vert\le\omega_1.$$

Note that the second claim follows immediately from the first, since at each countable stage we only add countably many reals; so suppose $r$ is a real definable over $M_{\omega_1}$ via some formula $\varphi$ (WLOG, using no parameters) - so $n\in r$ iff $M_{\omega_1}\models\varphi(n)$. For each $n\in\omega$, let $\mathcal{F}_n: \mathbb{R}^{M_{\omega_1}}\rightarrow\mathbb{R}^{M_{\omega_1}}$ be the function defined as:

  • if $M_{\omega_1}\models\varphi(n)$, then $\mathcal{F}_n$ is a Skolem function for $\varphi(n)$; and

  • if $M_{\omega_1}\models\neg\varphi(n)$, then $\mathcal{F}_n$ is the constant function always spitting out a counterexample real.

Of course, we don't want to use the phrase "Skolem function" here, but the beauty of a $\Pi_2$-sentence is that it's easy to define what a Skolem function is - we don't have to talk about Skolemization.

Now we can easily show that there is some $\alpha<\omega_1$ which is closed under every $\mathcal{F}_n$. Thus $r$ is defined by $\varphi$ over $M_\alpha$, and so is already in $M_{\alpha+1}$.


At this point there are two gaps: how do we replace "$\Pi^1_2$-definable" with "definable;" and how do we turn this into an "internal" (to $L$, that is) argument? (Note that it makes no sense to talk about this construction within second-order arithmetic, so the argument above is decidedly external.)

At this point, I'd introduce Skolemization to handle the first point (which is easy in light of the proof above), and say that what's needed for the second point is the ability to "make local truth-definitions" inside $L$ (note that these truth-definitions are the crucial step in the condensation lemma itself). This still leaves the serious work of building those truth-definitions, and checking that everything works, undone; but at this point they should have a sense of why the claim is true at least.


Again, this isn't anything close to a proof that $L\models CH$; but hopefully it would give some of the intuition with less of the technical difficulty.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .