Friday, July 11, 2014

Fundamental theorem on chain conditions

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} \]

Tuesday, July 8, 2014

Spectral Lore: III

An absolutely gorgeous long (LONG!) album from one-man Greek outfit Spectral Lore. Too upbeat to be doom, too riffy to be folk metal, too little guitar masturbation to be progressive, not quite black enough to be black, but shares something with all of these...

Listen to it all of a piece, or not at all. This is not an album to sample an isolated track from

Thursday, July 3, 2014


Oh my.

I only now realized the joke in that the alien Lurr, from Futurama, is from the planet Omicron Persei Eight.

O. P. Eight.

And they're always watching TV there.

Hmmmmm. I see what you did there.

Sunday, June 29, 2014

Candlelight Records sampler: "Legion III"

Hat tip to No Clean Singing for pointing to this sampler of tasty new metal. In particular, the last track, by UK band Xerath, is kinda addictive.

Saturday, June 28, 2014

Vignettes of modernia

A crushed bottle of Five Hour Energy in the parking lot of Ikea.
At ten in the morning on a Saturday.

Thursday, June 19, 2014

Knowledge Transfer

A quick note, stemming from discussions at the new job about depth of knowledge (on the part of elementary/middle school students and their teachers) and related questions. One of those related questions is knowledge transfer: the ability to take knowledge from one context and apply it in a related context. The first hurdle there, of course, is recognizing that the contexts are related; the second is knowing what to keep and what to change, as the contexts change.

A complicated link of half-remembered references brought me to a paper (PDF) by one Michelle Perry describing an experiment done with 4th and 5th graders. The children in the experiment were selected based on knowing basic arithmetic (addition and multiplication under 20) but not being able to correctly fill in a blank in a problem like
\[ 4 + 6 + 3 = \_\_ + 3 \]
which tests the conception of the \(=\) sign as a statement of equivalence (correct) or an instruction to go forth and compute (incorrect). Students were given either direct instruction in the procedure to follow (add up the left hand side and then subtract the known term on the right from that sum), or given a purely conceptual instruction with no explicit steps.

What is really interesting is the result: both groups did roughly as well on post-instructional assessment -- but only on the problems that used addition, and so were exactly analogous to the problem they'd been instructed on. The post-test, however, also included problems that required the same principle, but used multiplication instead:
\[ 3 \times 2 \times 3 = \_\_ \times 3\]
In these problems, the children who had been taught a procedure "followed" it by doing the multiplication on the left and then subtracting the known "term" on the right from the product! Around 40% of the children who had been taught the principle underlying the problem successfully transferred knowledge to the unfamiliar setting, compared to 10% of the "procedure" group.

The remainder of the study is interesting too: their results indicate that teaching concept-plus-procedure actually undercuts transfer: basically if you teach a concept and then immediately teach a procedure for it, students' conceptual understanding gets washed out by the procedural knowledge.

Tuesday, June 10, 2014

Be prepared

Note to self: when buying a can of beans to make into part of dinner, make sure that your new apartment has the use of a can opener.