Erdős–Radoの定理(Erdős–Rado theorem)とは、無限基数 $\kappa$ と自然数 $r\ge1$ について、$2$ の冪を $r-1$ 回重ねた基数の次の基数の上で、$r$ 点集合を $\kappa$ 色に塗ると濃度 $\kappa^+$ の単色集合があるという分割定理である。$r=2$ では $(2^\kappa)^+\to(\kappa^+)^2_\kappa$ となり、$2^\kappa$ の上には濃度 $\kappa^+$ の単色集合をもたない $2$ 色の塗り分けがあるので、台の大きさは最良である。Ramseyの定理の非可算への拡張にあたり、鎖と反鎖、強制法の鎖条件、位相空間の濃度の評価に使われる。
自然数全体の $2$ 点集合を有限色に塗ると、無限の単色集合がある(Ramseyの定理)。同じことは非可算では成り立たない。$\omega_1$ の $2$ 点集合には、非可算な単色集合をもたない $2$ 色の塗り方がある(弱コンパクト基数)。では、塗る集合を十分大きくとれば、非可算な単色集合は得られるか。Erdős–Rado の定理(Erdős–Rado theorem)は、これに次の形で答える。
$$
(2^{\aleph_0})^+\to(\aleph_1)^2_{\aleph_0}
$$
つまり、濃度が連続体より大きい集合の $2$ 点集合を可算個の色に塗ると、濃度 $\aleph_1$ の単色集合がある。一般に、$\kappa$ を無限基数とすると、$2$ の冪を $r-1$ 回重ねた基数の次の基数の上で、$r$ 点集合の $\kappa$ 色の塗り分けは濃度 $\kappa^+$ の単色集合をもつ。
この記事では定理を完全に証明し、$r=2$ の場合に台の大きさが最良であることを Sierpiński の塗り分けで示す。応用として、半順序の鎖と反鎖、強制法の鎖条件、位相空間の濃度の評価を述べる。
Erdős と Rado の名は別の定理にも付いている。有限集合の族についての Δ-システム の記事の定理「向日葵補題」、交わる集合族についての Erdős–Ko–Radoの定理 である。この記事で扱うのは、無限基数の分割関係の定理である。
集合 $A$ と自然数 $r\ge1$ について、$[A]^r:=\{s\subset A\mid\lvert s\rvert=r\}$ とおく。基数 $\gamma$ について、写像 $c\colon[A]^r\to\gamma$ を $A$ の $r$ 点集合の $\gamma$ 色の塗り分け という。$H\subset A$ が $c$ の 同質集合 であるとは、$c$ が $[H]^r$ の上で定数であることをいう。
基数 $\theta,\lambda,\gamma$ について、濃度 $\theta$ の集合 $A$ のどの $\gamma$ 色の塗り分けも濃度 $\lambda$ の同質集合をもつことを
$$
\theta\to(\lambda)^r_\gamma
$$
と書く。成り立たないことを $\theta\not\to(\lambda)^r_\gamma$ と書く。
$\theta\to(\lambda)^r_\gamma$ は $\theta$ を大きくしても、$\lambda$ や $\gamma$ を小さくしても保たれる。Ramseyの定理 の無限の形は、$k$ が自然数のとき $\aleph_0\to(\aleph_0)^r_k$ と書ける。$r=1$ のときは鳩の巣原理である。$\kappa$ が無限基数なら、$\kappa^+$ は正則なので、$\kappa^+$ 個の元を $\kappa$ 個の組に分けると、濃度 $\kappa^+$ の組がある。すなわち
$$
\kappa^+\to(\kappa^+)^1_\kappa
$$
である。
無限基数 $\kappa$ について、$\exp_0(\kappa):=\kappa$、$\exp_{i+1}(\kappa):=2^{\exp_i(\kappa)}$ と定める。
$\exp_i(\aleph_0)$ は $\beth_i$ とも書かれる。
主定理は導入で述べた形である。証明の鍵は、指数を $1$ つ下げる次の補題である。$A$ を順序数の集合とし、$s\in[A]^{r-1}$ の上に $1$ 点を足した $r$ 点集合の色が、足した点によらないとき、塗り分けは実質的に $r-1$ 点集合の塗り分けになる。
$r\ge2$ とし、$\mu\ge\kappa$ を無限基数、$\theta:=(2^\mu)^+$ とする。$c\colon[\theta]^r\to\kappa$ を塗り分けとする。このとき、順序型 $\mu^+$ の集合 $H\subset\theta$ で次を満たすものがある:どの $s\in[H]^{r-1}$ と、$\max s$ より大きいどの $a,b\in H$ についても
$$
c(s\cup\{a\})=c(s\cup\{b\})
$$
である。
$\beta<\theta$ について、$\beta$ の濃度 $\mu$ 以下の部分集合 $B$ と写像 $t\colon[B]^{r-1}\to\kappa$ の組 $(B,t)$ を $\beta$ の組と呼ぶ。点 $y\ge\beta$ が $(B,t)$ を 実現する とは、すべての $s\in[B]^{r-1}$ について $c(s\cup\{y\})=t(s)$ となることをいう。$B\subset\beta\le y$ なので $s\cup\{y\}$ は $r$ 点である。
$\lvert\beta\rvert\le2^\mu$ なので $B$ の個数は高々 $(2^\mu)^\mu=2^\mu$、$B$ ごとの $t$ の個数は高々 $\kappa^\mu\le2^\mu$ である。したがって $\beta$ の組は高々 $2^\mu$ 個である。
順序数の増加列 $(\delta_i)_{i<\mu^+}$ を次のように作る。$\delta_0:=0$ とし、極限では上限をとる。$\delta_{i+1}>\delta_i$ は、$\delta_i$ の組のうち $y\ge\delta_i$ によって実現されるものが、必ず $\delta_i\le y'<\delta_{i+1}$ を満たす $y'$ でも実現されるようにとる。実現される組ごとに実現する点を $1$ つ選び、その上限より大きくとればよい。$\theta$ は正則で $2^\mu<\theta$、$\mu^+\le2^\mu$ なので、列はすべて $\theta$ の中にとれ、$\delta:=\sup_{i<\mu^+}\delta_i<\theta$ である。
点 $x_i$($i<\mu^+$)を帰納的に選ぶ。$H_i:=\{x_j\mid j< i\}$ が選ばれ、$H_i\subset\delta_i$ であるとする。$\lvert H_i\rvert\le\mu$ である。$s\in[H_i]^{r-1}$ について $t_i(s):=c(s\cup\{\delta\})$ と定めると、$(H_i,t_i)$ は $\delta_i$ の組で、点 $\delta\ge\delta_i$ によって実現される。よって $(H_i,t_i)$ を実現する $x_i\in[\delta_i,\delta_{i+1})$ がある。
$H:=\{x_i\mid i<\mu^+\}$ とおく。列 $(x_i)$ は狭義増加なので、$H$ の順序型は $\mu^+$ である。$s\in[H]^{r-1}$、$a=x_i$、$b=x_k$ が $\max s$ より大きければ、$s\subset H_i$ かつ $s\subset H_k$ なので
$$
c(s\cup\{a\})=t_i(s)=c(s\cup\{\delta\})=t_k(s)=c(s\cup\{b\})
$$
である。$\square$
点 $\delta$ の役割を見ておく。$\delta$ は $H$ のすべての点より上にあり、$H$ の各点は「$\delta$ と同じ色の見え方をする」ように選ばれている。$\mu$ 個以下の点の上の色の見え方は高々 $2^\mu$ 通りしかないので、$\delta$ の見え方はすでに下の方に現れている。これが $\theta=(2^\mu)^+$ を使う場所である。
$\kappa$ を無限基数、$r\ge1$ を自然数とする。このとき
$$
\bigl(\exp_{r-1}(\kappa)\bigr)^+\to(\kappa^+)^r_\kappa
$$
である。特に $(2^\kappa)^+\to(\kappa^+)^2_\kappa$ である。
$r$ についての帰納法で示す。$r=1$ は上で述べた $\kappa^+\to(\kappa^+)^1_\kappa$ である。
$r\ge2$ とし、$r-1$ で正しいとする。$\mu:=\exp_{r-2}(\kappa)$ とおくと $\mu\ge\kappa$ で、$\exp_{r-1}(\kappa)=2^\mu$ である。濃度 $(2^\mu)^+$ の集合は $\theta:=(2^\mu)^+$ と同一視してよい。塗り分け $c\colon[\theta]^r\to\kappa$ をとり、lem-er-endhom の $H$ をとる。
$H$ の順序型は $\mu^+$ なので最大元がない。$s\in[H]^{r-1}$ について、$a\in H$ を $\max s$ より大きくとり $c'(s):=c(s\cup\{a\})$ とおく。lem-er-endhom により $c'(s)$ は $a$ によらない。
$\lvert H\rvert=\mu^+=(\exp_{r-2}(\kappa))^+$ なので、帰納法の仮定により、$c'$ の同質集合 $H'\subset H$ で $\lvert H'\rvert=\kappa^+$ のものがある。$u\in[H']^r$ について、$a:=\max u$、$s:=u\setminus\{a\}$ とすると $c(u)=c'(s)$ である。$c'$ は $[H']^{r-1}$ で定数なので、$c$ は $[H']^r$ で定数である。$\square$
| $r$ | $\kappa=\aleph_0$ の場合 | CH を仮定すると |
|---|---|---|
| $1$ | $\aleph_1\to(\aleph_1)^1_{\aleph_0}$ | 同じ |
| $2$ | $(2^{\aleph_0})^+\to(\aleph_1)^2_{\aleph_0}$ | $\aleph_2\to(\aleph_1)^2_{\aleph_0}$ |
| $3$ | $(2^{2^{\aleph_0}})^+\to(\aleph_1)^3_{\aleph_0}$ | $2^{\aleph_1}=\aleph_2$ もあわせて $\aleph_3\to(\aleph_1)^3_{\aleph_0}$ |
一般の指数の定理は ER56 Theorem 39(pp. 467–468)にあり、この形は HL10 Corollary 2.10 である。同所の形は $\kappa^+$ を順序型 $\kappa^++(r-1)$ に強めている。$r=2$ の場合は ER56 Theorem 4 (i)(p. 431)に $(a^a)^+\to(a^+)^2_a$ として挙げられている。無限の $a$ では $a^a=2^a$ である。$r=2$ の別証明は Kun80 Ch. VIII の演習 (B1)(p. 290)にある。
$r=2$ のとき、$(2^\kappa)^+$ を $2^\kappa$ に下げることはできない。色が $2$ つでも足りなくなる。
$\kappa$ を無限基数とする。$2^\kappa\not\to(\kappa^+)^2_2$ である。
$A:={}^\kappa2$ を $\kappa$ から $\{0,1\}$ への写像の全体とし、$<_{\mathrm{lex}}$ を辞書式順序とする。$\prec$ を $A$ の整列順序とする。$x\prec y$ のとき、$x<_{\mathrm{lex}}y$ なら $c(\{x,y\}):=0$、そうでなければ $c(\{x,y\}):=1$ と定める。
$H$ が濃度 $\kappa^+$ の同質集合であるとする。$H$ の $\prec$ についての順序型 $\kappa^+$ の始切片をとれば、$(A,<_{\mathrm{lex}})$ に長さ $\kappa^+$ の狭義単調な列 $(x_\xi)_{\xi<\kappa^+}$ が得られる。これが不可能であることを示す。
各 $\gamma\le\kappa$ について $V_\gamma:=\{x_\xi|_\gamma\mid\xi<\kappa^+\}$ とおく。$\lvert V_\kappa\rvert=\kappa^+$ なので、$\lvert V_\gamma\rvert=\kappa^+$ となる最小の $\gamma$ をとる。$\beta<\gamma$ とする。$\xi\mapsto x_\xi|_\beta$ は辞書式順序について広義単調なので、同じ値をとる $\xi$ の集合は $\kappa^+$ の凸集合である。$\lvert V_\beta\rvert\le\kappa$ であり $\kappa^+$ は正則だから、そのうちの $1$ つは非有界で、したがってある $\xi_\beta$ より先のすべてを含む。$\xi^*:=\sup_{\beta<\gamma}\xi_\beta<\kappa^+$ である。
$\xi,\xi'\ge\xi^*$ なら、すべての $\beta<\gamma$ で $x_\xi|_\beta=x_{\xi'}|_\beta$ である。$\gamma$ が極限なら $x_\xi|_\gamma=x_{\xi'}|_\gamma$ であり、$\gamma$ が後続なら $x_\xi|_\gamma$ は高々 $2$ 通りである。いずれの場合も $\lvert V_\gamma\rvert\le\lvert\xi^*\rvert+2\le\kappa$ となり矛盾する。$\square$
$\kappa=\aleph_0$ とすると、$2^{\aleph_0}\not\to(\aleph_1)^2_2$ である。実数直線の通常の順序と整列順序を比べる塗り分けがこれにあたる。主定理とあわせて、基数 $\theta$ について次が成り立つ。
$\kappa$ を無限基数、$\theta$ を基数とする。$\theta\to(\kappa^+)^2_\kappa$ と $\theta>2^\kappa$ は同値である。
$\theta>2^\kappa$ なら $\theta\ge(2^\kappa)^+$ なので、thm-er-main から成り立つ。$\theta\le2^\kappa$ なら、prop-er-sierpinski の塗り分けを濃度 $\theta$ の部分集合に制限すれば、成り立たないことが分かる。$2$ 色の塗り分けは $\kappa$ 色の塗り分けである。$\square$
色を $\kappa$ 個まで許すと、台が $2^\kappa$ のときには $3$ 点の同質集合さえなくなる。
$A:={}^\kappa2$ の相異なる $x,y$ について、$c(\{x,y\})$ を $x(\alpha)\ne y(\alpha)$ となる最小の $\alpha<\kappa$ と定める。
$r\ge3$ でも台は最良である。$\theta$ と $\lambda_0,\lambda_1$ が無限で $\lambda_0$ が正則、$\gamma\ge2$ のとき、$\theta\not\to(\lambda_\xi)^r_\gamma$ から $2^\theta\not\to(1+\lambda_\xi)^{r+1}_\gamma$ を導く負の階段補題(HL10 Theorem 2.11)を prop-er-sierpinski から繰り返し使うと、$r\ge2$ で $\exp_{r-1}(\kappa)\not\to(\kappa^+)^r_2$ が得られる。HL10 はこの補題の証明を文献に委ねており、この記事でも証明しない。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 台の濃度が $2^\kappa$ より大きい($r=2$) | 台 $2^\kappa$ の Sierpiński の塗り分け | 濃度 $\kappa^+$ の同質集合の存在 |
| 色の数が $\kappa$ 以下 | 台 $A$ の単射 $c\colon[A]^2\to[A]^2$ | $3$ 点の同質集合の存在 |
| 指数 $r$ が有限 | どの無限基数 $\theta$ についても、下の箱の $[\theta]^{\omega}$ の $2$ 色の塗り分け | 無限の同質集合の存在 |
$\theta$ を無限基数とし、$[\theta]^\omega$ を $\theta$ の可算無限部分集合の全体とする。$x,y\in[\theta]^\omega$ の対称差が有限であることは同値関係である。選択公理で各同値類の代表 $\rho(x)$ を選び、$\lvert x\mathbin{\triangle}\rho(x)\rvert$ の偶奇を $c(x)$ とする。
非対称な分割関係との違いにも触れておく。ER56 Theorem 3 (i)(p. 431)は、無限基数 $a$ について $2$ 色で塗ると、$0$ 色の可算無限の同質集合か、$1$ 色の濃度 $a$ の同質集合があることを述べる。一方の色の同質集合を可算に諦めれば、台を冪にする必要はない。
最初の $2$ つは、$2$ 点の関係を $2$ 色に塗るだけで得られる。
濃度が $(2^\kappa)^+$ 以上の半順序集合 $P$ には、濃度 $\kappa^+$ の鎖か、濃度 $\kappa^+$ の反鎖がある。比較可能な対を色 $0$、比較不能な対を色 $1$ に塗り、thm-er-main を使えばよい。$\kappa=\aleph_0$ なら、濃度が連続体より大きい半順序集合には非可算な鎖か非可算な反鎖がある。同じことはグラフの完全部分グラフと独立集合についても成り立つ。
台を $2^\kappa$ に下げると成り立たない。$^\kappa2$ に、$<_{\mathrm{lex}}$ と $\prec$ の両方で小さいときに $x\le y$ と定めた半順序を入れると、prop-er-sierpinski の塗り分けの $0$ 色の同質集合が鎖、$1$ 色の同質集合が反鎖であり、どちらも濃度 $\kappa^+$ に達しない。
$P,Q$ が ccc の半順序(可算鎖条件)なら、$P\times Q$ の反鎖の濃度は $2^{\aleph_0}$ 以下である。$\mathcal A\subset P\times Q$ が濃度 $(2^{\aleph_0})^+$ の反鎖なら、相異なる $(p,q),(p',q')\in\mathcal A$ は $p\perp p'$ または $q\perp q'$ を満たす。$p\perp p'$ のとき色 $0$、そうでないとき色 $1$ に塗る。thm-er-main により非可算な同質集合がある。色が $0$ なら第 $1$ 成分は $P$ の非可算な反鎖をなし、色が $1$ なら第 $2$ 成分は $Q$ の非可算な反鎖をなす。これは矛盾である。主張は Kun80 Ch. VIII の演習 (B6)(p. 291)である。
次の応用は、塗る色の情報を使う。$T_1$ 空間 $X$ について、$s(X)$ を離散部分空間の濃度の上限と $\aleph_0$ の大きいほう(基数関数 の定義「spread」)、$\psi(X)$ を各点が高々 $\psi(X)$ 個の開集合の共通部分として書ける最小の無限基数(擬指標(位相))とする。
$X$ が $T_1$ 空間なら $\lvert X\rvert\le2^{s(X)\psi(X)}$ である。
$\kappa:=s(X)\psi(X)$ とおき、$\lvert X\rvert\ge(2^\kappa)^+$ と仮定する。$X$ を整列順序 $<$ で順序づける。各 $x\in X$ について、$x$ を含む開集合の族 $(U_x(\xi))_{\xi<\kappa}$ で $\bigcap_\xi U_x(\xi)=\{x\}$ となるものを選ぶ。$x\ne y$ について、$y\notin U_x(\xi)$ となる $\xi<\kappa$ を $1$ つ選び $\xi(x,y)$ と書く。
$x< y$ のとき $c(\{x,y\}):=(\xi(x,y),\xi(y,x))\in\kappa\times\kappa$ と定める。色は $\kappa$ 個なので、thm-er-main により濃度 $\kappa^+$ の同質集合 $H$ があり、その色を $(\xi,\eta)$ とする。$x\in H$ について $V_x:=U_x(\xi)\cap U_x(\eta)$ とおく。$x< y$ なら $y\notin U_x(\xi)$、$y< x$ なら $y\notin U_x(\eta)$ である。よって $V_x\cap H=\{x\}$ であり、$H$ は離散部分空間である。$\lvert H\rvert=\kappa^+>s(X)$ となり矛盾する。$\square$
この不等式は Juhasz80 2.15 (a)(pp. 20–21)の主張である。同書も Erdős–Rado の分割定理を使う。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する