Let \kappa be a cardinal. The Milner-Rado paradox states:
Every ordinal \beta<\kappa^+ can be written as \bigcup_{n<\omega} X_n, where X_n is of order-type at most \kappa^n.
It's surprising because it goes against our intuition of the pigeonhole principle: the ordinals \kappa^n don't go very far up to \kappa^+.
There are some nice short proofs on mathstackexchange. But the one I find easiest to remember uses the method of walks on ordinals. For each \alpha<\kappa^+, fix an unbounded set C_\alpha\subseteq \alpha of order-type at most \kappa (and for successor ordinals \alpha this just means that the predecessor must be in C_\alpha). Now suppose \alpha\le\beta. The walk from \beta to \alpha is a finite sequence decreasing of ordinals \alpha_0>\alpha_1>\cdots>\alpha_n so that \alpha_0=\beta, \alpha_{i+1}=\min(C_{\alpha_i}\setminus \alpha), and the walk ends at \alpha_n=\alpha. In words, we start from \beta and follow C_\beta down as close to \alpha we can get without overshooting it, then jump to the set indexed by that ordinal and repeat the process. We must eventually get to \alpha by the well-ordering principle, and call n the length of the walk.
Now suppose \beta<\kappa^+. Let X_n be the set of \alpha so that the walk from \beta to \alpha has length n. A moment's thought shows that X_n has order-type at most \kappa^n. So we have proved the Milner-Rado paradox!
Games, Sets, Math!
Thursday, February 7, 2019
Tuesday, May 8, 2018
History at the BGU awards ceremony
At the BGU department awards ceremony, a certain name appeared with spooky regularity, like subtle clues in a novel.
![]() |
Profs. Miriam Cohen and Daniel Sternheimer at the ceremony in 2016. |
This figure was mentioned in various connections by mathematicians working in different countries---Israel, France, Japan, and Belgium---and in different areas. He was a friend, a colleague, and an advisor. And the truth turns out to be even more interesting than the imagination. A "sabra bull in a china shop", Moshe Flato was also an Air Force lieutenant who worked on Israel's nuclear program, an outstanding pianist trained by Daniel Barenboim's mother, and a first-rate mathematician and physicist.
Sunday, December 3, 2017
Balogh's small Dowker space, part 2
We are continuing the construction of Balogh's Dowker space of size continuum. From the paper, he says:
Quite a lot to take in! But let's break down how it works, given that we know we want to construct a system of filters satisfying (*) and (**) from last time.
First (**): For any function f:X\rightarrow \omega and any assignment \alpha\mapsto A_\alpha\in \mathcal{F}_\alpha, there are \alpha\neq \beta so that f(\alpha)=f(\beta) and \beta\in A_\alpha.
This is roughly what is expressed by Lemma 1.2. But we don't know how to build the filters yet.
We want to build them to satisfy (*): For every A\subseteq \mathfrak{c} there exists B\subseteq \mathfrak{c} such that B\in \mathcal{F}_\alpha \textrm{ if }\alpha\in A and \mathfrak{c}\setminus B\in \mathcal{F}_\alpha \textrm{ if }\alpha\not\in A.
Think of the sequence \langle c_\xi:\xi<\lambda \rangle as enumerating the characteristic functions of all possible A. For each A, we will find a set B as in (*); its characteristic function is d_\xi.
We will use the d_\xi's to generate our filters \mathcal{F}_\alpha. So for each \xi, \{\beta:d_\xi(\beta)=1\}\in \mathcal{F}_\alpha if c_\xi(\alpha)=1 and \{\beta:d_\xi(\beta)=0\}\in \mathcal{F}_\alpha if c_\xi(\alpha)=0.
What else has to be in the filter? We want to be able to take finite intersections of the sets given by d_\xi or complement (depending on which side makes it into the filter). This is expressed by g. Also, the filter will contain all cofinite subsets of \mathfrak{c}, a necessary condition for neighborhood filters in a space where points are closed. This is expressed by h.
So Lemma 1.2 succintly expresses (**) for filters satisfying (*)!
If we didn't care about the part involving the d_\xi's the rest is very easy to arrange. By a standard argument, there is a closed unbounded set of \beta<\mathfrak{c} closed under the function h; that is, for every \alpha<\beta, h(\alpha)\subseteq \beta. There is also a closed unbounded set of \beta so that for every n with f^{-1}[n] unbounded, f^{-1}[n]\cap \beta is unbounded in \beta. We will do similar, but more sophisticated arguments using the method of elementary submodels.
Let \theta be a large enough regular cardinal ((2^{2^{\mathfrak{c}}})^+ suffices). One of the basic ideas of the elementary submodel method is that if N\prec H(\theta), N countable, and \beta<\mathfrak{c} is greater than \sup(N\cap \mathfrak{c}) (an ordinal of countable cofinality), then formulas true of \beta reflect to unboundedly many \alpha in N\cap\mathfrak{c}. This is another way of stating what we did with clubs in the last paragraph.
But this idea is a bit more powerful. Suppose that we have \beta and N as above. Then there are unboundedly many \alpha\in N\cap\mathfrak{c} which satisfy the desired properties for f and h. Even more crucially, we can reflect some properties of g(\beta), d_\xi(\beta), and c_\xi(\beta) down to these \alpha.
But we can't reflect all of those properties down, since there are \lambda many \xi to consider and not all of them will be in N, and also g(\beta) is some subset of \lambda that may not be in N. But we will reflect enough of this information down, given by what happens inside some smaller countable elementary submodel M\in N.
So we know what happens inside this M. But there is a part outside of M as well. This, we will handle by knowing that there are many reflections---so many that we will be able to guess in advance what happens on at least one of them.
That's the basic idea, but we need to make sure the construction can be carried out in \mathfrak{c} many steps, while we are constructing \lambda-many of these d_\xi. The construction outlined above depends in part on the choice of submodels, but not on the full information of M and N---we shall see that there are only \mathfrak{c} many choices for the crucial information here, and the construction is in some sense canonical. That is part of the magic of this technique.
Suppose now that \xi<\lambda. We will define d_\xi. For each \beta<\mathfrak{c}, there are three cases.
Now pick \beta so that \langle A_\beta,B_\beta,u_\beta\rangle=\langle A,B,u\rangle. Say that \gamma reflects \beta if
Now define v:H\rightarrow [\lambda\setminus M]^{<\omega} by v(\gamma)=g(\gamma)\setminus r. So v\in N and there is \alpha\in \mathrm{dom}(u)\cap\mathrm{dom}(v) with u(\alpha)=\{c_\xi\upharpoonright A:\xi\in v(\alpha)\}. This is the \alpha we want.
Let's check: since \alpha reflects \beta, f(\alpha)=f(\beta). Since \alpha\in N, h(\alpha)\subseteq N. But \beta>\sup(A_\beta), so \beta\not\in h(\alpha). Finally, if \xi\in g(\alpha), there are two cases depending on if \xi is in the root of the \Delta-system or not. In the first case, \xi\in r, and then we defined d_\xi(\beta)=c_\xi(\beta)=c_\xi(\alpha). In the second, c_\xi\upharpoonright A\in u_\beta(\alpha), so we directly defined d_\xi(\beta)=c_\xi(\alpha).
(These are notes from a seminar given at Bar-Ilan University on December 4, 2017.)
"The heart of the proof of Theorem 1.1 is the following combinatorial lemma."Lemma 1.2 [Balogh] Let \lambda=2^{\mathfrak{c}}, and let \langle c_\xi:\xi<\lambda\rangle be a one-to-one enumeration of {}^\mathfrak{c}2. Then there is a sequence \langle d_\xi:\xi<\lambda\rangle of functions d_\xi:\mathfrak{c}\rightarrow 2 in such a way that for every g:\mathfrak{c}\rightarrow [\lambda]^{<\omega}, f:\mathfrak{c}\rightarrow \omega and h:\mathfrak{c}\rightarrow [\mathfrak{c}]^{<\omega}, there are \alpha<\beta in \mathfrak{c} such that f(\alpha)=f(\beta), \beta\not\in h(\alpha) and for every \xi\in g(\alpha), c_\xi(\alpha)=d_\xi(\beta).
1 Explanation
Quite a lot to take in! But let's break down how it works, given that we know we want to construct a system of filters satisfying (*) and (**) from last time.
First (**): For any function f:X\rightarrow \omega and any assignment \alpha\mapsto A_\alpha\in \mathcal{F}_\alpha, there are \alpha\neq \beta so that f(\alpha)=f(\beta) and \beta\in A_\alpha.
This is roughly what is expressed by Lemma 1.2. But we don't know how to build the filters yet.
We want to build them to satisfy (*): For every A\subseteq \mathfrak{c} there exists B\subseteq \mathfrak{c} such that B\in \mathcal{F}_\alpha \textrm{ if }\alpha\in A and \mathfrak{c}\setminus B\in \mathcal{F}_\alpha \textrm{ if }\alpha\not\in A.
Think of the sequence \langle c_\xi:\xi<\lambda \rangle as enumerating the characteristic functions of all possible A. For each A, we will find a set B as in (*); its characteristic function is d_\xi.
We will use the d_\xi's to generate our filters \mathcal{F}_\alpha. So for each \xi, \{\beta:d_\xi(\beta)=1\}\in \mathcal{F}_\alpha if c_\xi(\alpha)=1 and \{\beta:d_\xi(\beta)=0\}\in \mathcal{F}_\alpha if c_\xi(\alpha)=0.
What else has to be in the filter? We want to be able to take finite intersections of the sets given by d_\xi or complement (depending on which side makes it into the filter). This is expressed by g. Also, the filter will contain all cofinite subsets of \mathfrak{c}, a necessary condition for neighborhood filters in a space where points are closed. This is expressed by h.
So Lemma 1.2 succintly expresses (**) for filters satisfying (*)!
2 Proof of Lemma 1.2
Basic motivations
This section can be skipped if you are familiar with the use of elementary submodel arguments.If we didn't care about the part involving the d_\xi's the rest is very easy to arrange. By a standard argument, there is a closed unbounded set of \beta<\mathfrak{c} closed under the function h; that is, for every \alpha<\beta, h(\alpha)\subseteq \beta. There is also a closed unbounded set of \beta so that for every n with f^{-1}[n] unbounded, f^{-1}[n]\cap \beta is unbounded in \beta. We will do similar, but more sophisticated arguments using the method of elementary submodels.
Let \theta be a large enough regular cardinal ((2^{2^{\mathfrak{c}}})^+ suffices). One of the basic ideas of the elementary submodel method is that if N\prec H(\theta), N countable, and \beta<\mathfrak{c} is greater than \sup(N\cap \mathfrak{c}) (an ordinal of countable cofinality), then formulas true of \beta reflect to unboundedly many \alpha in N\cap\mathfrak{c}. This is another way of stating what we did with clubs in the last paragraph.
But this idea is a bit more powerful. Suppose that we have \beta and N as above. Then there are unboundedly many \alpha\in N\cap\mathfrak{c} which satisfy the desired properties for f and h. Even more crucially, we can reflect some properties of g(\beta), d_\xi(\beta), and c_\xi(\beta) down to these \alpha.
But we can't reflect all of those properties down, since there are \lambda many \xi to consider and not all of them will be in N, and also g(\beta) is some subset of \lambda that may not be in N. But we will reflect enough of this information down, given by what happens inside some smaller countable elementary submodel M\in N.
So we know what happens inside this M. But there is a part outside of M as well. This, we will handle by knowing that there are many reflections---so many that we will be able to guess in advance what happens on at least one of them.
That's the basic idea, but we need to make sure the construction can be carried out in \mathfrak{c} many steps, while we are constructing \lambda-many of these d_\xi. The construction outlined above depends in part on the choice of submodels, but not on the full information of M and N---we shall see that there are only \mathfrak{c} many choices for the crucial information here, and the construction is in some sense canonical. That is part of the magic of this technique.
Definition of the d's
We have the motivation in mind now. We will enumerate control triples \langle (A_\beta,B_\beta,u_\beta):\beta<\mathfrak{c}\rangle, which are ordered triples (A,B,u) that satisfy the following properties:
- A\in [\mathfrak{c}]^\omega, B\in [{}^A2]^{\le \omega},
- u is a function with \mathrm{dom}(u)\in[A]^\omega,
- for every \alpha\in\mathrm{dom}(u), u(\alpha)\in [{}^A2\setminus B]^{<\omega},
- (disjoint images) if \alpha\neq \beta in \mathrm{dom}(u), then u(\alpha)\cap u(\beta)=\emptyset.
Furthermore, let us ensure in the enumeration that \beta>\sup A_\beta.
From the sketch above, A corresponds to N\cap \mathfrak{c}, B corresponds to the information we need from M, and u captures the information that's not in M. But there are only \mathfrak{c} such triples!
Suppose now that \xi<\lambda. We will define d_\xi. For each \beta<\mathfrak{c}, there are three cases.
- If c_\xi\upharpoonright A_\beta\in B_\beta, then let d_\xi(\beta)=c_\xi(\beta).
- If c_\xi\upharpoonright A_\beta\in u_\beta(\alpha) for some \alpha\in \mathrm{dom}(u_\beta), then let d_\xi(\beta)=c_\xi(\alpha).
- Otherwise, set d_\xi(\beta)=0.
Intuitively, Case 1 corresponds to the case when \xi is in the part which is controlled by M, and Case 2 to when u captures the information outside of M of a reflected \alpha. Note that in Case 2, c_\xi\upharpoonright A_\beta\not\in B_\beta, and \alpha is chosen uniquely by the restrictions on u in the definition of a control triple.
Final proof
We will show that the sequence of d_\xi we have defined above works. Let f,g,h be functions as in the statement of Lemma 1.2. We will produce the required \alpha,\beta.
Let M\in N be elementary submodels of H(\theta) containing \langle c_\xi:\xi<\lambda\rangle, \langle d_\xi:\xi<\lambda\rangle, f,g,h. Let A=\mathfrak{c}\cap N and B=\{c_\xi\upharpoonright A:\xi\in \lambda\cap M\}.
We will construct u:A\rightarrow[{}^A2\setminus B]^{<\omega} satisfying the requirements of the control triple such that whenever v\in N is an infinite partial function \mathfrak{c}\rightarrow [\lambda\setminus M]^{<\omega} and \alpha\neq \alpha' in \mathrm{dom}(v) implies that v(\alpha)\cap v(\alpha')=\emptyset, then there is \alpha\in\mathrm{dom}(u)\cap\mathrm{dom}(v) such that
u(\alpha)=\{c_\xi\upharpoonright A:\xi\in v(\alpha)\}.
Basically, u agrees with v on at least one point of its domain for any v of the right shape. And here, agreement actually means u(\alpha)=\{c_\xi\upharpoonright A:\xi\in v(\alpha)\}, since u cannot actually take the ordinals less than \lambda in its range, as we were careful to only use \mathfrak{c}-many control triples.
This u is easy to construct. Just enumerate the countably many such v\in N and construct u^*:\mathfrak{c}\rightarrow [\lambda\setminus M]^{<\omega} so that the disjoint images property holds. Then get u by taking restrictions of the c_\xi to A. The only thing that requires some argument is to make sure that by taking the restrictions, we do not accidentally break the disjoint images property for u. But we will not, since the relevant \xi are in N and if \xi\neq\xi' then this is witnessed by something in A=N\cap\mathfrak{c}.
Now pick \beta so that \langle A_\beta,B_\beta,u_\beta\rangle=\langle A,B,u\rangle. Say that \gamma reflects \beta if
- f(\gamma)=f(\beta),
- g(\gamma)\cap M=g(\beta)\cap M,
- for every \xi\in g(\gamma)\cap M, c_\xi(\gamma)=c_\xi(\beta).
Find a maximal D which consists of \gamma reflecting \beta so that \langle g(\gamma):\gamma\in D\rangle forms a \Delta-system with root r:=g(\beta)\cap M. Choose D in M, possible since the definition of reflection only used parameters in M. This D is uncountable since otherwise it would be a subset of M, but \beta could be then be added to it, contradicting maximality. So there is also an infinite set H of \gamma\in D\cap N so that g(\gamma)\setminus r is disjoint from the countable set \lambda\cap M.
Now define v:H\rightarrow [\lambda\setminus M]^{<\omega} by v(\gamma)=g(\gamma)\setminus r. So v\in N and there is \alpha\in \mathrm{dom}(u)\cap\mathrm{dom}(v) with u(\alpha)=\{c_\xi\upharpoonright A:\xi\in v(\alpha)\}. This is the \alpha we want.
Let's check: since \alpha reflects \beta, f(\alpha)=f(\beta). Since \alpha\in N, h(\alpha)\subseteq N. But \beta>\sup(A_\beta), so \beta\not\in h(\alpha). Finally, if \xi\in g(\alpha), there are two cases depending on if \xi is in the root of the \Delta-system or not. In the first case, \xi\in r, and then we defined d_\xi(\beta)=c_\xi(\beta)=c_\xi(\alpha). In the second, c_\xi\upharpoonright A\in u_\beta(\alpha), so we directly defined d_\xi(\beta)=c_\xi(\alpha).
(These are notes from a seminar given at Bar-Ilan University on December 4, 2017.)
Balogh's small Dowker space, part 1
A Dowker space is a normal space which is not countably paracompact. Here, a (Hausdorff) space X is normal if for every pair of disjoint closed sets H,K, there exist disjoint open sets U,V with H\subseteq U and K\subseteq V. Normality is, according to M.E. Rudin, the boundary where point-set topology changes from analysis to set theory.
A space X is countably paracompact if for every \subseteq-increasing sequence of open sets \langle G_n:n<\omega\rangle with \bigcup_n G_n=X, there exist closed sets H_n\subseteq G_n so that \bigcup_n H_n=X. An interesting history of the concept of paracompactness can be found in the Encyclopedia of General Topology.
It turns out that Dowker spaces are the spaces whose normality is not preserved by product with compact metric spaces. See Dan Ma's topology blog for more information about Dowker spaces and all of the topological concepts considered here.
Dowker spaces are considered to be quite rare, and the first ZFC example was due to M.E. Rudin in 1971. In 1996, Zoltan Balogh published an example of a Dowker space of size continuum in ZFC. The problem of whether there exists a Dowker space of size \aleph_1 is still open.
Balogh's example was based off an earlier example of Watson which used strongly compact cardinals, together with an earlier argument of Rudin using the submodel method. He was able to use the techniques applied in this Dowker space construction towards other Dowker spaces and the solutions of the second and third Morita conjectures. This post gives a carefully motivated presentation of Balogh's proof.
1 Basic construction
We start the construction of X with an increasing sequence of open sets \langle G_n:n<\omega\rangle witnessing the failure of countable paracompactness. So the underlying set of X is \omega\times\mathfrak{c}, and we define G_n=(n+1)\times\mathfrak{c}. We will also consider the levels of the space, L_n=\{n\}\times\mathfrak{c}.
The levels L_n will be relatively discrete, which helps in the normality proof later. The set of open neighborhoods of a fixed point (n,\alpha) forms a filter. If n=0, a neighborhood base for (n,\alpha) is just the singleton. If n>0, the filter concentrates on \{(n,\alpha)\}\cup G_{n-1}. Following Watson's example, we will define a filter \mathcal{F}_{(n,\alpha)} on G_{n-1}. Then, a set U is open if and only if for every (n,\alpha)\in U, there is some A\in \mathcal{F}_{(n,\alpha)} so that A\subseteq U.
Motivated by the normality argument in Watson's paper (which he credits to Rudin), we will end up working on consecutive pairs of levels. So the filter \mathcal{F}_{(n,\alpha)} will be expressed as a filter \mathcal{F}_\alpha on \mathfrak{c} which does not depend on n. The filter will contain all cofinite subsets of \mathfrak{c}, which is necessary in a space where points are closed.
Let us find the properties of this filter system which we need to make X Dowker.
2 Normality
Let us try to get normality. The first level G_0 is relatively normal, since it has the discrete topology. If we consider the first two levels, however, we need to separate arbitrary disjoint sets A_0,A_1\subseteq L_1 by disjoint open sets. We may as well assume that A_1 is the complement of A_0 in its level. In total, we are looking for:
(*) \textrm{For every }A\subseteq \mathfrak{c}, \textrm{ there exists } B \subseteq \mathfrak{c} \textrm{ such that }
B\in \mathcal{F}_\alpha \textrm{ if }\alpha\in A,
\mathfrak{c}\setminus B\in \mathcal{F}_\alpha \textrm{ if }\alpha\not\in A.
For the next few claims, assume (*). We will show that X defined as above is normal.
First, we show this for subsets of single levels.
Claim 1. Suppose that m\le n and H\subseteq L_n and K\subseteq L_m have disjoint closures. Then there are disjoint open sets U,V separating them (H\subseteq U and K\subseteq V). Moreover, we can arrange so that L_n\setminus H\subseteq K.
Proof of Claim 1: Using (*) repeatedly, let U',V' be disjoint open sets so that L_m\setminus K\subseteq U' and K\cap L_m\subseteq V'. Then take U=U'\cup(X\setminus (G_m\cup \bar{K})) and V=V'. U is open since U' and X\setminus \bar{K} are open sets which are spliced together at a single level m, and U'\cap L_m=X\setminus K=(X\setminus \bar{K})\cap L_m. Clearly K\subseteq V, and H\subseteq U since H\cap \bar{K}=\emptyset. \square
Now we can separate a subset of a single level from an arbitrary closed set. Suppose that H,K are disjoint closed subsets of X. By taking only finite unions and intersections from the sets produced from Claim 1, we can show that there are disjoint open U'_n,V'_n and disjoint open U''_n,V''_n, all subsets of G_n, so that
- H\cap L_n\subseteq U'_n, K\cap G_n\subseteq V'_n, and L_n\setminus H\subseteq V'_n.
- H\cap G_n\subseteq U''_n, K\cap L_n\subseteq V''_n, and L_n\setminus K\subseteq U''_n.
Finally, take U_n:=\bigcup_n (U'_n\setminus \bigcup_{k\le n}\mathrm{cl}(V''_k)) and V_n:=\bigcup_n (V''_n\setminus \bigcup_{k\le n}\mathrm{cl}(U'_k)).
These sets are clearly open, and disjoint by the subtraction done at each step.
For each n, H\cap L_n\subseteq U'_n\setminus \bigcup_{k\le n}\mathrm{cl}(V''_k) and K\cap L_n\subseteq V''_n\setminus \bigcup_{k\le n}\mathrm{cl}(U'_k). This is because V^*_n:=V'_n\cup(X\setminus (G_n\cup H)) and U^*_n:=U''_n\cup(X\setminus (G_n\cup K)) are open, by the splicing argument. Furthermore, we have K\subseteq V^*_n and H\subseteq U^*_n and V^*_n\cap U'_n=U^*_n\cap V''_n =\emptyset.
So we have reduced normality to the property (*) of the filter system.
Remark: In fact, the proof shows that X built from a system satisfying (*) is hereditarily normal.
3 Non countable paracompactness
To get non-countable paracompactness, we need to show that every sequence of closed sets \langle H_n:n<\omega\rangle with H_n\subseteq G_n cannot have union X. The levels of each F_n are small in the following sense. H_n\cap L_n must be measure 0 according to \mathcal{F}_\alpha (that is, the complement is in the filter) for each \alpha\in\mathfrak{c}. Otherwise, if H_n\cap L_n is positive measure according to \mathcal{F}_\alpha, then (n+1,\alpha) is in its closure, contradicting that H_n\subseteq G_n closed. For each n, let us define the ideal \mathcal{I}^1 to be the ideal of sets which are measure 0 according to \mathcal{F}_\alpha for every \alpha\in\mathfrak{c}.
Now if n>0, H_n\cap L_{n-1} is measure 0 according to \mathcal{F}_\alpha for all \alpha except for a set in \mathcal{I}^1. Let \mathcal{I}^2 be the ideal of sets which have this property, and recursively define \mathcal{I}^m for every m<\omega. Let \mathcal{I} be the \sigma-ideal generated by \bigcup_{m<\omega} \mathcal{I}^m. For technical reasons, let \mathcal{I}^0=\{\emptyset\}.
We will be done if we can show that \mathcal{I} is proper, since \{\alpha:(0,\alpha)\in H_n\cap L_0\}\in\mathcal{I}.
Suppose otherwise. Then there is a partition of \mathfrak{c} into countably many sets, each in \mathcal{I}^m for some m. By partitioning further, we can assume for each class C of the partition, C\in \mathcal{I}_m is witnessed by a set D\in \mathcal{I}_{m-1}, so that C\cap D=\emptyset and \mathfrak{c}\setminus C\in \mathcal{F}_\alpha for all \alpha\not\in D (any set in \mathcal{I}_m has such a D, and if C\cap D is not empty, then it is in \mathcal{I}_{m-1} and we can subtract off this part; repeat the procedure finitely many times to get the further partitioning). Now to each \alpha\in C, we can associate a set A_\alpha=\mathfrak{c}\setminus C\in \mathcal{F}_\alpha.
We want to ensure that there are no such partitions. So we want:
(**) For any function f:X\rightarrow \omega and any assignment \alpha\mapsto A_\alpha\in \mathcal{F}_\alpha, there are \alpha\neq \beta so that f(\alpha)=f(\beta) and \beta\in A_\alpha.
Then, \alpha and \beta will be in the same class C, but we will have \beta\in A_\alpha, contradicting that A_\alpha was supposed to be disjoint from C.
We have reduced non countable paracompactness to (**). Next time we will see how to get (*) and (**).
Note that in this part, \mathfrak{c} here can be replaced by any infinite cardinal \kappa.
We will continue Balogh's proof in Part 2.
Note that in this part, \mathfrak{c} here can be replaced by any infinite cardinal \kappa.
We will continue Balogh's proof in Part 2.
(These are notes from a seminar given at Bar-Ilan University on November 27, 2017.)
Wednesday, November 22, 2017
New material coming
I have been in Israel at Ben-Gurion University for the past year (and plan to stay here for one more year), and I'm working on some new things. Look forward to more posts soon!
Thursday, February 25, 2016
UCI Summer School, part 7: Sacks forcing (Brent Cody)
This lecture will introduce some basic properties of Sacks forcing for uncountable inaccessible cardinals, and examine an Easton support iteration of such forcing.
The Sacks forcing on \omega adds a real of minimal constructibility degree, and crucially satisfies a fusion property. Although this was reviewed in the summer school, I'm going to omit the discussion for this post.
Instead we will start with Sacks forcing on uncountable cardinals, which traces back to Kanamori (1980), where using \diamond_\kappa it was shown that long products and iterations of \mathrm{Sacks}(\kappa) preserve \kappa^+.
Definition: We say p\subseteq 2^{<\kappa} is a perfect \kappa-tree if:
- If s\in p and t\subseteq s then t\in p.
- If \langle s_\alpha:\alpha<\eta\rangle is a sequence of nodes in p, then s=\bigcup_{\alpha<\eta} s_\alpha\in p.
- For every s\in p there is t\supset s with t\frown 0, t\frown 1\in p.
- Let \mathrm{Split}(p)=\{s\in p: s\frown 0, s\frown 1\in p\}. Then for some unique club C(p)\subseteq \kappa, we have \mathrm{Split}(p)=\{s\in p: \mathrm{length}(s)\in C(p)\}.
\mathrm{Sacks}(\kappa) is the poset of perfect \kappa-trees ordered by inclusion. We think of the generic subset of \kappa added by \mathrm{Sacks}(\kappa) as the intersection of the trees in the generic filter.
The only surprising thing in the generalization is (4): splitting happens for every node on certain levels, which form a club in \kappa.
Exercise: \mathrm{Sacks}(\kappa) is <\kappa-closed.
Assume \kappa>\omega is inaccessible. Then \mathrm{Sacks}(\kappa) is \kappa^{++}-c.c. We will really only consider this case.
Definition: \mathrm{Split}_\alpha(p) is the set of all nodes s\in p with \mathrm{length}(s)=\beta_\alpha, where \langle \beta_\alpha:\alpha<\kappa\rangle is an enumeration of C(p), i.e., the level of p at the \alphath member of C(p).
For p,q\in \mathrm{Sacks}(\kappa), write p\le_\beta q iff p\le q and \mathrm{Split}_\alpha(p)=\mathrm{Split}_\alpha(q) for all \alpha<\beta.
A descending sequence \langle p_\alpha:\alpha<\kappa\rangle in \mathrm{Sacks}(\kappa) is a fusion sequence if for all \alpha<\kappa, p_\alpha\le_\alpha p_\alpha.
Lemma (fusion lemma): If \langle p_\alpha:\alpha<\kappa\rangle is a fusion sequence, then p=\bigcap_{\alpha<\kappa} p_\alpha is a lower bound in \mathrm{Sacks}(\kappa).
Proof: exercise. Hint: show that any node p in the intersection is in a cofinal branch of the intersection.
This important lemma affords us a kind of \kappa^+ closure, with the catch that we require more of our decreasing sequence. We can see this in action in the next lemma.
Lemma: \mathrm{Sacks}(\kappa) preserves \kappa^+.
Proof: If \dot{f} is the name of a function \kappa\rightarrow \kappa^+, then we will find q\le p with q\Vdash \mathrm{ran}(\dot{f}) bounded.
Let p_0=p. Given p_\alpha, for each s\in \mathrm{Split}_\alpha(p_\alpha), let \bar{r}^s_\alpha\le (p_\alpha)_s be such that \bar{r}^s \Vdash \dot{f}(\alpha)=\eta^s_\alpha. Here the (p)_s means the subtree of p of nodes compatible with s.
Note \bigcup\{\bar{r}^s_\alpha:s\in \mathrm{Split}_\alpha(p_\alpha)\} might not be a condition by the requirement on splitting levels. Let C=\bigcap \{C(\bar{r}^s_\alpha:s\in \mathrm{Split}_\alpha(p_\alpha)\} and thin each \bar{r}^s_\alpha to some r^s_\alpha\le \bar{r}^s_\alpha with C(r^s_\alpha)=C.
At limits \gamma<\kappa, let p_\gamma=\bigcap_{\alpha<\gamma} p_\alpha by the fusion lemma. This defines a fusion sequence where the limit forces that the range of f is bounded.
Exercise: Suppose {}^\kappa M\subseteq M, for an inner model M. Suppose \mathrm{Sacks}(\kappa)\in M\subseteq V. If G is V-generic for \mathrm{Sacks}(\kappa) then {}^\kappa M[G]\subseteq M[G] in V[G].
Note: This holds for \kappa^+-c.c. forcing, but \mathrm{Sacks}(\kappa) is not \kappa^+-c.c.
Now we will see what happens when we iterate these Sacks forcings with Easton support below, and at, a measurable cardinal \kappa. Think of this like a Sacks forcing version of the Kunen-Paris iteration, where we use the nice fusion property to replace the \gamma^+ closure of the factors there.
Theorem (Friedman-Thompson 2008): Assume GCH holds. Suppose \kappa is measurable and let \mathbb{P} be the length \kappa+1 Easton support iteration with \mathbb{Q}_\gamma=\mathrm{Sacks}(\gamma) (computed in V^{\mathbb{P}_\gamma}) for \gamma\le \kappa inaccessible, and \mathbb{Q}_\gamma is trivial forcing otherwise. Then if G\ast H is V-generic for \mathbb{P}= \mathbb{P}_\kappa\ast \dot{\mathbb{Q}}_\kappa, then every normal ultrapower lifts to V[G\ast H] (and in a particularly interesting way!)
Proof: Let j:V\rightarrow M be a normal ultrapower by U\in V. Then j(\mathbb{P}_\kappa=\mathbb{P}_\kappa\ast \dot{\mathbb{Q}}_\kappa\ast \dot{\mathbb{P}}_{\kappa+1,j(\kappa)}. We get the actual \dot{\mathbb{Q}}_\kappa factor at the \kappa step by using the \kappa closure of the ultrapower.
Using this closure further, and the last exercise, {}^\kappa M[G\ast H]\subseteq M[G\ast H] in V[G\ast H], so M[G\ast H] \vDash \dot{\mathbb{P}}_{\kappa+1,j(\kappa)}\textrm{ is }\le \kappa-\textrm{closed.} So there are \kappa^+ maximal antichains of \mathbb{P}_{\kappa,j(\kappa)} in M[G][H]. We can now build as usual a generic G_{\kappa+1,j(\kappa)}\in V[G\ast H] for \mathbb{P}_{\kappa+1,j(\kappa)} over M[G\ast H]. Lift to j:V[G]\rightarrow M[j(G)].
Now we have to lift j through \mathbb{Q}_\kappa=\mathrm{Sacks}(\kappa). Using the Silver method, j``H has size \kappa^+, but the target model M[j(G)] does not have this much closure.
The crucial point is to just take t:=\bigcap j``H. We claim that t is a "tuning fork": by this we mean that t consists of a single branch up to the level \kappa, at which point it splits into two branch which are cofinal (and that's everything in t).
- The function f:\kappa\rightarrow 2 determined by H is in t, and this is everything in t below \kappa.
- Every condition in j``H splits at \kappa since for each p\in H, p splits at club many levels below \kappa, and therefore j(p) splits at level \kappa. Therefore, f\frown 0,f\frown 1\in t.
- Since H is a filter, t is cofinal in j(\kappa).
- We will argue that t does not split anywhere else. Given a club C\subseteq \kappa, D_C:=\{p\in \mathrm{Sacks}(\kappa): C(p)\subseteq C\} is dense. So there must be p_C\in H so that C(p_C)\subseteq C. Now we have:
Claim: X=\bigcap \{j(C):C\subseteq \kappa \textrm{ club in } V[G]\}=\{\kappa\}.
Proof of Claim: Clearly \kappa\in X. For the other inclusion, suppose \alpha\in X, \alpha>\kappa. Then choose f:\kappa\rightarrow \kappa, f\in V[G] so that j(f)(\kappa)=\alpha. Then let C_f=\{\nu<\kappa: f``\nu\subseteq \nu\} is club, but \alpha\not\in j(C_f) since \alpha is not a closure point of j(f) (\kappa<\alpha maps to \alpha). This proves the claim.
Let t_0, t_1 be the leftmost and rightmost branches through t, respectively. Let K_0=\{p\in j(\mathbb{Q}_\kappa):t_0\subseteq p\}. Clearly j``H\subseteq K_0.
It remains to show that K_0 is M[j(G)]-generic for j(\mathbb{Q}_\kappa). Let D be a dense open subset of j(\mathbb{Q}_\kappa in M[j(G)]. Then there is a sequence \vec{D}=\langle D_\alpha:\alpha<\kappa\rangle \in V[G] such that j(\vec{D})_\kappa=D, where each D_\alpha is a dense open subset of \mathbb{Q}_\kappa.
Claim: Every condition p\in \mathrm{Sacks}(\kappa) can be extended to q_\infty \le p so that for every \alpha<\kappa there is \beta<\kappa so that for any node s\in \mathrm{Split}_\beta(q_\infty), the condition (q_\infty)_s meets D_\alpha.
Proof of Claim: exercise, a fusion argument.
Let q_\infty\in H be as in the claim, using genericity of H. By elementarity, j(q_\infty) has the property that at some splitting level of j(q_\infty), say \beta<j(\kappa), any node s\in \mathrm{Split}_\beta(j(q_\infty)) is such that (j(q_\infty))_s meets D. Now we can just take s to be t_0\upharpoonright \delta_\beta, where \delta_\beta is the \betath splitting level of j(q_\infty).
Therefore K_0 is generic as claimed, and it is in V[G\ast H], so j lifts to
j:V[G\ast H]\rightarrow M[j(G)\ast j(H)].
Friday, February 19, 2016
The rearrangement inequality is everywhere
Recently, I've been talking with John Susice about some elementary Olympiad-style problems. I told him that in high school I was taught that virtually every inequality problem that appeared in this setting follows from the Rearrangement Inequality. This states that if x_1\le \cdots\le x_n and y_1\le \cdots\le y_n are real numbers, then the expression
x_1 y_{\sigma(1)}+\cdots+x_n y_{\sigma(n)}
for \sigma a permutation on [n] is maximized when \sigma is the identity permutation and minimized when \sigma is the reversing permutation. To me, this neatly isolates a useful and general principle that seems kind of obvious in hindsight.
The proof of the n=2 case of the inequality, which is all I'll need below, is just to expand (x_2-x_1)(y_2-y_1)\ge 0. This case also implies the AM-GM inequality (taking x_1=y_1=\sqrt{a} and x_2=y_2=\sqrt{b}).
Now sometime later, John told me an interesting problem about factoring numbers. He had a solution using a trick similar to Euler's product, but for me this was a chance to test my thesis about the rearrangement inequality:
Problem: Prove that every natural number n has at least as many factors congruent to 1 (mod 4) as factors congruent to 3 (mod 4).
Solution: By induction. Clearly this holds for 1 and for primes. Now suppose n is composite, so write n=pq where p,q<n. For any integer k, let r_k denote the number of factors it has which are congruent to 1 (mod 4) and s_k the number of factors congruent to 3 (mod 4).
The product of two 1 (mod 4) numbers is still 1 (mod 4), and the product of two 3 (mod 4) numbers is 3 (mod 4). On the other hand, the product of a 1 (mod 4) and a 3 (mod 4) is a 3 (mod 4), and even factors can never be 1 or 3 (mod 4). This proves that r_n=r_pr_q+s_ps_q, which must be greater than or equal to s_n=r_ps_q+r_qs_p by the rearrangement inequality!
x_1 y_{\sigma(1)}+\cdots+x_n y_{\sigma(n)}
for \sigma a permutation on [n] is maximized when \sigma is the identity permutation and minimized when \sigma is the reversing permutation. To me, this neatly isolates a useful and general principle that seems kind of obvious in hindsight.
The proof of the n=2 case of the inequality, which is all I'll need below, is just to expand (x_2-x_1)(y_2-y_1)\ge 0. This case also implies the AM-GM inequality (taking x_1=y_1=\sqrt{a} and x_2=y_2=\sqrt{b}).
Now sometime later, John told me an interesting problem about factoring numbers. He had a solution using a trick similar to Euler's product, but for me this was a chance to test my thesis about the rearrangement inequality:
Problem: Prove that every natural number n has at least as many factors congruent to 1 (mod 4) as factors congruent to 3 (mod 4).
Solution: By induction. Clearly this holds for 1 and for primes. Now suppose n is composite, so write n=pq where p,q<n. For any integer k, let r_k denote the number of factors it has which are congruent to 1 (mod 4) and s_k the number of factors congruent to 3 (mod 4).
The product of two 1 (mod 4) numbers is still 1 (mod 4), and the product of two 3 (mod 4) numbers is 3 (mod 4). On the other hand, the product of a 1 (mod 4) and a 3 (mod 4) is a 3 (mod 4), and even factors can never be 1 or 3 (mod 4). This proves that r_n=r_pr_q+s_ps_q, which must be greater than or equal to s_n=r_ps_q+r_qs_p by the rearrangement inequality!
Subscribe to:
Posts (Atom)