# More than continuum many functions

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.

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

• 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! – ctlaltdefeat Jun 8 '13 at 21:25
• @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. – 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

$$\beta(\alpha,n,k+1)=\min\{\gamma<\alpha:f_{\beta(\alpha,n,k)}(n)>f_\gamma(n)>f_\alpha(n)\}\tag{2}$$

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

$$\left\{\{\beta(\alpha,n,k):k<\ell(n)\}:n\in\omega\right\}\;,$$

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

$$\left\{\{\beta(\alpha_0,n,k):k<\ell(n)\}:n\in\omega\right\}=\left\{\{\beta(\alpha_1,n,k):k<\ell(n)\}:n\in\omega\right\}$$

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.

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^+$.

• Why does $f_\alpha$ have to have a maximal output? It could be that it doesn't achieve a maximal output. – ctlaltdefeat Jun 8 '13 at 19:31
• Here $M$ is just the maximal element of $o$, i.e. $o'$ in the standard definition of ordinals. – Denis Jun 8 '13 at 19:32
• Why can't $f_\alpha$ have the output $o$ at some $n$? The functions are built for $o$. – ctlaltdefeat Jun 8 '13 at 19:35
• $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. – Denis Jun 8 '13 at 19:36
• Oh right I got it confused with $o'$ So $M$ is just $o'$ all the time? – ctlaltdefeat Jun 8 '13 at 19:36