Hindmanの定理(Hindman's theorem)とは、正の整数全体を有限個の色に塗り分けると、ある無限集合 $H$ があって、$H$ の相異なる有限個の元の和がすべて同じ色になる、という定理である。$x,y,x+y$ を求める Schur の定理を無限個の数に強めたもので、有限個の数に限った形が Folkman の定理にあたる。正の整数の上の超フィルター全体 $\beta\mathbb N$ に和を入れるとコンパクトな半群になり、冪等元 $p+p=p$ が存在する。冪等元に属する集合からは、有限部分和がすべてその集合に入る無限列を選び出せる。
前提知識: 超フィルター, コンパクト空間, Hausdorff空間, 半群, Zornの補題
Hindmanの定理(Hindman's theorem)は、正の整数全体を有限個の色に塗り分けると、ある無限集合 $H$ があって、$H$ の相異なる有限個の元の和がすべて同じ色になる、という定理である。和について閉じた単色の構造を求める定理のうち、Schurの定理(和のない集合) が $x,y,x+y$ の 3 数だけを求めるのに対し、Hindman の定理は無限個の数とそのすべての有限部分和を一度に求める。有限個の数で止めた形が Folkmanの定理 である。
この定理は Hindman(1974)が初めて証明し、Baumgartner(1974)がより簡単な証明を与えた(帰属は Bla93 p. 47 による)。この記事では、正の整数の上の超フィルター全体 $\beta\mathbb N$ に和を入れ、和について自分自身と等しい超フィルター(冪等元)から無限集合を取り出す証明を、すべて展開して与える。この証明は Galvin と Glazer によるもので(帰属は Bla93 p. 47)、Bla93 p. 49 に述べられている。必要な位相と代数の事実($\beta\mathbb N$ がコンパクト Hausdorff であること、和が結合的で片側の移動が連続であること、冪等元が存在すること)も、この記事の中で証明する。
以下、$\mathbb N:=\{1,2,3,\dots\}$ を正の整数全体とする。$\mathbb N$ を $r$ 色に塗るとは、写像 $c\colon\mathbb N\to\{1,\dots,r\}$ を与えることであり、同じことを $\mathbb N=C_1\cup\dots\cup C_r$ と互いに素な集合(色の組)に分けることとも言う。
$H\subseteq\mathbb N$ に対し、$H$ の空でない有限部分集合 $F$ の元の和 $\sum_{x\in F}x$ 全体の集合を
$$
\mathrm{FS}(H):=\Bigl\{\sum_{x\in F}x\ \Bigm|\ F\subseteq H,\ F\text{ は空でない有限集合}\Bigr\}
$$
と書き、$H$ の 有限部分和の集合 という。列 $(h_i)_{i\ge1}$ については、$\mathrm{FS}((h_i)_i):=\{\sum_{i\in F}h_i\mid F\subseteq\mathbb N\text{ は空でない有限集合}\}$ とする。
和をとる元は相異なることに注意する。$x\in H$ について $x+x$ は一般に $\mathrm{FS}(H)$ に入らない。
$\mathbb N$ を有限個の色に塗る。このとき無限集合 $H\subseteq\mathbb N$ で、$\mathrm{FS}(H)$ が単色であるものが存在する。さらに、$h_1,\dots,h_{i-1}$ から正の整数 $k_i$ を決める規則($i=1,2,\dots$)を任意に与えたとき、$H=\{h_1< h_2<\cdots\}$ を、各 $h_i$ がその $k_i$ の倍数となるようにとれる。
主張の前半は Hal12 p. 23 の関連する結果 3 と Bla93 p. 47 の Theorem 7 にある。後半(倍数の条件)は次の prop-hindman-unions で使うために足したもので、前半と同時に prf-hindman-main で証明する。証明には、以下の節で準備する $\beta\mathbb N$ の冪等元を使う。
$H$ が無限集合であることが要点である。有限集合でよいなら、1 元集合 $H=\{h\}$ をとれば $\mathrm{FS}(H)=\{h\}$ はいつも単色である。$\mathrm{FS}(H)$ には $H$ の元そのもの、2 元の和、3 元の和、…がすべて入るので、$\mathrm{FS}(H)$ が単色であることは、とくに $H$ の相異なる $x,y$ について $x,y,x+y$ が同じ色であることを含む。したがって Hindman の定理は Schurの定理(和のない集合) の $x\ne y$ の場合を含む。
Hindman の定理は、有限集合の 和集合 についての定理と言い換えられる。$\mathcal P_{\mathrm f}(\mathbb Z_{\ge0})$ を $\mathbb Z_{\ge0}:=\{0,1,2,\dots\}$ の空でない有限部分集合全体とする。
$\mathcal P_{\mathrm f}(\mathbb Z_{\ge0})$ を有限個の色に塗る。このとき、互いに素な空でない有限集合の列 $D_1,D_2,\dots\in\mathcal P_{\mathrm f}(\mathbb Z_{\ge0})$ で、有限個の $D_i$ の和集合 $\bigcup_{i\in F}D_i$($F$ は空でない有限集合)がすべて同じ色であるものが存在する。逆に、この主張から thm-hindman-main の前半が従う。
$\sigma(D):=\sum_{s\in D}2^s$ とおくと、2 進展開の一意性により $\sigma$ は $\mathcal P_{\mathrm f}(\mathbb Z_{\ge0})$ から $\mathbb N$ への全単射であり、$D\cap D'=\emptyset$ なら $\sigma(D\cup D')=\sigma(D)+\sigma(D')$ である。$n\in\mathbb N$ を $\sigma^{-1}(n)$ の色で塗り、thm-hindman-main を、規則「$k_1:=1$、$i\ge2$ では $k_i:=2^{t_i}$($t_i$ は $2^{t_i}>h_{i-1}$ となる最小の整数)」について使う。$D_i:=\sigma^{-1}(h_i)$ とおく。$h_j< 2^{t_i}$($j< i$)なので $D_j\subseteq\{0,\dots,t_i-1\}$、$h_i$ は $2^{t_i}$ の倍数なので $D_i\subseteq\{t_i,t_i+1,\dots\}$ であり、$D_i$ は互いに素である。よって $\sigma(\bigcup_{i\in F}D_i)=\sum_{i\in F}h_i\in\mathrm{FS}(H)$ で、色はすべて等しい。
逆を示す。$c$ を $\mathbb N$ の塗り分けとし、$D\in\mathcal P_{\mathrm f}(\mathbb Z_{\ge0})$ を、$D$ の元に $1$ を足した集合の元の和 $\tau(D):=\sum_{s\in D}(s+1)$ の色 $c(\tau(D))$ で塗る。主張の $D_i$ をとると、互いに素なので $\tau(\bigcup_{i\in F}D_i)=\sum_{i\in F}\tau(D_i)$ である。$x_i:=\tau(D_i)\ge\min D_i+1$ で、互いに素な有限集合の最小元は相異なるので $\min D_i\to\infty$、よって $x_i\to\infty$ である。狭義に増加する部分列 $x_{i_1}< x_{i_2}<\cdots$ をとり $H:=\{x_{i_1},x_{i_2},\dots\}$ とすると、$H$ は無限集合で、$\mathrm{FS}(H)$ の元は $\tau(\bigcup_{j\in F}D_{i_j})$ の形なのですべて同じ色である。$\square$
証明の道具は、$\mathbb N$ の上の超フィルター全体の集合である。超フィルターの定義と基本性質は 超フィルター にある。ここで使うのは次のことである:$\mathbb N$ の上の 超フィルター $p$ は $\mathbb N$ の部分集合の族で、$\mathbb N\in p$、$\emptyset\notin p$、共通部分と上への包含で閉じ、各 $A\subseteq\mathbb N$ について $A$ と $\mathbb N\setminus A$ のちょうど一方が $p$ に属する。このとき $A\cup B\in p$ なら $A\in p$ または $B\in p$ である(両方属さなければ補集合の共通部分 $\mathbb N\setminus(A\cup B)$ が $p$ に属し、矛盾する)。有限交叉性をもつ部分集合の族は超フィルターに含まれる(超フィルター の超フィルターの存在定理。証明に Zornの補題 を使う)。
$n\in\mathbb N$ に対し $e_n:=\{A\subseteq\mathbb N\mid n\in A\}$ は超フィルターで、主超フィルター という。有限集合 $F$ が超フィルター $p$ に属すれば、$F$ は 1 元集合の有限和なので、ある $n\in F$ について $\{n\}\in p$、すなわち $p=e_n$ である。したがって 主でない超フィルターは有限集合を含まず、補集合が有限な集合をすべて含む。
$\mathbb N$ の上の超フィルター全体を $\beta\mathbb N$ と書く。$A\subseteq\mathbb N$ に対し $\widehat A:=\{p\in\beta\mathbb N\mid A\in p\}$ とおき、$\{\widehat A\mid A\subseteq\mathbb N\}$ を開集合の基とする位相を $\beta\mathbb N$ に入れる。
$\widehat{A\cap B}=\widehat A\cap\widehat B$、$\widehat{\mathbb N}=\beta\mathbb N$ なので、これらは確かに開集合の基になる。また $\widehat{\mathbb N\setminus A}=\beta\mathbb N\setminus\widehat A$、$\widehat{A\cup B}=\widehat A\cup\widehat B$、$\widehat\emptyset=\emptyset$ である。とくに各 $\widehat A$ は開かつ閉である。$e_n\in\widehat A$ と $n\in A$ は同値である。この空間は離散空間 $\mathbb N$ の Stone–Čech コンパクト化と同一視される(コンパクト化)が、以下ではその事実を使わず、必要なことを直接示す。
$\beta\mathbb N$ はコンパクト Hausdorff 空間である。
Hausdorff 性:$p\ne q$ なら、$A\in p$、$A\notin q$ となる $A$ がある。$\mathbb N\setminus A\in q$ なので、$\widehat A$ と $\widehat{\mathbb N\setminus A}$ はそれぞれ $p,q$ を含む互いに素な開集合である。
コンパクト性:開被覆は基の元による被覆に細分できるので、$\beta\mathbb N=\bigcup_{i\in I}\widehat{A_i}$ が有限部分被覆をもつことを示せばよい。もたないと仮定する。有限個の $i_1,\dots,i_k$ について $\widehat{A_{i_1}}\cup\dots\cup\widehat{A_{i_k}}=\widehat{A_{i_1}\cup\dots\cup A_{i_k}}\ne\beta\mathbb N$ なので、$\widehat{\mathbb N\setminus(A_{i_1}\cup\dots\cup A_{i_k})}\ne\emptyset$、とくに $\mathbb N\setminus(A_{i_1}\cup\dots\cup A_{i_k})\ne\emptyset$ である($\widehat\emptyset=\emptyset$)。よって族 $\{\mathbb N\setminus A_i\}_{i\in I}$ は有限交叉性をもち、これを含む超フィルター $p$ がある。$p$ はどの $A_i$ も含まないので $p\notin\bigcup_i\widehat{A_i}$ となり、矛盾する。$\square$
$A\subseteq\mathbb N$ と $m\in\mathbb N$ に対し
$$
A-m:=\{n\in\mathbb N\mid m+n\in A\}
$$
とおく($A$ を $m$ だけ左にずらして正の部分を残したもの)。$(A\cap B)-m=(A-m)\cap(B-m)$、$(\mathbb N\setminus A)-m=\mathbb N\setminus(A-m)$、$\mathbb N-m=\mathbb N$、$(A-l)-k=A-(l+k)$ が定義からすぐわかる。
$p,q\in\beta\mathbb N$ に対し
$$
p+q:=\bigl\{A\subseteq\mathbb N\ \bigm|\ \{m\in\mathbb N\mid A-m\in q\}\in p\bigr\}
$$
と定める。言い換えると、$A\in p+q$ は「$p$ について大部分の $m$ で、$q$ について大部分の $n$ が $m+n\in A$ をみたす」ことである。
この定義は Bla93 pp. 36–37 にある(ただし同論文では $\mathbb N$ が $0$ を含む)。
(1) $q$ を固定し、$A^q:=\{m\mid A-m\in q\}$ とおく。上の性質と $q$ が超フィルターであることから、$(A\cap B)^q=A^q\cap B^q$、$(\mathbb N\setminus A)^q=\mathbb N\setminus A^q$、$\mathbb N^q=\mathbb N$、$\emptyset^q=\emptyset$ であり、$A\subseteq B$ なら $A^q\subseteq B^q$ である。$p+q=\{A\mid A^q\in p\}$ なので、$p$ が超フィルターであることから $p+q$ も超フィルターの条件をすべてみたす。$A\in e_m+e_n$ は $m\in A^{e_n}$、すなわち $n\in A-m$、すなわち $m+n\in A$ と同値なので、$e_m+e_n=e_{m+n}$ である。
(2) $(A-l)-k=A-(l+k)$ を使う。$A\in(p+q)+r$ は $\{m\mid A-m\in r\}\in p+q$、すなわち$$\bigl\{l\ \bigm|\ \{k\mid A-(l+k)\in r\}\in q\bigr\}\in p$$と同値である。一方 $A\in p+(q+r)$ は $\{l\mid A-l\in q+r\}\in p$、すなわち$$\bigl\{l\ \bigm|\ \{k\mid (A-l)-k\in r\}\in q\bigr\}\in p$$と同値で、両者は一致する。
(3) $\rho_q^{-1}(\widehat A)=\{p\mid A^q\in p\}=\widehat{A^q}$ は開集合である。$\square$
左からの和 $p\mapsto q+p$ は、$q$ が主超フィルターでなければ一般には連続でない(Bla93 p. 37。同論文は、連続な側の引数の位置に合わせてこの構造を left topological semigroup と呼んでおり、文献によって左右の呼び方が異なることも注意している)。以下で使うのは (3) の右からの和の連続性だけである。
$p+p=p$ をみたす $p$ を 冪等元 という。有限半群には必ず冪等元がある(半群)が、$(\mathbb N,+)$ には冪等元がない($n+n\ne n$)。$\beta\mathbb N$ ではコンパクト性がこの差を埋める。
$S$ を空でないコンパクト Hausdorff 空間とし、$S$ 上の結合的な演算 $+$ が与えられ、各 $u\in S$ について右からの和 $x\mapsto x+u$ が連続であるとする。このとき $S$ は冪等元 $e+e=e$ をもつ。
Bla93 pp. 42–43 は、この事実を $\beta\mathbb N$ について Theorem 2 (4) とその系として証明し、Ellis に帰している。下の証明はその議論を一般の $S$ に書いたものである。
$\mathcal T$ を、空でない閉集合 $T\subseteq S$ で $T+T\subseteq T$(和で閉じている)をみたすもの全体とし、包含で順序を入れる。$S\in\mathcal T$ である。$\mathcal T$ の鎖 $(T_\lambda)$ をとると、有限個の共通部分は鎖の中で最小のものに等しく空でないので、コンパクト性により $\bigcap_\lambda T_\lambda\ne\emptyset$ である。この共通部分は閉集合で、和で閉じている。よって鎖は $\mathcal T$ に下界をもち、Zornの補題 により $\mathcal T$ には極小元 $C$ がある。
$u\in C$ をとる。$C+u$ は、コンパクト空間の閉集合 $C$(コンパクト)の連続写像 $x\mapsto x+u$ による像なのでコンパクトで、Hausdorff 空間の中で閉集合である。$C$ は和で閉じているので $C+u\subseteq C$ であり、$x,y\in C$ について $(x+u)+(y+u)=(x+u+y)+u\in C+u$ なので $C+u$ も和で閉じている。$C$ の極小性から $C+u=C$ である。
次に $D:=\{v\in C\mid v+u=u\}$ とおく。$u\in C=C+u$ なので $D\ne\emptyset$ である。$D$ は $C$ と、閉集合 $\{u\}$(Hausdorff 空間の 1 点)の連続写像 $x\mapsto x+u$ による逆像との共通部分なので閉集合である。$v,w\in D$ なら $(v+w)+u=v+(w+u)=v+u=u$ なので $D$ は和で閉じている。$C$ の極小性から $D=C$、とくに $u\in D$、すなわち $u+u=u$ である。$\square$
$\beta\mathbb N$ には $p+p=p$ をみたす超フィルター $p$ がある。このような $p$ はどれも主超フィルターでなく、補集合が有限な集合をすべて含む。さらに、各正の整数 $k$ について、$k$ の倍数全体 $k\mathbb N$ は $p$ に属する。
存在は prop-hindman-compact、prop-hindman-sum と thm-hindman-ellis から従う。$e_n+e_n=e_{2n}\ne e_n$ なので $p$ は主超フィルターでなく、前節の注意により補集合が有限な集合をすべて含む。
$k$ を固定し、$j=0,1,\dots,k-1$ について $R_j:=\{n\in\mathbb N\mid n\equiv j\pmod k\}$ とおく。$R_0,\dots,R_{k-1}$ は $\mathbb N$ の分割なので、ちょうど 1 つ $R_j$ が $p$ に属する。$R_j-m=R_{j-m}$(添字は $k$ を法とする)なので、$R_j-m\in p$ は $j-m\equiv j$、すなわち $m\in R_0$ と同値である。$R_j\in p=p+p$ は $\{m\mid R_j-m\in p\}=R_0\in p$ を意味する。$\square$
冪等元 $p$ を 1 つ固定する。$A\subseteq\mathbb N$ に対し
$$
A^\star:=\{n\in A\mid A-n\in p\}
$$
とおく。$A^\star$ は「$A$ に属し、しかも $p$ について大部分の $k$ で $n+k$ が再び $A$ に属する」ような $n$ の集合である。
証明の考え方は次のとおりである。色の組 $C$ が $p$ に属すれば、$C$ の「大部分」の元 $n$ について、$C$ の「大部分」の元 $k$ で $n+k$ がまた $C$ に入る。これが $p+p=p$ の意味である。そこで $h_1$ をそのような $n$ から選び、次に $h_2$ を「$h_2\in C$ かつ $h_1+h_2\in C$ で、しかも先へ続けられる」ものから選ぶ。こうして選び続けると、選んだ数のどの部分和も $C$ に入る。各段で残る候補がつねに $p$ に属する(とくに空でない)ことを保証するのが次の補題である。冪等でない超フィルター、たとえば主超フィルター $e_1$ では、$C=\{1\}$ が $e_1$ に属しても $1+1\notin C$ であり、この選び方は 1 段目で止まる。
$A\in p$ とする。
(1) $A^\star\in p$ である。
(2) $n\in A^\star$ なら $(A^\star)-n\in p$ である。
(1) $A\in p=p+p$ なので $\{m\mid A-m\in p\}\in p$ であり、$A^\star=A\cap\{m\mid A-m\in p\}\in p$ である。
(2) $(A-n)-k=A-(n+k)$ を使うと$$(A^\star)-n=\{k\mid n+k\in A,\ A-(n+k)\in p\}=\{k\in A-n\mid (A-n)-k\in p\}=(A-n)^\star$$である。$n\in A^\star$ なので $A-n\in p$ であり、(1) を $A-n$ に使えば $(A-n)^\star\in p$ となる。$\square$
色の組を $\mathbb N=C_1\cup\dots\cup C_r$ とする。$p$ は超フィルターなので、どれか 1 つ $C:=C_j$ が $p$ に属する。集合 $A_1\supseteq A_2\supseteq\cdots$(すべて $p$ に属する)と数 $h_1< h_2<\cdots$ を次のように帰納的に定める。
$A_1:=C$ とする。$A_i\in p$ まで決まったとき、$h_1,\dots,h_{i-1}$ から規則で決まる $k_i$ をとる。lem-hindman-star (1)、cor-hindman-idempotent と補集合が有限な集合が $p$ に属することから$$A_i^\star\cap k_i\mathbb N\cap\{n\mid n>h_{i-1}\}\in p$$($i=1$ では最後の条件を省く)なので、この集合は空でなく、その元を 1 つ選んで $h_i$ とする。そして$$A_{i+1}:=A_i^\star\cap\bigl((A_i^\star)-h_i\bigr)$$とおく。$h_i\in A_i^\star$ なので lem-hindman-star (2) により $(A_i^\star)-h_i\in p$ であり、$A_{i+1}\in p$、$A_{i+1}\subseteq A_i^\star\subseteq A_i$ である。
次を $|F|$ についての帰納法で示す:$i\ge1$ と、空でない有限集合 $F\subseteq\{i,i+1,\dots\}$ について $\sum_{j\in F}h_j\in A_i$。$F=\{j\}$ なら $h_j\in A_j^\star\subseteq A_j\subseteq A_i$ である。$|F|\ge2$ なら $j:=\min F$、$F':=F\setminus\{j\}\subseteq\{j+1,j+2,\dots\}$ とおく。帰納法の仮定から $s:=\sum_{l\in F'}h_l\in A_{j+1}\subseteq(A_j^\star)-h_j$、すなわち $h_j+s\in A_j^\star\subseteq A_j\subseteq A_i$ である。
$i=1$ の場合から、$H:=\{h_1,h_2,\dots\}$ について $\mathrm{FS}(H)\subseteq A_1=C$ である。$h_i$ は狭義に増加するので $H$ は無限集合で、$\sum_{j\in F}h_j$ は $F$ ごとの和として $\mathrm{FS}(H)$ を尽くす。各 $h_i$ は $k_i$ の倍数である。$\square$
Bla93 p. 49 の証明は同じ構成を、「$p$ について大部分の $n$ で」という量化子の言葉で書いている。上の $A^\star$ はその量化子を集合で表したものである。証明が示しているのは次のことである:冪等な超フィルター $p$ に属する集合は、どれも $\mathrm{FS}(H)$($H$ は無限集合)を含む。とくに、ある冪等元に属する色の組なら、どれでもその中に $\mathrm{FS}(H)$ をとれる(Bla93 p. 49 の注意)。
証明の流れをまとめると次のようになる。
| 段階 | 内容 | 使う性質 |
|---|---|---|
| 空間 | $\beta\mathbb N$ はコンパクト Hausdorff | 有限交叉性をもつ族の超フィルターへの拡張 |
| 演算 | 和は結合的で、右からの和は連続 | $(A-l)-k=A-(l+k)$ |
| 冪等元 | 極小な閉部分半群の元は冪等 | Zornの補題、コンパクト性 |
| 組合せ | 冪等元に属する集合から $h_1< h_2<\cdots$ を選ぶ | $A^\star\in p$ と $(A^\star)-n\in p$ |
$n$ を $n$ を 3 で割った余りで 3 色に塗る。余り $0$ の組には $H=\{3,6,9,\dots\}$ がとれ、$\mathrm{FS}(H)$ は 3 の倍数だけからなる。余り $1$ の組と余り $2$ の組には、2 元集合 $H=\{a,b\}$ ですら $\mathrm{FS}(H)$ を単色にするものがない:$a\equiv b\equiv1$ なら $a+b\equiv2$、$a\equiv b\equiv2$ なら $a+b\equiv1$ である。これは cor-hindman-idempotent と合う:どの冪等元も余り $0$ の組 $3\mathbb N$ を含み、余り $1,2$ の組を含まない。
$n=2^{v}m$($m$ は奇数)と書いて $v=v_2(n)$ とし、$v_2(n)$ の偶奇で 2 色に塗る。$H=\{4^i\mid i\ge0\}$ をとると、空でない有限集合 $F$ について $\sum_{i\in F}4^i$ は $4^{\min F}$ と $4^{\min F+1}$ の倍数の和なので $v_2=2\min F$(偶数)であり、$\mathrm{FS}(H)$ は単色である。$H'=\{2\cdot4^i\mid i\ge0\}$ では $v_2=2\min F+1$(奇数)で、もう一方の色の中に $\mathrm{FS}(H')$ がとれる。
次の表の各行は、仮定を 1 つだけ外すと結論が成り立たなくなる例である。
| 外した仮定 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| 色の数が有限(thm-hindman-main) | $c(n)=n$(すべての数を相異なる色に塗る) | $h< h'$ が $H$ に属すれば $h,h'\in\mathrm{FS}(H)$ は色が違い、2 元以上の $H$ で $\mathrm{FS}(H)$ が単色のものはない |
| 和をとる元が相異なる(def-hindman-fs) | ex-hindman-v2 の $v_2$ の偶奇による 2 色 | 同じ元を繰り返して足すことを許すと、和の集合は $x$ と $x+x=2x$ を含むが、$v_2(2x)=v_2(x)+1$ なので両者は色が違い、空でないどの $H$ でも単色にならない |
| 単色にする集合が色の組の 1 つであること(大きさの条件だけにする) | 奇数全体($\mathbb N$ の半分を占める) | 奇数 $a\ne b$ の和は偶数なので、2 元以上の $H$ で $\mathrm{FS}(H)$ が奇数全体に含まれるものはない |
| $S$ がコンパクト(thm-hindman-ellis) | 離散位相の $(\mathbb N,+)$ | Hausdorff で、右からの和は連続(離散空間からの写像)だが、$n+n=2n\ne n$ なので冪等元がない |
3 行目は、Hindman の定理が「大きな集合はどれも $\mathrm{FS}(H)$ を含む」という密度の主張ではないことを示している。奇数全体と偶数全体の 2 色の塗り分けでは、$\mathrm{FS}(H)$ は偶数の組の中にとれる(たとえば $H=\{2,4,8,\dots\}$)。
和の代わりに積を考えると、$n\mapsto 2^n$ で和が積に移るので、$\mathbb N$ のどの有限の塗り分けにも、無限集合 $H$ で相異なる有限個の元の積がすべて同じ色になるものがある($2^n$ の色で $n$ を塗り直して thm-hindman-main を使う)。一方、和と積を 同時に 単色にすることはできない:有限個の色の塗り分けで、どの無限列 $(x_i)$ についても $\{x_i+x_j\mid i< j\}\cup\{x_i\cdot x_j\mid i< j\}$ が単色にならないものがある(Hal12 p. 24 の関連する結果 8 が述べている。この記事では証明しない)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する