A universal algebraist proves Fodor's Lemma

In the last post, we mentioned Fodor's Lemma (in the context of an attempted proof that didn't end up working out). Well, my brain was idling the other evening, and decided that it needed to prove this lemma. Don't ask me why my brain does what it does.

Attention conservation notice: this post is written for someone with maybe a lower-level grad-school level of knowledge, or maybe upper-level undergrad, and who knows what a subalgebra is but doesn't necessarily know any logic.

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.

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

Don't stop! I yield!

Riffing on the topic I touched on a few weeks ago, of questions on high-pressure exams, I wanted to share some thoughts about a fun programming problem that I'm not sure makes a great interview question -- but maybe that's an argument for why it does.

The problem was mentioned in a thread about programming interview questions.

Consider the digits 123456789, in that order. Now consider the value of the expression resulting from inserting + or * between some of those digits: for example, you could insert + after 2 and 4 and * after 1 and 8, resulting in

>>> 1*2+34+5678*9
<<<   51148

or insert + after 3, 6, and 8, resulting in

>>> 123+456+78+9
<<<   666

Write a program which prints out all the expressions of this kind which evaluate to 2003. (Hint: there are exactly four.)

(Nil)Potent problems

Somehow, every year about this time, I start thinking about preliminary exams. (Also known at other institutions as subject exams, qualifying exams, etc.: the dreaded first hurdle of staying in grad school.) Specifically, I start thinking about questions that would be appropriate to ask on such exams, in difficulty, length, and subject matter.

Now, I'm going to avoid my usual rant about the content of most prelims in algebra -- this post isn't about prelims per se, and besides that, the problem I want to talk about is one that I emphatically wish algebra prelims wouldn't test! But it's a fun little argument nevertheless.

Proof by Contradiction

I spent one morning at the JMMs this week in a session on the Introduction-To-Proofs course (aka the Bridge course). I enjoyed the session; it contained some good techniques to include, some good warnings of things to avoid, etc. Such a course always includes learning about proof by contradiction.

Now, I have a bit of a thing about proof by contradiction. It's not that it's invalid; it's that, at least in classical logic, you can always transform a proof by contradiction into a proof by contraposition; in any case, while I'm not a constructivist and think that intuitionistic logic is mostly a curiosity, it's nice to have a proof which provides an implicit algorithm, when such a thing exists.

So today on the train I was puzzling over a little bit of boolean-algebra arithmetic which Tom Jech uses in his exposition of forcing. (I'm supervising an undergrad who wants to learn forcing, and the boolean-valued-model approach is so much nicer than the poset-only approach.) I tried to prove it forwards six ways to Sunday, and nothing seemed to work. So, remembering what we all tell students in Bridge courses, I turned it around and tried to prove it by contradiction, and that took all of six lines. I still don't see a direct proof that's not an artificial translation of the contradiction/contraposition result; if you know one, put it in the comments!

Theorem: Recall that in boolean algebras, the implication operation \( v_1 \Rightarrow v_2 \) is defined as \( v_2 \lor \neg v_1 \). If \(x,y,z \) belong to a boolean algebra \( \mathbf{B} \) and \( x \land y = x \land z \), then \( x \leq ( y \Leftrightarrow z) \).

Proof: Suppose otherwise. Then we can find elements \( x, y, z \) in a boolean algebra \( \mathbf{B} \) so that
\[ x > y \Rightarrow z = x \land ( z \lor (\neg y)) \]
Now observe that
\[ x \land ( z \lor (\neg y)) = (x \land z) \lor (x \land \neg y) = (x \land z) \lor (x \land y) \lor (x \land \neg y) = (x \land z) \lor x \geq x \]
Overall, \( x > x \), a contradiction.

A nice little finite group exercise

Exercise 1: Using the Structure Theorem for Finite Abelian Groups, or otherwise, show that a Sylow \(p\)-subgroup of a finite abelian group is a characteristic subgroup.

Exercise 2: If \(N \triangleleft G \) is a minimal nontrivial normal subgroup, and is finite and abelian, then \(|N|\) is a power of a prime.

An elementary exercise in group actions

Let \(G\) be a group, \(T\) a normal subgroup, and suppose that \(G\) acts transitively on a set \(X\). Then the induced action of \(T\) on \(X\) may not be transitive; let \(T \setminus X\) denote the orbit space. Show that the quotient group \(G/T\) acts well-definedly and transitively on \(T \setminus X\).

 I plan to do this somewhat regularly... I know that I'm terrible about keeping up a store of problems and examples, which is a key component of mathematical pedagogy.

Favorite problem

from yesterday's exam (2nd semester calculus, targeted at students going into engineering and sciences:

For which \(x\) does \[ \sum_{n=1}^\infty \left( \arctan (1 + \frac{x}{n}) \right)^n\]converge?

(If it wasn't obvious before, I'm done grading. It may as well be officially summer.)