Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This is a reference question. Does anyone know any book or paper that has the proof that every weakly compact cardinal is Mahlo, using only combinatorics?

I know the definition of weak compactness has a lot of equivalent forms. In this particular case I am referring to a proof that is based only on the combinatorial definition: $$\kappa \text{ is weakly compact iff }\kappa\to (\kappa)^2_2,$$ i.e. for every partition of the 2-element subsets of $\kappa$ into two sets, there is a homogeneous set of size $\kappa$.

share|cite|improve this question
Kanamori, The higher infinite, Corollary 4.7. The result dates back to William Hanf. Incompactness in languages with infinitely long expressions, Fundamenta Mathematicae 53, (1964), 309–324. –  Andrés Caicedo Jun 27 '13 at 17:37
Andres, your Monk reference deduces Mahloness from the tree property, not the partition property. –  Joel David Hamkins Jun 27 '13 at 19:14
My reference also uses the tree property. –  Joseph Van Name Jun 27 '13 at 19:20
I really like this question, and I don't think it is answered yet by any of the links in the comments (or by my answer), since these all seem to take a route through the tree property or similar characterization. To answer the question, what is wanted is a direct argument from the partition property to Mahloness. I am imagining that one takes a club $C\subset\kappa$ containing no regular cardinals and then defines a simple coloring that can have no homogeneous set. Can anyone find such a coloring? –  Joel David Hamkins Jun 27 '13 at 19:37
@St.D. Since we hope that you'll revisit the site, it may help if in the future you add this sort of information. The more background you provide, the better we may be able to help. Welcome! ("The combinatorial proofs I've seen interpolate through the tree property. I am interested in a direct proof that avoids this or detours through logic." Words to that effect. Also, if you have consulted some references beforehand, it would be helpful if you mention them. "I've looked at ... and ..., but none of their proofs is direct.") –  Andrés Caicedo Jun 27 '13 at 20:06

2 Answers 2

This may help:

Hajnal, Kanamori, and Shelah analyzed regressive partition relations for infinite cardinals in their paper

Regressive partition relations for infinite cardinals. Trans. Amer. Math. Soc. 299 (1987), no. 1, 145–154.

They characterize Mahlo cardinals (even n+1-Mahlo cardinals for each $n<\omega$) in terms of these regressive partition relations:

For example, Theorem 3.4 tells us that $\kappa$ is Mahlo if and only if

For any closed unbounded $C\subseteq\kappa$ and regressive coloring $f$ of $[C]^4$, there is a min-homogeneous set of size $\omega$.

There are some comments in the paper about how weakly compact cardinals satisfy these regressive partition relations, but it's not clear to me (yet) if there's a direct proof or if the proofs need to go through the tree property. I feel like Asaf --- I need to look at it after I get some other work done!

Edit: One can prove directly that if $\kappa\rightarrow (\kappa)^5_2$ then $\kappa$ satisfies the regressive partition relation mentioned above that is equivalent to being Mahlo.

This is still unsatisfying, but what I'm wondering is if this can be put together with the result from the paper to get something like: If $\kappa$ is not Mahlo, then there is a 2-coloring of the 5-tuples from $\kappa$ with no homogeneous set of size $\kappa$.

Another edit based on another strategy:

If $\kappa>\omega$ is not $\omega$-Mahlo, then $\kappa\nrightarrow(\kappa)^2_2$ by virtue of results on negative square-brackets partition relations: If $\kappa$ has a non-reflecting stationary subset this follows from Todorcevic's result that $\kappa\nrightarrow[\kappa]^2_\kappa$ for such $\kappa$. Otherwise, $\kappa$ must be weakly inaccessible with a stationary subset that does not reflect in an inaccessible cardinal, and by results in Shelah's Cardinal Arithmetic, we have $\kappa\nrightarrow[\kappa]^2_\theta$ for every $\theta<\kappa$.

In either case, we certainly have $\kappa\nrightarrow[\kappa]^2_2$, which is equivalent to $\kappa\nrightarrow(\kappa)^2_2$, so $\kappa$ cannot be weakly compact.

So the explicit "bad coloring" of pairs is there to see. It's just really really complicated.

Final Edit

Suppose $\kappa$ is weakly inaccessible and not Mahlo. Let $\langle C_\delta:\delta<\kappa\rangle$ be a $C$-sequence in the sense of Todorcevic, so $C_\delta$ is club in $\delta$ of order-type ${\rm cf}(\delta)$. Let $c(\alpha,\beta)$ be the length of the minimal walk from $\beta$ down to $\alpha$ (so $c:[\kappa]^2\rightarrow\omega$). The fact that $\kappa$ isn't Mahlo implies that the $C$-sequence is non-trivial in the sense of Todorcevic, and his work shows that for any $H\subseteq\kappa$ of size $\kappa$ the range of $c$ restricted to the pairs from $H$ is infinite. In particular, $\kappa\nrightarrow(\kappa)^2_{\omega}$ and so $\kappa$ is not weakly compact.

Still not as simple as we'd like, but I don't see how to do better! This is why the tree property is a good thing...

share|cite|improve this answer

Here is a way to get the tree property directly from the partition property, and this gets you to Mahloness from the references in the links provided in the comments.

Assume that $\kappa$ is an uncountable cardinal and that the partition property $\kappa\to(\kappa)^2_2$ holds.

First, show that $\kappa$ is regular. If not, there is a short unbounded sequence $\kappa_0\lt\kappa_1\lt\cdots\kappa_\xi<\cdots$ for $\xi\lt\text{cof}(\kappa)$, which is unbounded in $\kappa$. Define a coloring $f(\alpha,\beta)$ is $1$, if they are in the same interval determined by these $\kappa_\xi$, and $0$ otherwise. Since each interval has size less than $\kappa$, there cannot be a size $\kappa$ homogeneous set with value $1$; and since there are fewer than $\kappa$ many intervals, there cannot be a size $\kappa$ homogeneous set with value $0$. So $\kappa$ must be regular.

Next, show $\kappa$ is a strong limit and hence inaccessible. If $2^\beta\geq\kappa$ for some $\beta\lt\kappa$, then let $\langle a_\alpha\mid\alpha\lt\kappa\rangle$ be a $\kappa$-sequence of distinct subsets of $\beta$. Let $F(\alpha,\beta) = 0$ if $a_\alpha$ precedes $a_\beta$ in the lexical ordering of $2^\beta$, and otherwise 1. It is not difficult to prove that there is no monotone sequence of length $\beta^+$ in the lexical order on $2^\beta$. Consequently, there can be no monochromatic set for $F$ of size $\kappa$, and so $\kappa$ is inaccessible.

Finally, show the tree property. Suppose that $T$ is a $\kappa$-tree. We may assume that the underlying set of $T$ is exactly $\kappa$. For any two nodes $\alpha$ and $\beta$ in $T$, let us say that $\beta$ is to the right of $\alpha$ in $T$, if $\alpha\perp_T\beta$ and $\alpha'\lt\beta'$, where $\alpha'\leq_T\alpha$ and $\beta'\leq_T\beta$ are least in $T$ such that $\alpha'\perp_T\beta'$. Define $F(\alpha,\beta)=0$ if $\beta$ is above or to the right of $\alpha$, and otherwise $1$. Suppose that $H\subset\kappa$ is a monochromatic set of size $\kappa$. Suppose first that the monochromatic value is $0$. Thus, whenever $\alpha\lt\beta$ in $H$, then $\beta$ is above or to the right of $\alpha$ in $T$. By applying the partition property once more, we may further assume that only one of these answers arises. If any $\alpha\lt\beta$ in $H$ has $\alpha\lt_T\beta$, then the elements of $H$ are linearly ordered, and $T$ has a $\kappa$-branch, as desired. Otherwise, we assume that whenever $\alpha\lt\beta$ in $H$, then $\beta$ is to the right of $\alpha$ in $T$. We may therefore follow the ``right-most'' path through (the $T$-predecessors of elements of) $H$. Specifically, using the fact that the levels of $T$ have size less than $\kappa$ and $\kappa$ is regular, there is on each level $\xi$ a right-most node $\zeta$ that occurs as a $T$-predecessor of all sufficiently large elements of $H$. The set of such nodes is clearly linearly ordered, and therefore forms a $\kappa$-branch through $T$. The final case, when the monochromatic value of $F$ on $H$ is $1$, is similar, except that we follow the left-most branch through $H$ to provide a $\kappa$-branch through $T$. So we've got the tree property as desired.

(I'm sorry I don't have a direct argument from the partition property to Mahloness, but I suspect there may be one if one could find a clever coloring.)

share|cite|improve this answer
Here is a modified idea to my previous suggestion: For $\alpha<\beta$ let $c(\alpha,\beta)=0$ if and only if $\operatorname{otp}(\beta\cap C)>\alpha$ and $|\{\lambda<\beta\mid\operatorname{cf}(\lambda)=\lambda\}|>|\alpha|$. I feel that this should somehow work out. If you (or anyone else) want to check out the details, I'll be happy to see. Otherwise, I'll try to squeeze this into tomorrow's breaks from grading papers (talk about a backlog!) –  Asaf Karagila Jun 28 '13 at 1:22
Asaf, I think it is easy to get homogeneous sets for that coloring---use the fixed points of the enumeration of $C$ that are also $\aleph$-fixed points. –  Joel David Hamkins Jun 28 '13 at 1:25
Here's a possible repair. First prove that $\kappa$ is inaccessible. Now note that if $A$ is $c$-homogeneous then it must have $0$ on its values; and that its closure $\overline{A}$ is also $c$-homogeneous. Now repeat this argument on the collapse of $\overline{A}$. It seems to me that repeating this "enough" time (which is still $<\kappa$) should end up with some regular cardinal appearing in $C$. –  Asaf Karagila Jun 28 '13 at 1:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.