Types directed by constants

Let T be a complete, countable, first-order theory having infinite models. We introduce types directed by constants, and prove that their presence in a model of T guaranties the maximal number of non-isomorphic countable models :  I(ℵ₀,T)=2^ℵ₀.     

New spectra of strongly minimal theories in finite languages

We describe strongly minimal theories T_n with finite languages such that in the chain of countable models of T_n, only the first n models have recursive presentations. Also, we describe a strongly minimal theory with a finite language such that every non-saturated model has a recursive presentation.     

On a Problem of Cameron’s on Inexhaustible Graphs

A graph G is inexhaustible if whenever a vertex of G is deleted the remaining graph is isomorphic to G. We address a question of Cameron [6], who asked which countable graphs are inexhaustible. In particular, we prove that there are continuum many countable inexhaustible graphs with properties in common with the infinite random graph, including adjacency properties and universality. Locally finite inexhaustible graphs and forests are investigated, as is a semigroup structure on the class of inexhaustible graphs. We extend a result of [7] on homogeneous inexhaustible graphs to pseudo-homogeneous inexhaustible graphs.The authors gratefully acknowledge support from the Natural Science and Engineering Research Council of Canada (NSERC).     

Theories with constants and three countable models

We prove that a countable, complete, first-order theory with infinite dcl() and precisely three non-isomorphic countable models interprets a variant of Ehrenfeucht’s or Peretyatkin’s example.     

The γ-borel conjecture

In this paper we prove that it is consistent that every -set is countable while not every strong measure zero set is countable. We also show that it is consistent that every strong -set is countable while not every -set is countable. On the other hand we show that every strong measure zero set is countable iff every set with the Rothberger property is countable.Thanks to Boise State University for support during the time this paper was written and to Alan Dow for some helpful discussions and to Boaz Tsaban for some suggestions to improve an earlier version.     

Oligomorphic clones

A permutation group on a countably infinite domain is called oligomorphic if it has finitely many orbits of finitary tuples. We define a clone on a countable domain to be oligomorphic if its set of permutations forms an oligomorphic permutation group. There is a close relationship to ω-categorical structures, i.e., countably infinite structures with a first-order theory that has only one countable model, up to isomorphism. Every locally closed oligomorphic permutation group is the automorphism group of an ω-categorical structure, and conversely, the canonical structure of an oligomorphic permutation group is an ω-categorical structure that contains all first-order definable relations. There is a similar Galois connection between locally closed oligomorphic clones and ω-categorical structures containing all primitive positive definable relations. In this article we generalise some fundamental theorems of universal algebra from clones over a finite domain to oligomorphic clones. First, we define minimal oligomorphic clones, and present equivalent characterisations of minimality, and then generalise Rosenberg’s five types classification to minimal oligomorphic clones. We also present a generalisation of the theorem of Baker and Pixley to oligomorphic clones. Presented by A. Szendrei. Received July 12, 2005; accepted in final form August 29, 2006.     

Covering in the lattice of equational theories and some properties of term finite theories

For countable languages, we completely describe those cardinals κ such that there is an equational theory which covers exactly κ other equational theories. For this task understanding term finite theories is helpful. A theoryT isterm finite provided {ψ:Tτϕ≈ψ} is finite for all terms ϕ. We develop here some fundamental properties of term finite theories and use them, together with Ramsey's Theorem, to prove that any finitely based term finite theory covers only finitely many others. We also show that every term finite theory possesses an independent base and that there are such theories whose pairwise joins are not term finite. The paper was written with the support of NSF Grant MCS-80-01778. Presented by B. Jónsson. Received July 22, 1980. Accepted for publication in final form March 19, 1981.     

Upward Morley's theorem downward

By a celebrated theorem of Morley, a theory T is ?₁‐categorical if and only if it is κ‐categorical for all uncountable κ. In this paper we are taking the first steps towards extending Morley's categoricity theorem “to the finite”. In more detail, we are presenting conditions, implying that certain finite subsets of certain ?₁‐categorical T have at most one n‐element model for each natural number (counting up to isomorphism, of course).     

On extensions of countable filterbases to ultrafilters and ultrafilter compactness

We show in the Zermelo-Fraenkel set theory ZF without the axiom of choice:

1. Given an infinite set X, the Stone space S(X) is ultrafilter compact.

2. For every infinite set X, every countable filterbase of X extends to an ultra-filter i? for every infinite set X, S(X) is countably compact.

3. ω has a free ultrafilter i? every countable, ultrafilter compact space is countably compact.

   We also show the following:

4. There are a permutation model 𝒩 and a set X ∈ 𝒩 such that X has no free ultrafilters and S(X) is not compact but S(X) is countably compact and every countable filterbase of X extends to an ultrafilter.

5. It is relatively consistent with ZF that every countable filterbase of ω extends to an ultrafilter but there exists a countable filterbase of ? which does not extend to an ultrafilter. Hence, it is relatively consistent with ZF that ? has free ultrafilters but there exists a countable filterbase of ? which does not extend to an ultrafilter.

     

Computability in structures representing a Scott set

Continuing work begun in [10], we utilize a notion of forcing for which the generic objects are structures and which allows us to determine whether these “generic” structures compute certain sets and enumerations. The forcing conditions are bounded complexity types which are consistent with a given theory and are elements of a given Scott set. These generic structures will “represent” this given Scott set, in the sense that the structure has a certain weak saturation property with respect to bounded complexity types in the Scott set. For example, if ? is a nonstandard model of PA, then ? represents the Scott set ? = n∈ω | ?⊧“the nth prime divides a” | a∈?. The notion of forcing yields two main results. The first characterizes the sets of natural numbers computable in all models of a given theory representing a given Scott set. We show that the characteristic function of such a set must be enumeration reducible to a complete existential type which is consistent with the given theory and is an element of the given Scott set. The second provides a sufficient condition for the existence of a structure ? such that ? represents a countable jump ideal and ? does not compute an enumeration of a given family of sets ?. This second result is of particular interest when the family of sets which cannot be enumerated is ? = Rep[Th(?)]. Under this additional assumption, the second result generalizes a result on TA [6] and on certain other completions of PA [10]. For example, we show that there also exist models of completions of ZF from which one cannot enumerate the family of sets represented by the theory. Received: 8 October 1997 / Published online: 25 January 2001     

Some coinductive graphs

Summary LetT be a universal theory of graphs such that Mod(T) is closed under disjoint unions. Let _T be a disjoint union _i such that each _i is a finite model ofT and every finite isomorphism type in Mod(T) is represented in{ _i i<3}. We investigate under what conditions onT, Th( _T ) is a coinductive theory, where a theory is called coinductive if it can be axiomatizated by -sentences. We also characterize coinductive graphs which have quantifier-free rank 1.     

Vaught's conjecture for quite o-minimal theories

We study Vaught's problem for quite o-minimal theories. Quite o-minimal theories form a subclass of the class of weakly o-minimal theories preserving a series of properties of o-minimal theories. We investigate quite o-minimal theories having fewer than $2^{\omega }$ countable models and prove that the Exchange Principle for algebraic closure holds in any model of such a theory and also we prove binarity of these theories. The main result of the paper is that any quite o-minimal theory has either $2^{\omega }$ countable models or $6^a{3}^b$ countable models, where a and b are natural numbers.     

Minimal first-order structures

We prove a dichotomy theorem for minimal structures and use it to prove that the number of non-isomorphic countable elementary extensions of an arbitrary countable, infinite first-order structure is infinite.     

There are no hereditary productive γ-spaces

We show that if X is an uncountable productive γ-set [F. Jordan, Productive local properties of function spaces, Topology Appl. 154 (2007) 870-883], then there is a countable Y⊆X such that X?Y is not Hurewicz.Along the way we answer a question of A. Miller by showing that an increasing countable union of γ-spaces is again a γ-space. We will also show that λ-spaces with the Hurewicz property are precisely those spaces for which every co-countable set is Hurewicz.     

Linear orderings and powers of characterizable cardinals

We say that a countable model M completely characterizes an infinite cardinal κ, if the Scott sentence of M has a model in cardinality κ, but no models in cardinality κ⁺. If a structure M completely characterizes κ, κ is called characterizable. In this paper, we concern ourselves with cardinals that are characterizable by linearly ordered structures (cf. Definition 2.1).Under the assumption of GCH, Malitz completely resolved the problem by showing that κ is characterizable if and only if κ=ℵ_α, for some α<ω₁ (cf. Malitz (1968) [7] and Baumgartner (1974) [1]). Our results concern the case where GCH fails.From Hjorth (2002) [3], we can deduce that if κ is characterizable, then κ⁺ is characterizable by a densely ordered structure (see Theorem 2.4 and Corollary 2.5).We show that if κ is homogeneously characterizable (cf. Definition 2.2), then κ is characterizable by a densely ordered structure, while the converse fails (Theorem 2.3).The main theorems are (1) If κ>2^λ is a characterizable cardinal, λ is characterizable by a densely ordered structure and λ is the least cardinal such that κ^λ>κ, then κ^λ is also characterizable (Theorem 5.4) and (2) if ℵ_α and κ^ℵ_α are characterizable cardinals, then the same is true for κ^ℵ_α+β, for all countable β (Theorem 5.5).Combining these two theorems we get that if κ>2^ℵ_α is a characterizable cardinal, ℵ_α is characterizable by a densely ordered structure and ℵ_α is the least cardinal such that κ^ℵ_α>κ, then for all β<α+ω₁, κ^ℵ_β is characterizable (Theorem 5.7). Also if κ is a characterizable cardinal, then κ^ℵ_α is characterizable, for all countable α (Corollary 5.6). This answers a question of the author in Souldatos (submitted for publication) [8].     

Spaces in Which Countable Closed Sets Have Countable Character

It is proved that in a T ₃ space countable closed sets have countable character if and only if the set of limit point of the space is a countable compact set and every compact set is of countable character. Also, it is shown that spaces where countable sets have countable character are WN-spaces and are very close to M-spaces. Finally, some questions of Dai and Lia are discussed and some questions are proposed.     

Number of open sets for a topology with a countable basis

LetT be the family of open subsets of a topological space (not necessarily Hausdorff or evenT ₀). We prove that ifT has a countable base and is not countable, thenT has cardinality at least continuum. Partially supported by the Basic Research Fund, Israeli Academy of Sciences. Publication no. 454 done 6,8/1991. Partially sponsored by the Edmund Landau Center for research in Mathematical Analysis, supported by the Minerva Foundation (Germany).     

Theories of linear order

LetT be a complete theory of linear order; the language ofT may contain a finite or a countable set of unary predicates. We prove the following results. (i) The number of nonisomorphic countable models ofT is either finite or 2^ω. (ii) If the language ofT is finite then the number of nonisomorphic countable models ofT is either 1 or 2^ω. (iii) IfS ₁(T) is countable then so isS _n(T) for everyn. (iv) In caseS ₁(T) is countable we find a relation between the Cantor Bendixon rank ofS ₁(T) and the Cantor Bendixon rank ofS _n(T). (v) We define a class of modelsL, and show thatS ₁(T) is finite iff the models ofT belong toL. We conclude that ifS ₁(T) is finite thenT is finitely axiomatizable. (vi) We prove some theorems concerning the existence and the structure of saturated models. Most of the results in this paper appeared in the author’s Master of Science thesis which was prepared at the Hebrew University under the supervision of Professor H. Gaifman.     

Superstable theories with few countable models

Summary We prove here: Theorem. LetT be a countable complete superstable non -stable theory with fewer than continuum many countable models. Then there is a definable groupG with locally modular regular generics, such thatG is not connected-by-finite and any type inG ^eq orthogonal to the generics has Morley rank. Corollary. LetT be a countable complete superstable theory in which no infinite group is definable. ThenT has either at most countably many, or exactly continuum many countable models, up to isomorphism.Supported by NSF grant DMS 90-06628