2
$\begingroup$

Galvin-Hajnal rank of an ordinal function $f: A \to Ord$ with respect to $I$ is defined as

$|f|_I=\sup_{g <_I f} (|g|_I+1)$

where $I$ is an ideal of $A$ and $g <_I f$ iff $\{a \in A: f(a) \leq g(a)\} \in I$.

What are the Galvin-Hajnal ranks with respect to the ideal of bounded subsets of $\omega_1$ of the functions $f,g: \omega_1 \to \omega_1$, $f(\alpha)=\omega$ and $g(\alpha)=\omega+1$ if $\alpha$ is $0$ or a limit ordinal, and $f(\alpha)=\omega+1$ and $g(\alpha)=\omega$ if $\alpha$ is a successor ordinal?

In comparison, I think that with respect to the ideal of nonstationary subsets the ranks are $|f|_I=\omega$ and $|g|_I=\omega+1$ because the subset of limit ordinals is club in $\omega_1$.

Also, is it possible that $|h|_I > \alpha$ for some ordinal $\alpha$ and at the same time $\{a \in A : h(a) \leq \alpha\} \not\in I$?

1 Answers 1

3

If you're looking at the ideal of bounded sets, then one function dominating another on a club is irrelevant, unless the club in question is a final segment of $\omega_1$. More generally, let $\beta : \mathrm{Lim} \to \mathrm{Suc}$ be the order-preserving bijection between the limit ordinals of $\omega_1$ and the successor ordinals. Now define $F : {}^{\omega_1}\omega_1 \to {}^{\omega_1}\omega_1$ by:

$F(f)(\alpha) = \left \{ \begin{array}{cc}f(\beta (\alpha )) & \alpha \in \mathrm{Lim}\\ f(\beta ^{-1}(\alpha )) & \alpha \in \mathrm{Suc}\end{array} \right .$

It's not hard to prove that $F$ is a bijection preserving the $<_I$ relation, hence $|f|_I = |g|_I$ for the two functions you defined. Both of these functions have rank $\omega$. The rank is clearly at least $\omega$ since the constant functions with finite values are $<_I$ these function. To show that $|f|_I \leq \omega$, it'll suffice to show that any $h <_I f$ has finite rank.

To see this, let $h <_I f$, so $h$ is finite-valued for eventually all limit ordinals. By Fodor's Lemma, there's some constant finite value $n$ which $h$ takes on for unboundedly many limit ordinals. It's not hard to see that $|h|_I \leq n$ (by induction on $n$, if you like).

For your last question, the answer is "Yes." Let $h(\alpha) = \alpha +1$. Since the identity function eventually dominates every constant function, the identity function has rank at least $\omega_1$. Thus $h$ has rank at least $\omega_1 + 1 > \omega_1$. However $\{\alpha : h(\alpha) \leq \omega_1\} = \omega_1 \notin I$.

  • 0
    Thank you for the answer.$I$followed your advice and tried to prove that $h^{-1}\{n\}$ is positive implies $|h|_I \leq n$ for all $n \in \omega$. It seems that one can also prove in the same way by transfinite induction that if $I$ is a $\kappa$-complete ideal of an infinite cardinal $\kappa$ and $h^{-1}\{\alpha\}$ is $I$-positive for some \alpha<\kappa then $|h|_I \leq \alpha$. In the limit ordinal case of the induction it seems one needs the $\kappa$-completeness. This would be another way to see that the rank of $f$ and $g$ is $\omega$.2011-06-16