More on the countable chain condition

We last met the ccc in the context of preserving cofinalities in forcing extensions; but the exercise that I gave the proof for was specifically about forcing. This week, I ran across a nice little exercise which doesn't explicitly mention forcing at all -- it's pure combinatorics -- but, at least for me, thinking about it using the forcing idea was the key to solving the problem.

Exercise 1: Let \( \mathbb{P} \) be a ccc poset, and let \( X = \{ x_i \colon i < \omega_1 \} \subseteq \mathbb{P} \) be a subset. Show that there exists an uncountable subset of \( X \) whose every pair are compatible.

At first glance, this looks completely obvious -- things are either compatible or incompatible, and you can't have more than countably many pairwise incompatible things. The problem, though, is that the compatibility relation need not be transitive -- just because you have an uncountable subset of \(X\) which is not an antichain does not mean that it satisfies the conclusion of the exercise.

What made this problem interesting to me was that I had to discard some of the heuristics that usually serve me well. In particular, a dependable heuristic when dealing with posets is duality: if something is true for all posets, then you should be able to turn your poset upside-down and it should still be true. However, the compatibility relation is not stable under duality! Most forcing posets have a single weakest condition; if you dualize, you get that every two conditions are compatible, which is clearly useless.

Alice and Bob visit the cardinal, Part II

(Part I of this post can be found here.)

Greetings, loyal blog readers! I'm afraid life took over for a bit after writing Part I, but we're now back in the peanut gallery watching Alice and Bob battle wits.

In the last post, we talked about a fun game which Matt Baker used to prove the uncountability of the reals. (We'll call this the Nested-Intervals Game.) In his post about this game, he asked a question which (still weeks later) is vexing me:

Question 0: Does there exist a target set \(T\) such that neither player has a winning strategy for the Nested-Intervals Game targeting \(T\)?

On voter fraud

Dear Texas,

If you're so damn concerned about someone else showing up and voting under my name, sending voter registration cards as postcards seems awfully...casual, no?

Artery Metal

Nine Minutes


Nine minutes of local support. Have potential.

---

Find Balance

---

Silence The Messenger


Technically proficient screamcore

---

Allegaeon


Worth the price of a ticket on their own.

---

Upon This Dawning


Hey, if it gets screaming teenage girls to like death metal, who am I to complain?

---

Chimaira

Alice and Bob visit the cardinal, part I

(Part II of this post can be found here.)

Speaking of diagonal arguments: I ran across the blog of one Matt Baker yesterday, who sketched out probably the easiest proof I've ever seen of the uncountability of the real line. He also included a question in his post, one that I have a strong intuition about the answer, but so far haven't been able to prove I'm right.

(NB: when I say easiest proof I've ever seen, I mean that I sat down at lunch with a colleague who hadn't seen math since her freshman year of calc, and we finished lunch with her pretty much all over that shit.)

Anyway, I thought I'd record that argument in case Baker's blog disappears or (as has happened twice today) I can't figure out search terms to find it again. The next post will discuss his question, the version of an answer I can prove, and what makes the full problem more difficult. I'll try to pitch the level of these posts (well, more this one than the next) at the level of my lunch colleague.

Today in pissy racism

A quick note for those keeping score at home: Kevin Williamson is still a race-baiting piece of shit:

[National Review] decided to send roving correspondent Kevin Williamson, who has some strong revisionist views on American racial politics, to East St. Louis, Illinois, to take in the local scene, and … oh, no:

East St. Louis, Ill. — "Hey, hey craaaaaacka! Cracka! White devil! F*** you, white devil!" The guy looks remarkably like Snoop Dogg: skinny enough for a Vogue advertisement, lean-faced with a wry expression, long braids. He glances slyly from side to side, making sure his audience is taking all this in, before raising his palms to his clavicles, elbows akimbo, in the universal gesture of primate territorial challenge. Luckily for me, he’s more like a three-fifths-scale Snoop Dogg, a few inches shy of four feet high, probably about nine years old, and his mom — I assume she’s his mom — is looking at me with an expression that is a complex blend of embarrassment, pity, and amusement, as though to say: “Kids say the darnedest things, do they not, white devil?”

The scene ends with an interminable sentence Williamson probably regards as “literary":

... my terminus in East St. Louis, where instead of meeting my Kurtz I get yelled at by a racially aggrieved tyke with more carefully coiffed hair than your average Miss America contestant.

There are a few lines in here that a good editor would cut but could be waved off as unwitting bad judgment — the Heart of Darkness reference, three fifths, making fun of the hair. But when the writer also decides the best comparison for a young black kid’s behavior is a monkey and to gratuitously question his parentage, there’s really not much question, is there?

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