Metsatöll
Týr
Eluveitie
Thursday, September 25, 2014
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 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.
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 P be a ccc poset, and let X={xi:i<ω1}⊆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.
Exercise 1: Let P be a ccc poset, and let X={xi:i<ω1}⊆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?
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?
Subscribe to:
Posts (Atom)