Sunday, September 14, 2014

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 my 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.

Monday, September 8, 2014

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\)?

Friday, August 29, 2014

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?

Thursday, August 28, 2014

Artery Metal

Nine Minutes

Nine minutes of local support. Have potential.

Find Balance

Silence The Messenger

Technically proficient screamcore


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?


Thursday, August 21, 2014

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.

Tuesday, August 12, 2014

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?