Twierdzenie Erdősa–Rado

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Twierdzenie Erdősa–Rado – w kombinatoryce nieskończonej, twierdzenie udowodnione przez Paula Erdősa i Richarda Rado[1] będące rozszerzeniem twierdzenia Ramseya na zbiory odpowiednio dużej mocy.

Notacja[edytuj | edytuj kod]

Niech κ będzie liczbą kardynalną.

\exp_0(\kappa)=\kappa,
\exp_r(\kappa) = 2^{\exp_{r-1}(\kappa)}\;\;\;(r=1,2,3,\ldots).

Twierdzenie[edytuj | edytuj kod]

Niech r będzie liczą naturalną oraz niech κ będzie nieskończoną liczbą kardynalną. Wówczas zachodzi relacja podziałowa

 \exp_r(\kappa)^+\longrightarrow(\kappa^+)^{r+1}_\kappa,

tzn. dla każdego kolorowania f rodziny (r + 1)-elementowych podzbiorów zbioru mocy expr(κ)+ na κ kolorów istnieje zbiór monochromatyczny mocy κ+, tj. taka podrodzina rodziny (r + 1)-elementowych podzbiorów zbioru mocy expr(κ)+ na której funkcja f jest stała.

Przypisy

  1. P. Erdős, R. Rado, A partition calculus in set theory, Bull. Amer. Math. Soc. 62 (1956), 427–489.