More on regular reduced products

Juliette Kennedy Research partially supported by grant 40734 of the Academy of Finland. Department of Mathematics University of Helsinki Helsinki, Finland

Saharon Shelah The second author would like to thank the Israel Science Foundation for partial support of this research (Grant no. 242/03). Publication 852. Institute of Mathematics Hebrew University Jerusalem, Israel

November 27, 2006

Abstract
The authors show, by means of a finitary version □ λ , D f i n   of the combinatorial principle □ λ b *   of [6] , the consistency of the failure, relative to the consistency of supercompact cardinals, of the following: for all regular filters D   on a cardinal λ   , if M i   and N i   are elementarily equivalent models of a language of size ≤ λ   , then the second player has a winning strategy in the Ehrenfeucht-Fraïssé game of length λ +   on ∏ i M i / D   and ∏ i N i / D   . If in addition 2 λ = λ +   and i < λ   implies | M i | + | N i | ≤ λ +   this means that the ultrapowers are isomorphic. This settles negatively conjecture 18 in [1] .
The problem of when two elementarily equivalent structures have isomorphic ultrapowers was prominent in the model theory of the 1960's. Keisler [2] proved, assuming GCH, that elementarily equivalent structures have isomorphic ultrapowers. Keisler's proof depended on GCH both on the question of existence of good ultrafilters and on limiting the size of the ultraproducts.
More exactly, Keisler considered a language of size λ   , models M   of size ≤ λ +   and a λ +   -good countably incomplete ultrafilter D   on λ   . He proved that M λ / D   is λ +   -saturated. Under the weaker assumption that D   is regular he proved that M λ / D   is λ +   -universal, i.e. every N ≡ M λ / D   can be elementarily embedded into it.
Shelah [5] improved the result by eliminating GCH: two structures M   and N   are elementarily equivalent if and only if, for some λ   and some regular ultrafilter D   on λ   the structures M λ / D   and N λ / D   are isomorphic. This left open the following question, asked by Chang and Keisler as Conjecture 18 in [1] :
  • Let M   and N   be structures of cardinality ≤ λ   in a language of size ≤ λ   and let D   be a regular ultrafilter over λ   . If M ≡ N   , then M λ / D ∼ = N λ / D   .
The Conjecture is a natural one as most of the model theory regarding ultrapowers is centered on the regular ultrafilters. Also at the time of Keisler's question GCH was generally considered a reasonable assumption for the question.
Also the Conjecture is formulated for models of size ≤ λ   , perhaps for accidental reasons, but it seems more natural if M   and N   have cardinality ≤ λ +   .
Conjecture 19 of [1] , which we also address in this paper, is:
  • If D   is a regular ultrafilter over λ   , then for all infinite M   , M λ / D   is λ + +   -universal.
In [4] the authors proved that the transfer principle ( ℵ 1 , ℵ 0 ) → ( λ + , λ )   implies for all regular filters D   on λ  
  • ( 1 ) D   For all M   in a language of size ≤ λ   , M λ / D   is λ + +   -universal.
  • ( 2 ) D   If M i   and N i   are elementarily equivalent models of a language of size ≤ λ   , then the second player has a winning strategy in the Ehrenfeucht-Fraïssé game of length λ +   on ∏ i M i / D   and ∏ i N i / D   .
Assuming 2 λ = λ +   , ( 2 ) D   is equivalent to:
  • ( 2 ′ ) D   For M i , N i   as in ( 2 ) D   of cardinality ≤ λ +   , ∏ i M i / D ∼ = ∏ i N i / D   .
We note that regularity is necessary for ( 1 D )   . I.e.
Lemma 1 For any filter D   on an infinite cardinal λ   , if for all infinite N   the structure N λ / D   is λ +   -universal, then D   is regular.
Proof. For k = 1 , 2   let ℳ k = 〈 M k , P i k 〉 i < λ   , where M 1 = λ   , M 2 = λ + 1   and the P i k   are defined as follows. Let k = 1   and let D 0   be a regular filter on λ   .
Let { A i } ⊆ D 0   witness the regularity of D 0   . Thus for α < λ , { i < λ | α ∈ A i }   is finite. Set P i 1 = A i   . Now let k = 2   . Let P i 2 = A i ∪ { λ }   . Now let D   be any ultrafilter on λ   and suppose there is an elementary embedding g   mapping M 2   into M 1 λ / D   . Let g ( λ ) = [ f ]   and let X α = { i | f ( i ) ∈ P α 1 }   . For each α < λ , a ∈ P α 2   implies X α ∈ D .   It is easy to see that { X α } α < λ   is a regular family in D   . □  
We note that a similar argument can be used to show that ( 1 ) D   fails if the language of M   has size λ +   .
This was a partial answer to the above Conjectures 18 and 19. In this paper we show the converse for singular strong limit λ   . Under GCH this is necessary as by Chang's Two Cardinal Theorem the transfer principle ( ℵ 1 , ℵ 0 ) → ( λ + , λ )   can only fail, in the presence of GCH, for singular λ   . It is known that ( ℵ 1 , ℵ 0 ) ↛ ( ℵ ω + 1 , ℵ ω )   + GCH is consistent relative to the consistency of a supercompact cardinal. It follows that the statement ( 2 ) D   is independent of ZFC relative to the consistency of supercompact cardinals.
On the other hand ( ℵ 1 , ℵ 0 ) → ( λ + , λ )   holds for all λ   if V = L   .
In fact we show more. The results of [4] were obtained using a finitary version, denoted here by □ λ , D f i n   , of the combinatorial principle □ λ b *   from [6] , which is equivalent for all λ   to ( ℵ 1 , ℵ 0 ) → ( λ + , λ )   . We showed in [4] that whenever λ   is singular strong limit, □ λ , D f i n   is actually equivalent to □ λ b *   , using Theorem 2.3 and Remark 2.5 of [6] . Thus □ λ , D f i n   is equivalent to ( ℵ 1 , ℵ 0 ) → ( λ + , λ )   , again for λ   singular strong limit. The consistency of e.g. GCH+ ¬ □ λ b *   follows. Precisely we showed:
Lemma 2 [4] Let D   be a regular filter on λ   where λ   is a singular strong limit cardinal. Then □ λ , D f i n   is equivalent to □ λ b *   .
The final piece needed for obtaining the transfer principle from ( 1 ) D   , ( 2 ) D   and ( 2 ′ ) D   for singular strong limit λ   involves proving their equivalence with the principle □ λ , D f i n   , which equivalence is proved for all λ   (Theorem  4 ).
We note that ( 2 ) D   is more robust than what was originally conjectured, i.e. we have given a condition on when player II has a winning strategy in the EF game of length λ +   on the two structures ∏ i M i / D   and ∏ i N i / D   .
Thus again if λ   is singular strong limit, then the model theoretic ( 1 ) D   and ( 2 ) D   are equivalent to the set theoretic ( ℵ 1 , ℵ 0 ) → ( λ + , λ )   .
We need the following definition, from Lemma 4 of [4] :
Definition 3 Let D   be a regular filter on λ   . If there exist sets u i ζ   and integers n i   for each ζ < λ +   and i < λ   such that for each i , ζ  
  • (i) | u i ζ | < n i  
  • (ii) u i ζ ⊆ ζ  
  • (iii) Let B   be a finite set of ordinals and let ζ   be such that B ⊆ ζ < λ +   .
    Then { i : B ⊆ u i ζ } ∈ D  
  • (iv) Coherence: γ ∈ u i ζ ⇒ u i γ = u i ζ ∩ γ   ,
then we say that □ λ , D f i n   holds.
Our main result:
Theorem 4 Assume λ ≥ ℵ 0   and D   is a regular filter on λ   . Then the following conditions are equivalent:
  • ( i )   □ λ , D f i n   .
  • ( i i )   If M i   and N i   , i < λ   , are elementarily equivalent models of a language of cardinality ≤ λ   , then the second player has a winning strategy in the Ehrenfeucht-Fraïssé game of length λ +   on ∏ i M i / D   and ∏ i N i / D   .
  • ( i i i )   If M   and N   are structures of a language of cardinality ≤ λ   , N ≡ M λ / D   and | N | ≤ λ +   , then there is a homomorphism N → M λ / D   .
  • ( i v )   If Δ   is a set of quantifier-free formulas and M λ / D   satisfies every existential Δ   -sentence (i.e. a sentence of the form ∃ x ⃗ ( φ 1 ∧ . . . ∧ φ n )   , where each φ i   is in Δ   ) true in N   , | N | ≤ λ +   , then there is a Δ   -homomorphism N → M λ / D   , i.e. a homomorphism N → M λ / D   which preserves Δ   formulas.
Additionally, if D   is an ultrafilter, then ( i ) − ( i v )   are equivalent to
  • ( v )   If M   is a structure in a language of cardinality ≤ λ   , then M λ / D   is λ + +   -universal.
Moreover in ( i i )   , ( i i i )   and ( i v )   we can equivalently assume that the models M i   , N i   , M   and N   have cardinality ≤ λ +   .
Proof. ( i ) → ( i i )   , ( i ) → ( i i i )   and ( i ) → ( i v )   follow from the ” Δ   -existential” version of Theorem 2 of [4] which gives a Δ   -homomorphism of N   into M λ / D   for any set Δ   of first-order formulas such that every Δ   -existential sentence true in N   is true in M   . If D   is an ultrafilter, [4] gives ( i ) → ( v )   and, on the other hand, ( v ) → ( i i i )   is straightforward.
( i i ) → ( i i i )   : It follows from N ≡ M λ / D   that there are M 0 ≡ M   and a homomorphism N → M 0   (i.e. a mapping from N   to M 0   which respects the functions and relations of N   ) such that M 0   has cardinality ≤ λ +   . By ( i i )   the second player has a winning strategy in the Ehrenfeucht-Fraïssé game of length λ +   on M 0 λ / D   and M λ / D   . Using this winning strategy we get easily a homomorphism N → M λ / D   , by composing the appropriate mappings.
( i i i ) → ( i v )   : Let M   and N   be as in ( i v )   . Let N *   be an expansion of N   obtained by giving a name to every Δ   -definable relation. Let ( M λ / D ) *   be obtained similarly from M λ / D   . Let M 0 * ≡ ( M λ / D ) *   such that there is a homomorphism N * → M 0 *   . (The existence of such M 0 *   follows from the fact that we can find M 0 * ≡ ( M * ) λ / D   and a homomorphism N * → M 0 *   . But then ( M * ) λ / D   is canonically embeddable into ( M λ / D ) *   ). By ( i i i )   there is a homomorphism M 0 * → M λ / D   . Thus there is a Δ   -homomorphism N → M λ / D   .
( i v ) → ( i )   : Let λ , D   be given and let τ   denote a language of cardinality ≤ λ   . It suffices to prove the following Claim. There exist M , N   such that
  • a )   | M | = λ , | N | = λ +  
  • b )   τ M = τ N   and | τ N | ≤ λ  
  • c )   M ≡ N  
  • d )   For Δ =   the quantifier free formulas of τ M   , N   has a Δ   -homomorphism into M λ / D   , and hence □ λ , D f i n   holds.
Proof. Let τ * = { F α | α < λ } ∪ { < }   , for F α   a unary function symbol. Let K   be the family of all structures M   such that
  • K 1 )   M   is a finite τ *   -structure.
  • K 2 )   The universe of M   is { 0 , 1 , … , k − 1 }   , for some k ∈ N   , k ≠ 0   , denoted η ( M )   .
  • K 3 )   M ⊧ ∀ x ( F α ( x ) ≤ x )   for all α < λ   .
  • K 4 )   If m 1 = F α 1 M ( m )   , m 2 = F α 2 M ( m )   and m 1 < m 2   , then there exists a β < λ   such that m 1 = F β M ( m 2 )   .
  • K 5 )   If F α 2 M ( m 3 ) = m 2   , F α 1 M ( m 2 ) = m 1   and m 1 < m 2 < m 3   , then there exists α 3 < λ   such that F α 3 M ( m 3 ) = m 1   .
  • K 6 )   w ( M ) = d f { α | F α M is not the identity }   is finite.
  • K 7 )   For m 1 < m 2 < k   there is exactly one α   such that m 1 = F α ( m 2 ) )   .
We note that K   is non-empty, taking K   to be, e.g., a one element structure.
Let { M i | i < λ }   list K   . We will add the M i   together into one structure.
I.e., we define a model M *   for τ = τ * ∪ { E }   such that
  • a K )   The universe of M * = ∪ { { i } × M i | i < λ }  
  • b K )   E M * = { 〈 ( i 1 , m 1 ) , ( i 2 , m 2 ) 〉 | m 1 < η ( M i 1 ) , m 2 < η ( M i 2 ) and i 1 = i 2 }  
  • c K )   < M * = { 〈 ( i , m 1 ) , ( i , m 2 ) 〉 | m 1 < m 2 < η ( M i ) }  
  • d K )   F α M * ( i , m ) = 〈 i , F α M i ( m ) 〉   .
Now for ρ < λ +   let h ρ   be a partial one to one function from λ   onto ρ   , and let 〈 a ρ | ρ < λ + 〉   be a set of new constant symbols.
Subclaim. There is N *   such that
  • a )   N *   is a τ * *   structure of cardinality λ +   , where τ * * = τ ∪ { a ρ | ρ < λ + } ∪ { m ¯ } m ∈ M   ,
  • b )   M * ≼ N * ↾ τ   .
  • c )   a ρ E N * a 0   for ρ < λ +   ,
  • d )   a ρ < N * a ξ   , for ρ < ξ < λ +   ,
  • e )   N * ⊧ F j ( a ¯ ρ ) = a ¯ ε   , if h ρ ( j ) = ε   , for j < λ   and ε < ρ < λ +   .
Proof of Subclaim. Let T = T h ( M * , m ¯ ) m ∈ M * ∪ { a ρ E a 0 } ρ < λ + ∪ { a ρ < a ξ | ρ < ξ < λ + } ∪ { F j ( a ρ ) = a ε | h ρ ( j ) = ε , ε < ρ < λ + }   . We claim that T   is consistent. To see this, let T 0 = { φ i ( m ¯ ⃗ } i = 1 , … , n ∪ { a ρ i E a 0 } i = 1 , … k ∪ { a ε i < a ζ i } i = 1 , … , l ∪ { F α i ( a μ i ) = a ν i } i = 1 , … , m   be a finite part of T   , where a i 1 , … , a i k   and m ¯ j 1 , … , m ¯ j l   are all the parameters occurring in T 0   . Let I 0 = { i |   for some j = j 1 … , j l   , m j = ( i , a )   , i < λ   , a < η ( M i ) }   . We can find M i 0   , i 0 ∈ λ \ I 0   , such that if we interpret the constants a ρ   in M i 0   and m ¯ j i   by m j i ∈ M *   , then this expansion of M *   is a model of T 0   and thus T 0   is consistent. The subclaim is proved. Now let N *   be as in claim 1 and let N = N * ↾ τ M *   . We note that the pair of structures N   together with the M   defined above satisfying a K ) − d K )   , satisfy the hypothesis of Theorem 2-(iv), i.e. ( M * ) λ / D   satisfies every existential Δ   -sentence true in N   where Δ =   the quantifier-free formulas of τ M *   . This is because N ≡ M *   and these Δ   -sentences are preserved under reduced products. Therefore by ( i v )   there is a Δ   -homomorphism g : N → ( M * ) λ / D   .
Let g ( a ρ )   be denoted by f ρ / D   .
We are now ready to define the sets u i ζ   referred to in (i)-(iv) of the condition □ λ , D f i n   . To this end, for ε < ρ < λ +   , ρ ≥ λ   , define A ε , ρ = { j < λ | M * ⊧ ( f ρ ( j ) > f ε ( j ) ) ∧ F i ( ε , ρ ) ( f ρ ( j ) ) = f ε ( j ) } .   Note that if ε < ρ < λ +   , ρ ≥ λ   , then A ε , ρ ∈ D   , since ( M * ) λ / D ⊧ ( g ( a ε ) < g ( a ρ ) ) ∧ F i ( ε , ρ ) ( g ( a ρ ) ) = g ( a ε )   . For each ρ ∈ ( λ , λ + )   and j ≤ λ   define W ρ , j = { ε < ρ | ε ≥ λ and j ∈ A ε , ρ } .   First note that without loss of generality ( * ) 1   : M * ⊧ f ρ ( j ) E f 0 ( j )   for every j , ρ   .
We claim that ( * ) 2   : if we choose u j ρ = d f W ρ , j   then 〈 u j ρ | ρ < λ + , j < λ 〉   exemplifies □ λ , D f i n   , i.e. these objects satisfy the demands ( i ) − ( i v )   of Definition 3.
By ( * ) 1   we can let f ρ ( j ) = ( i j , m ( i j , ρ ) ) .   Clearly if we prove ( * ) 2   we are done.
(i), (ii): W ρ , j   is a finite subset of ρ   :
{ ε < ρ | ε ≥ λ and j ∈ A ε , ρ } = { ε < ρ | ε ≥ λ and M ⊧ F i ( ε , ρ ) ( f ρ ( j ) ) = f ε ( j ) }
= { ε < ρ | ε ≥ λ and M i 0 ⊧ F i ( ε , ρ ) M i 0 ( f ρ ( j ) ) = f ε ( j ) } .
But w ( M i 0 )   is finite, and therefore so is W ρ , j   . Thus if n i   is taken to be w ( M i o )   then (i) and (ii) of □ λ , D f i n   are satisfied.
(iv): (coherency) holds of W ρ , j   , i.e. if ρ 1 < ρ 2 < λ +   and j < λ   is given, if ρ 1 ∈ W ρ 2 , j   then W ρ 1 , j = W ρ 2 , j ∩ ρ 1   . Why? Let α ∈ W ρ 1 , j   . Then λ ≤ α < ρ 2   and j ∈ A α , ρ 1   . But then M * ⊧ F i ( α , ρ 1 ) ( f ρ 1 ( j ) ) = f α ( j )   and therefore M i 0 ⊧ F i ( α , ρ 1 ) M i 0 ( f ρ 1 ( j ) ) = f α ( j )   . ρ 1 ∈ W ρ 2 , j   and therefore j ∈ A ρ 1 , ρ 2   . This means M i 0 ⊧ F i ( ρ 1 , ρ 2 ) M i 0 ( f ρ 2 ( j ) ) = f ρ 1 ( j )   . By the definition of M i 0   , there is β   such that M i 0 ⊧ F β M i 0 ( f ρ 2 ( j ) ) = f α ( j )   . But β = i ( α , ρ 2 )   and j ∈ A α , ρ 2   and therefore α ∈ W ρ 2 , j   . For the other direction suppose α ∈ W ρ 2 , j ∩ ρ 1   . Then α ≥ λ   and j ∈ A α , ρ 2   , i.e. M i 0 ⊧ F i ( α , ρ 2 ) M i 0 ( f ρ 2 ( j ) ) = f α ( j )   . ρ 1 ∈ W ρ 2 , j   means that as before j ∈ A ρ 1 , ρ 2   , i.e. M i 0 ⊧ F i ( ρ 1 , ρ 2 ) M i 0 ( f ρ 2 ( j ) ) = f ρ 1 ( j )   . But then since α < ρ 1   , there is β   such that M i 0 ⊧ F β M i 0 ( f ρ 1 ( j ) ) = f α ( j )   , i.e. as before j ∈ A ρ 1 , j   and α ∈ W ρ 1 , j   .
To see that (iii) is satisfied, let B ⊆ λ +   be a finite set of ordinals such that B ∩ λ = ∅   , and let ρ   be such that B ⊆ ρ < λ +   . We wish to show that { j | B ⊆ W ρ , j } ∈ D   . Let B = { j 1 , … , j n }   . Recall that by (e) of the subclaim, N * ⊧ F i ( j , ρ ) ( a ρ ) = a j   whence C k = { i | M * ⊧ F i ( j k , ρ ) ( f ρ ( i ) ) = f j k ( i ) } ∈ D ,   for each k = 1 , … , n   . Also by definition if i ∈ C k   then i ∈ A j k , ρ   whence j k ∈ W ρ , i   . Thus C 1 ∩ ⋯ ∩ C n ⊆ { i | B ⊆ W ρ , j } ∈ D .   The claim is proved.
Now if we transfer the sets u j ρ   , λ ≤ ρ < λ +   to all of λ +   , (iv) implies (i), proving the Claim. The claim concerning the equivalent formulations involving models of size ≤ λ +   follows from the fact that in the derivation ( i v ) → ( i )   above we have | M | = λ   and | N | = λ +   . Thus Theorem 4 is proved. □  
Corollary 5 Assume λ ≥ ℵ 0   , 2 λ = λ +   and D   is a regular filter on λ   .
Then the following are equivalent:
  • ( i )   □ λ , D f i n   .
  • ( i i )   If M i   and N i   , i < λ   , are elementarily equivalent models of a language of cardinality ≤ λ   , and | M i |   , | N i | ≤ λ +   then ∏ i M i / D ∼ = ∏ i N i / D   .
Corollary 6 GCH +   the failure of properties (i)-(iv) of Theorem 4 for λ = ℵ ω   is consistent relative to the consistency of supercompact cardinals.
Proof. Assume GCH and ( ℵ 1 , ℵ 0 ) ↛ ( ℵ ω + 1 , ℵ ω )   . It is well-known (cf. [1] Proposition 4.3.5) that there is a regular ultrafilter D   on ℵ ω   . The principle □ ℵ ω b *   fails. Thus □ ℵ ω , D f i n   fails by [4] . By Theorem  4 , (i)-(v) fail for the regular ultrafilter D   . □   A drawback of Corollary 6 is that it deals with filters rather than ultrafilters, which was originally the most interesting case. This case will be dealt with in a work in preparation.
References

  1. C.C. Chang and J.Keisler, Model Theory, North-Holland.
  2. J. Keisler, Ultraproducts and saturated models. Nederl.Akad.Wetensch. Proc. Ser. A 67 (=Indag. Math. 26) (1964), 178-186.
  3. J. Kennedy and S. Shelah, On embedding models of arithmetic of cardinality ℵ 1   into reduced powers, Fundamenta Mathematicae, Volume 176, Issue 1, 2003, 17–24.
  4. J. Kennedy and S. Shelah, On regular reduced products. Journal of Symbolic Logic, Volume 67, 2002, 1169–1177.
  5. S. Shelah, Every two elementarily equivalent models have isomorphic ultrapowers, Israel J. Math., 10, 1971, 224–233,
  6. S. Shelah, “Gap 1” two-cardinal principles and the omitting types theorem for L ( Q )   . Israel Journal of Mathematics vol 65 no. 2,1989, 133–152.