6
$\begingroup$

We are writing a paper in which we need to use the following theorem to prove that a certain poset satisfies c.c.c. As far as I remember I learned this theorem from András Hajnal.

Theorem 1: If $\eta<\omega_1$ is an ordinal, and $f:\omega_1\to \mathcal P(\omega_1)$ is a mapping such that $tp(f(\alpha))<\eta$ for each $\alpha<\omega_1$, then there is an uncountable $f$-free set $A$ (i.e. $\alpha\notin f(\beta)$ for each $\{\alpha,\beta\}\in [A]^2$).

(Lázár considered and solved the special case $\eta=\omega$ in 1936).

I can prove this Theorem, but I can not find a reference. Could you help me?

UPDATE. Fodor proved the following strengthening of Lázár's result:

Theorem 2: If $f:\omega_1\to [\omega_1]^{<\omega}$ is a mapping , then there is an partition $\{A_n:n<\omega \}$ of $\omega_1$ into $f$-free sets.

What about the following common generalization of Theorem 1 and 2?

Problem: If $\eta<\omega_1$ is an ordinal, and $f:\omega_1\to \mathcal P(\omega_1)$ is a mapping such that $tp(f(\alpha))<\eta$ for each $\alpha<\omega_1$, then there is an partition $\{A_n:n<\omega \}$ of $\omega_1$ into $f$-free sets.

The proofs I know for Theorem 1 and Theorem 2 do not work here.

$\endgroup$
2
  • $\begingroup$ @bof yes, the family of pairs of countable ordinals $\endgroup$ Commented Apr 4 at 4:50
  • $\begingroup$ @bof Thank you, I corrected (it was too early here in Hungary when I wrote my first silly answer). $\endgroup$ Commented Apr 4 at 6:48

1 Answer 1

8
$\begingroup$

Theorem 1 is due to P. Erdős and E. Specker, On a theorem in the theory of relations and a solution of a problem of Knaster, Colloq. Math. 8 (1961), 19–21 (pdf). This Erdős–Specker paper was cited by P. Erdős, A. Hajnal, and E. C. Milner, Set mappings and polarized partition relations, Colloq. Math. Soc. János Bolyai 4 (1969), 327–363 (pdf).

Your proposed common generalization of Theorems 1 and 2, specialized to $\eta=\omega+1$, contradicts the continuum hypothesis, or more precisely the "stick" principle.

Theorem. Assuming CH, there is a mapping $f:\omega_1\to\mathcal P(\omega_1)$ such that $f(\alpha)\subseteq\alpha$ and $\operatorname{tp}f(\alpha)\le\omega$ for all $\alpha\lt\omega_1$, and such that $\omega_1$ is not the union of countably many $f$-free sets.

Proof. Assuming CH we can construct the mapping $f$ so that $f(\alpha)\subseteq\alpha$ and $\operatorname{tp}f(\alpha)\le\omega$ for all $\alpha\lt\omega_1$, and for each subset $X$ of $\omega_1$ of order type $\omega$ we have $X=f(\alpha)$ for some $\alpha\lt\omega_1$.

Assume for a contradiction that $\omega_1=\bigcup_{n\lt\omega}A_n$ where each $A_n$ is $f$-free. Choose an ordinal $\beta\lt\omega_1$ so that, for each $n\lt\omega$, either $A_n\subseteq\beta$ or else $A_n$ is uncountable. Construct a set $X\subseteq\omega_1$ of order type omega such that $X\cap(A_n\setminus\beta)\ne\varnothing$ whenever $A_n$ is uncountable, and let $X=f(\alpha)$. Then $\alpha\in A_n$ for some $n$, and $A_n$ is uncountable since $\alpha\gt\beta$, so $f(\alpha)\cap A_n\ne\varnothing$, contradicting our assumption that $A_n$ is $f$-free.

Remark. So the CH (in fact the combinatorial principle "stick" which is weaker) implies that the common generalization is false for $\eta=\omega+1$. On the other hand, $\text{MA}_{\aleph_1}$ implies that the common generalization is true for any $\eta\lt\omega_1$.

$\endgroup$
2
  • 1
    $\begingroup$ Thank you. I just wanted to add a weaker result using diamond^+. $\endgroup$ Commented Apr 4 at 10:16
  • 1
    $\begingroup$ I could prove that if diamond^+ holds, then the proposed generalization fails for eta=omega+1. This result is weaker than yours. $\endgroup$ Commented Apr 4 at 11:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .