format: text

text:
# More on the Ehrenfencht-Fraïssé game of length 𝜔₁.

## 1 Getting a weakly compact cardinal

In this section we show that if CH holds and $`\mathrm{EFG}_{\omega _1}(𝔄,𝔅)`$ is determined for all models $`𝔄`$ and $`𝔅`$ of cardinality $`\mathrm{}_2`$, then $`\omega _2`$ is weakly compact in $`L`$ (Corollary 8). We use the results from  that if $`\omega _2`$ is not weakly compact in $`L`$, then there is a bistationary $`SS_0^2`$ such that for all $`\alpha <\omega _2`$ either $`\alpha S`$ or $`\alpha S`$ is non-stationary.

If $`I`$ is a linear order, we use $`(I)^{}`$ to denote the reverse order of $`I`$. We call a sequence $`s=(s_\xi )_{\xi <\zeta }`$ coinitial sequence of length $`\zeta `$ in $`I`$, if it is decreasing in $`I`$ and has no lower bound in $`I`$. The coinitiality $`\mathrm{coinit}(I)`$ of a linear order $`I`$ is the smallest length of a coinitial sequence in $`I`$.

Let $`\theta =\omega +((\omega _1)^{}+\omega )\omega _1`$.

###### Lemma 3

There is a dense linear order $`I`$ such that

$`|I|=\mathrm{}_1`$.

$`\mathrm{coinit}(I)=\mathrm{}_0`$

$`I(\alpha +1)I`$ for all $`\alpha \omega _1`$.

$`II\omega +I(\omega _1)^{}`$.

$`I\theta +II`$.

Proof. This is like Lemma 4.7.16 in . If $`J_1`$ and $`J_2`$ are linear orders, let $`H(J_1,J_2)`$ be the set of $`f:n_fJ_1J_2`$, where $`n_f<\omega `$ is even, $`f(2i)J_1`$ and $`f(2i+1)J_2`$ for all $`i<n_f`$. We can make $`H(J_1,J_2)`$ a linear order by ordering the functions lexicographically, i.e.

$$fgmn_f(i<m(f(i)=g(i))\&(m<n_ff(m)<g(m))).$$

Let $`I_0=H(,\omega +(\omega _1)^{})`$ and $`I_1=H(I_0,\omega _1)`$. Thus $`I_0(1+I_0)(\omega +(\omega _1)^{})`$ and $`I_1(1+I_1)\omega _1I_0`$. By using $`+1+`$, $`\omega =1+\omega `$ and $`\omega _1=1+\omega _1`$, one gets easily the following, first for $`I_0`$, and then for $`I_1`$:

$$I_0I_0+1+I_0,I_1I_1+1+I_1.$$
(1)
Let $`I`$ be the set of $`f:\omega I_1\theta `$, where $`f(2i)I_1`$ and $`f(2i+1)\theta `$ for all $`i<\omega `$ ordered lexicographically. Thus $`II\theta I_1`$. In fact, $`I`$ is of the form $`J`$, so (ii) is true. By (1) and $`\theta 1+\theta `$ one gets immediately (v). As $`II\theta (1+I_1)\omega _1I_0`$, we get from (v) easily (iii) for $`\alpha =\omega _1`$. From this and $`\alpha +\omega _1=\omega _1`$ we get immediately (iii) for $`\alpha <\omega _1`$. Note that $`\theta \omega +(\omega _1)^{}+\theta `$. If we combine this with $`II\theta I_1`$ and $`(\omega _1)^{}(\omega _1)^{}+1`$, we get (iv).

As to (i), we only have $`|I|=2^\omega `$. We use this lemma in a context where CH is assumed, so we could simply assume it here. But actually the lemma is true without CH, as we can construct $`I`$ in $`L`$. Then $`|I|=\mathrm{}_1`$. Note that our $`I_0`$ and $`I_1`$ are in $`L`$, and the only property of $`\omega _1`$ that we used was that it is a limit ordinal. $`\mathrm{}`$

###### Definition 4

Suppose $`SS_0^2`$. We define

$$\mathrm{\Phi }(S)=\underset{i<\omega _2}{}\eta _i,$$

where

$$\eta _i=\{\begin{array}{cc}I(\omega _1)^{},\hfill & \text{ if }iS\hfill \\ I,\hfill & \text{ if }iS.\hfill \end{array}$$

Let $`\mathrm{\Phi }_{\alpha ,\beta }(S)`$ be the suborder $`_{\alpha i<\beta }\eta _i`$ of $`\mathrm{\Phi }(S)`$. The rank of $`x\mathrm{\Phi }(S)`$ is the least $`\alpha `$ such that $`x\mathrm{\Phi }_{\alpha ,\alpha +1}(S)`$. We denote this $`\alpha `$ by $`\mathrm{rnk}(\mathrm{\Phi }(S),x)`$.

###### Lemma 5

Assume $`SS_0^2`$ is such that there is no $`\alpha S_1^2`$ with both $`S\alpha `$ and $`(SS_0^2)S`$ stationary. Then

$$\mathrm{\Phi }_{\alpha ,\beta +1}(S)I$$

whenever $`\alpha <\beta <\omega _2`$ and $`\alpha S`$.

Proof. This is like Lemma 4.7.19 in . We use Lemma 3 and induction on $`\beta `$.

Let us first assume $`\beta S`$. If $`\beta `$ is a successor ordinal, then $`\mathrm{\Phi }_{\alpha ,\beta +1}(S)I+I=I`$ by (iii). If $`\beta `$ has cofinality $`\omega `$, then $`\mathrm{\Phi }_{\alpha ,\beta +1}(S)I\omega +II`$. If $`\beta `$ has cofinality $`\omega _1`$ and $`\beta S`$ is non-stationary, then $`II\omega _1+II`$. Finally, if $`\beta `$ has cofinality $`\omega _1`$ and $`\beta S`$ is non-stationary, then $`II\theta +II`$, by (v).

Let us then assume $`\beta S`$. Thus $`\beta `$ has cofinality $`\omega `$. Therefore $`\mathrm{\Phi }_{\alpha ,\beta +1}(S)I\omega +I(\omega _1)^{}I`$, by (iv). $`\mathrm{}`$

###### Lemma 6

Assume $`SS_0^2`$ is such that there is no $`\alpha S_1^2`$ with both $`S\alpha `$ and $`(SS_0^2)S`$ stationary. Then $`\mathrm{\Phi }_{0,\alpha }(S)\mathrm{\Phi }_{0,\alpha }(\mathrm{})`$ whenever $`\alpha S_1^2`$ and $`S\alpha `$ is not stationary.

Proof. Let $`(\alpha _\xi )_{\xi <\omega _1}`$ by a continuously increasing cofinal sequence in $`\alpha `$ such that $`\alpha _\xi S`$ for all $`\xi <\omega _1`$. By Lemma 5 there is an isomorphism

$$f_\xi :\mathrm{\Phi }_{\alpha _\xi ,\alpha _{\xi +1}+1}(S)\mathrm{\Phi }_{\alpha _\xi ,\alpha _{\xi +1}+1}(\mathrm{}).$$

Let $`f=_{\xi <\omega _1}f_\xi `$. This is the required isomorphism. $`\mathrm{}`$

###### Proposition 7

Assume CH and that there is $`SS_0^2`$ such that both $`S`$ and $`S_0^2S`$ are stationary but there is no $`\alpha S_1^2`$ with both $`S\alpha `$ and $`(SS_0^2)S`$ stationary. Then there are models $`𝔄`$ and $`𝔅`$ of cardinality $`\mathrm{}_2`$ such that $`EF_{\omega _1}(𝔄,𝔅)`$ is non-determined.

Proof. We may assume, that $`\{\alpha S_1^2:\alpha S\text{ is non-stationary }\}`$ is stationary, for otherwise we work with $`S^{}=S_0^2S`$. Let $`𝔄=\mathrm{\Phi }(S)`$ and $`𝔅=\mathrm{\Phi }(\mathrm{})`$. We first show that $``$ cannot have a winning strategy in $`EF_{\omega +\omega +1}(𝔄,𝔅)`$. Suppose $`\tau `$ is a strategy of $``$. Let $`C`$ be the cub of ordinals $`\alpha <\omega _2`$ such that if during the first $`\omega `$ rounds of the game, $``$ plays elements of the models of rank $`<\alpha `$, then so does $``$ following $`\tau `$. Let $`\delta CS`$. Let $`(\delta _n)_{n<\omega }`$ be an increasing cofinal sequence in $`\delta `$. Now we let $``$ play against $`\tau `$ as follows: On round number $`n<\omega `$ we let $``$ play some element of $`𝔄`$, if $`n`$ is even, and of $`𝔅`$, if $`n`$ is odd, of rank $`\delta _n`$. During rounds $`\omega +n`$, $`n<\omega `$, we let $``$ play a coinitial sequence of length $`\omega `$ in $`\mathrm{\Phi }_{\delta ,\delta +1}(\mathrm{})𝔄`$. As $`\mathrm{coinit}(\mathrm{\Phi }_{\delta ,\delta +1}(S))=\omega _1`$, the game is lost for $``$. So $`\tau `$ could not be a winning strategy.

Suppose then $`\rho `$ is a strategy of $``$. We show that this cannot be a winning strategy. By CH we have an $`\omega _1`$-cub set $`D`$ of ordinals $`\delta <\omega _2`$ such that if $``$ plays only elements of rank $`<\delta `$, then $`\rho `$ directs $``$ to play also elements of rank $`<\delta `$ only. Let $`\delta DS_1^2`$ such that $`\delta S`$ is non-stationary. By Lemma 6 there is an isomorphism $`f:\mathrm{\Phi }_{0,\alpha }(S)\mathrm{\Phi }_{0,\alpha }(\mathrm{})`$. Now $``$ can beat $`\rho `$ by using $`f`$. $`\mathrm{}`$

###### Corollary 8

If CH holds and $`\mathrm{EFG}_{\omega _1}(𝔄,𝔅)`$ is determined for all models $`𝔄`$ and $`𝔅`$ of cardinality $`\mathrm{}_2`$, then $`\omega _2`$ is weakly compact in $`L`$.

## 2 Getting determinacy from a weakly compact cardinal

In this section we show that if $`\kappa `$ is weakly compact, then there is a forcing extension in which the game $`\mathrm{EFG}_{\omega _1}(𝔄,𝔅)`$ is determined for all $`𝔄`$ and $`𝔅`$ of cardinality $`\mathrm{}_2`$.

We shall consider models $`𝔄,𝔅`$ of cardinality $`\mathrm{}_2`$, so we may as well assume they have $`\omega _2`$ as universe. For such a model $`𝔄`$ and any ordinal $`\alpha <\omega _2`$ we let $`𝔄_\alpha `$ denote the structure $`𝔄\alpha `$. Similarly $`𝔅_\alpha `$. Let us first recall the following basic fact from :

###### Lemma 9

 Suppose $`𝔄`$ and $`𝔅`$ are structures of cardinality $`\mathrm{}_2`$. If $``$ does not have a winning strategy in $`\mathrm{EFG}_{\omega _1}(𝔄,𝔅)`$, then

$$S=\{\alpha :𝔄_\alpha 𝔅_\alpha \}$$

is $`\omega _1`$-stationary.

This shows that to get determinacy of $`\mathrm{EFG}_{\omega _1}(𝔄,𝔅)`$ it suffices to give a winning strategy of $``$ under the assumption that the above set $`S`$ is $`\omega _1`$-stationary. In  an assumption $`I^{}(\omega )`$ was used. This assumption says that the non-$`\omega _1`$-stationary ideal on $`\omega _2`$ has a $`\sigma `$-closed dense set. The rough idea was that $``$ uses the Pressing Down Lemma on $`S`$ to ”normalize” his moves so that he always has an $`\omega _1`$-stationary sets of possible continuations of the game. We use now the same idea. The hypothesis $`I^{}(\omega )`$ is equiconsistent with a measurable cardinal. Since we assume only the consistency of a weakly compact cardinal, we have to work more.

Suppose $`\kappa `$ is a weakly compact cardinal. Let $``$ denote the $`\mathrm{\Pi }_1^1`$-ideal on $`\kappa `$, i.e.. the ideal of subsets of $`\kappa `$ generated by the sets $`\{\alpha :(H(\alpha ),ϵ,AH(\alpha ))\neg \varphi \}`$, where $`AH(\kappa )`$ and $`\varphi `$ is a $`\mathrm{\Pi }_1^1`$-sentence such that $`(H(\kappa ),ϵ,A)\varphi `$. We collapse $`\kappa `$ to $`\omega _2`$ and then force a cub to the complement of every set $`SS_1^2`$ in $``$. In the resulting model the above ”normalization” strategy of $``$ works even though the non-$`\omega _1`$-stationary ideal on $`\omega _2`$ may not have a $`\sigma `$-closed dense set.

###### Definition 10

Let $``$ be a set of cardinality $`\kappa `$ of regressive functions $`\kappa \kappa `$ and $`S\kappa `$. The game $`\mathrm{PDG}_{\omega _1}(S,)`$ has two players called $``$ and $``$. They alternately play $`\omega _1`$ rounds. During each round $``$ first chooses $`f_i`$. Then $``$ chooses a subset $`S_i`$ of $`_{j<i}S_j`$ (of $`S`$, if $`i=0`$) such that it is unbounded in $`\kappa `$ and $`f_i`$ is constant on $`S_i`$. Player $``$ wins if he can play all $`\omega _1`$ moves following the rules.

###### Lemma 11

Suppose $`S=\{\alpha <\omega _2:\alpha 0,𝔄_\alpha 𝔅_\alpha \}`$ and $`h_\alpha :𝔄_\alpha 𝔅_\alpha `$ for $`\alpha S`$. Let

$$=\{f_\alpha :\alpha S\}\{g_\alpha :\alpha S\},$$

where $`f_\alpha :\omega _2\omega _2`$ is the regressive function mapping $`\xi `$ ($`0`$) to $`h_\xi (\alpha )`$ if $`\xi >\alpha `$, and to $`0`$ otherwise, and $`g_\alpha `$ is the regressive function mapping $`\xi `$ ($`0`$) to $`(h_\xi )^1(\alpha )`$ if $`\xi >\alpha `$, and to $`0`$ otherwise. Suppose $``$ has a winning strategy in $`\mathrm{PDG}_{\omega _1}(S,)`$. Then $``$ has a winning strategy in the game $`\mathrm{EFG}_{\omega _1}^\mathrm{}_2(𝔄,𝔅)`$.

Proof. We present the proof for $`\mathrm{EFG}_{\omega _1}^2(𝔄,𝔅)`$. The case of $`\mathrm{EFG}_{\omega _1}^\mathrm{}_2(𝔄,𝔅)`$ is similar. $`=\{h_\alpha :\alpha S\}`$, where $`h_\alpha :𝔄_\alpha 𝔅_\alpha `$ for $`\alpha S`$. Let $`\tau `$ be a winning strategy of $``$ in the game $`\mathrm{PDG}_{\omega _1}(S,)`$. Suppose the sequence $`(x_i,y_i):i<\alpha `$ has been played, where $`\alpha <\omega _1`$, $`x_i`$ denotes a move of $``$ and $`y_i`$ a move of $``$. Suppose $``$ plays next $`x_\alpha `$. During the game $``$ also plays $`\mathrm{PDG}_{\omega _1}(S,)`$. Let us denote his moves in $`\mathrm{PDG}_{\omega _1}(S,)`$ by $`S_i`$. Thus $`S_jS_i`$ for $`i<j<\alpha `$. The point of the sets $`S_i`$ is that $``$ has taken care that for all $`i<\alpha `$ and $`jS_i`$ we have $`y_i=h_j(x_i)`$ or $`x_i=h_j(y_i)`$ depending on whether $`x_i𝔄`$ or $`x_i𝔅`$. Let $`S_\alpha ^{}=_{i<\alpha }S_i\alpha _i`$. The winning strategy $`\tau `$ gives an $`S_\alpha S_\alpha ^{}`$ and a $`y_\alpha `$ such that $`f_i(x_\alpha )=y_\alpha `$ for all $`iS_\alpha `$, if $`x_\alpha 𝔄`$, and $`g_i(x_\alpha )=y_\alpha `$ for all $`iS_\alpha `$, if $`x_\alpha 𝔅`$. This element $`y_\alpha `$ is the next move of $``$. Using this strategy $``$ cannot lose and hence wins. $`\mathrm{}`$

###### Theorem 12

It is consistent relative to the consistency of a weakly compact cardinal, that for every $`\omega _1`$-stationary $`S\omega _2`$ and every set $``$ of cardinality $`\mathrm{}_2`$ of regressive functions $`\omega _2\omega _2`$, $``$ has a winning strategy in the game $`\mathrm{PDG}_{\omega _1}(S,)`$.

Proof. We may assume GCH. Suppose $`\kappa `$ is weakly compact. Let $``$ be the Levy-collapse of $`\kappa `$ to $`\mathrm{}_2`$. In $`V^{}`$ we define by induction a sequence $`_\alpha `$, $`\alpha <\kappa ^+`$, of forcing notions. Let $`(A_\alpha ),\alpha <\kappa ^+`$, be a complete list of all sets in the $`\mathrm{\Pi }_1^1`$-ideal $``$ on $`\kappa `$ such that every element of $`A_\alpha `$ has uncountable cofinality. If $`\alpha `$ is limit of cofinality $`\omega _1`$, then $`_\alpha `$ is the inverse limit of all $`_\beta `$, $`\beta <\alpha `$. For other limit $`\alpha `$, $`_\alpha `$ is the direct limit of $`_\beta `$, $`\beta <\alpha `$. At successor stages we let $`_{\alpha +1}=_\alpha _\alpha `$, where $`_\alpha `$ is defined as follows: $`q_\alpha `$ iff $`q`$ is a bounded closed sequence of elements of $`\kappa `$ such that $`qA_\alpha =\mathrm{}`$. $`_\alpha `$ is ordered by the end extension relation. Thus each $`_\alpha `$ is countably closed. Let $`=_{\kappa ^+}`$. Now $``$ satisfies the $`\kappa ^+`$-chain condition. Note also that for all $`\alpha <\kappa ^+`$, $`_\alpha `$ has power $`\kappa `$. We prove that it is true in $`V^{}`$ that $`_\alpha `$ does not add new subsets of $`\kappa `$ of cardinality $`\mathrm{}_1`$, hence $`\kappa `$ remains $`\mathrm{}_2`$ also after forcing with $``$. It follows also that $``$ and each $`_\alpha `$ are countably closed.

We show now that in $`V^{}`$ the claim is true. Suppose $`S`$ and a set $`=\{f_\alpha :\alpha <\kappa \}`$, of regressive functions $`\kappa \kappa `$ are given in $`V^{}`$ such that (in $`V^{}`$) $`SS_1^2`$ is $`\omega _1`$-stationary. Suppose $`\alpha <\kappa ^+`$ is such that $`\stackrel{~}{S},\stackrel{~}{}`$ and $`\stackrel{~}{f_i}`$ are $`_\alpha `$-names for $`S,`$ and $`f_i`$, correspondingly. Since $`S`$ is $`\omega _1`$-stationary in $`V^{}`$, $`S`$ is not in the ideal generated by $``$ in $`V^_\alpha `$. Suppose $`(p,q)\stackrel{~}{S}`$. For a contradiction, suppose also that $`(p,q)`$ forces that $``$ does not have a winning strategy in the game $`BM_{\omega _1}(S,)`$.

Let $`(_0^{},)`$ be a sufficiently elementary substructure of $`(V,)`$ such that $`|_0^{}|=\kappa `$, $`_{}^{}{}_{0}{}^{<\kappa }_0^{}`$, $``$, $`_\alpha `$, $`\alpha `$, $`\kappa `$, $`\stackrel{~}{},\stackrel{~}{f_i}`$, $`\stackrel{~}{S}`$, are in $`_0^{}`$, and $`\alpha \kappa _0^{}`$. Let $`_0`$ be the transitive collapse of $`_0^{}`$. Thus $`,_\alpha ,\alpha ,\kappa _0`$, $`A_j_0`$ for $`i\alpha `$ and $`\stackrel{~}{f_i}_0`$ for $`i<\kappa `$. Let

$$T=\{\alpha <\kappa |(p^{},q^{})(p,q)((p^{},q^{})__\alpha \alpha \stackrel{~}{S})\}.$$

Clearly $`T_0`$ and $`T`$. By weak compactness, there are a transitive $`_1`$ and an elementary embedding $`j:_0_1`$ such that $`\kappa `$ is the critical point of $`j`$, $`\kappa j(T)`$ and $`\kappa j(A_i)`$ for $`i\alpha `$. So there is some $`(p^{},q^{})j(_\alpha )`$ such that $`(p^{},q^{})j((p,q))=(p,q)`$ and $`(p^{},q^{})_{j(_\alpha )}\kappa j(\stackrel{~}{S})`$. Note that $`,_\alpha _1`$ and $`\stackrel{~}{f_i}_1`$ for $`i<\kappa `$.

By (the proof of) Lemma 3 in , there are a $`_\alpha `$-generic $`G`$ over $`_1`$ and a forcing notion $`_1[G]`$ such that $`(p,q)G`$, in $`_1[G]`$, $``$ is countably closed, for all $``$-generic $`K`$ over $`_1[G]`$, there is a canonical $`j(_\alpha )`$-generic $`G_K`$ over $`_1`$ such that $`_1[G_K]=_1[G][K]`$ and for some $`K`$, $`G_K`$ is such that $`(p^{},q^{})G^{}`$. Then for every $`_\alpha `$-name $`\stackrel{~}{X}_0`$, there is a canonical $``$-name $`\stackrel{~}{Y}_1[G]`$ such that for all $``$-generic $`K`$ over $`_1[G]`$, $`j(\stackrel{~}{X})`$ and $`\stackrel{~}{Y}`$ have the same interpretation in $`_1[G][K]`$. We do not distinguish $`j(\stackrel{~}{X})`$ and $`\stackrel{~}{Y}`$. With this notation, there is $`r`$ which forces in $`_1[G]`$, that $`\kappa j(\stackrel{~}{S})`$. Then there is some $`(p^{},q^{})(p,q)`$ in $`G`$ that in $`_1`$ forces the existence of such $``$ and $`r`$. So we may assume that $`G`$ is generic over $`V`$ and our $`V^_\alpha `$ is the same as $`V[G]`$.

We describe in $`_1[G]`$ a winning strategy of $``$ in the game $`BM_{\omega _1}(S,)`$. This is a contradiction since all possible winning plays of $``$ are in $`_1[G]`$ and being unbounded is absolute in transitive models. The strategy of $``$ is to play on the side conditions $`q^i`$ in $`_1[G]`$ and sets $`S_i_0[G]`$ with $`_\alpha `$-names $`\stackrel{~}{S_i}`$ in $`_0`$ such that

1. $`q^i`$.
2. $`q^0r`$.
3. $`i<k<\omega _1`$ implies $`q^kq^i`$.
4. $`i<k<\omega _1`$ implies $`S_kS_iS`$.
5. $`q^i_{}\kappa j(\stackrel{~}{S_i})`$ in $`_1[G]`$.

Suppose $``$ has followed this strategy, forming conditions $`q^i`$ and sets $`S_i`$ for $`i<k`$. Let $`p=inf(\{q^i:i<k\})`$. If we let $`S`$ to be $`_{i<k}S_i`$ and $`\stackrel{~}{S}`$ a name for this, then in $`_1[G]`$,

$$p_{}\kappa j(\stackrel{~}{S}).$$

Suppose then $``$ moves $`f_k`$. Let $`q^kp`$ such that for some $`\delta <\kappa `$ we have $`q^k_{}j(\stackrel{~}{f_k})(\kappa )=\delta `$ in $`_1[G]`$ and let $`S_k`$ be $`\{\beta S:f_k(\beta )=\delta \}`$ and $`\stackrel{~}{S_k}`$ a name for this. Then $`q^k_{}\kappa j(\stackrel{~}{S_k})`$ in $`_1[G]`$.

Finally we have to prove that $`_\alpha `$ does not add new subsets of $`\kappa `$ of cardinality $`\mathrm{}_1`$ over and above those added by $``$. The proof of this is, mutatis mutandis, like the proof of the Main fact (page 761) in . Here we use the assumption $`\kappa j(A_i)`$ for $`i\alpha `$. Thus, if $`C`$ is a generic sequence in the complement of $`j(A_\beta )`$ in $`V^{j(_\alpha )}`$, then we can continue it to a closed condition $`C\{\kappa \}_{j(\beta )}`$. $`\mathrm{}`$

Results similar to Theorem 12 have been treated also in  and .

###### Corollary 13

It is consistent relative to the consistency of a weakly compact cardinal, that the game $`\mathrm{EFG}_{\omega _1}(𝔄,𝔅)`$ is determined for all $`𝔄`$ and $`𝔅`$ of cardinalty $`\mathrm{}_2`$.

## 3 Non-determinacy and structure theory

In this section we prove Theorem 2, which essentially establishes, under cardinality assumptions concerning the continuum, the existence of non-determined Ehrenfencht-Fraïssé games of length $`\omega _1`$ for models of non-classifiable theories. This complements the observation, made in , that the Ehrenfencht-Fraïssé game of length $`\omega _1`$ is determined for models of classifiable theories.

We start be proving Theorem 2 under assumption (iii), which we consider the most intereting case. That is, we start with a countable complete stable and unsuperstable first order theory and show that, assuming $`2^\omega \omega _3`$, it has two models $`𝔄`$ and $`𝔅`$ of cardinality $`\mathrm{}_3`$ for which $`\mathrm{EFG}_{\omega _1}(𝔄,𝔅)`$ is non-determined. Actually, we construct $`𝔄`$ and $`𝔅`$ so that $``$ does not have a winning strategy even in $`\mathrm{EFG}_{\omega +\omega }^2(𝔄,𝔅)`$ and $``$ does not have a winning strategy even in $`\mathrm{EFG}_{\omega _1}^{\omega _3}(𝔄,𝔅)`$.

We then prove Theorem 2 under assumption (i), that is, we now start with a countable complete unstable first order theory and show that, assuming $`2^\omega <2^{\omega _3}`$, it has two models $`𝔄`$ and $`𝔅`$ of cardinality $`\mathrm{}_3`$ for which $`\mathrm{EFG}_{\omega _1}(𝔄,𝔅)`$ is non-determined.

Theorem 2 under assumption (ii) can be dealt with in the same way as under assumption (i). The section ends with some remarks on possible improvements.

### 3.1 The stable unsuperstable case

We will prove Theorem 2, case (iii), in a series of lemmas. We assume $`\omega _3^\omega =\omega _3`$ all the time. Let $`T`$ be a countable complete stable and unsuperstable first order theory. As usual, we work inside a large saturated model $`𝐌`$ of $`T`$. We start by fixing some notation. By a tree $`I`$ we mean a lexicographically ordered downwards closed subtree of $`\theta ^{<(\omega +1)}`$ for some linear order $`\theta `$, that is, $`I=(I,,P_\alpha ,<,H)_{\alpha \omega }K_{tr}^\omega (\theta )`$, see  Definition 8.2 or . For a while, we fix a tree $`IK_{tr}^\omega (\lambda )`$, where $`\lambda `$ is some large enough cardinal, so that $`(I,)`$ is isomorphic to $`\lambda ^{<(\omega +1)}`$. As in , for $`u,v𝒫_\omega (I)`$ (=finite subsets of $`I`$), we define $`r(u,v)`$ to be the unique set $`R`$ which satisfies

$`RX_{u,v}=\{H(\eta ,\xi )|\eta u,\xi v\}`$,

For all $`\nu X_{u,v}R`$, there is $`\nu ^{}R`$ such that $`\nu \nu ^{}`$,

If $`\eta `$ and $`\xi `$ are distinct elements of $`R`$, then $`\eta \ll ̸\xi `$.

We write $`uv`$ if $`r(u,v)=r(u,u)`$. For more on these definitions, see . In , it is shown that there are models $`𝒜`$ and $`𝒜_u`$, $`u𝒫_\omega (I)`$, and sequences $`a_\eta `$ from $`𝒜_{\{\eta \}}`$, $`\eta I`$, such that

$`𝒜=_{u𝒫_\omega (I)}𝒜_uT`$,

if $`uv`$, then $`𝒜_u𝒜_v`$,

for all $`u,v𝒫_\omega (I)`$, $`𝒜_u_{𝒜_{r(u,v)}}𝒜_v`$,

for all $`u𝒫_\omega (I)`$, $`|𝒜_u|\omega _3`$,

if $`P_\omega (\eta )`$ holds and $`\xi \eta `$ is an immediate successor of $`\xi ^{}`$, then

$$a_\eta \mathrm{}_{𝒜_{\{\xi ^{}\}}}a_\xi .$$

These models are exactly what we want except that they are too large, we want the models $`𝒜_u`$, $`u𝒫_\omega (I)`$, to be countable. In order to get this, we use the Ehrenfeucht-Mostowski construction.

We extend the signature $`L`$ of $`T`$ to $`L_{}`$ by adding $`\omega _3`$ new function symbols, some of which will be interpreted in $`𝐌`$ so that they provide Skolem-functions for the $`L`$-formulas. In addition we interpret the functions so that if we write $`SH_{}(u)`$ for the $`L_{}`$-Skolem-hull of $`\{a_\eta |\{\eta \}u\}`$ then

for all $`u𝒫_\omega (I)`$, $`SH_{}(u)=𝒜_u`$.

By the usual argument (using \[11, Appendix Theorem 2.6\] and compactness) we can interpret the new function symbols so that $`𝐌`$ remains sufficiently saturated and the following holds

if $`U`$ is a downwards closed subtree of $`I`$ and $`f`$ is an automorphism of $`U`$, then there is an $`L_{}`$-automorphism $`g`$ of $`_{u𝒫_\omega (U)}𝒜_u`$ such that for all $`\eta U`$, $`g(a_\eta )=a_{f(\eta )}`$.

Finally, it is easy to see that we can choose countable $`L_1L_{}`$ so that $`LL_1`$, $`L_1`$ contains the Skolem-functions for the $`L`$-formulas and if we write $`SH_1(u)`$ for the $`L_1`$-Skolem-hull of $`\{a_\eta |\{\eta \}u\}`$ then

for all $`u,v𝒫_\omega (I)`$, $`SH_1(u)_{SH_1(v)}SH_{}(v)`$.

So we have proved the following lemma (for the notion $`\mathrm{\Phi }`$ proper for $`K_{tr}^\omega `$ and the Ehrenfeucht-Mostowski models $`EM^1(J,\mathrm{\Phi })`$, see  Definition 8.1 or ).

###### Lemma 14

There are countable $`L_1L`$ and $`\mathrm{\Phi }`$ proper for $`K_{tr}^\omega `$ such that the following holds:

For all $`JK_{tr}^\omega `$ there are an $`L_1`$-model $`EM^1(J,\mathrm{\Phi })T`$ and sequences $`a_\eta EM^1(J,\mathrm{\Phi })`$, $`\eta J`$, such that $`EM^1(J,\mathrm{\Phi })`$ is the $`L_1`$-Skolem-hull of $`\{a_\eta |\eta J\}`$ (i.e. $`\{a_\eta |\eta J\}`$ is the skeleton of $`EM^1(J,\mathrm{\Phi })`$ and as before for $`uJ`$, $`SH_1(u)`$ denotes the $`L_1`$-Skolem hull of $`\{a_\eta |\{\eta \}u\}`$).

If $`U`$ is a downwards closed subtree of $`J`$ and $`f`$ is an automorphism of $`U`$, then there is an $`L_1`$-automorphism $`g`$ of $`SH_1(U)`$ such that for all $`\eta U`$, $`g(a_\eta )=a_{f(\eta )}`$.

Assume $`(\eta _i)_{i<\omega }`$ is a strictly $``$-increasing sequence of elements of $`J`$, $`\eta _{i+1}`$ is an immediate successor of $`\eta _i`$ and $`\eta _0`$ is the root. Then $`(\eta _i)_{i<\omega }`$ has an upper bound in $`J`$ iff there is a sequence $`aEM(J,\mathrm{\Phi })`$ such that for all $`i<\omega `$, $`a\mathrm{}_{SH_1(\{\eta _i\})}a_{\eta _{i+1}}`$. $`\mathrm{}`$

We will write $`EM(J,\mathrm{\Phi })`$ for $`EM^1(J,\mathrm{\Phi })L`$.

Our next goal is to define the skeletons for the models $`𝒜`$ and $``$ in the theorem. For this we use the weak box from . By $`S_m^n`$ we denote the set $`\{\alpha <\omega _n|cf(\alpha )=\omega _m\}`$.

###### Theorem 15

(\[8, Lemma 16\]) There are sets $`S`$, $`U`$ and $`C_\alpha `$, $`\alpha S`$, such that the following holds:

(a) $`SS_0^3S_1^3`$ and $`SS_1^3`$ is stationary,

(b) $`US_0^3`$ is stationary and $`SU=\mathrm{}`$,

(c) for all $`\alpha S`$, $`C_\alpha \alpha S`$ is closed in $`\alpha `$ and of order-type $`\omega _1`$,

(d) for all $`\alpha S`$, if $`\beta C_\alpha `$, then $`C_\beta =C_\alpha \beta `$,

(e) for all $`\alpha SS_1^3`$, $`C_\alpha `$ is unbounded in $`\alpha `$. $`\mathrm{}`$

We will construct trees $`I_\alpha `$ and $`J_\alpha `$, $`\alpha <\omega _3`$, so that the following holds:

if $`\alpha <\beta `$ then $`I_\alpha `$ is a submodel of $`I_\beta `$ and $`J_\alpha `$ is a submodel of $`J_\beta `$; now for $`\eta I_\alpha `$, we will write $`rk(\eta )`$ for the least $`\beta `$ such that $`\eta I_\beta `$ and similarly for $`\eta J_\alpha `$,

for all $`\alpha S`$, there is an isomorphism $`G_\alpha :I_\alpha J_\alpha `$,

if $`\alpha C_\beta `$, then $`G_\alpha G_\beta `$,

for all $`\alpha \beta `$ and $`\eta I_\alpha `$, if $`P_\omega (\eta )`$ does not hold, then there is an immediate successor $`\xi `$ of $`\eta `$ such that $`\xi I_{\beta +1}I_\beta `$

if $`(\eta _i)_{i<\omega }`$ is an increasing sequence of elements of $`I_\alpha `$ (for some $`\alpha `$) and the sequence has an upper bound $`\xi `$ in $`I_\alpha `$, then $`rk(\xi )=sup_{i<\omega }rk(\eta _i)`$ and similarly for sequences from $`J_\alpha `$,

if $`(\eta _i)_{i<\omega }`$ is an increasing sequence of elements of $`I_\alpha `$, $`(rk(\eta _i))_{i<\omega }`$ is not eventually constant and the sequence has an upper bound $`\xi `$ in $`I_\alpha `$, then $`rk(\xi )`$ $`(=sup_{i<\omega }rk(\eta _i))`$ $`U`$; in $`J_\alpha `$ such sequences never have an upper bound,

$`|I_\alpha |\omega _3`$ and $`|J_\alpha |\omega _3`$,

$`I_\alpha ,J_\alpha H_\omega (\omega _3)`$, where $`H_\omega (\omega _3)`$ is the least set $`H`$ such that $`\omega _3H`$ and if $`EH`$ is of power $`\omega `$, then $`EH`$.

It is easy to see that such trees can be constructed by induction on $`\alpha `$. However, in order to get what we want we need to do a bit more work when we define $`I_\alpha `$ and $`J_\alpha `$ in the case $`\alpha U`$. In order to decide, which branches like the one in (6) above, we want to have an upper bound, we use a guessing machine from  called black box, which we formulate so that it fits exactly to our purposes.

###### Theorem 16

() ($`\omega _3^\omega =\omega _3`$.) There are $`(\overline{M}^\alpha ,\eta ^\alpha )`$, $`\alpha <\omega _3`$, such that

$`\overline{M}^\alpha =(M_i^\alpha )_{i<\omega }`$ is an increasing elementary chain of elementary submodels of some $`(H_\omega (\omega _3),A,B,\sigma )`$, such that $`A,BH_\omega (\omega _3)`$ and $`\sigma `$ is a strategy of $``$ in $`EF_\omega ^2(A,B)`$ ($`A`$ and $`B`$ can be viewed as models of the empty signature),

$`M_i^\alpha =(M_i^\alpha ,A_i^\alpha ,B_i^\alpha ,\sigma _i^\alpha )H_\omega (\omega _3)`$,

$`\eta ^\alpha `$ is an increasing function from $`\omega `$ to $`\omega _3`$, $`𝐌_i^\alpha H_\omega (\eta ^\alpha (i+1))`$ and $`sup_{i<\omega }\eta ^\alpha (i)U`$,

$`(\eta ^\alpha (j))_{ji},(M_j^\alpha )_{ji}M_{i+1}^\alpha `$,

if $`\alpha \beta `$, then $`\eta ^\alpha \eta ^\beta `$,

player I does not have a winning strategy for the following game: The length of the game is $`\omega `$. At each move $`i<\omega `$, first I chooses $`M_i`$ and then II chooses $`\alpha _i<\omega _3`$. I must play so that in the end (i), (ii) and (iv) above are satisfied. I wins if he has played according to the rules and there is no $`\alpha <\omega _3`$ such that $`((M_i)_{i<\omega },(\alpha _i)_{i<\omega })=(\overline{M}^\alpha ,\eta ^\alpha )`$.

First we uniformize (partially) the Ehrenfeuct-Mostowski construction: We assume that for all $`I,I^{}K_{tr}^\omega `$, if $`I`$ is a substructure of $`I^{}`$ and $`I^{}H_\omega (\omega _3)`$, then there is a unique model $`EM^1(I,\mathrm{\Phi })`$, it is a substructure of $`EM^1(I^{},\mathrm{\Phi })`$ and $`EM^1(I^{},\mathrm{\Phi })H_\omega (\omega _3)`$.

So let $`\alpha U`$ and assume that $`I_\beta `$ and $`J_\beta `$ are defined for all $`\beta <\alpha `$. Write $`I_\alpha ^{}=_{\beta <\alpha }I_\beta `$ and $`J_\alpha ^{}=_{\beta <\alpha }I_\beta `$. For $`\gamma <\omega _3`$, we write $`M^\gamma `$ for $`_{i<\omega }M_i^\gamma `$ and $`A^\gamma `$, $`^\gamma `$ and $`\sigma ^\gamma `$ are defined similarly. Let $`W^\alpha `$ be the set of all $`\gamma <\omega _3`$ such that

$`A^\gamma =EM(I_\alpha ^{}M^\gamma ,\mathrm{\Phi })`$ and $`B^\gamma =EM(J_\alpha ^{}M^\gamma ,\mathrm{\Phi })`$,

$`sup_{i<\omega }\eta ^\gamma (i)=\alpha `$,

there are $`\xi _i^\gamma I_\alpha ^{}M^\gamma `$, $`i<\omega `$, such that $`\xi _0^\gamma `$ is the root of $`I_\alpha ^{}`$, $`\xi _{i+1}^\gamma `$ is an immediate successor of $`\xi _i^\gamma `$ and $`\xi _i^\gamma I_{\eta ^\gamma (i)+1}I_{\eta ^\gamma (i)}`$.

Notice that by Theorem 16 (v), if $`\gamma \delta `$, then $`(\xi _i^\gamma )_{i<\omega }(\xi _i^\delta )_{i<\omega }`$. Let $`C_i^\gamma =SH(\{\xi _i^\gamma \})`$. Then we can find a partial function $`g^\gamma :A^\gamma ^\gamma `$ such that

$`dom(g^\gamma )=_{i<\omega }C_i^\gamma `$,

$`g^\gamma `$ is a result of a play of $`EF_\omega ^2(A^\gamma ,B^\gamma )`$ in which $``$ has used $`\sigma ^\gamma `$.

We let $`W_J^\alpha `$ be the set of those $`\gamma W^\alpha `$ such that

$`g^\gamma `$ is a partial isomorphism from $`EM(I_\alpha ^{}M^\gamma ,\mathrm{\Phi })`$ to $`EM(J_\alpha ^\gamma M^\gamma ,\mathrm{\Phi })`$,

there is $`J`$ such that if we let $`J_\alpha =J`$, then (1),(5)-(8) above are satisfied and there is a sequence $`aEM(J,\mathrm{\Phi })`$ such that for all $`i<\omega `$, $`a\mathrm{}_{g^\gamma (C_i^\gamma )}g^\gamma (a_{\xi _{i+1}^\gamma })`$.

We let $`W_I^\alpha `$ be the set of all $`\gamma W^\alpha W_J^\alpha `$ such that $`g^\gamma `$ satisfies (f) above.

Now we can define $`I_\alpha `$ and $`J_\alpha `$. First we choose $`I_\alpha `$ so that it consists of all $`\eta I_\alpha ^{}`$ together with the supremums for the branches $`(\xi _i^\gamma )_{i<\omega }`$, $`\gamma W_I^\alpha `$. $`J_\alpha `$ is chosen so that it satisfies (g) for all $`\gamma W_J^\alpha `$ (and so especially (1),(5)-(8)).

Then we let $`I=_{\alpha <\omega _3}I_\alpha `$, $`J=_{\alpha <\omega _3}J_\alpha `$, $`𝒜=EM(I,\mathrm{\Phi })`$ and $`=EM(J,\mathrm{\Phi })`$. Clearly $`𝒜`$ and $``$ can be chosen so that $`𝒜,H_\omega (\omega _3)`$.

###### Lemma 17

$``$ does not have a winning strategy for $`EF_{\omega _1}^{\omega _3}(𝒜,)`$.

Proof. For this it is enough to show that $`A`$ does not have a winning strategy for $`EF_{\omega _1}^{\omega _3}(I,J)`$, which is clear by (2) and (3) above and Theorem 15. $`\mathrm{}`$

###### Lemma 18

$``$ does not have a winning strategy for $`EF_{\omega +\omega }^2(𝒜,)`$.

Proof. For a contradiction, assume $`\sigma `$ is a winning strategy of $``$ for the game $`EF_{\omega +\omega }^2(𝒜,)`$. We play a round of the game defined in Theorem 16 (vi). We let player I play so that he follows the rules and

for all $`i<\omega `$, $`M_i(H_\omega (\omega _3),𝒜,,\sigma \omega )`$,

for all $`\delta ,\delta ^{}M_i`$, if $`\delta \delta ^{}`$, $`\eta I_\delta M_i`$ and $`P_\omega (\eta )`$ does not hold, then there is $`\xi (I_{\delta ^{}+1}I_\delta ^{})M_{i+1}`$ such that $`\xi `$ is an immediate successor of $`\eta `$,

the Skolem-hulls of $`\{a_\eta |\eta IM_i\}`$ and $`\{a_\eta |\eta JM_i\}`$ are subsets of $`M_{i+1}`$,

$`𝒜M_i`$ is a subset of the Skolem hull of $`\{a_\eta |\eta IM_{i+1}\}`$ and $`M_i`$ is a subset of the Skolem hull of $`\{a_\eta |\eta JM_{i+1}\}`$,

$`\{rk(\eta )|\eta IM_i\}\{rk(\eta )|\eta JM_i\}M_{i+1}`$.

By Theorem 16 (vi), the round can be played so that $``$ loses. Let $`\alpha _i`$, $`i<\omega `$, be the choices $``$ made and $`\gamma `$ such that $`((M_i)_{i<\omega },(\alpha _i)_{i<\omega })=(\overline{M}^\gamma ,\eta ^\gamma )`$. Finally, let $`\alpha =_{i<\omega }\alpha _i`$ ($`U`$).

Now it is easy to see that $`\gamma W^\alpha `$, in fact $`\gamma W_I^\alpha `$ or $`\gamma W_J^\alpha `$ (otherwise we have demonstrated that $`\sigma `$ is not a winning strategy). In the first case, there is a sequence $`a𝒜`$ such that for all $`i<\omega `$, $`a\mathrm{}_{C_i^\gamma }a_{\xi _{i+1}^\gamma }`$ but in $``$ there is no sequence $`b`$ such that for all $`i<\omega `$, $`b\mathrm{}_{g^\gamma (C_i^\gamma )}g^\gamma (\xi _{i+1}^\gamma )`$, a contradiction. In the latter case, there is a sequence $`b`$ such that for all $`i<\omega `$, $`b\mathrm{}_{g^\gamma (C_i^\gamma )}g^\gamma (\xi _{i+1}^\gamma )`$ but by (the construction,) Lemma 2.3 (c) and Theorem 16 (v), there is no sequence $`a𝒜`$ such that for all $`i<\omega `$, $`a\mathrm{}_{C_i^\gamma }a_{\xi _{i+1}^\gamma }`$, a contradiction. $`\mathrm{}`$

Now Lemmas 2.6 and 2.7 imply Theorem 2 (iii).

### 3.2 The unstable case

We will prove Theorem 2, case (i), again in a series of lemmas. We assume $`\omega _3^\omega <2^{\omega _3}`$. Let $`T`$ be a countable complete unstable first order theory. Let $`L`$ be the signature of $`T`$.

###### Theorem 19

() Assume $`T`$ is a countable unstable theory in the signarute $`L`$. There are a countable signature $`L_1L`$, a complete Skolem theory $`T_1T`$ in the signature $`L_1`$, a first-order $`L`$-formula $`\varphi (x,y)`$ and $`\mathrm{\Phi }`$ proper for $`(\omega ,T_1)`$ (see \[Sh1\] Definition VII 2.6) such that for every linear order $`I`$ there is an Ehrenfeucht-Mostowski model $`EM^1(I,\mathrm{\Phi })`$ of $`T_1`$ with a skeleton $`\{a_\eta |\eta I\}`$ such that

$$EM^1(I,\mathrm{\Phi })\varphi (a_\eta ,a_\xi )\text{iff}I\eta <\xi .$$

We write $`EM(I,\mathrm{\Phi })`$ for $`EM^1(I,\mathrm{\Phi })L`$. Notice that by using the terminology from \[12, Definition III 3.1\], $`\{a_\eta |\eta I\}`$ is weakly $`(\omega ,\varphi )`$-skeleton-like in $`EM(I,\mathrm{\Phi })`$.

In order to use Theorem 19, linear orders are needed. If $`A`$ is a linear ordering, $`xA`$ and $`BA`$, then by $`x<B`$ we mean that for every $`yB`$, $`x<y`$, $`x>B`$ and $`C>B`$, $`CA`$ are defined similarly. By $`A^{}`$ we mean the inverse of $`A`$. Again let $`S`$, $`U`$ and $`C_\alpha `$, $`\alpha S`$, be as in \[8, Lemma 16\], i.e. Theorem 15 above, with the exception that $`0S`$ and for all $`\alpha S\{0\}`$, $`0C_\alpha `$. By induction on $`i<\omega _3`$, we will define linear orders $`A_\alpha ^i`$ and $`B_\alpha ^i`$, $`\alpha <\omega _3`$, and for $`iS`$, isomorphisms

$$G_i:\mathrm{\Sigma }_{\beta <i+2}A_\beta ^i\mathrm{\Sigma }_{\beta <i+2}B_\beta ^i.$$

We write $`A^i(\beta ,\alpha )`$ for $`\mathrm{\Sigma }_{\beta \gamma <\alpha }A_\gamma ^i`$ and similarly $`B^i(\beta ,\alpha )`$. We will do the construction so that the following holds:

$`A_\alpha ^0\omega ^{}`$ for all $`\alpha <\omega _3`$ and if $`\alpha U`$, then $`B_\alpha ^0\omega ^{}`$ and otherwise $`B_\alpha ^0(\omega _1)^{}`$,

If $`i<j`$, then $`A_\alpha ^iA_\alpha ^j`$ and $`B_\alpha ^iB_\alpha ^j`$ and otherwise the sets are distinct and if $`jC_i`$, then $`G_jG_i`$,

if $`cf(\alpha )=\omega `$, then $`A_\alpha ^0`$ is coinitial in $`A_\alpha ^i`$ and similarly for $`B`$.

We will do this by induction on $`i`$. However, in order to be able to show that (3) holds in each step, we need additional machinery.

Let $`C\{A,B\}`$. We say that $`(I,J)`$ is a $`(C,i,\beta )`$-cut if $`I`$ is an initial segment of $`C_\beta ^i`$ and $`J=C_\beta ^iI`$. We say that the cut is basic if $`I=\mathrm{}`$. We define a notion of forbidden cut by induction on $`i`$ as follows (we should talk about $`i`$-forbidden cuts, but $`i`$ is always clear from the context):

for all limit $`\beta `$, the basic $`(C,0,\beta )`$-cut is forbidden,

if $`(I,J)`$ is a $`(C,i,\beta )`$-cut, $`j<i`$ and $`(C_\beta ^jI,C_\beta ^jJ)`$ is forbidden, then $`(I,J)`$ is forbidden,

if $`(I,J)`$ is a forbidden $`(A,i,\beta )`$-cut, $`I^{}=I_{\gamma <\beta }A_\gamma ^i`$ and $`G_i(I^{})`$ is not bounded by any $`x_{\gamma <\delta }B_\gamma ^i`$ but some $`yB_\delta ^i`$ bounds it, then $`(G_i(I^{})B_\delta ^i,B_\delta ^iG_i(I^{}))`$ is forbidden and similarly for $`A`$ and $`B`$ reversed (and $`G_i`$ replaced by $`(G_i)^1`$).

Now we can state the additional properties we want our construction have. Let $`E\{A,B\}`$, $`i,\beta <\omega _3`$ and $`(I,J)`$ be a $`(E,i,\beta )`$-cut.

If $`(I,J)`$ is forbidden, then there is no $`j<\omega _3`$ and $`xE_\beta ^j`$ such that $`I<x<J`$.

Assume $`(I,J)`$ is forbidden and $`jS`$ is such that $`j<i`$ and either $`E_\beta ^jI`$ is cofinal in $`I`$ or $`E_\beta ^jJ`$ is coinitial in J (we say that $`\mathrm{}`$ is both cofinal and coinitial in $`\mathrm{}`$). Then $`(E_\beta ^jI,E_\beta ^jJ)`$ is forbidden.

If $`\beta `$ is successor, then $`E_\beta ^0`$ is coinitial in $`E_\beta ^i`$.

###### Lemma 20

Let $`E\{A,B\}`$.

For all $`i,\beta <\omega _3`$, if (5) holds upto the stage $`i`$, then $`(E_\beta ^i,\mathrm{})`$ is not forbidden and neither is $`(\mathrm{},E_\beta ^i)`$, if $`\beta `$ is successor.

For limit $`\beta `$, every basic $`(E,i,\beta )`$-cut is forbidden.

The property (4) implies the property (3).

If $`i+1<\beta `$ and $`(I,J)`$ is a forbidden $`(E,i,\beta )`$-cut, then it is basic (and $`\beta `$ is limit).

Proof. Immediate. $`\mathrm{}`$

Now we are ready to do the construction: For $`i=0`$, the linear orders are defined by (1) and we let $`G_0`$ be the only possible one. Clearly (1)-(6) hold. If $`iS`$ or $`supC_i=i`$, then we let $`A_\alpha ^i=_{j<i}A_\alpha ^j`$, $`B_\alpha ^i=_{j<i}B_\alpha ^j`$ and if $`iS`$ (and $`supC_i=i`$), then $`G_i=G_{jC_i}G_j`$, where $`G`$ is the obvious isomorphism from $`A^i(i,i+2)`$ to $`B^i(i,i+2)`$ (both are isomorphic to $`\omega ^{}+\omega ^{}`$). Now (1), (2), (4) and (6) hold trivially. By Lemma 2.9 (iii), (3) holds. For (5), assume that $`C\{A,B\}`$ and $`(I,J)`$ is a forbidden $`(C,i,\beta )`$-cut. Now the reason why $`(I,J)`$ is forbidden is (b) in the definition of forbidden cut (if $`iS`$, then this is trivial and otherwise by the definition of $`G_i`$, (c) does not give forbidden cuts not forbidden by (b)). But then (5) follows immediately from the induction assumption.

We are left with the case $`iS`$ and $`j=supC_i<i`$. Notice that now $`jC_i`$. Let $`\alpha <j+2`$ and $`A\mathrm{}`$ be an initial segment of $`A_\alpha ^j`$. Let $`A^+=A_{\gamma <\alpha }A_\gamma ^j`$. Then there is the least $`\beta <j+2`$ such that $`B^+=G_j(A^+)(_{\gamma \beta }B_\beta ^j)=G_j(A^+)`$. Let $`A^{}=(A_\alpha ^jA_{\alpha +1}^j)A`$, $`B=G_j(A)B_\beta ^j`$ and $`B^{}=(B_\beta ^jB_{\beta +1}^j)B`$. Assume that at least one of $`C^{}=\{x_{k<i}(A_\alpha ^kA_{\alpha +1}^k)|A<x<A^{}\}`$ and $`D^{}=\{x_{k<i}(B_\beta ^kB_{\beta +1}^k)|B<x<B^{}\}`$ is non-empty. Then by the induction assumption, $`B\mathrm{}`$. Let $`C`$ be a copy of $`C^{}`$ and $`D`$ a copy of $`D^{}`$. Then we define $`A_\alpha ^i`$ so that it contains $`_{k<i}A_\alpha ^k`$ and in each cut like above we add $`D`$ so that $`A<C^{}<D<A^{}`$ and $`B_\beta ^i`$ is defined similarly but now $`B<C<D^{}<B^{}`$ (this is possible by (6) in the induction assumption). Then, by (4) in the induction assumption, we can find an isomorphism $`G_i^{}:_{\alpha <j+2}A_\alpha ^i_{\alpha <j+2}B_\alpha ^i`$. Notice that by (5) in the induction assumption, for all $`\delta <i`$, the $`(A,\delta ,\alpha )`$-cut $`(A_\alpha ^\delta A(\delta ),A(\delta ))`$ and $`(B,\delta ,\beta )`$-cut $`(B(\delta ),B_\beta ^\delta B(\delta ))`$ are not forbidden, where $`A(\delta )=\{xA_\alpha ^\delta |x>C^{}\}`$ and $`B(\delta )=\{xB_\beta ^\delta |x<D^{}\}`$. So we have not violated the property (4).

For all $`\alpha >j+1`$, we let $`A_\alpha ^i=_{k<i}A_\alpha ^k`$ and $`B_\alpha ^i`$ is defined similarly. However we will still make changes to $`B_{j+1}^i`$ and $`A_{i+1}^i`$! Let $`A`$ be a copy of $`B^i(j+3,i+2)`$ and $`B`$ be a copy of $`A^i(j+2,i+1)`$. Furthermore, extend $`A_{i+1}^i`$ so that there is an isomorphism $`g:A_{i+1}^iB_{j+2}^i`$ such that $`g(A_{i+1}^0)=B_{j+2}^0`$ (this is not a problem since $`A_{i+1}^0=_{k<i}A_{i+1}^k\omega ^{}B_{j+2}^0`$ and by Lemma 2.9 (iv), the sets $`A_{i+1}^k`$, $`k<i`$, do not contain forbidden $`(A,k,i+1)`$-cuts; so we do not violate (4)). Then we add $`A`$ to (the extended) $`A_{i+1}^i`$ as an end segment and $`B`$ to $`B_{j+1}^i`$ as an end segment. By Lemma 2.9 (i), this does not violated (4). Now it is easy to extend $`G_i^{}`$ to $`G_i`$ so that $`G_i(A^i(j+2,i+1))=B`$, $`G_i(A_{i+1}^iA)=B_{j+2}^i`$ and $`G_i(A)=B^i(j+3,i+2)`$.

Now (1), (2) and (6) hold trivially, (4) is already shown to hold and by Lemma 2.9 (iii), (4) implies (3). So we are left to show that

###### Lemma 21

(5) holds.

Proof. Assume $`(I,J)`$ is a forbidden $`(E,i,\beta )`$-cut, $`E\{A,B\}`$, and $`\delta S`$ is such that $`\delta <i`$ and $`E_\beta ^\delta J`$ is coinitial in J, the other case is similar. If $`\beta j+1`$ and both $`J(_{k<i}A_{j+1}^k)`$ and $`J(_{k<i}B_{j+1}^k)`$ are empty, then the claim follows easily from Lemma 2.9 and the induction assumption. So we assume that this is not the case. If $`(I,J)`$ is forbidden because of (b) in the definition of forbidden cut, the claim follows from the induction assumption. So we assume that $`E=B`$ and there is a forbidden $`(A,i,\gamma )`$-cut $`(C,D)`$ such that $`(I,J)`$ is forbidden by (c) applied to $`(C,D)`$ (the case $`A`$ and $`B`$ reversed is symmetric). Since $`(I,J)`$ is not forbidded by (b) in the definition of forbidded cut, $`(C,D)`$ must be forbidden because of it, i.e. for some $`\alpha <i`$, $`(A_\gamma ^\alpha C,A_\gamma ^\alpha D)`$ is a forbidden $`(A,\alpha ,\gamma )`$-cut.

If

For no $`yA_\gamma ^\alpha D`$, $`y<A_\gamma ^jD`$,

then by the induction assumption, $`(B_\beta ^jI,B_\beta ^jJ)`$ is a forbidden $`(B,j,\beta )`$-cut and the claim follows from the definition of forbidden cut if $`\delta j`$ and from (5) in the induction assumption if $`\delta <j`$. So we assume that ($``$) fails. Let $`y`$ be the bound. Then $`\mathrm{}D^{}=\{zA_\gamma ^iD|zy\}A_\gamma ^idom(G_j)`$. So by the construction, $`G_i(D^{})JB_\beta ^\delta `$ and for all $`xB_\beta ^\delta `$, ether $`x<G_i(D^{})`$ or $`x>G_i(D^{})`$. By the choice of the cut $`(C,D)`$, there can not be $`xJB_\beta ^\delta `$ such that $`x<G_i(D^{})`$. But then $`G_i(D^{})<JB_\beta ^\delta `$, which contradicts the assumption that $`JB_\beta ^\delta `$ is coinitial in $`J`$. $`\mathrm{}`$

Let $`A=\mathrm{\Sigma }_{\alpha <\omega _3}_{i<\omega _3}A_\alpha ^i`$ and $`B=\mathrm{\Sigma }_{\alpha <\omega _3}_{i<\omega _3}B_\alpha ^i`$. Notice that by (1) and (3), $`inv_\omega ^1(A)`$ differs from $`inv_\omega ^1(B)`$ in a stationary set which consists of ordinals of cofinality $`\omega `$ (for the definition of $`inv_\omega ^n`$, see \[12, Definition III 3.4\]. Let $`S_\alpha S_0^3`$, $`i<2^{\omega _3}`$, be stationary sets such that for $`\alpha <\beta <2^{\omega _3}`$, $`S_\alpha \mathrm{}S_\beta `$ is stationary and define $`\mathrm{\Psi }_\alpha =\mathrm{\Sigma }_{\alpha <\omega _3}\tau _\alpha `$, where $`\tau _\alpha =A^{}`$ if $`\alpha S_\alpha `$ and otherwise $`\tau _\alpha =B^{}`$. Notice that for $`\alpha \beta `$, $`inv_\omega ^2(\mathrm{\Psi }_\alpha )`$ differs from $`inv_\omega ^2(\mathrm{\Psi }_\beta )`$ in a stationary set which consists of ordinals of cofinality $`\omega `$.

Finally, let $`𝒜_\alpha =EM((\mathrm{\Psi }_\alpha )^{}\omega _1,\mathrm{\Phi })`$.

###### Lemma 22

For all $`\alpha ,\beta <2^{\omega _3}`$, A does not have a winning strategy for $`EF_{\omega _1}^{\omega _3}(𝒜_\alpha ,𝒜_\beta )`$.

Proof. For this, it is enough to show that A does not have a winning strategy for $`EF_{\omega _1}^{\omega _3}((\mathrm{\Psi }_\alpha )^{}\omega _1,(\mathrm{\Psi }_\beta )^{}\omega _1)`$, which follows easily from (2) in the construction of $`A`$ and $`B`$ and Theorem 15 (see e.g. \[8, Claim 3 in the proof of Theorem 17\]). $`\mathrm{}`$

###### Lemma 23

There are $`\alpha <\beta <2^{\omega _3}`$ such that E does not have a winning strategy for $`EF_{\omega _1}^2(𝒜_\alpha ,𝒜_\beta )`$.

Proof. By using the usual forcing notion, we collapse $`\omega _3`$ to an ordinal of power $`\omega _1`$. Since this forcing notion does not kill those stationary subsets of $`\omega _3`$ which consist of ordinals of cofinality $`\omega `$ and cofinalities $`\omega _1`$ are preserved, in the extension, $`inv_\omega ^2(\mathrm{\Psi }_\alpha )inv_\omega ^2(\mathrm{\Psi }_\beta )`$ for all $`\alpha \beta `$. Clearly, the skeletons of the models $`𝒜_\alpha `$, remain weakly $`(\omega ,\varphi )`$-skeleton-like in $`𝒜_\alpha `$. So by (the proof of) \[12, Lemma III 3.15 (1)\], $`inv_\omega ^2(\mathrm{\Psi }_\alpha )INV_\omega ^2(𝒜_\alpha ,\varphi )`$ in the extension (for the definition of $`INV_\omega ^n`$, see \[12, Definition III 3.11\] and notice that $`𝒜`$ implies $`INV_\omega ^2(𝒜,\varphi )=INV_\omega ^2(,\varphi )`$). Also by \[Sh2\] Lemma III 3.13 (1), $`|INV_\omega ^2(𝒜_\alpha ,\varphi )|=\omega _1`$. Since $`\omega _3^\omega <2^{\omega _3}`$ in the ground model, in the generic extension, $`(2^{\omega _3})^V`$ is a cardinal $`>\omega _1`$. So there are $`\alpha <\beta <(2^{\omega _3})^V`$ such that $`𝒜_\alpha \cong ̸𝒜_\beta `$ in the extension. Since countable subsets are not added, E does not have a winning strategy for $`EF_{\omega _1}^2(𝒜_\alpha ,𝒜_\beta )`$ (in the ground model). $`\mathrm{}`$

Now Lemmas 2.11 and 2.12 imply Theorem 2 (i). $`\mathrm{}`$

Before proving the theorem, we make some remarks which follow from the proof.

###### Remark 24

In many cases in Theorem 2, the assumption on $`2^\omega `$ can be removed. For example, this is true of linear orders. An easy proof for this is given in , alternatively this follows immediately from the proof of Theorem 2 (i) by checking where the assumption $`2^\omega <2^{\omega _3}`$ was needed. Another case where the assumption on $`2^\omega `$ can be removed is the case that $`\theta =\omega _3`$ in the stable unsuperstable case. This follows from the proof of Theorem 2 (iii) by noticing that the black box can now be replaced by an argument from . Another remark is that in Theorem 2 (i) and (ii), $`\omega _3`$ can be replaced by any cardinal $`\kappa \omega _3`$ such that $`\kappa `$ is a successor of a regular cardinal and $`2^\kappa >\kappa ^\omega `$. Finally, in Theorem 2 (iii), $`\omega _3`$ can be replaced by any cardinal $`\kappa \omega _3`$ such that $`\kappa `$ is a successor of a regular cardinal and $`\kappa ^\omega =\kappa `$.


text:
# An Automated System to Classify Stellar Spectra I.

## 1 Introduction

Mass, radius, and luminosity are some of the most interesting properties of a star. Unfortunately, it is non-linear combinations of them that produce quasi-linear changes on a stellar spectrum. Stellar fluxes are commonly interpreted in terms of atmospheric temperature, pressure, and chemical composition. In the context of classical flux-constant model atmospheres, these fields are simply specified with three scalars: the effective temperature, the surface gravity, and a solar-scaled metallicity. Nevertheless, extracting the three from an observed spectrum is rarely trivial.

A spectroscopic classification system has been developed independently of the physical parameters. The MK system (Morgan, Keenan & Kellman 1943) lays out a series of rules to assign spectral classes from medium-low resolution spectra. This method has the advantage of providing a standard reference independent of models. However, it is somewhat artificial, in the sense that the defined spectral classes are obviously correlated with the relevant atmospheric parameters. Moreover, the classical MK system does not provide for metal-poor stars. One may note, as an example, that the metal-poor giant HD 122563, which has an effective temperature around 4600 K, has been often classified as a late-F or early-G type star. On the other hand, classification methods based on physical parameters are more natural, but model-dependent.

Both the MK and the physical classification systems have their own advantages, and this may be the reason why they still coexist. But, the fact that it is the physical parameters what is ultimately demanded for astronomical applications is shifting most of the recent research toward the direct extraction of those quantities. As recognized by many specialists, repeatability and high speed in spectroscopic stellar classification can only be achieved by using automatic methods. A recent discussion of the most used methods can be found in Bailer-Jones (2001).

Derived stellar parameters may differ when determined from different wavelength ranges or spectral features. Among other reasons, this may be caused by using models that are too simplistic. As the parameters will be derived from their expected effect on the spectra, inaccurate predictions, or neglect of other relevant parameters, will bias the results. Details in the implementation of a classification procedure are also a reason to worry. The wide range of effective temperatures that have been assigned to the metal-poor subgiant HD 140283 in the recent literature serves as testimony of the respectable uncertainties still involved in the scale of effective temperatures (see, e.g., the discussion in Snider et al. 2001).

Discrepancies produced by interpreting stellar spectra with model atmospheres that are too simple will decrease as progress in theory takes place. For main-sequence stars, remarkable advances are happening as efforts focus on relaxing the assumptions of Local Thermodynamic Equilibrium (LTE) and hydrostatic equilibrium. Systematic differences that arise in the implementation of different methods for spectroscopic classification can be controlled by establishing standards. A reference implementation would be far more powerful than a set of standard stars. Modern information technologies have paved the way for implementing a public automatic classification system accessible over the Internet. Such open system, if reliable and fast, could serve as a standard reference.

This paper discusses the first steps toward the implementation of a prototype for an open classification system. This work will only deal with a section of the HR diagram; stars with spectral types A to K and scaled solar metal abundances. Section 2 describes the selected wavelength band, §3 the working parameters space, and §4 provides details of the implementation. Section 5 is devoted to connecting the parameters derived from spectroscopy to a widely accepted scale of effective temperatures based on the Infrared Flux Method, and checking the performance of the method. Section 6 concludes with a summary of present results and ideas for subsequent work.

## 2 Wavelength range

When using equivalent widths and classical flux-constant model atmospheres in abundance analyses, the relevant parameters can be usually reduced to four: the stellar effective temperature ($`T_{\mathrm{eff}}`$), the surface gravity ($`g`$), the micro-turbulence ($`\xi `$), and the metal abundances – commonly considered proportional to the iron abundance. For stars with spectral types A-K, the most useful and accessible observational probes for these parameters are the flux distribution and the spectral lines: excitation and ionization equilibrium of metals, the pressure-enhanced wings of strong metal lines, and the hydrogen lines. Different procedures to derive stellar parameters rely on one or several of these indicators.

At this point we set aside potential difficulties to model some of the spectral features mentioned above. We refer the reader to the papers by Dragon & Mutschlecner (1980), Castelli, Gratton & Kurucz (1997), or Bell, Balachandran & Bautista (2001) regarding the modelling of the continuum flux; Thévenin & Idiart (1999) or Asplund et al. (2000) on the calculation of Fe I line profiles; and Fuhrmann, Axer & Gehren (1996), Gardiner, Kupka & Smalley (1999), Barklem, Piskunov & O’Mara (2000), or Cowley & Castelli (2002) on modelling Balmer lines. With the ultimate goal of deriving chemical abundances, most spectroscopic observations aim at providing reliable line profiles or equivalent widths for lines of weak-to-moderate strength. Ideally, one would use the same type of spectra to determine the stellar atmospheric parameters. In addition, accurate spectrophotometry is challenging and highly vulnerable to reddening. Forcing the excitation and ionization equilibrium balance for metal lines is, in most cases, insufficient to reliably determine the quartet ($`T_{\mathrm{eff}}`$, $`\mathrm{log}g`$, \[Fe/H\]111\[Fe/H\] $`=\mathrm{log}\frac{N(\mathrm{Fe})}{N(\mathrm{H})}\mathrm{log}\left[\frac{N(\mathrm{Fe})}{N(\mathrm{H})}\right]_{}`$, where $`N(\mathrm{E})`$ represents the number density of the element E., $`\xi `$). Therefore, we resort to a second feature, the Balmer lines.

We selected a continuous spectral window around H$`\beta `$: 4810–4960 Å. This wavelength range represents a balance in many aspects. It is red enough that the continuum opacity is well described by H and H- for the stars under consideration, avoiding the difficulties of dealing with much more complicated (metal) opacities, and it is blue enough that the presence of spectral lines makes possible a reliable determination of the metal abundance – even in metal-poor stars.

## 3 Working domain

Use of equivalent widths, quantifying the strength of a spectral line by a single number, represents a loss of information. Use of line profiles introduces more variables in the analysis through the different line broadening mechanisms. Accounting for the broadening involves a number of difficulties in the practical implementation of a classification algorithm, although it also comes with extra information, e.g. projected rotational velocity, or instrument spectral resolution. At this point we wish to restrict the classification to ($`T_{\mathrm{eff}}`$, $`\mathrm{log}g`$, \[Fe/H\], $`\xi `$) and, therefore, we use a fixed resolving power $`R\lambda /\delta \lambda 5000`$. We covered the selected spectral range with 301 points, equally spaced in wavelength (every 0.5 Å). Our choice of resolution is a compromise: low enough to make rotational and macro-turbulent broadening in late-type stars negligible, and high enough to be able to recover information on the stellar atmospheric parameters. Fig. 1 shows observations for the Sun (solid; Kurucz et al. 1984), Procyon (dashed; Allende Prieto et al. 2002), and Arcturus (dash-dotted; Hinkle et al. 2000). The most relevant features have been identified in the figure.

The range for each of the atmospheric parameters was selected to avoid some extreme conditions where classical model atmospheres in general, or those used here in particular, are expected, or known, to fail: cool temperatures at which the contribution of molecules to the equation of state is incomplete in the models; hot temperatures at which departures from LTE are important for the atmospheric structure; or too extended an atmosphere that the plane-parallel approximation is inadequate. The selected domain is:

(5)
Arcturus is probably cooler than our lower limit for $`T_{\mathrm{eff}}`$ \[Griffin & Lynas-Gray (1999) assign $`4290\pm 30`$ K to this star\], but it serves the purpose of showing an example of the coolest spectra in our working sample. As will become clear later, our raw $`T_{\mathrm{eff}}`$s are systematically higher than other scales and thus a star with this effective temperature is technically within the limits of our grid.

Extensive testing showed that the flux in the selected spectral window satisfies a one-to-one relationship with most of the parameters space. In other words, for a given combination of the four atmospheric parameters considered, the resulting flux in this window is unique. Approaching the extreme metal-poor limit, below \[Fe/H\] $`<3`$, degeneracy is unavoidable, as metal lines vanished, and so does the information on metallicity, gravity and microturbulence. The flux in the selected window is not equally sensitive to changes in the different stellar parameters. Changes in $`T_{\mathrm{eff}}`$ affect the most the spectrum, followed by variations in the metal abundance. The effect of changes in the surface gravity is mainly felt through the different sensitivity of lines of neutral and ionized metals to pressure, and it is more subtle than the response to $`T_{\mathrm{eff}}`$ or \[Fe/H\].

## 4 Implementation

To find the set of parameters that best reproduces an observed spectrum, we need to choose an algorithm. We want to minimize (or maximize) a function of the stellar parameters. This will require us to evaluate a function – thus compute synthetic spectra – a number of times. This number can be very large, and therefore a strategy to reduce computing time is needed. We have tackled this problem by computing a discrete grid and interpolating. We adopted the following increments for the four parameters involved: 500 K in $`T_{\mathrm{eff}}`$, 1.0 dex in $`\mathrm{log}g`$, 1.0 dex in \[Fe/H\], and 1.0 km s-1 in $`\xi `$. These were chosen to keep the changes in the spectrum small enough so that a fast multilinear interpolation would provide a reasonable approximation. Interpolation errors can reach up to 2 % for the warmer stars in the grid, but up to 7 % for the coolest metal-rich stars. These errors are smaller than the precision with which the real spectra can be reproduced, and it was later verified that use of a finer grid does not improve the performance of the classification method. We used a genetic algorithm (GA) to solve our minimization problem. GAs are suitable for solving global optimization problems in complex landscapes where local extrema can confuse simpler algorithms (see Charbonneau 2002 for an informal introduction).

The grid of synthetic spectra was based on non-overshooting Kurucz (1993) model atmospheres. These models include mixing-length convection with $`\alpha =1.25`$, and $`\xi =2.0`$ km s-1. The radiative transfer equation was solved with the code Synspec (Hubeny & Lanz 2000), using very simple continuous opacities: H, H-, Rayleigh and electron scattering (as described in Hubeny 1988). An atomic line list was prepared with the data obtained from the Vienna Atomic Line Database (VALD; Kupka et al. 1999). This line list includes 7169 lines that are expected to contribute to the opacity in a solar-like atmosphere. The computed spectra were degraded to a resolving power of about 5000, sampled with a common wavelength vector, and normalized.

The presence of a very broad line in the spectral window ($`H\beta `$) makes normalization difficult. We have adopted a straightforward unsupervised polynomial normalization. Although the results of this scheme would visually displease most stellar spectroscopists (see Fig. 2), this simple procedure can be carried out quickly, and repeatability is easily achieved for a given set ($`T_{\mathrm{eff}}`$, $`\mathrm{log}g`$, \[Fe/H\], $`\xi `$). In addition, the fluxes were also divided by a constant, 1.8, to enforce flux values between 0 and 1 – a requirement of the GA software.

We implemented a FORTRAN routine to perform multilinear interpolation in the four parameters under consideration. This routine is the interface between the grid of synthetic spectra and the genetic algorithm. The function we chose to maximize is:

$$1\underset{i}{}w_i(f_iO_i)^2$$
(6)
where f is the vector of interpolated synthetic flux, O is the vector of observations, and the index i indicates a particular wavelength bin. We adopted

$$w_i=(f_i^{}O_i^{})^2/10^4,$$
(7)
as derived from the solar spectrum and a synthetic flux calculated with solar parameters, but reset to

(13)
The many necessary multilinear interpolations are very fast, as the grid of previously computed synthetic spectra is kept in memory. In fact, a non-negligible fraction of the time is invested in loading those data. We adopted a publicly available GA software222Available from http://cuaerospace.com/carroll/ga.html, due to D. L. Carroll (see, e.g., Carroll 1996). The default parameters were kept, namely, a micro-GA with uniform crossover. The GA was run for 500 generations. This number was chosen from inspection of the convergency curve for a limited number of stars, but it was later verified that increasing this value to 2000 generations did not produce any improvement in the performance. Classification of a single spectrum takes about 3 seconds on a Sun Ultra5. Fig. 2 illustrates the agreement between the observed and the matched synthetic spectra for Procyon, the Sun, Arcturus, and the metal-poor star HD 2665 (\[Fe/H\] $`1.9`$). The spectrum of HD 2665 was obtained from the Elodie library (Prugniel & Soubiran 2001).

## 5 Connecting our stellar parameters to the IRFM $`T_{\mathrm{eff}}`$ scale

Detailed modelling of H$`\beta `$ is an issue. Even though the wings of Balmer lines are considered to form very close to LTE conditions, that does not apply to their cores. A tougher complication is the fact that Balmer lines are commonly affected by the temperature distribution in the deepest atmospheric layers, which for late-type stars are significantly influenced by convection. Convection is typically treated using a mixing-length formalism which implies a choice for one or several parameters. This represents an important additional source of uncertainty in the derived parameters – very likely a systematic bias in the derived $`T_{\mathrm{eff}}`$. Such a bias in $`T_{\mathrm{eff}}`$, because of the tight coupling between $`T_{\mathrm{eff}}`$, $`g`$, and \[Fe/H\], will also produce a bias in the other two parameters. In our view, the best possible option is to anchor our spectroscopic $`T_{\mathrm{eff}}`$ scale to a more reliable scale. The systematic effect in $`g`$ and \[Fe/H\] implied by the necessary correction to our derived $`T_{\mathrm{eff}}`$ can be easily predicted. Empirical studies have shown that a shift in an adopted $`T_{\mathrm{eff}}`$ will, through the iron excitation-ionization balance, translate to a shift in $`\mathrm{log}g`$:

$$\mathrm{\Delta }\mathrm{log}g\mathrm{\Delta }T_{\mathrm{eff}}/466.$$
(14)
(Allende Prieto 1998), and a correction to \[Fe/H\]:

$$\mathrm{\Delta }[\mathrm{Fe}/\mathrm{H}]\frac{\mathrm{\Delta }\mathrm{log}g}{3.0}$$
(15)
(e.g. Gray 1992; Allende Prieto et al. 1999).

As we will be applying this correction to our $`T_{\mathrm{eff}}`$ scale, and the sensitivity to $`T_{\mathrm{eff}}`$ of the selected spectral region relies largely on the $`H\beta `$ profile, there is no need to make a serious emphasis on the accuracy of the calculated absorption profile for H$`\beta `$. We can make use of some approximations, and take advantage of a reduced computing time. In particular, we use an approximate broadening treatment described in the Appendix B of Hubeny, Hummer & Lanz (1994). As this approach underestimates the width of the solar H$`\beta `$ profile, we apply a zeroth order correction, using twice the default value. This modification is not strictly necessary, as the correction to be applied later to the $`T_{\mathrm{eff}}`$ scale would be able to fix this zero point as well.

We decided to anchor our spectroscopic $`T_{\mathrm{eff}}`$ scale to that of Alonso, Arribas & Martínez-Roger (1996, 1999), which is based on the Infrared Flux Method, as modelled with fluxes from Kurucz (1993) model atmospheres. A library of high-resolution spectra recently published by Prugniel & Soubiran (2001) is used as testing field for our classification scheme. This library, hereafter the Elodie library, consists of more than 908 spectra from 709 stars spanning a large fraction of, and in some instances exceeding, our parameter space. We determine the $`T_{\mathrm{eff}}`$ for each star using the Alonso et al. calibrations for $`(BV)`$. These calibrations use $`(BV)`$ and \[Fe/H\], and both parameters were adopted from those given in the Elodie library. The division of the stars in IV-V or I-III classes, in order to select the appropriate IRFM calibration, is based on the gravities provided in the Elodie library, setting the division line at $`\mathrm{log}g=3.8`$.

The spectra in the library with a resolution of $`R=10,000`$ are convolved with a Gaussian profile with a FWHM of 1.0 Å, and then fed to our classification system to find a best-fitting vector ($`T_{\mathrm{eff}}`$, $`g`$, \[Fe/H\], $`\xi `$). Then, the values derived for $`T_{\mathrm{eff}}^{raw}`$ are compared against those from the IRFM calibrations. The two scales are confronted in Fig. 3. A second-order least-squares polynomial fit is adopted to anchor the derived $`T_{\mathrm{eff}}^{raw}`$ to the IRFM scale:

$$T_{\mathrm{eff}}^{raw}=57830.6686T_{\mathrm{eff}}^{IRFM}+0.0001159(T_{\mathrm{eff}}^{IRFM})^2,$$
(16)
and this correction is also translated to $`\mathrm{log}g`$, and \[Fe/H\], based on the correlation expected for the excitation-ionization balance (see Eqs. 5 and 6). Fig. 3 reveals a tendency for some stars to clump at certain values of $`T_{\mathrm{eff}}`$, in particular at $`5375`$ K. Too aggressive a choice for the steps in the grid parameters (with the implied errors in the linear interpolation) is not to blame for this systematic effect, which is related to caveats involved in the implementation of GAs. Noticeably, the scatter is not symmetrically distributed about the adopted mean relationship, defined by the polynomial fit. This is actually what we expect when reddening is not negligible, introducing significant errors in the photometric $`T_{\mathrm{eff}}`$ \[which are based on unreddened values for $`(BV)`$\]. Addressing these and other issues exceeds the scope of this exploratory study.

The corrected $`T_{\mathrm{eff}}`$, $`\mathrm{log}g`$, and \[Fe/H\] values can be directly compared to those given in the Elodie library. The mean difference and the $`\sigma _{rms}`$ (607 spectra) are

(20)
and Fig. 4 compares the two sets of parameters.

A contribution to the error bars is connected with the parameters adopted for the Elodie library, mainly compiled from the literature. The library also provides estimates of the reliability of the adopted values. Restricting the comparison to the spectra with the most trusted parameters333Using the library’s code: q($`T_{\mathrm{eff}}`$)=4, q($`\mathrm{log}g`$)=1, q(\[Fe/H\])=4, we find (71 spectra)

(24)
The $`\sigma _{rms}`$ for the same stars between the IRFM $`T_{\mathrm{eff}}`$s, and those we derived is 80 K. The agreement for $`T_{\mathrm{eff}}`$ and \[Fe/H\] is satisfying, but it is not so for $`\mathrm{log}g`$. As explained in §4, the sensitivity of the spectrum to this parameter is not nearly as high as to the others. We find that 36 stars from the last set are included in the determination of stellar parameters by Allende Prieto & Lambert (1999) based on the comparison of observed colors and parallaxes with evolutionary models. The mean and median uncertainties for the reference gravities are both 0.08 dex. For these stars, we find a more satisfactory mean difference and $`\sigma _{rms}`$ in $`\mathrm{log}g`$: $`0.05\pm 0.28`$ dex, as shown in Fig. 5, which leads us to believe that 0.3 dex is a reasonable estimate for our random errors in gravity.

## 6 Conclusions and Future applications

We have implemented a spectroscopic classification algorithm that provides estimates for $`T_{\mathrm{eff}}`$, $`\mathrm{log}g`$, \[Fe/H\], and $`\xi `$ based on the observations with a resolving power $`R5000`$ in the spectral range 4810–4960 Å. The classification system is based on synthetic spectra calculated with classical flux-constant model atmospheres, and it is anchored to the photometric calibrations of effective temperature derived by Alonso and collaborators (Alonso et al. 1996, 1999) based on the Infrared Flux Method. By using the Elodie spectroscopic library (Prugniel & Soubiran 2001) and the gravities determined by Allende Prieto & Lambert (1999) for nearby Hipparcos stars, we derive upper limits to the uncertainties in the retrieved $`T_{\mathrm{eff}}`$, $`\mathrm{log}g`$, and \[Fe/H\], as 100 K, 0.3 dex, and 0.1 dex, respectively.

Our classification algorithm can be used on spectral types A to K, for main-sequence and evolved stars with gravities as low as $`\mathrm{log}=2`$, and all metallicities. The system is able to classify a stellar spectrum in only 3 seconds on a modern workstation. Work is in progress to improve the accuracy of the synthetic spectra by using a more realistic line absorption profile for H$`\beta `$. We also plan on varying the parameters that affect the performance of the employed GA, and testing different optimization algorithms. An important question to answer is how the performance of our system improves or degrades with spectral resolution and signal-to-noise ratio. Different spectral ranges should be explored. Spectral bands with lines of metals whose abundances do not scale well with iron should be avoided, unless more parameters are included in the search, which is certainly feasible.

Different classification algorithms for stellar spectra have been tested in the literature. In particular, artificial neural networks hold the promise for the highest speeds, which may be critical for problems involving a large number of free parameters (see, e.g. Bailer-Jones 2001; Snider et al 2001). When the number of parameters is limited, like in the spectroscopic classification considered here, GAs have the advantage of not requiring training. This, in turn, allows us to explore different strategies, such as the selection of the spectral range or the resolving power, very quickly, while keeping the search global.

Our final goal is to provide a web interface and make this or a similar system publicly available. Future work will target hotter spectral types, using calculations based upon non-LTE model atmospheres. Extension to the bottom of the main-sequence and beyond could follow, although theoretical modelling of cool atmospheres has not yet reached the same level of maturity as for warmer stars. The adopted strategy can easily accommodate future improvements in model atmospheres and spectral synthesis.

## 7 Acknowledgments

Paul Barklem, Tim Beers, Norbert Christlieb, David Lambert, Chris Sneden, and Ted von Hippel are thanked for inspiring discussions. I am obliged to David Carroll for making his GA software publicly available, and to the Elodie team for sharing their database of stellar spectra. NSF support (grant AST 00-86321) is gratefully acknowledged.