Continuing on our occasional theme of "problems suitable for a prelim exam".
Lo these many years ago, I took (and passed) the prelim exam in Logic at the CUNY Grad Center. (I think they call it a "qualifying exam" there, but whatever. "Subject exam", if you will.) Now, the course structure was all model theory the first semester (syntax and semantics of first-order logic, compactness theorem, various other applications of ultraproducts, quantifier elimination, ... maybe a couple of other things?) and most of the second semester was spent proving the soundness and completeness theorems for the first-order syntactic calculus, and then the Incompleteness Theorem(s). We had maybe a month or so left at the end of that time, which the professor offered to spend on set theory and computability theory, divided as we liked. None of us had strong feelings, so we dipped a toe in each and went on our merry. The structure of the prelim exam followed the structure of the course.
The point of the preceding story was, that I have seen prelim problems from model theory, but few from set theory or recursion theory. (I think that exam did have a problem on it requiring use of a finite injury argument, but that was one of the ones I skipped.)
Anyway: I was reading some set theory this week, just for fun, and the author said something like "... it is a basic fact that c.c.c. forcing preserves cardinals and cofinalities, ...", and I said to myself, self, if it's so basic, why can you never remember why this should be true? And down the rabbit hole I went.
It took a few tries before I came up with a proof, and I still haven't gone back to see if the proof of this theorem in Jech or Kunen is substantially different. But I like the proof I came up with, it seems natural, and I think, if a prelim course were to cover forcing (like a first-year course devoted only to set theory really should) that a problem like this would make a natural prelim problem.
Theorem: If \( \kappa \) is a cardinal, \( \lambda = \mathrm{cf}(\kappa) \), and \( \mathbb{P} \) satisfies the \( \lambda \)-chain-condition, then for any \(V\)-generic filter \( G \) over \( \mathbb{P} \), the cofinality of \( \kappa \) in \(V[G] \) is still \( \lambda \).
Proof: Let \(\gamma < \lambda \), and let \( \mathring{f} \) be a \( \mathbb{P}\)-name for a function from \( \gamma \) into \( \kappa \). We must show that \[ \mathbb{1} \vdash \exists \xi < \kappa \; \forall \alpha < \gamma \; \mathring{f}(\alpha) < \xi \]
Now fix some \( \alpha < \gamma \) for the moment: we know by the Truth Lemma that, if \( V[G] \models \mathring{f}(\alpha) = \beta \), then for some \( p_{(\alpha, \beta)} \in G \), \( p_{(\alpha, \beta)} \vdash \mathring{f}(\alpha) = \beta \). For each \( \beta \) which could equal \( \mathring{f}(\alpha) \) in such a generic extension, fix such a \( p_{(\alpha, \beta)} \).
Then (with \(\alpha\) still fixed) it is clear that the \( p_{(\alpha, \beta)} \) are pairwise incompatible. Since \( \mathbb{P} \) satisfies the \( \lambda \)-chain condition, this collection of conditions has size \( \mu_\alpha < \lambda \), and hence \[ \left| \left\{ \beta < \kappa \colon \exists p \in \mathbb{P} \; p \vdash \mathring{f}(\alpha) = \beta \right\} \right| = \mu_\alpha < \lambda \]It follows that the set of possible range values of \( \mathring{f} \), namely \[ Y = \bigcup_{\alpha < \gamma} \left\{ \beta < \kappa \colon \exists p \in \mathbb{P} \; p \vdash \mathring{f}(\alpha) = \beta \right\} \]has cardinality no greater than \[ \sum_{\alpha < \gamma} \mu_\alpha \]
Now recall that \( \lambda \) is regular, so the sum of fewer than \( \lambda \) smaller cardinals \( \mu_\alpha \) must be less than \( \lambda \). It follows that \( Y \) is a bounded subset of \( \kappa \); say \( Y \) is bounded by \( \xi < \kappa \). Then \[ \mathbb{1} \vdash \forall \alpha < \gamma \; \mathring{f}(\alpha) < \check{\xi} \]
Lo these many years ago, I took (and passed) the prelim exam in Logic at the CUNY Grad Center. (I think they call it a "qualifying exam" there, but whatever. "Subject exam", if you will.) Now, the course structure was all model theory the first semester (syntax and semantics of first-order logic, compactness theorem, various other applications of ultraproducts, quantifier elimination, ... maybe a couple of other things?) and most of the second semester was spent proving the soundness and completeness theorems for the first-order syntactic calculus, and then the Incompleteness Theorem(s). We had maybe a month or so left at the end of that time, which the professor offered to spend on set theory and computability theory, divided as we liked. None of us had strong feelings, so we dipped a toe in each and went on our merry. The structure of the prelim exam followed the structure of the course.
The point of the preceding story was, that I have seen prelim problems from model theory, but few from set theory or recursion theory. (I think that exam did have a problem on it requiring use of a finite injury argument, but that was one of the ones I skipped.)
Anyway: I was reading some set theory this week, just for fun, and the author said something like "... it is a basic fact that c.c.c. forcing preserves cardinals and cofinalities, ...", and I said to myself, self, if it's so basic, why can you never remember why this should be true? And down the rabbit hole I went.
It took a few tries before I came up with a proof, and I still haven't gone back to see if the proof of this theorem in Jech or Kunen is substantially different. But I like the proof I came up with, it seems natural, and I think, if a prelim course were to cover forcing (like a first-year course devoted only to set theory really should) that a problem like this would make a natural prelim problem.
Theorem: If \( \kappa \) is a cardinal, \( \lambda = \mathrm{cf}(\kappa) \), and \( \mathbb{P} \) satisfies the \( \lambda \)-chain-condition, then for any \(V\)-generic filter \( G \) over \( \mathbb{P} \), the cofinality of \( \kappa \) in \(V[G] \) is still \( \lambda \).
Proof: Let \(\gamma < \lambda \), and let \( \mathring{f} \) be a \( \mathbb{P}\)-name for a function from \( \gamma \) into \( \kappa \). We must show that \[ \mathbb{1} \vdash \exists \xi < \kappa \; \forall \alpha < \gamma \; \mathring{f}(\alpha) < \xi \]
Now fix some \( \alpha < \gamma \) for the moment: we know by the Truth Lemma that, if \( V[G] \models \mathring{f}(\alpha) = \beta \), then for some \( p_{(\alpha, \beta)} \in G \), \( p_{(\alpha, \beta)} \vdash \mathring{f}(\alpha) = \beta \). For each \( \beta \) which could equal \( \mathring{f}(\alpha) \) in such a generic extension, fix such a \( p_{(\alpha, \beta)} \).
Then (with \(\alpha\) still fixed) it is clear that the \( p_{(\alpha, \beta)} \) are pairwise incompatible. Since \( \mathbb{P} \) satisfies the \( \lambda \)-chain condition, this collection of conditions has size \( \mu_\alpha < \lambda \), and hence \[ \left| \left\{ \beta < \kappa \colon \exists p \in \mathbb{P} \; p \vdash \mathring{f}(\alpha) = \beta \right\} \right| = \mu_\alpha < \lambda \]It follows that the set of possible range values of \( \mathring{f} \), namely \[ Y = \bigcup_{\alpha < \gamma} \left\{ \beta < \kappa \colon \exists p \in \mathbb{P} \; p \vdash \mathring{f}(\alpha) = \beta \right\} \]has cardinality no greater than \[ \sum_{\alpha < \gamma} \mu_\alpha \]
Now recall that \( \lambda \) is regular, so the sum of fewer than \( \lambda \) smaller cardinals \( \mu_\alpha \) must be less than \( \lambda \). It follows that \( Y \) is a bounded subset of \( \kappa \); say \( Y \) is bounded by \( \xi < \kappa \). Then \[ \mathbb{1} \vdash \forall \alpha < \gamma \; \mathring{f}(\alpha) < \check{\xi} \]
No comments:
Post a Comment