数理解析研究所講究録
第 1555 巻 2007 年 9-17

9On stability of saturated generic hypergraphs
筑波大学数理物質科学研究科安保勇希 (Yuki Anbo)(Graduate school of Pure and Applied Sciences, University of Tsukuba)

概要

1997 年に J. Baldwin は strictly super stable な generic 構造は存在するか,という問題を提示した [1]. 池田氏は generic graph 1 こ関してはそのような構造は存在しないということを示した [4]. 本稿では generic hypergraph に関しても同じことが成立することを示す (定理 11).

1

序
$R$

を 3 項関係記号とし, 言語 $L=\{R\}$ の構造で以下を満たすものを

hypergraph と呼ぷ :$\bullet$

For all$a_{1},$ $a_{2},$ $a_{3}$and$\sigma\in S_{3},$$R(a_{1}, a_{2}, a_{3})\Leftrightarrow R(a_{\sigma(1)}, a_{\sigma(2)},a_{\sigma(3)})$.

(symmetry)$\bullet$

For all$a_{1},$ $a_{2},$ $a_{3},$$R(a_{1}, a_{2}, as)\Rightarrow a_{1},$ $a_{2},$ $a_{3}$are distinct. (irreflexive)構造という言葉を hypergraph という意味で使う.
有限 -構造 $A$ に対して, 関係 $R$ が成立する $A$ の点の 3 つ組の数を$r(A)$ で表すとき, $A$ の (に関する) 局所次元を $\delta_{\alpha}(A)=|A|-\alpha r(A)$で定める. 例えば, 頂点が $\{a, b, c\}$ で $R(a, b,c)$ が成立しているとき,$\delta_{\alpha}(A)=3-1\cdot\alpha$ である.
添え字のは省略して書くことが多い. また,相対次元を $\delta(A/B)=\delta(AB)-\delta(B)$ で定義する.
for all $A’\subset A$ } とおき, 以下では
{ $A$ : 有限 $L$-構造$K$は臨の部分集合とする. 有限 $L$-構造の拡大 $A\subset B$ に対し, $A$ が $B$
以下,

$L$

$L$$\alpha$$\alpha$$K_{\alpha}=$$|\delta_{\alpha}(A’)\geq 0$で閉であるという関係を $A\leq B\Leftrightarrow\delta(A)\leq\delta(B’)$ for any $A\subset B’\subset B$ で定める. 一般の $L$ 構造 $A\subset B$ に対しては, $A\leq B\Leftrightarrow A\cap B’\leq B’$ for
any finite subset $B’$ of $B$ と定める.
定義 1. $L$ -構造 $M$ は以下の 3 条件を満たす時 K-generic であると言われる$\bullet$

$M$

は可算

10$\bullet$$\bullet$$K$$M$の任意有限部分が $K$ に属する.

$A\leq M,$ $A\leq B\in K\Rightarrow\exists B’<Ms.t$が有限閉包性をもつとは,$B’$

は $B$ と $A$ 上同型となる $K$ の元の拡大列$\delta(A_{i})>\delta(A_{i+1})$が存在しないことをいう.
は subhypergraphs に関して閉じていて有限閉包性をも以下,つとし, $M$ は saturated K-generic hypergraph とする.

$A_{0}\subset A_{1}\subset\cdots$$K\subset K_{\alpha}$

事実 2. $/2fK\subset K_{\alpha}$ が部分構造にっいて閉じていて有限閉包性をもち,$M$ が saturated K-generic hypergraph のとき,

1. $T=Th(M)$ is stable2.

2$\alpha\in \mathbb{Q}\Rightarrow T$is w-stable

特徴的な hypergraph たち

定義 3. $A$ が $L$ -構造, $a,$ $b\in A$ のとき,を以下のように定める :$a$と$b$の $A$ における距離 $d_{A}(a,b)$

1. $d_{A}(a,b)=0\Leftrightarrow a=b$

2. $d_{A}(a, b)\leq 1\Leftrightarrow d_{A}(a, b)=0$ orS.

$d_{A}(a, b)<n\Leftrightarrow\exists a_{1},$ $\cdots$d_{A}(*, u_{+1})\leq 1$

4$\cdot$

5.

$\exists c\in As.t$a_{n-1}\in As.t$. $R(a, b, c)$. $a_{0}=a,a_{n}=b$ とするとき,

for each $0\leq i\leq n-1$$d_{A}(a, b)=n\Leftrightarrow d_{A}(a, b)\leq n$

かつ $d_{A}(a, b)\not\leq n-1$$d_{A}(a, b)=\infty\Leftrightarrow\forall n<w,$ $d_{A}(a,b)\not\leq n$

定義 4. $A\subset B$ を -構造とするとき, $A$ が $B$ で連結であるとは, 任意の $a,$ $b\in A$ に対し, $d_{B}(a, b)<\omega$ となることをいう. 単に $A$ が連結といったら, $A$ で連結であるということとする. X が trivial であるとは,$\sup$ { $|A|$ : $A\in K,$ $A$ は連結} $<w$ となることをいう.
$L$

命題 6. $K$ が trivial なら, $T=Th(M)$ is w-stable
証明$\mathcal{M}$を $T$ の big model とし,$A$を$\mathcal{M}$の可算部分集合とする. $A$ はと関係を持たないとしてよい.
$A$ に対し,砺たちの connected components の$\mathcal{M}-A$$\overline{a}=(a_{1}, \cdots,a_{n}),\overline{b}=(b_{1}, \cdots b_{n})\not\in$

たちについての和との connected components のについての和が同型で, その同型によって
とわ- は $A$ 上 type が等しい. connected componentとが移る時,の形は有限通りしかないので, $A$ 上の tyPe の数は可算.
$i$$\overline{b}$$\overline{a}$$\overline{a}$ここまでで,$i$$b_{i}$

11$\alpha\in \mathbb{Q}\Rightarrow T$$\bullet$$\omega$is $trivial\Rightarrow T$ is -stable$K$$\bullet$

is -stable$\omega$

is non-trivial の時,superstable にはならないことを示すことにする.
これからよく扱う hypergraph の形に名前をつけておく.
が分かったので, 今後の目標は,$R$で関係をもたない.

, 但しどの 3 つ組も$R$で関係をもたない.

$I_{n}=\{a_{1}, \cdots, a_{\mathfrak{n}}\}$$\bullet$$I_{\infty}=\{a_{1}, a_{2}, \cdots\}$$\bullet$$D_{n}=\{a, b_{1}, c_{1}, \cdots, b_{n}, c_{n}\}$てや$R(a, b_{i}, c_{i})$$,$$D_{\infty}$$\cdots$$T$がfor $i\neq i$ であっand no other relations.

$\{b_{i},c:\}\neq\{b_{j},c_{j}\}$,$n$, 但し { , 儒}\neq

for $i\neq i$ であつfor eaeh $i=1,$ $\cdots n$ and no other relations.
$b_{i}$$\{b_{j},c_{j}\}$のことを daisy flower と呼ぶこともある.

補題 6. $\exists a\in M,$$\Rightarrow\exists D_{\infty}\subset M$

さらに,

, 但し

for $ewhi=1,$$D_{\infty}=\{a, b_{1}, c_{1}, b_{2}, c_{2}, \cdots\}$$\bullet$$D_{\mathfrak{n}}$$R(a, b_{i}, c_{i})$$K$, 但しどの 3 つ組も$\bullet$-c,$\alpha\not\in \mathbb{Q},$$\exists B\subset M$.

infinite$s.t$. $\sup\{d_{M}(a,b):b\in B\}<w$$D_{\infty}=\{a’, b_{1}, c_{1}, b_{2}, c_{2}, \cdots\}$のとき, ($b_{i}$, 果)i $<w$ が$a’$

上 indis$-$cemible になるようにできる.
証明 $L$-構造 $A$ と $a\in A$ に対し, degA(a) $=|\{b\in A :d_{A}(a, b)=1\}|$ と定める.
Claim $\exists a’\in M$ s.t. deg $M(a’)=\infty$
そうでないとする. 次のようにして, $M$ の元を並べて有限分岐の troe を考える :.

$\bullet$$a$からスタートし,$d_{M}(a, b)=1$となるすべての点$b_{1},$$\cdots b_{k}$に分岐する.
$\bullet$$\bullet$

次に, $d_{M}(b_{1}, c)=1$ となるすべての点を並べて,$b_{1}$から分岐させる.

これを繰り返す.

すべての $b\in B$ は深さ $k_{0}= \sup\{d_{M}(a, b) :b\in B\}$ までに登場する.
ところが深さまでには高々有限個しか点が無い. 矛盾. (Claim 終わり)
Claim より, $a’$ につながる $(b, c)$ は無限にある. 従って, 次が充足的になる.
$k_{0}$$\Gamma((x_{i},y_{i})_{i<\omega})=\{R(a’,x_{i},y_{i}) :i<w\}\cup\{\{x_{t},y_{i}\}\neq\{x_{j},y_{j}\}$: $i<j<$$w\}$

こ解 $(b_{i}, q)_{t<w}$ を 上 indiscernible にとる. この時,は $R$ ( $a’,$ ,ci) の他に関係を持たない. なぜなら, 例えば $R(a, b_{1}, b_{2})$ が関係を持ったとすると $R(a, b_{i}, b_{j})$ for an $i<i$ となるが, この集合の有$a’$$b_{i}$$\{a’,b_{1}, c_{1}, b_{2},c_{2}, \cdots\}$

12
限部分で局所次元が負になる部分ができてしまう.

は generic 構造な$M$

のでそれは起こりえない.

補題 7. $K$ が non-tnvial なら,証明 次の性質.

$\exists D\infty\subset M$

で場合分けをする.

$(^{*})$. for an $a,b\in M,$ $d_{M}(a,b)<w\Rightarrow d_{M}(a,b)<n$$(^{*})\exists n<\omega s.t$という 3 条が成り立っ時は, $K$ is nontrivial, $M$ is saturated,件から, $M$ の中に無限の大きさの connected subset がとれる. 従って前補題より.
が成り立たない時は, 次が成立する.
$(^{*})$$(^{*})$$\exists D_{\infty}\subset M$$(^{*})$$\forall n<w,$ $\exists a,b\in M$

s.t. $d_{M}(a,b)=n$ .

このとき次を満たす無限列 $(h),<w$ が存在する : $d_{M}(a0, a_{n})=n$ for each$n<w$
またこのとき,$\alpha\leq 2$がわかる. 実際, 距離の定義にあるように $A_{n}=$の局所次元が一番大きくなるのan’ } が得られた時,
O\leq i\leq n のみがすべて相異なり, 関係が $R(\alpha, \alpha+1, b_{i+1})$ for
はについてこれが成りの場合である. よって $2n+1-n\alpha\geq 0$ . すべての{$a0,a_{1},$ $b_{1},$ $\cdots$$A_{n}$$b_{\mathfrak{n}}$$eac\dot{h}$$b_{i}$$n$

立っのでClaim$\alpha\leq 2$.

s.t.

$\exists A\subset M$$A$

is finite, connected, and$\exists a,$$b\in As.t.\{a, b\}\leq A$

少し複雑な場合分けになる.
s.t. $R(h-1$ , bi-l, \alpha ののとき.
Casel$\exists i\geq 4$$\{a_{0}, a_{i}\}\leq\{a0,a_{1},$Case2$\exists i\geq 4$s.t.

$b_{1,},b_{i-1,*\}}$$R(\alpha_{-1},b_{i-1}, b_{i})$のとき.

$\{a_{0}, b_{i}\}\leq\{a_{0},a_{1},b_{1}, \cdots, a_{i-1}, b_{i-1}, b_{i}\}$

Case3$\exists t\geq 4$s.t. $\neg R(u_{-1},$$b_{i-1},$ $a$のかつ$\neg R(b_{i-1},b_{i}, a_{i})$のとき.

$\{a0, *\}\leq\{\infty, a_{1},b_{1,\cdot\cdot,k-1},b_{i-1A},b_{i}\}$Case4$\forall i\geq 4,$$\neg R(u_{-1}, b_{i-1}, a_{i}),$$\neg R(\alpha_{-1}, b_{i-1}, b_{i}),$$i\backslash ’\supset R(b_{i-1},b_{i,4})$のとき.
はすべて相異なり, 関係は $R(\alpha, \alpha+1, b_{i+1}),$ $R(b_{i,h+1}, b_{i+1})$
このとき, 話を単純にする為,for each $i<w$ のみであると仮定する. すると,
$b_{i}$$\forall n<w,2n+1-(2n+1)\alpha\geq 0$

よって,$\alpha\leq 1$.

従って,.

$\{a0, \alpha\}\leq\{a0, a_{1}, b_{1,}, b_{i-1}, *,b_{i}\}$.

(Clalm 終了)
は無限なので Ramseyの定理よりすべての 3 点が関係をもつ無限部分集合かすべての 3 点が関$I_{\infty}=\{h,b_{1},b_{2}, \cdots\}\leq M$がとれる. 実際,

$M$

13
係をもたない無限部分集合が存在するが, 前者はその有限部分で局所次元が負になる部分があるので generic 構造の中には存在しない. $M$ の中でclosed にとれることは, $M$ の genericity と saturatedness から従う. この$I_{\infty}$

について,視して,$M${恥, } $\leq M$ . Claim の$b_{i}$の genericity より,の $a,$$b$とこの$b_{0},$$b_{i}$を同一と $\{a, b\}$ 上同型な構造が $M$ の中にと$A$

このとき,れる.

$d_{M}(b_{0}, b_{i})=d_{M}(b_{0}, b_{j})<w$

従って, 前補題より

3$A$

for each $i,j<w$ .

が存在する.

$D_{\infty}$

主定理の証明定理 8.
stable.

$\alpha$が無理数で,$K$が non-triviat なら,$T=Th(M)i\epsilon str\dot{t}ctly$

事実 9. 7 可次は同値である :$\bullet$$\bullet$$T$

is superstable

次を満たす無限上昇列 $A_{i}(i<\omega)$ と type の上昇列 $p_{i}(i<w)$ は存在
しない :
$\mu$

は

$A_{i}$

上の type で,$Pi+1$

forks over$A_{i}$.の有限部分 $A$ に対して, $A$ の $M$ における d-dimension を, $d_{M}(A)=$$\delta(c1_{M}(A))$ と定める. 相対次元を $M$ の有限部分 $A,$ $B$ に対して $d_{M}(A/B)=$$M$$d_{M}(AB)-d_{M}(B)$ と定める.

事実 10. [$5JK$ が subhypefgraphs について閉じていて有限閉包性をもち,$A,$ $B,$ $C$ が $M$ の有限部分構造で,$B,$ $C\leq M$ かつ $A=B\cap C$ とするとき, 次は同値である :$\bullet$$\bullet$$d(B/A)=d(B/C)$$tp(B/C)$ does notfork over$A$

これらの事実を用いて ‘forking の無限列 ” を構成する.
定理の証明 前補題より ( finite indisoernible) daisy flower が存在する.
その形について場合分けをする.
$\dot{i}$のCasel daisy flower$\exists\{eBC\}\in K$ s.t.
Claim$\{a, b_{1}, c_{1}, \cdots\}$$b_{i}$, 果たちがすべて相異なるとき.

$0<\forall\epsilon<\alpha,$

1. $-\epsilon<\delta(C/eB)<0$ .

2. $\delta(X/eB)>0$ for all nonempty proper subset $X$ of$C$

14
3. $\delta(C/Y)>0$ for all nonempty proper subset$\alpha$$Y$of $eB$ .

が無理数なので,$\min${ $n:-\epsilon<n-q\alpha<0$ for some $q<w$ }が存在する. これをのときは,$P$とおく.

$-\epsilon<p-q_{p}\alpha<0$となる$q_{p}$をとる. $p=1$$eBC=D_{q,}$ でよい.のときは, 便宜上 $q_{1}=0$ とおいて, 各 $2\leq n<p$ に対し, $q_{n}=$$mas\mathfrak{c}\{q:n-q\alpha>0\}$ とおく.
また, 各 $1\leq n\leq p$ に対し, $d_{n}=n-q_{n}\alpha$$p\geq 2$

とおく.
$2arrow\alpha>0$より$q_{2}\geq 1$

を $e,c_{2}$ , 残りの部分を$c_{2}\leq D_{q_{2}}\leq M$$>q_{2}$卯$c_{2}\leq D_{q_{3}-\wp}$$B_{1}$.の場合,$c_{2}$

. 従って

$M$

. daisy flowerと名付ける.

$D_{\infty}$の中心を $c_{1},1$ つの花びら$D_{q_{2}}\leq M$としてよい. このとき,を中心とする daisy flowerの genericity から$D_{\infty-q_{2}}$$D_{q_{2}}\cup D_{q\epsilon-qa}$を考えると.

が $M$ の closed

を中心とする花びらが新しくちょうset として取れる. またこのとき,ど qs-q2 枚加わったと仮定してよい. 新しく加わった花びらの中の 1 点$c_{2}$

を$c_{l}$, その他をとする.

$B_{2}$の場合は,とおく.とは独立な点をどちらの場合でも, $c_{3}\leq eB_{1}B_{2}c_{1}c_{2}c_{3}$ となるので, 再びる花びらを $q_{4}-q_{3}$ 枚新しく加えることができる.
$q_{3}=q_{2}$$D_{q_{2}}$$c_{3}$$c_{3}$

を中心とす

これを繰り返して$B=B_{1}\cup\cdots\cup B_{p},$ $C=\{c_{1}, \cdots c_{p}\}$とする.

eBC が求める性質をもっことを確認する.

$\delta(C/eB)$$=$$|C|-r(C,eB)$$p- \alpha\sum_{i=1}^{p-1}(q_{i+1}-q_{i})$$=p-\alpha q_{p}$となるので, (1) が成立する. 但し, $r(C, eB)$ は $C$ と $eB$ の間の関係の

X,$X$

RPb $r(C,eB)=r(eBC)-(r(eB)-r(C))$ .
を $C$ の空でない真部分集合とする.

Subclalm $X$ が eBC で連結なら $\delta(X/eB)>0$ .
$X=\{c_{i}\}_{n<i\leq m}$と書くと, $n=1$ のとき, $m<p$ となり,$\delta(X/eB)=\{\begin{array}{ll}m-q_{m}\alpha (m\geq 2)1 (m=1)\end{array}$15であり,$n\geq 2$のとき,$\delta(X/eB)=m-(n-1)-\alpha$.となるので, いずれの場合も $\delta(X/eB)>0$ (Subclaim 終了)としたとき, $\delta(X/eB)=$
一般の $X$ に対して, $X$ の連結成分を$\sum\delta(X_{i}/eB)>0$ となるので, (2) が成立する.
$X_{i}$

また,$Y$を $eB$ の空でない真部分集合とすると,$\delta(C/Y)\geq\delta(C/eB)+$となり, (3) も成立する. (Claim 終了)に対して eBiCi をとを十分大きくとり, Claim において,$\alpha>-\epsilon+\alpha$$i_{0}$$\epsilon=\frac{1}{2^{i_{0}+i}}$

る (for $euhi$ ).

このとき,は共通にとり, $i\neq i$ のとき関係が無いと仮定してよい ( $eB_{1}C_{1}$ ができたら,独立になるように B2C2 の構成を始める.. .)$B_{\mathfrak{n}}^{l}= \bigcup_{i\leq n}B:,$

このとき,と BjCj の間には全く$B_{i}C_{i}$$e$$C_{n}^{*}= \bigcup_{i\leq n}$

Ci とおき,$c1(eB_{n}^{*})=eB_{n}^{*}C_{n}^{*}$$e$を中心にして$B_{1}C_{1}$と.と仮定してよい.の任意の真部分集合 $X$$eB_{\mathfrak{n}}^{*}C_{\mathfrak{n}}^{*}\leq M$である. 実際$C_{n}^{*}$

に対し,$\bullet$$\delta(eB_{n}^{*}C_{n}^{*}/eB_{\mathfrak{n}}^{l}X)=\sum\delta(eB_{i}C_{i}/eB_{i}(X\cap C_{i}))$$\bullet$$\delta(eB_{i}C_{i})\leq\delta(\epsilon B_{i}(X\cap C_{i})),$$\bullet$$X\cap C_{i}\neq C_{i}\Rightarrow\delta(eB_{i}C_{i})\leq\delta(eB_{i}(X\cap C_{i}))$

なので,
また,

$\delta(eB_{n}^{l}C_{n}^{*}/eB_{n}^{*}X)<0$$B_{\mathfrak{n}}^{*}\leq eB_{n}^{*}C_{n}^{l}$$l^{a}\cdot\supset$.

である. 実際, 任意の$X\subset eC_{n}^{l}$に対し,Casel $e\in X$ のとき,$\delta(X/B_{\mathfrak{n}}^{r})$$=$$\delta(X/eB_{n}^{*})+\delta(e/B_{n}^{*})$$\sum_{i=1}^{n}\delta(X\cap C_{i}/eB_{i})+1$$\geq$

Case2 $e\not\in X$ のとき,$\delta(Y/B_{i})>0$$C_{i}$$0$.の任意の空でない真部分集合 $Y$ に対してとなることに注意すると,.

$\delta(X/B_{n}^{*})=\sum_{i=1}^{n}\delta(X\cap C_{i}/B_{i})>0$

16
以上より,
$d_{M}(e/B_{n}^{*})$$=$$d_{M}(eB_{n}^{*})-d_{M}(B_{n}^{*})$$=$$\delta(eB_{n}^{*}C_{n}^{l})-\delta(B_{n}^{*})$$=$$\delta(eC_{\mathfrak{n}}^{*}/B_{n}^{l})$$=$$\delta(C_{n}^{r}/eB_{n}^{*})+1$$\sum\delta(C_{i}/eB_{i})+1n$$i=1$がわかり, 従って
$d_{M}(e/B_{n+1}^{r})$$=$$\sum_{i=1}^{n}\delta(C_{i}/eB_{i})+1$$=$$d_{M}(e/B_{n}^{l})+\delta(C_{\mathfrak{n}+1}/eB_{\mathfrak{n}+1})$$<$$d_{M}(e/B_{n}^{l})$となる.

事実 10 より$tp(e/B_{n+1}^{*})$

は$B_{n}^{l}$

上 fork する. 事実 9 より$T$

is notsuperstable.

Indiscernible daisy flower の形はもう 1 つある$(\forall i,j, b_{i}=b_{j})$が, 形が異なるだけで同様の計算によって定理が成立することが確かめられる.
以上より次の定理が得られた.
が subhypergraphs
定理 11. 有限 $(tema\eta)hypergrnphs$ のクラス K
について閉じていて有限閉包性をもつとする. このとき, 任意の saturated
K-generic hypergraph は w-stable か stnctly stable になる.
$CK_{\alpha}$

参考文献[1] J.T.Baldwin, Problems on pathological structures, In Helmut Wolter
Martin Weese, editor, Proceedings of 10th Easter Conference inModel $Th\infty ry$ (1993) 1-9[2] J.T.Baldwin and N.Shi, Stable generic structures, Annals of Pureand Applied Logic 79 (1996) 1-35

[3] K.lkeda, Algebraic typesof generic graphs, 京都大学数理解析研究所
年9月
講究録 1450, 63-68,$2\mathfrak{W}5$[4] K.Ikeda, A remark on the stability of saturated generic graphs, Journal of the Mathematical Society of Japan, vol.57, no.4(2005)

17[5] K.Ikeda, Forking in Generic Structures, preprints[6] A.Pillay, An introduction to stability
press, 1983

, Oxford : Clarendon$th\infty ry$[7] F.O.Wagner, Relational structures and dimensions, Kaye, Richard(ed.) et al., Automorphisms of first-order structures. Oxford: Clarendon Press. 153-180 (1994)