数理解析研究所講究録 1450 巻 2005 年 42-62

42

GENERIC STRUCTURES AND CONTROL FUNCTIONS(A COMMENTARY ON EVANS’PREPRINT )米田 郁生 (IKUO YONEDA)
MATHEMATICS,
TOKAI UNIVERSITY
DEPARTMENT OF

東海大学理学部数学科

ABSTRACT We survey the results in “Some remarks on generic structures”[E] written by Evans, and give some detailed proofs which are omitted in
his note.

1. INTRODUCTION
In simplicity theory, Hrushovski’s generic constructions yield various results.
As in his -categorical stable pseudoplane, he constructed an w-categorical,
simple, rank one, non-locally modular theory by amalgamating finite graphs
whose local rank is controlled by an increasing unbounded convex function.
In [E1], Evans gave a sufficient condition on control functions for constructing-categorical simple generic structures. We review this in fifth section. In[E], Evans gave an -categoricai non-simple generic structure by carefully setting a control function (In this note, sixth section). This non-simple genericstructure has 3-strong order property. For any $n\geq 3$ , -strong order property
was introduced by Shelah. (See [Sh] and third section in this note.) Strict
order property implies -strong oder property, and $n+1$ -strong order property implies -strong order property for any $n\geq 3$ . Evans showed that genericstructures given by control functions do not have 4-strong order property, we
follow this result in fourth section.
In [P], Pourmahdian conjectured that generic stuructures without control func-generic structure, will be non-simple. In [P], Pourmahtion, so-calledof adina considered a natural expansioned inductive (incomplete) theory
non-zerohas
anyfinitesubstructure
axiomatizing
thatuniversal theory onlyis a Robinson theory andpositive local rank. Pourmahdian showed that
does not have model
andstructure,asasimpleis
its universal domaincompanion. (Natural expansioned structure of (Ko, )-generic structure is an
generic) Evans gave an example ofexistentially closed model ofstructure having strict order property, we discuss this issue in second section.
$\omega$$\omega$$\omega$

$n$

$n$

$n$

$(\mathrm{K}_{0}, <)$$T_{nat}$$T_{0}$$T_{nal}$$T_{nat}$$<$$T_{nat}.$$(\mathrm{K}_{0}, <)$Date: August 1, 2005.
I would like to thank David M. Evans for his permission to submit this note

43This note is organized as follows.
has strict order property,
Section 2: We will follow the proof that-generic structure with one ternary relation.
where
isSection 3: Review of [Sh].
, wheredoes not have
Section 4: We will follow the proof thatis the class of finite graph A satisfying-generic structure and
is a
with
and control function is a convex increasing unbounded
function from to R.
Section 5: Review of [E],Section 6: We will follow the proof that for some control function ,, where $\delta(*)=2|$ $*|-e(*)$ .
has: Long appendices for Section 6, which are omitted in [E1].
Section$\mathrm{T}\mathrm{h}(\Lambda I_{0})$$(\mathrm{K}_{0}, <)$$\mathrm{A}I_{0}$$\mathrm{T}\mathrm{h}(flI_{f})$$(\mathrm{K}_{f}, <)$$\mathrm{S}\mathrm{O}\mathrm{P}_{4}$$\mathrm{A}I_{f}$$\mathrm{K}_{f}$$f$$\grave{\delta}(A)\geq f(|A|)$$\mathrm{N}$$f$$\mathrm{T}\mathrm{h}(\Lambda I_{f})$$\mathrm{S}\mathrm{O}\mathrm{P}_{3}$$7,\mathrm{S}$2.

$\mathrm{T}\mathrm{h}(\lambda I_{0})$HAS SOP.

(DEFINABLE CORRESPONDENCE BETWEEN GRAPHSAND TERNARY HYPERGRAPHS)

Let be a ternary relation. For finte ternary-hypergraph 21, we define thepredimension as follows.
$\Re$$\delta^{\urcorner}(\mathfrak{U})=|\mathfrak{U}|-|\Re^{\mathfrak{U}}|$For finite$\mathfrak{U}\subseteq \mathfrak{B}$we define a partial order$<$

as follows$\mathfrak{U}<\mathfrak{B}\Leftrightarrow\overline{\delta}(X)>\delta(\mathfrak{U})(\mathfrak{U}\subset\forall X\subseteq \mathfrak{B})$For possibly infinite$\mathit{2}t\underline{\subseteq}\mathfrak{B}$we define$\mathfrak{U}<\mathfrak{B}\Leftrightarrow$Note that(1) of 2[ in$\mathfrak{U}<\mathfrak{U}$$\mathfrak{B}$$\mathrm{c}1_{\mathfrak{B}}$.

$\cap A<X(\forall X\subset_{\omega}\mathfrak{B})$.

, there exists the -closureis the class of finite 3-hypergraphs defined by$2\mathrm{t}$$\overline{\mathrm{K}_{0}}$I. For possibly infinite$\mathrm{K}_{0}$.

$\mathfrak{U}$$<$$\subseteq \mathfrak{B}$$\in \mathrm{K}_{0}\Leftrightarrow\emptyset<\mathfrak{U}$is the class of 3-hypergraphs whose finite sub-hypergraph is all in-generic structure.
denotes the$\mathrm{K}_{0}$.

$(\mathrm{K}_{0}, <)$$\mathrm{J}I_{0}$Notation 2,1. Let $(A, R)$ be a graph, where is the binary relation for the.
graph. We define the following ternary graph,are new elements.
, where1J$R$$(\mathfrak{H}_{A}, \Re)$$\bullet$$\bullet$$\mathfrak{H}_{A}=A\cup R^{A}$$\{x_{A}, y_{A}\}$$(\Re)^{\mathfrak{H}4}.=\{(x_{A}, y_{A}, a) :$x_{A}$

a\in A\}$

1J$y_{A}$$\{(\mathrm{a}, b, (a, b)) :(a, b)\in R^{A}\}$(A,$\Re)$ is definable in (A, R) with two new constants.

Lemma 2.2. Let { A, R) be a graph. Then
.
(1)
.
(2)
$\mathfrak{H}_{A}\in\overline{\mathrm{K}_{0}}$$\mathfrak{H}\mathfrak{H}_{A}=\mathrm{c}1_{\mathfrak{H}_{A}}(x_{A}, y_{A})$44, and let $V(X)$ be the vertex set of $x$ . Then
$R^{A}\cup\{x_{A}, y_{A}\}$ follows.
) $=|V(X)|-(|V(X)$If , $y_{A}\in x$ , then$R^{A}|+|V(X)$ $\cap A|)>0$ , since $V(X)$ $=\{x_{A}, y_{A}\}\cup(V(X) \cap R^{A})\cup(V(X) \cap A)$ .
$=|V(X)|-(|V(X) \cap R^{A}|)>0$ , since $|V(X)$ $\cap R^{A}|>0$ implies
Otherwise,$|V(X)$ $\cap A|>0$ .
, then 0
Let $c\in A$ . Then $\delta(c/x_{A}, y_{A})=0$. So, if, a contradiction. Next, let $=(a, b)\in$. As$\delta(c/a,b)=0$. By the above argument, we see. Then.
, we see that,
Next, for any symmetric 3-hypergraph having at least two vertices, we construct a graph as follows.

Proof. Let$x$$V(X)\underline{\subset}$$\subset_{\omega}g_{A}$$A|\mathrm{J}$$\cap$$\delta_{\mathrm{t}}’X$$x_{A}$$6(\mathrm{X})$$<$$c\not\in \mathrm{c}1_{\mathfrak{H}_{A}}(x_{A}, y_{A})$$c$$\delta(c/\mathrm{c}1_{\mathfrak{H}_{A}}(x_{A}, y_{A}))\leq\overline{\delta}(c/x_{A}, y_{A})=0$$R^{A}$$a$$c\in \mathrm{c}1_{\mathfrak{H}_{A}}(a, b)$$\square$$c\in \mathrm{c}1_{\mathfrak{H}_{A}}(x_{A}, y_{A})$$b\in \mathrm{c}1_{\mathfrak{H}_{A}}(x_{A}, y_{A})$be a symmetric 3-hypergraph having at least two
Notation 2.3. Let. We define the following graphvertices. Fix two vertices ,as follows.
$(\mathfrak{U}, \Re)$$a$$b\in \mathfrak{U}$$G_{(\mathfrak{U},a,b\}}=$$(\mathrm{c}, R)$$\bullet G_{\mathfrak{U}}=\{c\in \mathfrak{U} :$R^{G\mathrm{r}}\lrcorner=$$\bullet${\mathfrak{U}\models\Re(c, a, b)\}$$(c, d)\in \mathfrak{U}^{2}$:$21\models${$(\mathrm{c},$R) is definable in$G_{(\mathfrak{U},a,b)}=(G_{\mathfrak{U}},$

Remark 2.4.

$a$

,

$b)$

A $\Re(d,$ ,$a$where ,
(1),
not appear in the righthand.)

(2)

$a$

A

$\exists x\Re(x,$ $c$, $d)$ }with parameters a, b$(\mathfrak{U}, \Re)$$\mathfrak{U}\not\simeq \mathfrak{H}c_{\mathfrak{l}^{\lrcorner a,b)^{j}}}\mathrm{r}$$b)$$b\in \mathfrak{U}$. (If$2\mathrm{t}$$\in \mathfrak{U}$$\models\neg\Re(d, a, b)$

,

.

$d$

will

$A\simeq G_{\langle \mathrm{i}_{A}x_{A},y_{A})}‘,\cdot$

Proof. Clearly,$G_{\mathrm{f}_{\mathit{1}A}}=A$

and$R^{G_{\mathfrak{H}_{A}}}=R^{A}$, as desired.

be a symmetric 3-hypergraph having at least two verLemma 2.5. Let
tices. Then(1) ,, then(2) If, then(3) If$(\mathfrak{U}, \Re)$$a$$b\not\in G_{\mathfrak{U}}\subseteq \mathrm{c}1_{\mathfrak{U}}(a, b)$$(\mathrm{c}, d)\in R^{91}$$\Re^{\mathrm{c}1_{\mathfrak{U}}\langle a,b\}}\models\exists x\Re(x, c, d)$$\mathfrak{U}<\mathfrak{B}$Proof. If$G_{(\mathfrak{U},a,b)}=G_{(\mathfrak{B},a,b)}$, then. So, (3) follows.

$\mathfrak{U}|^{=}1\{(\mathrm{c}, a, b)$$\mathrm{c}1_{\mathfrak{U}}(a, b)=\mathrm{c}1_{\mathfrak{B}}(a, b)$$c\in \mathrm{c}1_{\Re}(a, b)$. (1),(2) follow. If$\mathfrak{U}<\mathfrak{B}$, then$\square$Notation 2.6. Let be a sentence in the language of graphs with binary
having free varirelation symbol $R(x_{1}, x_{2})$ . We construct a fourmulaable , in the the language of 3-hypergraphs with ternary relation
as follows.
symbol$z)$ A $\Re(x_{2}, y, z)$ A
Replace all atomic subformulasby$\varphi$$\sigma_{\varphi}$

$y$

$z$

$\Re(x_{1}, x_{2}, x_{3})$$R(x_{1}, x_{2})$$\bullet$$\mathrm{V}(\mathrm{X})y,$$\exists u’\Re(w, y, z)$$\bullet$Replace Vr $(\psi(x))$ ,$\psi(\overline{x}))$.

$\exists x(\psi(\overline{x}))$by$\forall x(\Re(x,y, z)arrow\psi(\overline{x}))$,$\exists x(\Re(x, y, z)$A45

Remark 2.7. Letof graphs. Then, ,$(\mathfrak{U}, \Re)\in\overline{\mathrm{K}_{0}}$$a$$b\in \mathfrak{U}$and$\varphi$

be a sentence in the language$G_{(\mathfrak{U},a,b)}\models\varphi\Leftrightarrow \mathfrak{U}\models\psi_{\varphi}(a, b)$

The above remark follows from “REDUCTION THEOREM” , a (non-onto)
map from
to 1, and the way of replacement of quantifiers. Reduction
theorem needs a onto map, but our
quatifiers are bounded in $\Re(*, a, b)$ .
So we need not a onto map, here.
$G_{(\mathfrak{U},a,b)}$$\psi_{\varphi}’ \mathrm{s}$Fact 2.8. Let
be an -structure, and $N$ be an Lf-str ucture. Suppose thatto $N$ (for some $n<\omega$ )there exists a partial onto map fromfor every positive atomic -formula 0, there exists an -formula( (ci))
such that
THEN, by induction on the complexity of formulas, for ever$w$ -formula ,such that
there exists an $L’$ -formula$L$$\lambda I$$f$$\bullet$$\Lambda I^{n}$

$L’$

$L$

$\bullet$$\lambda I$$\models\theta(\overline{a})\Leftrightarrow N\vdash-\psi_{\theta}$$\psi_{\theta}$

$f$

$L$

$\Lambda I$$\psi_{\varphi}$$\varphi$$\models\varphi(\overline{a})\Leftrightarrow N\models\psi_{\varphi}(f(\overline{a}))$be a sentence in the language of graphs. THEN, “there
Lemma 2.9. Let.
exists a finite graph’iff$\varphi$$A_{1}|=\varphi’$

Proof.

$(\Rightarrow)$$\Lambda I_{0}\models\exists yz\psi_{\varphi}(y)z)$: We may assume that
. Therefore, A$\mathfrak{H}\mathfrak{H}_{A}<\lambda I_{0}$$G_{(\mathscr{F}_{\mathrm{J}A},x_{A},y_{A}\rangle}\simeq G_{(M_{0},x_{A},y_{A})}$$(\Leftarrow):G_{(M\mathrm{o},a,b)}l^{=}\}\varphi$

and. So, by Remark 2.4,

$I_{0}\models\psi_{\varphi}(x_{A}, y_{A})$$A\simeq$.
$\square$$G_{(M_{0},a,b)}\subseteq \mathrm{c}1_{M_{0}}(a, b)\subset_{\alpha I}\lambda I_{0}$Proposition 2.10. Let be a sentence in the language of graphs. Supposethat has arbitralily large finite model. Then there exists an infinite model,.
definable in some model of$\varphi$$\varphi$$\mathrm{T}\mathrm{h}(\Lambda I_{0})$Proof By our assumption, for any $n<" J$ , there exists a finite graphthat$\omega$$A_{n}\models\varphi$

and $|A_{n}|\geq n$ . As
, for any $n<\omega$ ,$A_{n}\simeq G_{\mathrm{t}\mathfrak{H}_{A_{n}},x_{A_{n}},y_{A_{n}})}$$A_{n}$

such( by Remark 2.4) and$>|\mathfrak{H}_{A_{n}}|\geq|A_{n}|\geq n$$\mathfrak{H}_{A_{l}},\models\psi_{\varphi}(x_{A}, y_{A})$As$AI_{0}$is$(\mathrm{K}_{01}<)$$G_{(\mathfrak{U},a,b)}=G_{(M_{\}}a,b)}$A-generic, there exists,, where$|\Re^{\mathfrak{H}_{A_{n}}}(*, x_{A}, y_{A})|\geq n$$\mathfrak{H}_{A_{1}},\simeq \mathfrak{U}<\lambda I_{0}$. Since

A $|\Re(*, y, z)|\geq n$ .

Th(I ) and
By compactness, there exist infinite $II$
$G_{(M,a’,b’)}$ is definable in M.

,

$|=|$

$I_{0}$$\models\varphi,\cdot \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e}$$b’\rangle$

Theorem 2.11. Th(M ) has strict order property.
$I_{0}$

be the graph as follows;
Vertices:
Edges: $\{(b_{i}, c_{j}) : 0\leq \mathrm{i}<j<n\}$Proof. Let$\bullet$$\bullet$$G_{(\mathfrak{H}_{A_{71}}\cdot x_{A_{n}},y_{A_{n}})},\simeq$$x_{A}y_{A}\vdasharrow ab$$\mathrm{T}\mathrm{h}(\Lambda I_{0})\vdash\exists yz\psi_{\varphi}(y, z)$$G_{(M,a}$.

$A_{n}$$\{b_{i} :\mathrm{i}<n\}\cup\{c_{i} :\mathrm{i}<n\}$$a’$, $b’\in II$ such that$\square$46

Let $a_{i}=(b_{i}, c_{l})$ , and $\varphi(xy, zw)\equiv R(x, y)\Lambda R(z, w)\Lambda R(x, w)\Lambda\neg R(x, z)\Lambda$.
$\neg R(y, w)\Lambda\neg R(y, z)$ . Then
By Lemma 2.9, we can find a linear (uniformly definable) ordering of arbihas the strict. By compactness, we see that
traily finite length inorder property.
$A_{n}\models\varphi(a:, aj)\Leftrightarrow \mathrm{i}<j<n$$\mathrm{T}\mathrm{h}(\mathbb{J}I_{0})$$BI_{0}$$\square$

3. REVIEW OF STRONG ORDER
This section consists of Shelah’s results in [Sh].

$\mathrm{p}_{\mathrm{R}\mathrm{O}\mathrm{P}\mathrm{E}\mathrm{R}\mathrm{T}\mathrm{Y}}$Definition 3.1. A complete theory T has -strong order property, denoted
and a sequence ( : iy)if there exists a formula$N$ ofsuch thatin some model
for $i<j<\omega$(1)-loops;nois(2) there, ,$n$$\varphi(x,$$\mathrm{S}\mathrm{O}\mathrm{P}_{n}$$(1\mathrm{h}(x)=1\mathrm{h}(y))$$a_{\mathrm{t}}$

$<$

$T$

$\vee\prime \mathit{0})$$N\vdash-\varphi(a_{i}, dj)$

$n-\varphi$$N\models\neg\exists x_{0}$Fact 3.2.
(2)(3) if$\ldots x_{n-1}\varphi(x_{0}, x_{1})\Lambda\varphi(x_{1}, x_{2})\Lambda\cdots\Lambda\varphi(x_{n-2}, x_{n-1})$$x_{1}$.
(1) SOP implies
implies SOPn.
, then has the tree property.
has$\mathrm{S}\mathrm{O}\mathrm{P}_{n}$$\mathrm{S}\mathrm{O}\mathrm{P}_{n+1}$

$T$

$T$

$\mathrm{S}\mathrm{O}\mathrm{P}_{3}$Proof. (1): By way of contradiction, suppose that
So, there exist$\varphi(x, y)$$\varphi(x, x_{0}))$$\varphi(x, x_{1}))\Lambda\exists x(\neg\varphi(x, x_{0})$but it is impossible.
, a model(2): Letmay assume that
two cases, whether$\varphi(x, y)$$\mathrm{A}I|=\exists x_{0}|$’$\mathrm{A}I$

N$$\forall x(\varphi(x, a_{i})arrow$$\psi(x_{0}, x_{1})=\forall x(\varphi(x, x\mathrm{o})arrow$$\varphi(x, a_{\mathrm{i}}))\Lambda\exists x(\neg\varphi(x, a_{i})\Lambda\varphi(x, a_{\mathrm{j}}))$$(a_{i} :has SOP and NSOPn.
such that$T$, $N\models T$ and (a :for $\mathrm{i}<j<d$ . Let. As has $NSOP_{n}$ , there exists
A$\mathrm{i}<"$ ) $)\subset$T$$n-\psi$-loop,. We
be witness for, andis indiscernible. We divide the arugum ent into$(a_{i} :\mathrm{i}<ul)$$\in I\downarrow I$$\mathrm{S}\mathrm{O}\mathrm{P}_{n+1}$\mathrm{i}<\omega)$. . . $x_{n-1}[x_{0}=a_{1}$ A $x_{n-1}=a_{0}$ A$i,j<n,k\equiv t+1(\mathrm{m}\mathrm{o}\mathrm{d}n\rangle\Lambda^{\varphi(x_{i},x_{j})}$or not.
,...
The case that,
, we haveAs. By the way,
, be the witness for , . . .
Let , ,$(n+1)-\varphi$
a contradiction.
-loop,,
is an, ,...
, so,...
The case that,Put
-loops never exist.
Then $AI$ $\models\psi(a_{i}, a_{i})(i<j<\omega)$ , andimpliesand “
be such thatand(3): Let’and(strongly limit singular cardinal of cofinality ). Put
1$\lambda I$$\Lambda I$$a_{1}\equiv_{a_{0}}a_{2}$$a_{2}$$c_{1}$$\varphi(a_{0\}}a_{1})$$\ldots$$c_{n-2}$$\models\exists x_{0}$$x_{n-1}[x \mathit{0}=a_{2}\mathrm{A}x_{n-1}=a_{0}\Lambda\bigwedge_{i,j<n,k\equiv t+1\langle \mathrm{m}\mathrm{o}\mathrm{d}n)}\varphi(xi, xj)]$$x_{0}$$\mathrm{c}\mathrm{n}_{-}2$$a_{1_{7}}a_{2}$$\ldots$$a_{0}$$\lambda I$$x_{n-1}$$\vdash\varphi(a_{1}, a_{2})\Lambda$$a_{0}$$c_{1}$$\Lambda I\mathrm{p}\geq$$\bullet$$x_{n-1}[x_{0}=a_{1} \Lambda x_{n-1}=a_{0}\Lambda\bigwedge_{i,j<n,k\equiv l+1\langle \mathrm{m}\mathrm{o}\mathrm{d}n)}\varphi(xi, xj)]$$\vdash\exists x_{0}$$x_{n-1}[x_{0}=a_{1} \Lambda x_{n-1}=a\mathrm{o}\Lambda\bigwedge_{i,j<n,k\equiv l+1(\mathrm{m}\mathrm{o}\mathrm{d}n)}\varphi(x_{i}, xj)]$$\exists x_{0}$$\mathrm{A}(x, y)\equiv\varphi(x, y)\Lambda\urcorner\exists x_{0}$$\ldots$$x_{n-1}[x_{0}=x \mathrm{A}x_{1}=y]\Lambda\bigwedge_{i,j<n,k\equiv l+1(\mathrm{m}\mathrm{o}\mathrm{d}n)}\varphi(xi, xj)$

$n-\psi$$\kappa=\mathrm{c}\mathrm{f}(\kappa)>|T|$$2^{\mu}<\lambda^{\mathrm{t}}$$\lambda>\kappa$$\mathrm{c}\mathrm{f}(\lambda)=\kappa$$\kappa$$\mu<\lambda$$J=\kappa\lambda$.

47

large enough.
be such that
iff $\eta(i)=0$ for every. By compactness, there exist a sequenceLetbe the witnee forfor any $\eta<\nu$ .
in some modelshch that $II$,
The lexicographic order on I is as usual; if 2 is the least such that.
then
A. Fix an.
We may assume that is -saturated, andas follows.
We will define$x)$ :
, )A
Put
}.
{ (
,
and
,
Note that$I\subset J$$\mathrm{i}<\kappa$$\eta\in I$$\varphi(x, y)$$(a_{\eta} :$\mathrm{S}\mathrm{O}\mathrm{P}_{3}$\eta\in I)$$\mathrm{A}I$$\models\varphi(a_{\eta}, \mathrm{a}\mathrm{v})$$\eta|\mathrm{i}=\nu|\mathrm{i}$$\eta(\mathrm{i})=\nu(\mathrm{i})$$\kappa^{+}$$\lambda I$$\eta\in\kappa(\lambda\backslash \{0\})\backslash I$$|\lambda^{J}I|\geq$$a_{\eta}$$p_{\eta}=$$\varphi$$x$$a_{(\eta|i)0_{\mathrm{l}i,\kappa)}}$$(\eta|i)0_{[i,\kappa)}$$(\eta|\mathrm{i}, \eta(i)+1)0_{(i,\kappa)}\in I$$a_{(\eta|i\eta(i)\}0_{\langle i,\kappa)}}\models\varphi\{a_{(\eta|i)0_{\mathrm{l}i,\kappa)}}$As$\lambda I$

is$\kappa^{+}$

Claim. if$\mathrm{i}<\kappa$$\varphi(a_{(\eta|i,\eta(i)+1)0_{(i,\kappa\rangle}},$,$x)\Lambda\varphi(a_{(\eta|i\eta(i)+1)0_{\iota i,\kappa\}}}, x)$.

-saturated, there exists a realization of$\eta_{1}\neq\eta_{2}\in\kappa(\lambda\backslash \{0\})\rangle$

then$p_{\eta}$in$\Lambda I$$\eta_{1}<\eta_{2}$$\eta_{2}(\mathrm{i})$$\eta_{1}<\nu$$\nu$$\nu_{2}(i+1)$Asof$\varphi(x, a_{\rho})\in p_{\eta_{2}},\mathrm{a}\mathrm{n}\mathrm{d}\lambda I$$|=\varphi(a_{\nu}, a_{p})$$c$$p_{\eta_{1}}\cup p_{\eta 2}$$c$

We also have$|p_{\eta}|=\kappa,$$\eta\in\kappa(\lambda\backslash \{0\})\}\subseteq\{a_{\nu} :By(by$7\mathrm{J}(3)$$a_{\mu}$$a_{\rho}$.

$\eta_{1}|\mathrm{i}=\eta_{2}|\mathrm{i}$,$\eta_{1}(i)<$$<\eta_{2}$,,, $\rho(j)=0(j>\mathrm{i}+1)$ .
,, say , then , ,$\varphi’(x_{7}a_{\nu})\in p_{\eta_{1}}$$<\rho$$\rho(\mathrm{i})=\nu_{2}(\mathrm{i})$$\nu(\mathrm{i})=\eta_{1}(\mathrm{i})+1$$a_{\eta}$

is inconsiient.

$p_{\eta_{1}}\cup p_{\eta_{2}}$. Then there exists $i<\kappa$ such that
Suppose thatas follows.
. Take $<\rho\in I$ be with$\eta_{1}|\mathrm{i}=\eta_{2}|\mathrm{i}=\nu|\mathrm{i}=\rho|\mathrm{i}$, saywould be the$|\cup\{\mathrm{D}\mathrm{o}\mathrm{m}(p_{\eta}) :$3-\varphi$, $\nu(j)=0(j>\mathrm{i})$ , $\rho(\mathrm{i}+1)=$, if we found the realization-loop, a contradiction.

\eta\in\kappa(\lambda\backslash \{0\})\}|\leq$A (as$\cup\{\mathrm{D}\mathrm{o}\mathrm{m}(p_{\eta})$:\nu \in I\})$and 7.6(2) on p.141 of Shelah’s 2nd editon book, A) and $\kappa>|T|$ imply that has the tree property.

$=\lambda^{<\kappa}>2^{|T|}$$T$$\mathrm{c}\mathrm{f}(\lambda)=\kappa<\lambda$$\square$is a good dividing line for existence of universal
It is conjectured that, it will have universal models of carmodels, i.e. if does not havedinality A $>|T|$ (Shelah showed that if is simple and A $>|T|$ , then there. As the above, simplicity implies
exists universal models of cardinality$\mathrm{S}O\mathrm{P}_{4}$$T$$\mathrm{S}\mathrm{O}\mathrm{P}_{4}$$T$$\lambda^{++}$$N\mathrm{S}\mathrm{O}\mathrm{P}_{3}.)$4.

$\mathrm{T}\mathrm{h}(\lambda I_{f})$$\mathrm{D}$OES NOT HAVE$\mathrm{S}\mathrm{O}\mathrm{P}_{4}$be a local rank on relational finite structures such that $\delta(A/B)\leq$
be upper un$\delta(A/A\cap B)$ , where. Let ::
bounded and monotone increasing. Let$A)\}$ and $\beta(x\rangle=\min\{\grave{\delta}(X/A) : A<X\in \mathrm{K}0, A\neq X, |X|\leq x\}$ .

Let$\delta$$f$$\delta(A/B)=\mathrm{S}(\mathrm{A}\mathrm{B})-\vec{\delta}(B)$$\mathrm{K}_{f}=\{A\in$

Fact 4.1. Suppose that$f’(x) \leq\frac{\beta(x)}{x}$.

$\mathbb{R}^{\geq 0}arrow \mathbb{R}^{\geq 0}$$\mathrm{K}0$$\overline{\delta}(X)\geq f(|X|)(\forall X\subseteq$

48

exists,$<)$ -genericis closed under free amalgamation, so
Then
and Th(A//) is -categorical. ( -categoricity follows fromacl incl
for finite graphs.)
and let $C=B_{1}\otimes_{A}B_{2}$ . We need to show
Proof. Let $A<B_{1}$ ,$\delta(X)\geq
f(|X|)$. We may assume that $X<C$ , because, thenthat ifand $f(|\mathrm{c}1(X)|)\geq f(|X|)$ .
$\langle$$\mathrm{K}_{f}$$=$$\omega$$\Lambda I_{f}$$llI_{f}$$\mathrm{K}_{f)}$$\omega$$|\mathrm{c}1(*)|\leq f^{-1}(\delta(*))$$B_{2}\in \mathrm{K}_{f}$$X\underline{\subset}C$$\delta(X)\geq\tilde{\delta}(\mathrm{c}1(X))$

Let $X_{i}=X\cap B_{i}(i=1,2)$ and let $X_{0}=X\cap A$ . Suppose that$\frac{\delta(X_{1})-\delta(X_{0})}{|X_{1}|-|X_{0}|}\leq\frac{\tilde{\delta}(X)-\delta(X_{0})}{|X|-|X_{0}|}\leq\frac{\delta(X_{2})-\overline{\delta}(X_{0})}{|X_{2}|-|X_{0}|}$

As $X_{0}<X_{1}$ ,$f’(|X_{1}|)$$\beta(|X_{1}|)\leq \mathrm{H}\mathrm{X}\mathrm{t}/\mathrm{X}\mathrm{o})$. So, the line between

Therefore.

$(|X_{0}|, 6(\mathrm{X}0)$and.

$\frac{\tilde{\delta}(X_{1})-\grave{\delta}(X_{0})}{|X_{1}|-|X_{0}|}\geq\frac{\beta(|X_{1}|)}{|X_{1}|}\geq$$(|X_{1}|, \delta(X_{1}))$lies above . As$f$

is decreasing and $\delta(X_{1})\geq f(|X_{1}|)$ , $\delta(X)\geq f(|X|)$ follows.
Let $d(A)=\delta(\mathrm{c}1(A))$ , and $d(a/A)=\delta(\mathrm{c}1(aA)/\mathrm{c}1(A))$ . For possibly infinite, let $d(a/B)= \inf\{d(a/B_{0}) : B_{0}\subset_{\omega}B\}$ .
.
ucture having -rank. Let , ,be a relational
Fact 4.2. $Lei$. Then $d(a/B)=d(a/A)$
Suppose that $A<B<$ IX and
.
$\cap
B=A$
and
,
iff
$\square$

$f’$

$B$

$st$

$\mathcal{M}$$a$$\grave{\delta}$$A$$B\subset_{\omega}\mathcal{M}$$\mathrm{c}1(aA)\subset_{\omega}\mathcal{M}$$\mathrm{c}1(aA)B=\mathrm{c}1(\mathrm{a}\mathrm{A})$$\mathrm{c}1(aA)$$cl(aA)B\leq \mathrm{c}1(aB))$

Proof. As

So,$d(aB)=\grave{\delta}(\mathrm{c}1(aA)B)(\mathrm{i}.e$$\otimes_{A}B$.

$A<\mathrm{c}1(aA)$ $\cap B$

or$A=\mathrm{c}1(aA)$ $\cap B$)$\tilde{\delta}(\mathrm{c}1(aA)/\mathrm{c}1(aA)\cap B)\leq 6\{\mathrm{c}\mathrm{l}\{\mathrm{a}\mathrm{A}$$/\mathrm{B}$, we have$\delta(A)$$\leq\delta(\mathrm{c}1(A)\cap B)$). Therefore$d(a/B)\leq 6\{\mathrm{c}1\{\mathrm{a}\mathrm{A})/\mathrm{B})\leq\tilde{\delta}(\mathrm{c}1(aA)/\mathrm{c}1(aA)\cap B)\leq\delta(\mathrm{c}1(aA)/A)=d(a/A)$

Now we can see the conclusion.
,
By Fact 4.2, for , ,
$a$

$b$

.

.
$\square$$A\subset_{\omega}\mathcal{M}$$d(a/Ab)=d(a/A)\Leftrightarrow d(b/Aa)=d(b/A)$.

,(By $d(a/Ab)=d(a/A)\Leftrightarrow$ “”.)
Prom now on, we assume that the control function f saitsfies$\mathrm{c}1(aA)\cap \mathrm{c}1(bA)$$=\mathrm{c}1(A)$$\mathrm{c}1(aA)\mathrm{c}1(bA)$$=cl(aA)\otimes_{\mathrm{c}1(A\}}$$\mathrm{c}1(bA)\leq \mathrm{c}1(abA)$,,. Letbe the class of possibly infinite structures whose finite: $\delta(A)<f(|A|)$ , $|A|<$. Let
substructures are all in. Note that if. Then. Let
be a big model of, then.
, $d(a/A)=d(a/Ab)$ ,, if
Proposition 4.3. Suppose that, in$=A$ , ifeen there exists
such that $d(a/A_{0}b)=$$d(a/A_{0})$ . THEN
has.
“ $f’(x) \leq\frac{\beta(x)}{x}$$\overline{\mathrm{K}_{f}}$$T_{f}=\{\forall x\neg \mathrm{D}\mathrm{i}\mathrm{a}\mathrm{g}_{A}(\overline{X})$$\mathrm{K}_{f}$$\lambda I$$\omega\}$$A\subset_{\omega}\mathcal{M}$$|^{=}|T_{f}\Leftrightarrow \mathit{1}I$$\mathcal{M}$$\in\overline{\mathrm{K}_{f}}$$A\in \mathrm{K}_{f}$$\mathcal{M}$$\mathrm{c}\mathrm{l}(\mathrm{a}\mathrm{A})$$\lambda I_{f}$$\cap \mathrm{a}\mathrm{c}\mathrm{l}(6\mathrm{A})$$\mathrm{T}\mathrm{h}(\mathbb{J}I_{f})$$A=\mathrm{a}\mathrm{c}\mathrm{l}(\mathrm{j}4)$$A_{0}\subset_{\omega}$$N\mathrm{S}\mathrm{O}\mathrm{P}_{4}$

$A$

48

Proof. Let$(a_{i} :be an infinite indiscernible sequence in. We will show that\mathrm{i}<\omega)$$p(x_{0}x_{1})=\mathrm{t}\mathrm{p}(a_{0}a_{1})$$\mathcal{M}$. Put$p(x_{0}x_{1})\cup p(x_{1}, x_{2})\cup p(x_{2}x_{3})\cup p(x_{3}x_{0})$is consistent.

Claim. There exists
such that $(a_{i} : i<\omega)$ is B-indiscernible,$d(a_{2}/Ba_{0}a_{1})=d(a_{2}/Ba_{1})=d(a_{2}/B)$. (Then,and$d(a_{2}/Ba_{2})$ follows.)$B\mathrm{C}_{\omega}\mathcal{M}$$a_{2}\equiv_{a_{0}}a_{1}$Extend $(a_{i} : i<\omega)$ to$(a_{i} :\mathrm{i}<\mathbb{Z})$. As$(a_{i} :is indiscernible overi\geq 0)$$\mathrm{d}(\mathrm{a}2/\mathrm{B}\mathrm{a}\mathrm{o}\mathrm{a}\mathrm{i})=$is indiscernible over. As
, we see that $d(a_{i}/A_{0}a_{<i})=d(a_{i}/A_{0})$ .
By extendingover
and applying Erdos-Rado Theorem, we
may assume thatis constant for any $\mathrm{i}<j<k$ ,over.
)and (c4 :is indiscernible
Now, by our assumption, takesuch that.
as desired. The claim is proven.
$(a_{i} :\mathrm{i}<0)$,$(a_{i} :\mathrm{i}\geq 0)$$\mathrm{a}\mathrm{c}1(a_{i} :\mathrm{i}<0)=:A_{0}$$a_{<i}\equiv_{a_{i}}a_{<0}$$(a_{i} :\mathrm{i}\geq 0)$$A_{0}$$\mathrm{a}\mathrm{c}1(A_{0}a_{k})\cap \mathrm{a}\mathrm{c}1(A_{0}a_{i}a_{j})=:C$$C$$\mathrm{i}\geq 0$$B\subset_{\mathrm{t}B}C$$\mathrm{d}\{\mathrm{a}2/\mathrm{B}\mathrm{a}mathrm{a}\mathrm{i})=\mathrm{d}(\mathrm{a}2/\mathrm{B})$As $d(a_{2}/Ba_{0}a_{1})=d(a_{2}/B)$ , we have$\mathrm{c}1(a_{2}B)\mathrm{c}1(a_{0}a_{1}B)=\mathrm{c}1(a_{2}B)\otimes_{\mathrm{c}1(B\rangle}\mathrm{c}1(a_{0}a_{1}B)$As$\mathrm{c}1(\mathrm{a}\mathrm{o}\mathrm{a}\mathrm{i}\mathrm{a}2\#)\in \mathrm{K}_{f}$$\leq \mathrm{c}1(a0a_{1}a_{2}B)$.

, we may assume that$\mathrm{c}1(a_{0}a_{1}a_{2}B)<BI_{f}$.

, ,A such that
. we haveSo, we can work inside$d_{M_{f}}(a_{2}/Ba_{0}a_{1})=d_{M_{f}}(a_{2}/B).)$is B-ind iscernibie and. By $d(a_{2}/Ba_{0}a_{1})$ $=d(a_{2}/Ba_{1})$ and Fact,
Let
. And $C_{/0,1}\cap C_{0,2}=C_{0}$ an
4.2, we see that$=d(a_{2}/Ba_{1})$$C_{1,2}\cap C_{0,2}=C_{2}$ follow by $d(a_{2}/Ba_{0}a_{1})$, $d(a_{1}/Ba_{0}a_{2})=d(a_{1}/Ba_{2})$and Fact 4.2. So we have$a_{07}a_{1}$$\Lambda I_{f}.(\mathrm{i}.\mathrm{e}$$C_{i,j}=\mathrm{c}1(a_{i}a_{J}B)$$a_{2}$$B\subset_{\omega}$$(a_{0}, a_{1}, a_{2})$$I_{f}$$C_{i}=\mathrm{c}1(a_{i}B)$$C:=c_{0}^{\gamma},,{}_{1}C_{1.2}=C_{0,1}\otimes_{C_{1}}C_{1,2}$$C\cap \mathrm{C}0,‘ \mathrm{i}$$\mathrm{d}$$=\mathrm{C}0)2=C_{0}\otimes_{B}C_{2}<C$.

to a2a$, andbe an isomorphism over $B$ sending$g’=g\circ
f$
.
map.
As
is closed
Put
be
the
inclusion
let :
$h’$
such that
under free amalgamation, there exist $D\in K_{f}$ and , :. We may assume thatand
. Put $a_{0}’=h\circ g(a_{0})$ , $a_{1}’=h(a_{1})$ , $a_{2}’=h’\circ g’(a_{2})$ , $a_{3}’=h’(a_{1})$ .
Let

$f$

:

$C_{0}C_{2}arrow C_{2}C_{0}$$a_{0}a_{2}$$C_{0}C_{2}arrowarrow C$$g$$\mathrm{K}_{f}$$h$$h\mathrm{o}g|C_{\acute{0}}C_{2}=h’\mathrm{o}g’|C_{0}C_{2}$$C\mathrm{c}arrow D$$D=h(C)\otimes_{h\circ g(C_{0}C_{2}\rangle}\mathrm{h}(\mathrm{C})$$D<\mathrm{A}I_{f}$Claim.

$a_{0}’a_{1}’$,$a_{1}’a_{2}’$,$a_{2}’a_{3}’$,$a_{3}’a_{0}’\vdash p=\mathrm{t}\mathrm{p}(a_{0}a_{1})$. (’This proposition is proven.)

Note that$h(a_{0}a_{1})$$=a_{0}’a_{1}’$, $h(a_{1}a_{2})=a_{1}’a_{2}’$ ,$h’(a_{0}a_{1})$$=(h’\mathrm{o}g’(a_{2}))a_{3}^{l}=$a2a$,$h’(a_{1}a_{2})=a_{3}’(h’\mathrm{o}g’(a_{0}))=a_{3}’(h\mathrm{o}\mathrm{g}(\mathrm{a}0), =a_{3}’h(a_{0})=a_{3}’a_{0}’$.

50

On the other hand,$h(C_{0,1})$, $h(C_{1,2})<h(C)<D<\mathrm{A}I_{f}$ ,, $h’(C_{1,2})<h’(C)<D<\Lambda I_{f}$ .
Put $B’=h\circ g(B)=h’\circ g’(B\rangle$ . Then$h’(C_{0,1})$$h(\mathrm{c}1(a_{0}a_{1}B))=h(C_{0,1})=\mathrm{c}1(a_{0}’a_{1}’B’)$, $h(\mathrm{c}1(a_{1}a_{2}B))=h(C_{1,2})=\mathrm{c}1(a_{1}’a_{2}’B’)$ ,$h’(\mathrm{c}1(a_{0}a_{1}B))=h’(C_{0,1})=\mathrm{c}1(a_{2}’a_{3}’B’)$

By genericity of$\lambda I_{f}$, $h(\mathrm{c}1(a_{1}a_{2}B))=h(C_{1,2})=\mathrm{c}1(a_{3}’a_{0}’B’)$ .

, we see that.

$\mathrm{d}(\mathrm{a}\mathrm{o}\mathrm{a}\mathrm{i}\mathrm{B})\equiv \mathrm{c}1(a_{1}a_{2}B)\equiv \mathrm{c}1(a_{0}’a_{1}’B’)\equiv \mathrm{c}1(a_{1}’a_{2}’B’)\equiv \mathrm{c}1(a_{2}’a_{3}’B’)\equiv \mathrm{c}1(a_{3}’a_{0}’B’)$cs
A such, there exists
Remark 4.4. Suppose that for any , CI
holds.
4.3. Then the assumption of Proposition
that $d(a/A)$
$a$

$A$

$A_{o}\subset_{\omega}$$\mathrm{A}$$=\mathrm{d}(\mathrm{a}/\mathrm{A}\mathrm{o})$,such that $d(a/Ab)=d(a/A_{0}b)$ and $d(a/A)\square =$Take$d(a/A_{1})$ . Then $d(a/A_{0}A_{1})=d(a/A_{0}A_{1}b)$ .

Proof.

$A_{0}$$A$$A_{1}\subset_{\omega}$

5. REVIEW OF EVANS’ PAPER ON SIMPLE -CATEGORICAL GENERIC$\omega$

STRU CTURES

Let 6 be a local rank on relational finite structures such that $\delta(A/B)\leq$
be upper. Let :(A ), where 6
unbounded, monotone increasing, convex ( $f’(x)$ is monotone decreasing) and$(\mathrm{A}/\mathrm{B})=\mathrm{S}$$6(\mathrm{A}/\mathrm{A}\cap B)$$\mathrm{f}(\mathrm{x})\leq\underline{\beta(x)}$Let, where$\mathrm{K}_{f}=\{Ax\in \mathrm{K}_{0} :$\mathrm{B}$$f$$-\mathrm{g}(\mathrm{B})$$\mathrm{f}(\mathrm{x})=\mathrm{f}\mathrm{f}\mathrm{l};\delta(X/A)$:$\mathbb{R}^{\geq 0}arrow \mathbb{R}^{\geq 0}$$A<X\in \mathrm{K}_{0},$ $A\neq X,$\mathrm{f}(\mathrm{x})\geq f(|X|)(\forall X\subseteq A)\}$$|X|\leq x$}.

.

The following fact is Corollary 2.20 of [E1].
(bigbe-generic. And suppose the condition on
Fact 5.1. Let
model ofas in Proposition 4.3. Furthemore, suppose the following.
)(1) ( -extension property inLetbe algebraically closed and
A4. Then there
andsuch thatexists$\lambda I_{f}$$\mathcal{M}$$(\mathrm{K}/, <)$$\mathrm{T}\mathrm{h}(\lambda I_{f}))$$d$$\mathcal{M}$$A\subset B\subset \mathcal{M}$$c\subset_{\omega}$$c’\subset_{\omega}\mathcal{M}$$\mathrm{a}\mathrm{c}1(c’A)\cap B=A$$\mathrm{t}\mathrm{p}(c/A)=\mathrm{t}\mathrm{p}(\mathrm{c}/\mathrm{A})$$\mathrm{d}(\mathrm{c}/\mathrm{B})=d(c/A)$.

)(2) (Independen ce theorem over finite closed sets in$B_{1}\cap
B_{2}=A$
and $d(B_{1}/B_{2})=$
Let , ,
be finite such that$d(B_{1}/A)$ . Suppose thatand $d(c_{i}/B)=$,I ,$d(c_{i}/A)$ . then there exists
andsuch that$d(c/B_{1}B_{2})=d(c/A)$ .
THEN
is simple and ’and, for , algebraically closed in.
$\Lambda I_{f}$$A$$B_{1}$$B_{2}<\lambda I_{f}$$c_{1}$$c_{2}\mathrm{C}_{\omega}$$I_{f}$$c\subset_{\omega}\mathrm{A}I_{f}$$\mathrm{T}\mathrm{h}(fiI_{f})$

$A$

$A$

$B$

$\mathrm{t}\mathrm{p}(c_{1}/A)=\mathrm{t}\mathrm{p}(c_{2}/A)$$\mathrm{t}\mathrm{p}(c/B_{i})=\mathrm{t}\mathrm{p}(c_{i}/B_{i})$$‘ c\mathrm{L}_{A}\backslash B\Leftrightarrow d(c/B)=d(c/A)$$\mathcal{M}"$$\mathrm{a}\mathrm{c}1(cA)\cap B=$

51

We give the proof of the following lemma.(Theorem 3.6 of [E1])Lemma 5.2. Supose that -extension property over finite closed sets in A4
and $f(3x)\leq f(x)+\beta(x)$ . Then the independence theorem over finite closed
sets holds in A .
$d$$I_{f}$

Proof. Let$c_{i}$,$B_{i}$$E_{12}=\mathrm{a}\mathrm{c}\mathrm{l}(\mathrm{B}\mathrm{i}\mathrm{J}32)$,,

be as in Fact 5.1. Then$A$

$E_{13}=\mathrm{a}\mathrm{c}1(c_{1}$D13,$E_{23}=\mathrm{a}\mathrm{c}\mathrm{l}(\mathrm{c}252)$

gamation and copies, we may assume that
$B_{1}=E_{12}\cap E_{13}$, $B_{2}=E_{12}\cap \mathrm{E}13$ ,,$B_{1}$,$B_{2}$$B_{3}$$:=E_{13}\cap$

A23$=\mathrm{a}\mathrm{c}1(c_{i}A)$

$A$

$d$

$B_{3}$.

Put. By considering free amal-, are -independent over ,Let $E=E_{12}E_{13}E_{23}$ . We need to show that $A<E$ and$B_{1}\cap B_{2}\cap B_{3}=A$$\simeq_{A}\mathrm{a}\mathrm{c}1(c_{2}A)$$\mathrm{a}\mathrm{c}1(c_{1}A)$,$E_{lj}E_{J^{k}}=E_{ij}\otimes_{B_{j}}E_{jk}$$E\in \mathrm{K}_{f}$.

.

Claim. A $<E$ .
, $E_{ik}E_{jk}\leq E$ follows.
. As
By Fact 4.2,
$E_{ik}<E_{ik}E_{jk}$follows. Thus
and $B_{k}<E_{jk}$ ,We also have$E_{ik}<E$ . As $A<B_{i}<E_{ik}$ , $A<E$ follows.
$E=E_{ij}\otimes_{B_{i}B_{j}}E_{ik}E_{jk}$$B_{i}B_{j}\leq E_{ij}$$E_{ik}E_{jk}=E_{ik}\otimes_{B_{k}}.E_{J^{k}}$Claim. E$\in \mathrm{K}_{f}$

.

. So
,
, but we do not have
We havewe can not conclude this claim by using Fact 4.1.
for any $D<E$ as in Fact 4.1.Put $D_{ij}=D\cap E_{ij}$We need to show
is the largest of these.
.
that
Supposeand, we may assume that $D\neq$ D12D2$. Put $D^{1}=D_{12}D_{13}$ . AsAs
$E_{12}E_{13}\leq E$ , we see that $D^{1}\leq D$ . As
and $D\cap B_{1}<$ D13,
$B_{i}B_{j}<E_{i_{J}}$$E=E_{ig}\otimes_{B_{i}B_{j}}E_{ik}E_{jk}$$E_{ik}E_{jk}$$\overline{\delta}(D)\leq f(|D|)$$d_{ij}=\delta(D_{ij})$$d_{12}$$E_{12}E_{23}\in \mathrm{K}_{f}$$D^{1}=D_{12}\otimes_{D\cap B_{1}}D_{13}$$\delta(D^{1})=d_{12}+\delta(D_{13}/D\cap B_{1})\geq d_{12}+\beta(|D_{13}|)$.

, $|D_{13}|\leq f^{-1}(d_{13})\leq f^{-1}(d_{12})$ .
As
So, as is monotone decreasing, $d_{12}\leq\delta(D^{1})-\beta(|D_{13}|)\leq\delta(D^{1})-\beta(f^{-1}(d_{12}))$ .
By our assumption on( $f(3x)\leq f(x)+\beta(x)$ , so 3 $f^{-1}(x)\leq f^{-1}(x+\beta(f^{-1}(x)))$ ,$d_{13}\leq d_{12}$$\beta$$f$

3 $f^{-1}(d_{12})=f^{-1}(d_{12}+\beta(f^{-1}(d_{12})))$ .

So, 3
and

$f^{-1}(d_{12})\leq f^{-1}(\tilde{\delta}(D^{1}))$$\grave{\delta}(D^{1})\leq\delta(D)$. As$|D| \leq\sum_{\dot{\tau}j}|D:j|\leq\sum_{ij}f^{-1}(d_{ij})\leq 3f^{-1}(d_{12})$, we see that$|D|\leq f^{-1}(\grave{\delta}(D))$.
$\square$52

6.

$\mathrm{T}\mathrm{h}(\mathrm{A}I_{f})$HAS$\mathrm{S}\mathrm{O}\mathrm{P}_{3}$FOR SOME $f$$=2|A|-e(A)$ . Note that $\beta(x)=$We work with undirected graphs, andis an upper unbounded, monotone. The control fuction :increasing satisfying the following five conditions;$\delta(A)$$\mathbb{R}^{\geq 0}arrow \mathbb{R}^{\geq 0}$

$f$

$1$

(F1): $f(0)=0$ , $f(2)$ $=2$ , $f(4)=3$ , $f(8)=4<f(10)<4 \frac{1}{2}<f(12)<5<$$f(14)<5 \frac{1}{3}<f$(F2): 2

(F3):(16) $<f(18)\leq 6$ .

$f’(2n) \leq\frac{1}{n}$$f( \frac{k^{2}}{2})\leq k$

for $n\geq 7$

if $k\geq 6$(F1): $f(3n)\leq/(\mathrm{n})+1$ for $n\geq 10$ .
(F3): $/(10)+1\geq f(14)$ , $f(12)+1\geq f(16)$ .

Let /3 (x) $=f(2x)$ . So, $f_{1}’(x)=2f’(2x)$ and F2:.
We consider$f_{1}’(n) \leq\frac{1}{n}$for $n\geq 7$ .

$K_{f_{1}}$(1) 6(3-cycle)
Remark 6.1.
.
does not belong to.
tobelongs
4-cycle$K_{f_{1}}$$6-3=3=f(4)<f(6)=f_{1}(3)$ , so 3-cycle-cycle $=8$ $-4=4=f(8)=f_{1}(4)$ , so$\delta 4$$K_{f_{1}}$does not belong to(2) The graph, because its -rank $=14-$$\delta$$\mathrm{K}_{f_{1}}$$9=5<f(14)=f_{1}(7)$ .

.
(3) (F1) and (F2) give the free amalgamation property of$G(A_{n}, B_{n}, x_{0})$ belong
graphs
the
show
that
to
(F3)
are needed(4) (F1) andto. (Lemma 6.4.)(5) (F4) is needed to show Subclaim 2 in the proof of Lemma 6.7. Lemmacan be closedly embedded
6.7 ensures that the important graphs
will give the witness formula for $SOP_{3}$ .
and the graphs
into(6) (F1), (F2) and (F5) are needed to show Lemma 6.6. (Lemma 6.6 gives
a very important key to get Lemma 6.7.)
and infinite
By the graphs $E_{n}<AI_{f_{1}}(n\in\omega)$ , we will give a formula
whenever $i<j$ . But if
sequenceinsuch that, then $N$ would have the-loop in some model $N$ of
there were a$(\mathrm{K}_{f_{1}}, <)$$\mathrm{K}_{f_{1}}$$E_{n}$$E_{n}$$\mathrm{A}I_{f_{1}}$$\varphi(x, y)$$(a_{i})_{i<\omega}$$3-\varphi$$\lambda I_{f_{1}}$$\lambda I_{f_{1}}\models\varphi(a_{i}, a_{j})$$\mathrm{T}\mathrm{h}(\lambda I_{f_{1}})$

53

graph as in (2) of Remark 6.1. As any finite graph of $N$ belongs tofollows.

$\mathrm{K}_{f_{1}}$, so$\mathrm{S}\mathrm{O}\mathrm{P}_{3}$Lemma 6.2.

$\mathrm{K}_{f}1$

has the free amalgamation property.

and let $C=B_{1}\otimes_{A}B_{2}$ . We need to show
Let $A<B_{1}$ ,, then. We may assume that $X<C$ , becausethat ifand $f_{1}(|\mathrm{c}1(X)|)\geq f1(|X|)$ .
i5

Proof

$B_{2}\in \mathrm{K}_{f}$$X\subseteq C$$\mathrm{S}(\mathrm{X})\geq f_{1}(|X|)$$(X|)\geq\delta(\mathrm{c}1(X))$

Let $X_{i}=X\cap B_{i}(\mathrm{i}=1,2)$ and let $X_{0}=X\cap A$ . Suppose that
, $|X_{1}|\geq 7$ .

$\frac{\delta(X_{1})-\delta(X_{0})}{|X_{1}|-|X_{0}|}\leq\frac{\delta(X)-\grave{\delta}(X_{0})}{|X|-|X_{0}|}\leq\frac{\delta(X_{2})-\grave{\delta}(X_{0})}{|X_{2}|-|X_{0}|}$

As $X_{0}<X_{1}$ ,$f_{1}’(|X_{1}|)$$\beta(|X_{1}|)\leq\delta(X_{1}/X_{0})$. So, the line between. So, by (F2),$(|X_{0}|,\overline{\delta}(X_{0}))$and$\frac{\delta(X_{1})-\overline{\delta}(X_{0})}{|X_{1}|-|X_{0}|}\geq\frac{1}{|X_{1}|}\geq$

is decreasing and
1, we give the proof when $|X_{1}|\leq 6$ .
$\delta(X_{1})$$f_{1}’$

lies above . As
follows. In Appendix$(|X_{1}|, \delta(X_{1}))$$\geq f_{1}(|X_{1}|),\tilde{\delta}(X)\geq f_{1}(|X|)$$f_{1}$$\square$Notation 6.3. Consider the following graphs $G(A_{n}, B_{n}, x_{0})$ for each $n<\omega$ .
:Vertex set: $A_{n}\cup B_{n}\cup\{x_{0}\}\cup\{ztj : 0\leq \mathrm{i}<j\leq n\}$ , where$0\leq j\leq n\}$ , $B_{n}=\{b_{i} ; 0\leq i\leq n\}$ .
for
,
and
for
,
1 Edges:$A_{n}=\{a_{\mathrm{t}}$$\bullet$$R(x_{0}, a_{i})$$0\leq \mathrm{i}<j\leq n$

Lemma 6.4.

(1)$\mathrm{S}(\mathrm{X}0)b_{\mathrm{i}})$$0\leq \mathrm{i}\leq n$$R(z_{ij}, a_{i})$$R(z_{ij}, b_{j})$.

$G(A_{n}, B_{n}, x_{0})\in \mathrm{K}_{f_{1}}$(2) $x_{0}A_{n}<G(A_{n}, B_{n}, x_{0})$(3) $d(A_{n}/B_{n})=d(A_{n}/x_{0})$ , where$d(*)=d_{G\langle A_{11},B_{n},x_{0})}(*)$.

, $B=B_{n}$ , $Z=\{z_{ij} : 0\leq \mathrm{i}<j\leq n\}$ .
,$\geq f_{1}(|X|)$ . It is clear in case(1): It suffices to show that if $X<G$ , then$b\in
X$ , then $\delta(x_{0}/ab)=0$ , so$x_{0}\in
X$
,
. (If
of $|X|=1$ . If $|X|\geq 2$ , then(ab)\subset X.)

Proof. Put$G=G(A_{n}, B_{n}, x_{0})$ $A=A_{n}$$\overline{\delta}(X)$$x_{0}\neq a$$x_{0}\in \mathrm{c}1_{G}$Claim,$a_{i}$,$b_{j}\in X\Leftrightarrow z_{ij}\in X$.

(
This claim follows from $\tilde{\delta}(z_{ij}/a_{i}b_{j})=S(ai/xoZij)$$X<G$ .

$=\tilde{\delta}(b_{j}/x_{0}z_{ij})=0$

and

Put $X_{A}=X\cap A_{n}$ , $X_{B}=X\cap B$ , $X_{Z}=X\cap Z$ and $m=|X_{A}|+|X_{B}|$ . By
claim, we see that $\delta(X_{Z}/x_{0}X_{A}X_{B})=0$ , so we have$\delta(X)=\tilde{\delta}(x_{0}X_{A}X_{B})=2(m+1)-m=m+2=:k1$

54

As $|X_{Z}| \leq|X_{A}||X_{B}|\leq|X_{A}|(m-|X_{A}|)=(\frac{m}{2})^{2}-(|X_{A}|-\frac{m}{2})^{2}\leq(\frac{m}{2})^{2}$, we
have$|X| \leq 1+m+(\frac{m}{2})^{2}=(1+\frac{m}{2})^{2}=\frac{k^{2}}{4}$, as desired.
If $k\geq 6$ , by (F3),and $\delta(X)=$
If $k\leq 5$ , then $|X_{A}|+|X_{B}|\leq 3$ . If $|X_{A}|=3$ , then
2 . $4-4=4=f_{1}(4)$ .
2 $\cdot 5-5=5>f_{1}(6)>f_{1}(5)$If $|X_{A}|=2_{j}|X_{B}|=1$ , then
2 $\cdot 4-3$ $=5>f_{1}(6)>f_{1}(5)$and $\delta(X)=2\cdot 3-2=4=f(8)>f(6)=$
If $|X_{A}|=2$ , $|X_{B}|=0$ , then$\delta(X)=k\geq f(\frac{k^{2}}{2})=f_{1}(\frac{k^{2}}{4})\geq f_{1}(|X|)$$X_{Z}=\emptyset$$\delta\backslash (X)\geq\{$$X_{Z}=\emptyset$$f_{1}(3)$.

If $|X_{A}|=1$ , $|X_{B}|=0$ , thenBy symmetry, we see that

$X_{Z}=\emptyset$$X\in \mathrm{K}_{f_{1}}$(2)$X<G$ . By \dag er we have$:\mathrm{L}\mathrm{e}\mathrm{t}$$x_{0}A\subset X\underline{\subset}G$.

and $6(X)=2$ . $2-1=3$ $=f(4)=fi$ (2).

. We show that $\delta(X/x_{0}A)>0$ . We may assume$6(\mathrm{X}/\mathrm{x}0\mathrm{A})=\delta(x_{0}X_{A}X_{B}/x_{0}A)=\overline{\delta}(X_{B}/x_{0}A)=\dot{\delta}(X_{B}/x_{0})=2|X_{B}|-|X_{B}|>0$.

=x$B, and,$x_{0}AB\leq \mathrm{c}1_{G}(x_{0}AB)=G$ , because$(A/Bx_{0})=\delta(A/x_{0})$
have
.
We
also
6
$[]$
$\delta(Z’/x_{0}AB)=\sum_{z\in Z}$ , $\delta(z/x_{0}AB)=0$ . So, by Fact 4.2, we are done.

(3): It is clear that$\mathrm{c}1_{G}(x_{0})=x0$$\mathrm{c}1_{G}(x_{0}A)$$=x_{0}A_{2}\mathrm{c}1_{G}(x0B)$.
Notation 6.5. Suppose that $C_{n}=\{c_{i}$:$0\leq i\leq n\}$ and$G(C_{n},A_{n},
x_{0})$ .
be the free amalgam of $G(A_{n}, B_{n}, x_{0})$ , $G(B_{n}, C_{n}, x_{0})$ andLeti.e.
$G(B_{n}, Cn, x_{0})$ and $G(C_{n}, A_{n}, x_{0})$ , only.
Edges edges of
In particular, we have
$G(B_{n}, C_{n}, x_{0})G(C_{n}, A_{n}, x_{0})=G(B_{n}, C_{n}, x_{0})\otimes_{C_{n}x_{0}}G(C_{n)}A_{n}, x_{0})$ and$G(Gn, A_{n}, x_{0})G(A_{n}, B_{n}, x_{0})=G(C_{n}, A_{n}, x_{0})\otimes_{A_{n}x_{0}}G(A_{n}, B_{n}, x\mathrm{o})$ .
$C_{n}\cap A_{n}B_{n}=\emptyset$$E_{n}$$=$$G(A_{n}, B_{n}, \mathrm{x}\mathrm{O})$$G(A_{n}, B_{n}, x_{0})G(B_{n}, C_{n}, x_{0})=G(A_{n}, B_{n}, x_{0})\otimes_{B_{|1}x\mathrm{o}}G(B_{n}, C_{n}, x\mathrm{o})$, $|B|$ , $|C|\leq 4$ . Suppose that,
Lemma 6.6. Suppose that , ,$B\cap
C<B$$A\cap B<A$ , , $A\cap C<A$ ,, , and $AB=A\otimes_{A\cap B}B$ , $AC=$
and$BC=B$ (C. Put $X=A\cap B\cap C$, $Z=A\backslash (B\cup C)$ , $W=$
A
$U=C\backslash(A\cupB)$ .
,Suppose that$A$$\otimes_{A\cap C}(^{\gamma},,$$B$$C\in \mathrm{K}_{f_{1}}$

$|A|$
$C$

$C$

$B$

$\otimes_{B\cap C}$$B\backslash (A\cup C)$$D=ABC\not\in \mathrm{K}_{f_{1}}$Then is isomorphic to, $z\in Z,u)\in W$, $u\in U$.
$D$

$X$

where

,

$a\in \mathrm{A}\mathrm{n}\mathrm{G}$$b\in \mathrm{A}\mathrm{n}$Bn $c\in B\cap C$ , $x\in$,55, there is no
Proof. See Appendix 2. As $A\cap B<A$ , if
$b\in
A\cap
B$
$R(b,
c)$
$R(a,
c)$
,
A
. This easy fact is important for thesuch thataproof. (FI),(F2) and (F5) are also needed.
$c\in A\backslash (A\cap B)$

$a$

(1)
Lemma 6.7.
(2) $E_{n}<E_{n+1}$ , so we may assume $E_{n}<E_{n+1}<\lambda I_{f_{1}}$ for any $n<\omega$ .
$E_{n}\in \mathrm{K}_{f1}$Proof. (1): Let

and $D_{AB}=D\cap G(A_{n}, B_{n}, x_{0})$ , $D_{BC}=DnG(Bn, Cn, x_{0})$ , $D_{CA}=$By$<f_{1}(|D|)$ .
way of contradiction, suppose that$D\subseteq E_{n}$$D\cap G(Cn, A_{n}, x\mathrm{o})$and $D_{A}=D\cap x0$ ), $D_{B}=D\cap x0Bn$ , $D_{C}=D\cap x0Cn-$$\check{\delta}(D)$Claim. $|D_{AB}|$ , $|D_{BC}|$ , $|D_{CA}|\leq 4$ .

Suppose that
Fact 6.2,. Put $D’=D_{AB}D_{CA}$ . By
. So we have $D’\neq D$ . As $E_{n}=$$\delta(D_{BC}),\tilde{\delta}(D_{C}))\leq\overline{\delta}(D_{AB})=:d_{AB}$$G(A_{n}, B_{n}, x_{0})G(C_{n}, A_{n}, x_{0})\in \mathrm{K}_{f_{1}}$$G(An, B_{n}, \mathrm{x}\mathrm{o})\mathrm{G}(\mathrm{C}\mathrm{n}, A_{n}, x_{0})\otimes_{B,{}_{\mathrm{z}}C_{?1}x_{0}}G(B_{n)}C_{n}, x_{0})$and$B_{n}C_{n}x_{0}\leq G(Bn, C_{n}, x\mathrm{o})$by (3) of Lemma 6.4, we see$D’\leq D$ .

As $x_{0}A_{n}<G(C_{n}, A_{n}, x_{0})$ (so $D_{A}<D_{CA}$ ) and $D’=D_{AB}\otimes_{D_{A}}D_{CA}$ , so$\grave{\delta}(D’)\geq d_{AB}+1$.

.
Subclaim 1: $f^{-1}(d_{AB}+1)<3f^{-}$ ’$f^{-1}(d_{AB})\geq
f^{-1}(\delta(D_{**}))\geq
2|D_{**}|$. Suppose that this subclaim does
Note thatnot hold, then we have$(d_{AB})$$f^{-1}(d_{AB}+1)\geq 3f^{-1}(d_{AB})\geq 2(|D_{AB}|+|D_{BC}|+|D_{CA}|)\geq 2|D|$.

So, we have $6(D)\geq\delta(D’)\geq d_{AB}+1\geq f_{1}(|D|)$ , a contradiction. This subclaim
is proven.

Subclaim 2: $d_{AB}<f(10)$ .
Otherwise, we have $f^{-1}(d_{AB})\geq 10$ . Thus, by ((F4): $f(3n)\leq f(n)+1$ ), we have
$3f^{-1}(d_{AB})\leq f^{-1}(f(f^{-1}(d_{AB}))+1)=f^{-1}(d_{AB}+1)$ , this contradicts subclaim
1. Subclaim 2 is proven.

As $\delta(D_{**})\leq d_{AB}<f(10)$ , and$D_{**}\in \mathrm{K}_{j_{1}}$, we see the claim.

$E_{n+1}=E_{n}\cup\{a_{n+1}, b_{n+1}, c_{n+1}\}\cup V$.

56

Let $X$ ; $\{a_{n+1}, b_{n+1}, c_{n+1}\}\cup V$ . Then $e(X, E_{n})=|X|$ , so$|X|=|X|-e(X)$ . If $X\cap V=\emptyset$ or $X\cap\{a_{n+1}, b_{n+1}, c_{n+1}\}=\emptyset$ , then $e(X)=0$ .
there , $e(X)$ $=|X\cap V|<|X|$ , as desired.

$\check{\delta}(X/E_{n})=\tilde{\delta}(X)-$$\square$$\mathrm{i}\mathrm{s}\mathrm{e}$Theorem 6.8. Th(fiProof. Let$I_{f_{1}}$) has$\mathrm{S}\mathrm{O}\mathrm{P}_{3}$.

$\varphi(x_{1}y_{1}z_{1}, x_{2}y_{2}z_{2})\equiv\bigwedge_{i=1,2}(R(x_{0}, x_{i})\Lambda R(x_{0}, y_{i})\Lambda R(x_{0}, z_{i}))\Lambda$, $u(R(x_{1}, z)$ A $R(z,y_{2})$ A $R(y_{1}, w)$ A $R(w, z_{2})$ A $R(z_{1}, u)$ A $R(u, x_{2}))$ .
.
Let , , be as in $E_{n}(n<\omega)$ , and put
.
for
Then
$\exists z,w$$a_{n}$$b_{n}$$d_{n}=a_{n}b_{n}c_{n}$$c_{n}$$\mathrm{i}<j<\mu j$$\Lambda I_{f_{1}}\models\varphi(d_{i}, d_{\mathrm{i}})$By way of contradiction, suppose that there exist$N$ such that
. Let
A
A

$N \frac{1}{1-}\mathrm{T}\mathrm{h}(\mathbb{J}I_{f_{1}})$$N|=\varphi(d_{0}^{J}, d_{1}’)$$\varphi(d_{1}’, d_{2}’)$$\varphi(d_{2}’, d_{0}’)$$d_{i}’=a_{i}’b_{i}’c_{i}’$and$d_{0}’$,$d_{1}’$,.

Cla contradiction.

7. APPENDIX 1(FREE AP OF$\mathrm{K}_{f_{1}}$$d_{2}’\in$)

We show Lemma 6.2, when $|X_{1}|\leq 6$ and.

$\frac{\delta(X_{1})-\tilde{\delta}(X_{0})}{|X_{1}|-|X_{0}|}\leq\frac{\delta(X)-\delta(X_{0})}{|X|-|X_{0}|}\leq\frac{\delta(X_{2})-\delta(X_{0})}{|X_{2}|-|X_{0}|}$By assumption and $|X|-|X_{1}|=|X_{2}|-|X_{0}|$ ,$\delta(X_{2}/X_{0})\geq\delta(X_{1}/X_{0})\frac{|X|-|X_{1}|}{|X_{1}|-|X_{0}|}$follows.
Remark 7.1.
(2)
(3)

(1)

$f’(x)( \leq\frac{1}{14})$$\overline{\delta}(X)\geq\delta(X_{1})+\delta^{\neg}(X_{1}/X_{0})\frac{|X|-|X_{1}|}{|X_{1}|-|X_{0}|}$is decreasing for $x\geq 14$ by (F2).
by $X_{0}<X_{1}$ . So we have$e(X_{1}\backslash X_{0}, X_{0})\leq|X_{1}\backslash X_{0}|$$\tilde{\delta}(X_{1}/X_{0})\geq|X_{1}\backslash X_{0}|-e(X_{1}\backslash X_{0})$(4).

$X_{0}$,

Proof. (3):

$X_{1}$,$X_{2}$.

do not contain 3-cycles, since they belong to$\mathrm{K}_{f_{1}}$.

$\tilde{\delta}(X_{1}/X_{0})=\delta(X_{1}\backslash X_{0})-e(X_{1}\backslash X_{0}, X_{0})\geq\delta(X_{1}\backslash X_{0})-|X_{1}\backslash X_{0}|=\square$$|X_{1}\backslash X_{0}|-e(X_{1}\backslash X_{0})$Now we check
Recall (Fl):$f$.

$\overline{\delta}(X)\geq f(2|X|)$for each case on the size of$X_{1}\backslash X_{0}$,$X_{0}$.

(0) $=0$ , $f(2)$ $=2$ , $f(4)$ $=3$ : (8) $=4<f(10)$ $<4 \frac{1}{2}<f(12)$$5<f(14)<5 \frac{1}{3}$

$f$

.

$<$

57

The case that$|X_{1}\backslash X_{0}|=1$$\bullet|X_{1}\backslash X_{0}|=1$, $|X_{0}|=0$$\delta(X)\geq 2+2\frac{|X|-1}{1}=2|X|\geq f(2|X|)$(By$\delta(X_{1})=\grave{\delta}(X_{1}/X_{0})=2$$\bullet|X_{1}\backslash X_{0}|=1$.

and $2x\geq f(2x)$ for $x\geq 2$ ), $|X_{0}|=1$$\tilde{\delta}(X)\geq(4-1)+(2-1)\frac{|X|-2}{1}=1+|X|\geq f(2|X|)$(By $1+x\geq f(2x)$ and, $|X_{0}|=2$$\grave{\delta}(X_{1})\geq 4-$$1$.

, $\delta(X_{1}/X_{0})\geq 2-1.$ )$\bullet|X_{1}\backslash X_{0}|=1$$\delta(X)\geq(6-2)$ $+1 \frac{|X|-3}{1}=1+|X|\geq f(2|X|)$ .

(By$6\{\mathrm{X}$) $\geq 6-2$ ,$\mathrm{S}(\mathrm{X}1/\mathrm{X}0)\geq 2-1$

and $1+x\geq/(2\mathrm{x}))$, $|X_{0}|=3$$\bullet|X_{1}\backslash X_{0}|=1$$\delta(X)\geq(8-3)+1\frac{|X|-4}{1}=1+|X|\geq f(2|X|)$ .

(By$6\{\mathrm{X}$)$\geq \mathrm{S}-$$3$,$\mathrm{S}(\mathrm{X}1/\mathrm{X}0)\geq 2-1$

, $|X_{0}|=4$$\bullet|X_{1}\backslash X_{0}|=1$$\overline{\delta}(X)\geq(10-5)$(By$6\{\mathrm{X}$and $1+x\geq f(2x))$$+1 \frac{|X|-5}{1}=1+|X|\geq f(2|X|)$) $\geq 10-$ , $\delta(X_{1}/X_{0})\geq 2-1$ and, $|X_{0}|=5$$5$.

$x\geq/(2\mathrm{x})$if $x\geq 6.$ )$\bullet|X_{1}\backslash X_{0}|=1$$6 \{\mathrm{X})\geq(12-6)+1\frac{|X|-6}{1}=|X|\geq f(2|X|)$ .

(By$6\{\mathrm{X}$) $\geq 12-6$ ,The case that$\mathrm{S}(\mathrm{X}1/\mathrm{X}0)\geq 2-1$$|X_{1}\backslash X_{0}|=2$$\bullet|X_{1}\backslash X_{0}|=2$, $|X_{0}|=0$$\delta(X)\geq 3+3\frac{|X|-1}{1}\geq f(2|X|)$(By$6\{\mathrm{X}$)$=\mathrm{S}(\mathrm{X}1/\mathrm{X}0)\geq 3$$\bullet|X_{1}\backslash X_{0}|=2$, $|X_{0}|=1$.

$6\{\mathrm{X})(\geq 6- 2, \mathrm{S}(\mathrm{X}1/\mathrm{X}0)\geq 3-1$$\bullet|X_{1}\backslash X_{0}|=2$$6\{\mathrm{X}$and$x[perp]_{\mathrm{I}}1\geq f(2x).)$, $|X_{0}|=2$$\tilde{\delta}(X)\geq 4+1\frac{|X|-4}{2}\geq f(2|X|)$(As.

and $3x+2\geq f(2x).)$$\delta(X)\geq 4+2\frac{|X|-3}{2}\geq f(2|X|)$(By

and $x\geq f(2x)$ if $x\geq 6.$ ).

) $\geq 8-$ , $\delta(X_{1}/X_{0})\geq 3-2$ and $4+ \frac{x-4}{2}\geq f(2x)$ if $x\geq 5.$ )
$4$

58

$\bullet|X_{1}\backslash X_{0}|=2$, $|X_{0}|=3$.

$\delta(X)\geq 5+1\frac{|X|-5}{2}\geq f(2|X|)$(As $\delta(X_{1})\geq 10-5$ ,$6\{\mathrm{X}1/\mathrm{X}\mathrm{q}$$\bullet|X_{1}\backslash X_{0}|=2$) $\geq 3-2$ and $5+ \frac{x-5}{2}\geq f(2x)$ if $x\geq 6.$ ), $|X_{0}|=4$.

$\delta(X)\geq 5+1\frac{|X|-6}{2}\geq f(2|X|)$(As$\mathrm{d}(\mathrm{X})\geq 12-$The case that$7$

, $\delta(X_{1}/X_{0})\geq 3-2$ and $5+ \frac{x-6}{2}\geq f(2x)$ if $x\geq 7.$ )$|X_{1}\backslash X_{0}|=3$$\bullet|X_{1}\backslash X_{0}|=3$, $|X_{0}|=0$$\delta(X)\geq 4+4\frac{|X|-3}{3}\geq f(2|X|)$.

(As

and $4+4 \frac{x-3}{3}\geq f(2x)$ if $x\geq 4.$ )$\mathrm{d}(\mathrm{X})=\grave{\delta}(X_{1}/X_{0})\geq 6-2$$\bullet|X_{1}\backslash X_{0}|=3$, $|X_{0}|=1$$\overline{\delta}(X)\geq 5+3\frac{|X|-4}{3}\geq f(2|X|)$(As$\mathrm{d}(\mathrm{X})\geq 8-$$3$.

, $\delta(X_{1}/X_{0})\geq 4-1$ and $5+3 \frac{x-4}{3}=x+1\geq f(2x)$ if$x\geq 5.)$$\bullet|X_{1}\backslash X_{0}|=3$, $|X_{0}|=2$$\delta(X)\geq 5+2\frac{|X|-5}{3}\geq f(2|X|)$(As$\grave{\delta}(X_{1})\geq 10-$$5$,$\bullet|X_{1}\backslash X_{0}|=3$$\overline{\delta}(X_{1}/X_{0})\geq 4-$$\mathrm{d}(\mathrm{X})\geq 12-$The case that

$7$

,

$2$

and $5+2 \frac{x-5}{3}\geq f(2x)$ if $x\geq 6.$ )$3$

and $5+1 \frac{x-6}{3}\geq/(2\mathrm{x})$ if $x\geq 7.$ ), $|X_{0}|=3$$\tilde{\delta}(X)\geq 5+1\frac{|X|-6}{3}\geq f(2|X|)$

(As

.

.

$\grave{\delta}(X_{1}/X_{0})\geq 4-$$|X_{1}\backslash X_{0}|=4$$\bullet|X_{1}\backslash X_{0}|=4_{!}.|X_{0}|=0$$\delta(X)\geq 4+4\frac{|X|-4}{4}\geq f(2|X|)$(As$\delta(X_{1})=\delta(X_{1}/X_{0})\geq \mathrm{S}$$\bullet|X_{1}\backslash X_{0}|=4$.

$-4$ and $4+4 \frac{x-4}{4}=x\geq f(2x)$ if $x\geq 5.$ ), $|X_{0}|=1$

59$\delta(X)\geq 5+3\frac{|X|-5}{4}\geq f(2|X|)$(As$\check{\delta}(X_{1})\geq 10-$$5$.

, $\delta(X_{1}/X_{0})\geq 4-1$ and$\bullet|X_{1}\backslash X_{0}|=4$, $|X_{0}|=2$$\delta(X)\geq 5+2\frac{|X|-6}{4}\geq f(2|X|)$.

(As $\delta(X_{1})\geq 12-$ , $\delta(X_{1}/X_{0})\geq 4-$$7$

The case that$2$

(As $5(\mathrm{X}\mathrm{a})=\delta(X_{1}/X_{0})\geq 10-5$ and$\bullet|X_{1}\backslash X_{0}|=5$

–

7,

(As

.

$x\geq \mathrm{f}\{2\mathrm{x}$) if $x\geq 6.$ )$6\{\mathrm{X}\mathrm{i}/\mathrm{X}0$.

) $\geq 5-$$2$

and $5+3 \frac{x-6}{5}\geq f(2x)$ if $x\geq 7.$ )$|X_{1}\backslash X_{0}|=6$$\bullet|X_{1}\backslash X_{0}|=6$$\delta(X)\geq f(12)$) if $x\geq 7.$ ), $|X_{0}|=1$$\delta(X)\geq 5+3\frac{|X|-6}{5}\geq f(2|X|)$

The case that$5+ \frac{x-6}{2}\geq \mathrm{f}\{2\mathrm{x}$, $|X_{0}|=0$$\delta(X)\geq 5+5\frac{|X|-5}{5}=|X|\geq f(2|X|)$$\overline{\delta}(X_{1})\geq 12$

and$|X_{1}\backslash X_{0}|=5$$\bullet|X_{1}\backslash X_{0}|=5$(As) if $x\geq 6.$ )$5+3 \frac{x-5}{4}\geq \mathrm{f}\{2\mathrm{x}$, $|X_{0}|=0$$+f(12) \frac{|X|-6}{6}=f(12)|X|\geq f(2|X|)$$\delta(X_{1})=\overline{\delta}(X_{1}/X_{0})\geq/(12)$.

and $f(12)|X|>4|X|\geq f(2x)$ if $x\geq 7.$ )Cl

8. APPENDIX 2 (THE proof 0F LEMMA 6.6)
We show the following.
Lemma 6.6 Suppose that

, $|A|$ , $|B|$ , $|C|\leq 4$ . And suppose that,
$A\cap B<A$ , , $A\cap C<A_{7}C$ and $B\cap C<B$ , , and $AB=A\otimes_{A\cap B}B$ , $AC=$, $BC=B\otimes_{B\cap C}C$ . Put $X=A\cap B\cap C$ , $Z=A\backslash (B\mathrm{U}C)$ , $W=$
, $U=C\backslash (A\cup B)$ .
$A$

,

$B$

$C\in \mathrm{K}_{f_{1}}$

$C$

$B$

$A\otimes_{A\cap C}C$

$B\backslash (A\cup C)$

If$D=ABC\not\in \mathrm{K}_{f_{1}}$$A\cap B$, then $D$

where $a\in A\cap C$ .

$b\in$, $c\in B\cap C$ , $x\in X$ , $z\in$

Proof. We use the following easy fact: If $X<Y$ ,$R(a, c)\Lambda R(b, c)$does not hold$c\in Y\backslash X$, , $b\in X$ , then$a$

eo
Clearly, $D=BCZ$ .
We may assume that , $W$,
by free AR As$Z$$U\neq\emptyset$$B\otimes_{B\cap C}C\in \mathrm{K}_{f_{1}}$, since, for example, if

$|A|$

,

$|B|$

,

$|C|\leq 4$, we have$Z=\emptyset$, then $D=$$|A\cap C|\leq 3$.

, denote elements of $A\cap C$ , , denote elements of $A\cap B$ , , denote$W$elements of $B\cap C$ , , denote elements of , , $w’$ , $w’$ denote elements of ,, denote elements of and , denote elements of $X$ .
$a$

$b$

$a’$

$z$

$u$

$c$

$Z$

$z’$

$U$

$u’$

$b’$

$x$

$c’$

$w$

$x’$

We check each case on the size of $|A\cap C|$ .
The case that $|A\cap C|=3$

follow. So,
We have $6\leq|D|\leq 9$ . As $|A|\leq 4$ , $|Z|=1$ and$\delta(D)=\overline{\delta}(BC)+\tilde{\delta}(Z/BC)\geq
f(2|D|-2)+1\geq$$\delta(Z/BC)\geq
1$. Thuswe have$A\cap B\backslash X=\emptyset$$f(2|D|)$ .

The case that $|A\cap C|=2$$\bullet$$|(A\cap C)\backslash X|=2$(i.e.

$X=\emptyset.$)

Suppose that $|Z|=2$ . So, $6\leq|D|\leq 10$ .
As $A\cap B=\emptyset$ , $\delta(Z/BC)\geq 3-2$ follows. So, $\delta(D)\geq\delta(BC)+1\geq f(2|D|-$$4)+1\geq f(2|D|)$ by (F2). $f(8)+1=5\geq f(12)$ , $f(14)+1\geq 6\geq/(18)$ and(F2).
Suppose that $|Z|=1$ , so $|A\cap B|\leq 1$ .
If $A\cap B=\emptyset$ , then $5\leq|D|\leq 9$ ,$\mathrm{S}(\mathrm{Z}/\mathrm{B}\mathrm{C})\geq 2-1$

follows. So,$\overline{\delta}(D)\geq$$\overline{\delta}(BC)+1\geq f(2|D|-2)+1\geq f(2|D|)$ .

If $|A\cap B|=1$ , then $6\leq|D|\leq 9$ .
If $|D|=6$ , then $D=aafzbwu$ . Then $\grave{\delta}(D)=12-5=7\geq f$ (12).
.
If $|D|=7$ , then $D=aafzbwuu’$ , aa’zbwcu or aafzbww’cu, because , $W$,$=7\geqf(14)$.
Then. ThenIf $|D|=8$ , then $D=aafzbwuu’$ , or aafzbww’cu, because ,$\delta(D)\geq 16-9=7\geq f(16)$ .
. ThenIf $|D|=9_{\}}$ then $D=aa’zbww’w’uu’$ , because $Z,$ $W,$
$Z$$\dot{\delta}(D)\geq 14-$

$7$

$Z$

$U\neq\emptyset$$18-9=9\geq f(18)$$U\neq\emptyset$.

$\bullet|(A\cap C)\backslash X|=|X|=1$.

Suppose that $|A\cap B\backslash X|=0$ . Then
So, 6 $(D)\geq f(2|D|-2|Z|)+1$ .

$\tilde{\delta}(Z/BC)\geq 1$.

$W_{7}U\neq\emptyset$$\delta(D)\geq$61

If $|Z|=1$ , then $5\leq|D|\leq 8$ , so $f(2|D|-2)$ $+1\geq f(2|D|)$ holds.
If $|Z|=2$ , then $6\leq|D|\leq 9$ . $f(2|D|-4)$ $+1\geq f(2|D|)$ holds for $|D|=6,9$ .
( $f(8)+1=5\geq f(12)$ and $f(14)+1\geq 6\geq f(18).$ ) For $|D|=7$ , $D=xazzfwuuf$
xazzfwuuf or xazzfwwfu and then $\grave{\delta}(D)\geq 14-8\geq/(14)$ holds. For $|D|=8_{7}$$D=xazz’ ww’ cu$ or $xazz’ww’uu’$ and then $\grave{\delta}(D)\geq 16-10\geq f(16)$ holds.

Suppose that $|A\cap B\backslash X|=1$ . Then $6\leq|D|\leq 8$ .

If $|D|=6$ , then $D=$ xazbwu and $\delta(D)\geq 12-6\geq f(12)$ .
If $|D|=7$ , then $D=$ xazbevuu’, xazbww’u or xazbwcu. If the former twocases hold, then $\delta(D)\geq 14-8\geq f(14)$ .

if and only if $\delta(D)=14-9<f(14\grave{)}$ .
and $\delta(D)\geq 16-10\geq f(16)$ .
$\bullet$$|(A\cap C)\backslash X|=0$, $|X|=2$

We have $5\leq|D|\leq 8$ .
If $|D|=5$ , then $D=xx’ zwu$ and $\delta(D)\geq 10-4,\geq f(10)$ .
If $|D|=6$ , then $D=xxfzzfwu$ , xx’zbwu, xx’zwu , xx’zwcu or xx’zbwu, and$u$$\delta(D)\geq 12-7\geq f(12\rangle$.

If $|D|=7$ , then $D=xxfzzfwu/u$ , xazbwuvf, $xx’zww’uu’$ , $xx’zz’wcu$ , $xx’zz’wuu’$ ,xx’zbw , or xxfzwwfuuf.
i4 $-8\geq f(14)$ . And we have
If $D\neq xxfzzfwu$ , xazbwuvf, then$u$$5(\mathrm{D})\geq$$\delta(D)=14-9</(14)$ if andnever happens, because
edges to $B\cap C$ , also to $A\cap B$ .
, then $D=xxfzzfwu/u$, and $\overline{\delta}(D)=16-10\geq f(16)$ .
If$B\cap C$

But thishave two$|D|=\mathrm{S}$The case that $|A\cap C|=1$$\bullet$$|(A\cap C)\backslash X|=1(|X|=0)$

By symmetry, we may assume $|A\cap B|$ , $|B\cap C|\leq 1$ .

Suppose that $|A\cap B|$ $|B\cap C|=1$ . Then $6\leq|D|\leq 9$ .
If $|D|=6$ , $\delta(D)\geq 12-6\geq f(12)$ . If $|D|=7$ , $\delta(D)\geq 14-7\geq f(14)$ . If$|D|=8,5(\mathrm{D})\geq 16-8\geq f(16)$ . If $|D|=9,\grave{\delta}(D)\geq 18-9\geq f(18)$ .
)62Suppose that $|A\cap B|=0$ or $|B\cap C|=1$ .
By symmetry, we assume that $|A\cap B|=0$ . Then $AC\cap B=B\cap C$ . By
by freeassumption on , , , $B\cap C<C<AC$ and.
by free. As $B\cap C<AC$, and $D=AC\otimes_{A\cap C}B$ , we have
$A$

$B$

$AC=A\otimes_{A\cap C}C\in \mathrm{K}_{f_{1}}$$C$$\mathrm{A}\mathrm{P}$$D\in \mathrm{K}_{f_{1}}$$B$$\mathrm{A}\mathrm{P}$and $|X|=1$ .
As we have shown tha case that $|A\cap C|=2,3$ , by symmetry, we may assumthat $D=XZWU$ . (i.e. $|(A\cap B)\backslash X|=0$ and $|(B\cap C,7\backslash X|=0)$ As$X<XZW=XZ\otimes_{X}XW\in \mathrm{K}_{f_{1}}$ and $X<XU\in K_{f_{1}}$ , we have $D=$.
$XZW\otimes_{X}XZ\in \mathrm{K}_{f1}$ by free$\bullet$$|(A\cap C)\backslash X|=0$$\mathrm{e}$$\mathrm{A}\mathrm{P}$The case that $|A\cap C|=0$

As we have shown tha case that $|A\cap C|=1,2,3$ , by symmetry, we may, weassume that $D=ZWU$ . (i.e. $|A\cap B|=0$ and $|B\cap C|=0.$ ) By free.
see$\mathrm{A}\mathrm{P}$$\square$$D\in \mathrm{K}_{f_{1}}$REFERENCES[E] D.M.Evans, Some remarks on generic structures, preprint, July 2003 (working draft)[E1] D.M.Evans, -categorical structures with a predimensions, Annals of Pure and Applied Logic 120 (2003) 157-186.
[P] M.Pourmahdian, Smooth classes without AC and Robinson theories, The Journal of
Symbolic Logic 67 (2002) 12741294,[Sh] S.Shelah, Toward classifying unstable theories, Annals of Pure and Applied Logic 80.
(1996)-mail address: ikuo.yoned a$s3.dion.ne . jp$\aleph_{0}$$229rightarrow 255$

$E$