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.
Here are the relevant definitions: let \( \kappa \) be a regular uncountable cardinal. A cardinal is an ordered set (of ordinals), so we know what it means for a subset of \( \kappa \) to be unbounded. The order relation on \( \kappa \) also gives rise to a topology in the following way: the basic open sets are intervals of the form \( (\alpha, \beta) \) and \( (\alpha, \infty) \). A subset \( C \subseteq \kappa \) is closed if it is closed in this topology.
Test your understanding:
Lemma 1: The intersection of fewer-than-\(\kappa\)-many clubs is a club.
Proof: Let \( \langle C_i \colon i < \gamma \rangle \) be clubs, and let \(B = \bigcap_i C_i \). We learn on the first day of topology that arbitrary intersections of closed sets are closed, so that half is done.
To show that \(B\) is unbounded, let \( \delta < \kappa \). We define an increasing function \( f: \gamma \times \gamma \rightarrow \kappa\). We will build it so that its sup belongs to \( B\). (Oddly enough, \( f(\alpha, i) \) need not belong to \( B \) for any \( \alpha, i < \gamma\).)
Define
We can think of putting the \( C_i \) in a circle, all pointing upwards like sticks in a bundle; then \(f(\alpha, i)\) will look like a ribbon winding upwards around and around the bundle.
Now: for each \( i < \gamma \), the elements \( f(\alpha, i) \) form an increasing \( \gamma\)-sequence of elements of \( C_i \). We proved above that this means that the sup \( a_i \) of these elements also belongs to \( C_i \).
Check your understanding: Show that the suprema \(a_i \) are all equal to each other.
This last statement shows that this supremum belongs to \(B\), which completes the proof.
Corollary 2: the set of all club subsets of \( \kappa \) generate a filter \( \mathcal{F} \).
Proof: Lemma 1 showed that the set of clubs has the finite intersection property. Q.E.D.
Now, the usual terminology set theorists use for things related to this filter drive me batty. I'll mention these standard names in footnotes, and maybe sometime in the future I'll go on a rant about why these names are so terrible, but for now I'll just protest by using what I think are better names.
The basis of my preferred nomenclature is the idea of a measure. Now, normally a measure takes sets and assigns them a number between 0 and 1. Here, though, I'll think of a measure as taking values in a certain boolean algebra. Don't worry if you aren't familiar or comfortable with boolean algebras -- we won't actually be doing anything with them today. All you need to know is that a boolean algebra allows you to talk about a single biggest possible measurement (called True, or 1, or something like that), a single smallest possible measurement (called False, or 0, or something), and then maybe other intermediate measurements which may or may not be comparable to each other.
In particular, a filter is a notion of "largeness", so it makes sense to say that if a set \(S \subseteq \kappa \) is a club, or has a club subset, it belongs to the filter \( \mathcal{F} \) we constructed above, and we'll say it has "club-measure 1". Conversely, if the complement of \(S\) has a club subset, i.e. \(S\) is disjoint from some club, then \(S\) has club-measure 0. A set may have positive club-measure without having measure 0 or 1; in this case, it follows that this set must have nonempty intersection with every club.[1]
So now we can state Fodor's Lemma (sometimes known as the Regressive Function Lemma, or the Pressing Down Lemma):
Fodor's Lemma: Let \(S \subseteq \kappa \) have nonzero club-measure, and let \(f: S \rightarrow \kappa \) be a function such that \(f(\alpha) < \alpha \) for all \( \alpha \in S\). Then \(f\) is constant on some set of nonzero club-measure.
(You can think of this lemma as providing a kind of generalization of the pigeonhole principle. Sort of.)
OK, so that's what we want to prove. What does this have to do with universal algebra?
Lemma 3: Let \( \langle \kappa; \mathcal{R} \rangle \) be any algebra structure on \( \kappa \), where \( \mathcal{R} \) is a set of (finitary) operations and \( |\mathcal{R}| < \kappa \). Then the set \(S\) of those \( \beta < \kappa \) which are substructures of this algebra structure form a club.
Proof: Since the union of any chain of subalgebras is again a subalgebra, \(S\) is closed (in the order topology).
To show that \(S\) is unbounded, let \( \delta < \kappa \). We define an increasing chain of subalgebras whose union will be an ordinal.
Let \[\delta_0 = \delta\]\[A_0 = \mathrm{Sg}(\delta_0)\]\[\delta_{k+1} = \sup A_k\]\[A_{k+1} = \mathrm{Sg}(\delta_{k+1})\]\[A = \bigcup_{k < \omega} A_k\]Then if \( \beta \in A \) and \( \alpha < \beta\) then \( \alpha < \delta_{k+1} \) so \( \alpha \in A_{k+1} \subseteq A \). This proves that \(A\) is an ordinal, so belongs to \(S\), so \(S\) is unbounded. Q.E.D.
Corollary 4: If \(f: \kappa \rightarrow \kappa \) is increasing and continuous, then the set of fixed points of \(f\) form a club.
Proof: For any \( \beta < \kappa \), \( \beta \leq f(\beta) \) since \(f\) is increasing. Now let \(\beta < \kappa \) be a substructure of \( \langle \kappa; f \rangle \). Then \( f(\beta) = \sup_{\alpha < \beta} f(\alpha) \) since \(f\) is continuous. But since \( f(\alpha) < \beta \) for all \( \alpha < \beta \), \(\sup_{\alpha < \beta} f(\alpha) \leq \beta \). These inequalities combine to assert that \( f(\beta) = \beta \). Q.E.D.
Now we get to the definition which makes all the magic happen.
Check your understanding:
Definition: If \( S_i \subseteq \kappa \) for \( i < \kappa \), the diagonal intersection of these sets consists of all \( \beta < \kappa \) such that \( \beta \in S_\alpha \) for all \( \alpha < \beta \).
This definition looks strange and artificial at first. That's OK; it ends up being really, really useful. Remember how I said I wasn't going to talk about boolean algebras? Well, this is me not talking, but just mentioning that this diagonal intersection idea ends up enabling us to compute sups and infs in the boolean algebra where we're taking measurements of sets. I've said too much already.
One thing to observe is that, while order is irrelevant for ordinary intersections, that is no longer true for diagonal intersections. (However: it is possible to prove that any reordering of the \(S_i\) ends up changing the diagonal intersection by only a club-measure 0 set.)
Lemma 5: The diagonal intersection \(D\) of any family \( \langle C_i \colon i < \kappa \) of clubs is once again a club.
Proof: Define a \(\kappa\)-sequence by recursion: \( x_0 = \omega \), and \(x_{j+1} \) is some element of \( \bigcap_{i \leq j} C_i \) which is greater than \(x_j\). For limit ordinals \(j\), define \( x_j \) to be the limit of the \( x_i \) for \(i < j\).
By Corollary 4, this sequence has a club of fixed points. Let \(\beta = x_\beta \) be one of them. Then since \( x_\beta \) belongs to all \(C_i\) for \(i < \beta\), \(\beta = x_\beta \) belongs to \(D\). Hence \(D\) has club-measure 1. I'll leave the proof that \(D\) is closed to you. Q.E.D.
Proof of Fodor's Lemma: Let \(S \subseteq \kappa \) have positive club-measure, and let \(f: S \rightarrow \kappa \) satisfy \( f(\alpha) < \alpha \) for all \( \alpha \).
Suppose for the sake of contradiction that \(f^{-1}(\alpha) \) has club-measure 0 for all \( \alpha \). Choose clubs \( C_\alpha \) disjoint from the \(f^{-1}(\alpha) \), and let \(D\) be their diagonal intersection. Lemma 5 shows that \(D\) is a club. Since \(S\) has positive measure and \(D\) has measure 1, \(S \cap D\) has positive measure.
Since \(D\) is unbounded, we can choose \( \beta > 0 \) in \(D\). By the definition of "diagonal intersection", \(\beta\) belongs to each \( C_\alpha \) for \( \alpha < \beta \). Hence \( \beta \) does not belong to any \( f^{-1}(\alpha)\) for \( \alpha < \beta \). But this is absurd, since \( \beta \) definitely belongs to \( f^{-1}(f(\beta)) \)! Q.E.D.
Final thoughts: In one sense, "almost all" ordinals are successors. However, observe that the set of limit ordinals less than \( \kappa \) is club, so using the club filter as a notion of "almost everything", "almost all" ordinals are limit! This actually corresponds much better to the usual heuristics that a set theorist's brain runs on -- very little of substance happens at successor ordinals, or successor cardinals, when it comes to independence proofs. (I'm exaggerating somewhat, of course.)
[1] The usual nomenclature used by set-theorists is that a set of club-measure 0 is nonstationary, while a set of positive club-measure is called stationary. All I can say to that is "ugh".
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.
Here are the relevant definitions: let \( \kappa \) be a regular uncountable cardinal. A cardinal is an ordered set (of ordinals), so we know what it means for a subset of \( \kappa \) to be unbounded. The order relation on \( \kappa \) also gives rise to a topology in the following way: the basic open sets are intervals of the form \( (\alpha, \beta) \) and \( (\alpha, \infty) \). A subset \( C \subseteq \kappa \) is closed if it is closed in this topology.
Test your understanding:
- Show that every successor ordinal is an isolated point in this topology.
- Show that \( \omega \) (and similarly every limit ordinal) is not isolated.
- Show that a subset \( S \subseteq \kappa \) is closed if and only if, for every increasing sequence \( \langle s_i \colon i < \gamma \rangle \subset S \), where \( \gamma < \kappa \) is a limit ordinal, \( \sup_{i < \gamma} s_i \) also belongs to \(S\).
Lemma 1: The intersection of fewer-than-\(\kappa\)-many clubs is a club.
Proof: Let \( \langle C_i \colon i < \gamma \rangle \) be clubs, and let \(B = \bigcap_i C_i \). We learn on the first day of topology that arbitrary intersections of closed sets are closed, so that half is done.
To show that \(B\) is unbounded, let \( \delta < \kappa \). We define an increasing function \( f: \gamma \times \gamma \rightarrow \kappa\). We will build it so that its sup belongs to \( B\). (Oddly enough, \( f(\alpha, i) \) need not belong to \( B \) for any \( \alpha, i < \gamma\).)
Define
- \( f(0,0) \) to be some element of \( C_0 \) which is greater than \( \delta \);
- if \( \alpha < \kappa \) and \(f(\alpha, i) \) have been defined for all \(i < j\), define \( f(\alpha, j) \) to be some element of \(C_j\) which is greater than all \(f(\alpha, i)\) defined so far;
- lastly, if \( f(\alpha, i) \) is defined for all \( \alpha < \beta \) and all \(i < \kappa \), define \( f(\beta, 0) \) to be some element of \( C_0 \) greater than all \( f(\alpha, i) \) defined so far.
We can think of putting the \( C_i \) in a circle, all pointing upwards like sticks in a bundle; then \(f(\alpha, i)\) will look like a ribbon winding upwards around and around the bundle.
Now: for each \( i < \gamma \), the elements \( f(\alpha, i) \) form an increasing \( \gamma\)-sequence of elements of \( C_i \). We proved above that this means that the sup \( a_i \) of these elements also belongs to \( C_i \).
Check your understanding: Show that the suprema \(a_i \) are all equal to each other.
This last statement shows that this supremum belongs to \(B\), which completes the proof.
Corollary 2: the set of all club subsets of \( \kappa \) generate a filter \( \mathcal{F} \).
Proof: Lemma 1 showed that the set of clubs has the finite intersection property. Q.E.D.
Now, the usual terminology set theorists use for things related to this filter drive me batty. I'll mention these standard names in footnotes, and maybe sometime in the future I'll go on a rant about why these names are so terrible, but for now I'll just protest by using what I think are better names.
The basis of my preferred nomenclature is the idea of a measure. Now, normally a measure takes sets and assigns them a number between 0 and 1. Here, though, I'll think of a measure as taking values in a certain boolean algebra. Don't worry if you aren't familiar or comfortable with boolean algebras -- we won't actually be doing anything with them today. All you need to know is that a boolean algebra allows you to talk about a single biggest possible measurement (called True, or 1, or something like that), a single smallest possible measurement (called False, or 0, or something), and then maybe other intermediate measurements which may or may not be comparable to each other.
In particular, a filter is a notion of "largeness", so it makes sense to say that if a set \(S \subseteq \kappa \) is a club, or has a club subset, it belongs to the filter \( \mathcal{F} \) we constructed above, and we'll say it has "club-measure 1". Conversely, if the complement of \(S\) has a club subset, i.e. \(S\) is disjoint from some club, then \(S\) has club-measure 0. A set may have positive club-measure without having measure 0 or 1; in this case, it follows that this set must have nonempty intersection with every club.[1]
So now we can state Fodor's Lemma (sometimes known as the Regressive Function Lemma, or the Pressing Down Lemma):
Fodor's Lemma: Let \(S \subseteq \kappa \) have nonzero club-measure, and let \(f: S \rightarrow \kappa \) be a function such that \(f(\alpha) < \alpha \) for all \( \alpha \in S\). Then \(f\) is constant on some set of nonzero club-measure.
(You can think of this lemma as providing a kind of generalization of the pigeonhole principle. Sort of.)
OK, so that's what we want to prove. What does this have to do with universal algebra?
Lemma 3: Let \( \langle \kappa; \mathcal{R} \rangle \) be any algebra structure on \( \kappa \), where \( \mathcal{R} \) is a set of (finitary) operations and \( |\mathcal{R}| < \kappa \). Then the set \(S\) of those \( \beta < \kappa \) which are substructures of this algebra structure form a club.
Proof: Since the union of any chain of subalgebras is again a subalgebra, \(S\) is closed (in the order topology).
To show that \(S\) is unbounded, let \( \delta < \kappa \). We define an increasing chain of subalgebras whose union will be an ordinal.
Let \[\delta_0 = \delta\]\[A_0 = \mathrm{Sg}(\delta_0)\]\[\delta_{k+1} = \sup A_k\]\[A_{k+1} = \mathrm{Sg}(\delta_{k+1})\]\[A = \bigcup_{k < \omega} A_k\]Then if \( \beta \in A \) and \( \alpha < \beta\) then \( \alpha < \delta_{k+1} \) so \( \alpha \in A_{k+1} \subseteq A \). This proves that \(A\) is an ordinal, so belongs to \(S\), so \(S\) is unbounded. Q.E.D.
Corollary 4: If \(f: \kappa \rightarrow \kappa \) is increasing and continuous, then the set of fixed points of \(f\) form a club.
Proof: For any \( \beta < \kappa \), \( \beta \leq f(\beta) \) since \(f\) is increasing. Now let \(\beta < \kappa \) be a substructure of \( \langle \kappa; f \rangle \). Then \( f(\beta) = \sup_{\alpha < \beta} f(\alpha) \) since \(f\) is continuous. But since \( f(\alpha) < \beta \) for all \( \alpha < \beta \), \(\sup_{\alpha < \beta} f(\alpha) \leq \beta \). These inequalities combine to assert that \( f(\beta) = \beta \). Q.E.D.
Now we get to the definition which makes all the magic happen.
Check your understanding:
- We showed in Lemma 1 that the club filter was closed under intersections of size less than \( \kappa \). Show that this is equivalent to the fact that the union of fewer than \( \kappa \) sets of club-measure 0 still has club-measure 0.
- Show that \( \kappa \) is the union of \( \kappa \)-many sets of club-measure 0.
Definition: If \( S_i \subseteq \kappa \) for \( i < \kappa \), the diagonal intersection of these sets consists of all \( \beta < \kappa \) such that \( \beta \in S_\alpha \) for all \( \alpha < \beta \).
This definition looks strange and artificial at first. That's OK; it ends up being really, really useful. Remember how I said I wasn't going to talk about boolean algebras? Well, this is me not talking, but just mentioning that this diagonal intersection idea ends up enabling us to compute sups and infs in the boolean algebra where we're taking measurements of sets. I've said too much already.
One thing to observe is that, while order is irrelevant for ordinary intersections, that is no longer true for diagonal intersections. (However: it is possible to prove that any reordering of the \(S_i\) ends up changing the diagonal intersection by only a club-measure 0 set.)
Lemma 5: The diagonal intersection \(D\) of any family \( \langle C_i \colon i < \kappa \) of clubs is once again a club.
Proof: Define a \(\kappa\)-sequence by recursion: \( x_0 = \omega \), and \(x_{j+1} \) is some element of \( \bigcap_{i \leq j} C_i \) which is greater than \(x_j\). For limit ordinals \(j\), define \( x_j \) to be the limit of the \( x_i \) for \(i < j\).
By Corollary 4, this sequence has a club of fixed points. Let \(\beta = x_\beta \) be one of them. Then since \( x_\beta \) belongs to all \(C_i\) for \(i < \beta\), \(\beta = x_\beta \) belongs to \(D\). Hence \(D\) has club-measure 1. I'll leave the proof that \(D\) is closed to you. Q.E.D.
Proof of Fodor's Lemma: Let \(S \subseteq \kappa \) have positive club-measure, and let \(f: S \rightarrow \kappa \) satisfy \( f(\alpha) < \alpha \) for all \( \alpha \).
Suppose for the sake of contradiction that \(f^{-1}(\alpha) \) has club-measure 0 for all \( \alpha \). Choose clubs \( C_\alpha \) disjoint from the \(f^{-1}(\alpha) \), and let \(D\) be their diagonal intersection. Lemma 5 shows that \(D\) is a club. Since \(S\) has positive measure and \(D\) has measure 1, \(S \cap D\) has positive measure.
Since \(D\) is unbounded, we can choose \( \beta > 0 \) in \(D\). By the definition of "diagonal intersection", \(\beta\) belongs to each \( C_\alpha \) for \( \alpha < \beta \). Hence \( \beta \) does not belong to any \( f^{-1}(\alpha)\) for \( \alpha < \beta \). But this is absurd, since \( \beta \) definitely belongs to \( f^{-1}(f(\beta)) \)! Q.E.D.
Final thoughts: In one sense, "almost all" ordinals are successors. However, observe that the set of limit ordinals less than \( \kappa \) is club, so using the club filter as a notion of "almost everything", "almost all" ordinals are limit! This actually corresponds much better to the usual heuristics that a set theorist's brain runs on -- very little of substance happens at successor ordinals, or successor cardinals, when it comes to independence proofs. (I'm exaggerating somewhat, of course.)
[1] The usual nomenclature used by set-theorists is that a set of club-measure 0 is nonstationary, while a set of positive club-measure is called stationary. All I can say to that is "ugh".
How do you make money in casinos using software to make money?
ReplyDeleteHow do you make 온카지노 money in casinos using software to หาเงินออนไลน์ make money? 샌즈카지노 I use software for betting at a casino. I use software for betting at a casino.