Suppose we have a function $f_\alpha:\mathbb{N} \to o$ for each $\alpha<c^+$ (successor cardinal of $c=2^{\aleph_{0}}$), where $o$ is some ordinal. Show that there exists a set $S \subseteq c^+$ such that $|S|=c^+ $ and for every $\alpha,\beta \in S$ where $\alpha<\beta$ we have that $f_\alpha(n)\leq f_\beta(n)$ for all $n \in \mathbb{N}$.

I was thinking maybe to color pairs $\alpha,\beta \in o$ in colors depending on the smallest index $n$ for which $f_\alpha(n)\leq f_\beta(n)$ doesn't hold (i.e countable number of colors), and maybe use some coloring theorem? The problem is I can't see an appropriate coloring theorem for the result I want, and also I don't see a contradiction in there being a homogeneous set not of color $-1$ (i.e no such index).

My second approach would be assuming the negation and somehow building an infinite decreasing sequence in $o$, $f_{\alpha_1}(n)>f_{\alpha_2}(n)>f_{\alpha_3}(n)...$ which would contradict well-orderedness, but I can't really see how to do that either.

  • $\begingroup$ Do you have any conditions on $o$? $\endgroup$ – Sungjin Kim Jun 8 '13 at 18:12
  • $\begingroup$ No, $o$ is just there to be able to compare $f_\alpha(n)$ and $f_\beta(n)$. $\endgroup$ – ctlaltdefeat Jun 8 '13 at 18:31
  • $\begingroup$ Just to remind myself: what was the successor cardinal? $\endgroup$ – Sungjin Kim Jun 8 '13 at 18:53
  • $\begingroup$ Well, it's the minimal cardinal (initial ordinal) that is greater than the specified cardinal. $\endgroup$ – ctlaltdefeat Jun 8 '13 at 19:00

I need the following generalization of (a special case of) the Dushnik-Miller theorem: If the set $[c^+]^2$ of $2$-element subsets of $c^+$ is partitioned into countably many pieces $P_n$ ($n\in\omega$), then either there is a set $H\subseteq c^+$ of order-type $c^+$ with $[H]^2$ (the set of $2$-element subsetes of $H$) included in $P_0$, or there is an infinite $H\subseteq c^+$ with $[H]^2$ included in $P_n$ for some $n>0$. Looking for a reference for this, the first I found was Theorem 3.10 of Chapter 2 ("Partition Relations" by András Hajnal and Jean Larson) of the Handbook of Set Theory. This is a theorem of Erdős and Rado, which (by specializing to $\kappa=\aleph_1$ and $\gamma=\omega$) gives more than I need; I expect there are easier proofs of what I actually need.

Given that result, and given functions $f_\alpha$ as in the question, define $P_0$ to consist of those $2$-element sets $\{\alpha<\beta\}$ for which $(\forall n)\,f_\alpha(n)\leq f_\beta(n)$, and define $P_{k+1}$ to consist of those $\{\alpha<\beta\}$ for which $k$ is the smallest integer with $f_\alpha(k)>f_\beta(k)$. These $P_n$'s constitute a partition of $[c^+]^2$, and a homogeneous set of order-type $c^+$ for piece $P_0$ is exactly what the question asks for. So all I need to do is to exclude the possibility of infinite homogeneous sets for any of the other pieces $P_{k+1}$. But such a homogeneous set would begin with an $\omega$-sequence of ordinals $\alpha(0)<\alpha(1)<\dots$ such that, for each $i$, $f_{\alpha(i)}(k)>f_{\alpha(i+1)}(k)$. That is, we'd have an infinite decreasing sequence of ordinals, a contradiction.

| cite | improve this answer | |
  • $\begingroup$ I had the same idea (when I wrote coloring I was meaning partitioning), but must have missed that specific partition theorem because it looks like we did indeed learn it. Thanks! $\endgroup$ – ctlaltdefeat Jun 8 '13 at 21:25
  • 2
    $\begingroup$ @user14111 An alternative to winning the lottery: Find the table of contents of the Handbook, go to the web sites of the authors of individual chapters, and look for downloadable pre-publication versions of the chapters. By the way, the handbook is in three volumes, any one of which already presupposes a very large hand, so I would not advise printing out what you download. $\endgroup$ – Andreas Blass Jun 9 '13 at 22:51

Here’s a proof that doesn’t use a big combinatorial hammer, though I got the idea from a proof of the Erdős-Rado theorem. Let $S=\{\alpha<\mathfrak{c}^+:\operatorname{cf}\alpha=\omega_1\}$. For each $\alpha\in S$ and $n\in\omega$ construct a finite sequence $\langle\beta(\alpha,n,k):k<\ell(\alpha,n)\rangle$ as follows. If $\{\gamma<\alpha:f_\gamma(n)>f_\alpha(n)\}\ne\varnothing$, let $$\beta(\alpha,n,0)=\min\{\gamma<\alpha:f_\gamma(n)>f_\alpha(n)\}\;;\tag{1}$$ otherwise let $\ell(\alpha,n)=0$. Given $\beta(\alpha,n,k)$, let


if such an ordinal exists, and otherwise let $\ell(\alpha,n)=k+1$. Since $\beta(\alpha,n,k)>\beta(\alpha,n,k+1)$ whenever both ordinals are defined, $\ell(\alpha,n)\in\omega$ for each $\alpha\in S$ and $n\in\omega$. For each $\alpha\in S$ let $A_\alpha=\bigcup_{n\in\omega}\{\beta(\alpha,n,k):k<\ell(\alpha,n)\}$, and if $A_\alpha\ne\varnothing$, let $\eta_\alpha=\sup A_\alpha$; $A_\alpha$ is countable, so $\eta_\alpha<\alpha$. The map $\alpha\mapsto\eta_\alpha$ is a pressing-down function on $S_0=\{\alpha\in S:A_\alpha\ne\varnothing\}$.

If $S_0$ is stationary, then there are a stationary $S_1\subseteq S_0$ and an $\eta<\mathfrak{c}^+$ such that $\eta_\alpha=\eta$ for all $\alpha\in S_1$. There are only $\mathfrak{c}$ distinct possibilities for


so there is $S_2\subseteq S_1$ such that $|S_2|=\mathfrak{c}$, and


for all $\alpha_0,\alpha_1\in S_2$. Suppose that there are $\alpha_0,\alpha_1\in S_2$ and $n\in\omega$ such that $\alpha_0<\alpha_1$ and $f_{\alpha_0}(n)>f_{\alpha_1}(n)$. Then for all $k<\ell(\alpha_1,n)$ we have $f_{\beta(\alpha_1,n,k)}(n)>f_{\alpha_0}(n)>f_{\alpha_1}(n)$, and $\beta\big(\alpha_1,n,\ell(\alpha_1,n)\big)$ should have been defined: there was at least one ordinal available, $\alpha_0$, that met the requirements of whichever of $(1)$ and $(2)$ was appropriate. This contradiction shows that if $\alpha_0,\alpha_1\in S_2$ with $\alpha_0<\alpha_1$, then $f_{\alpha_0}(n)\le f_{\alpha_1}(n)$ for all $n\in\omega$, which is the desired result.

Suppose now that $S_0$ is not stationary, and let $S_1=S\setminus S_0$; $S_1$ is stationary, so $|S_1|=\mathfrak{c}^+$. Suppose that $\alpha_0,\alpha_1\in S_1$ with $\alpha_0<\alpha_1$. $A_{\alpha_1}=\varnothing$, so for each $n\in\omega$ we must have $f_{\alpha_0}(n)\le f_{\alpha_1}(n)$, which is again the desired result.

| cite | improve this answer | |

Here is a partial answer by transfinite induction. I'm not very used to ordinals so I hope it's correct.

We proceed by transfinite induction on $o$. We strenghten the problem by considering partial functions: $f_\alpha\leq f_\beta$ if for all $n$ where both are defined, we have $f_\alpha(n)\leq f_\beta(n)$, The base case with $o=\{1\}$ is clear.

If $o=o'+1$ is a successor ordinal, we will isolate the maximal possible output $M$ (i.e. $o'$). We consider the partial functions $f'_\alpha$ where $M$ is replaced by $\bot$ (undefined). By hypothesis, there is $S'\subseteq c^+$ verifying all the requirements on the $f'_\alpha$'s.

Now for each $g:\mathbb N\to \{o',\{M\},\{\bot\}\}$ we define the set $S_g=\{\alpha \in S' : \forall n\in\mathbb N,f_\alpha(n)\in g(n)\}$. Since the $S_g$'s form a $c$-partition of $S'$, and $|S'|=c^+$, there exists $g$ such that $|S_g|=c^+$. This $S_g$ verifies all the conditions required for the $S$ we are looking for.

We now have to treat the limit case. For each $o'<o$, we consider $f_\alpha^{o'}$ to be $f_\alpha$ where the value is undefined outside of $o'$. Let $S_{o'}$ be the solution to the problem on the $f_\alpha^{o'}$ (by induction hypothesis). Notice that if $\alpha\leq \beta$ then $S_\alpha\supseteq S_\beta$ Let $S=\bigcap_{o'<o} S_{o'}$, we just need to prove that $|S|=c^+$.

| cite | improve this answer | |
  • $\begingroup$ Why does $f_\alpha$ have to have a maximal output? It could be that it doesn't achieve a maximal output. $\endgroup$ – ctlaltdefeat Jun 8 '13 at 19:31
  • $\begingroup$ Here $M$ is just the maximal element of $o$, i.e. $o'$ in the standard definition of ordinals. $\endgroup$ – Denis Jun 8 '13 at 19:32
  • $\begingroup$ Why can't $f_\alpha$ have the output $o$ at some $n$? The functions are built for $o$. $\endgroup$ – ctlaltdefeat Jun 8 '13 at 19:35
  • $\begingroup$ $o$ is defined as the set of ordinals $\alpha<o$. So if it is the codomain of $f$, it is not a possible output value. $\endgroup$ – Denis Jun 8 '13 at 19:36
  • $\begingroup$ Oh right I got it confused with $o'$ So $M$ is just $o'$ all the time? $\endgroup$ – ctlaltdefeat Jun 8 '13 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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