In 1986, Osherson, Stob and Weinstein asked whether two variants of anomalous vacillatory learning, TxtFex** and TxtFext**, could be distinguished [3]. In both, a machine is permitted to vacillate between a finite number of hypotheses and to make a finite number of errors. TxtFext**-learning requires that hypotheses output infinitely often must describe the same finite variant of the correct set, while TxtFex**-learning permits the learner to vacillate between finitely many different finite variants of the correct set. In this paper we show that TxtFex** ≠ TxtFext**, thereby answering the question posed by Osherson, et al. We prove this in a strong way by exhibiting a family in TxtFex*2 TxtFext**.

Computability, while usually performed within the context of ω, may be extended to larger ordinals by means of α-recursion. In this article, we concentrate on the particular case of ω1-recursion, and study the differences in the behavior of ${\rm{\Pi }}_1^0$-classes between this case and the standard one.

Of particular interest are the ${\rm{\Pi }}_1^0$-classes corresponding to computable trees of countable width. Classically, it is well-known that the analog to König’s Lemma—“every tree of countable width and uncountable height has an uncountable branch”—fails; we demonstrate that not only does it fail effectively, but also that the failure is as drastic as possible. This is proven by showing that the ω1-Turing degrees of even isolated paths in computable trees of countable width are cofinal in the ${\rm{\Delta }}_1^1\,{\omega _1}$-Turing degrees.

Finally, we consider questions of nonisolated paths, and demonstrate that the degrees realizable as isolated paths and the degrees realizable as nonisolated ones are very distinct; in particular, we show that there exists a computable tree of countable width so that every branch can only be ω1-Turing equivalent to branches of trees with ${\aleph _2}$-many branches.

For countable structures and , let abbreviate the statement that every sentence true in also holds in . One can define a back and forth game between the structures and that determines whether . We verify that if θ is an Lω,ω sentence that is not equivalent to any Lω,ω sentence, then there are countably infinite models and such that ⊨ θ, ⊨ ¬θ, and . For countable languages ℒ there is a natural way to view ℒ structúres with universe ω as a topological space, Xℒ. Let [] = { ∊ Xℒ∣ ≅ } denote the isomorphism class of . Let and be countably infinite nonisomorphic ℒ structures, and let C ⊆ ωω be any subset. Our main result states that if , then there is a continuous function f: ωω → Xℒ with the property that x ∊ C ⇒ f(x) ∊ [] and x ∉ C ⇒ f(x) ∊ f(x) ∈ []. In fact, for α ≤ 3, the continuous function f can be defined from the relation.

In this paper we investigate omitting types for a certain kind of stable theories which we call stable ccc theories. In Theorem 2.1 we improve Steinhorn's result from [St]. We prove also some independence results concerning omitting types. The main results presented in this paper were part of the author's Ph.D. thesis [N1].

Throughout, we use the standard set-theoretic and model-theoretic notation, such as can be found for example in [Sh] or [M]. So in particular T is always a countable complete theory in the language L. We consider all models of T and all sets of parameters subsets of the monster model ℭ, which is very saturated. Ln(A) denotes the Lindenbaum-Tarski algebra of formulas with parameters from A and n free variables. We omit n in Ln(A) when n = 1 or when it is clear from the context what n is. If φ, ψ ∈ L(A) are consistent then we say that φ is below ψ if ψ⊢ψ. For a type p and a set A ⊆ ℭ, p(A) is the set of tuples of elements of A which satisfy p. Formulas are special cases of types. We say that a type p is isolated over A if, for some φ() ∈ L(A), φ() ⊢ p(x), i.e. φ isolates p. For a formula φ, [φ] denotes the class of types which contain φ. We assume that the reader is familiar with some basic knowledge of forking, as presented in [Sh, III] or [M].

Throughout, we work in ZFC. and denote (countable) transitive models of ZFC. cov K is the minimal number of meager sets covering the real line R. In this paper we prove theorems showing connections between omitting types and the combinatorics of the real line. More results in this direction are presented in [N2] and [N3].

The paper continues [1]. Let S be a complete theory of ultraflat (e.g. planar) graphs as introduced in [4]. We show a strong form of NOTOP for S: The union of two models M1 and M2, independent over a common elementary submodel M0, is the primary model over M1 ∪ M2 of S. Then by results of [1] Mekler's construction [6] gives for such a theory S of nice ultraflat graphs a superstable 2-step-nilpotent group of exponent p (> 2) with NDOP and NOTOP.

It is shown, assuming the existence of a Woodin cardinal δ, that every tree ordering on some limit ordinal λ < δ with a cofinal branch is the tree ordering of some iteration tree on V.

The central notion of this paper is that of a (conjunctive) game-sentence, i.e., a sentence of the form

where the indices ki, ji range over given countable sets and the matrix conjuncts are, say, open -formulas. Such game sentences were first considered, independently, by Svenonius [19], Moschovakis [13]—[15] and Vaught [20]. Other references are [1], [3]—[5], [10]—[12]. The following normal form theorem was proved by Vaught (and, in less general forms, by his predecessors).

Theorem 0.1. Let L = L0(R). For every -sentence ϕ there is an L0-game sentence Θ such that ⊨′ ∃Rϕ ↔ Θ.

(A word about the notations: L0(R) denotes the language obtained from L0 by adding to it the sequence R of logical symbols which do not belong to L0; “⊨′α” means that α is true in all countable models.)

0.1 can be restated as follows.

Theorem 0.1′. For every-sentence ϕ there is an L0-game sentence Θ such that ⊨ϕ → Θ and for any-sentence ϕ if ⊨ϕ → ϕ and L′ ⋂ L ⊆ L0, then ⊨ Θ → ϕ.

(We sketch the proof of the equivalence between 0.1 and 0.1′.

0.1 implies 0.1′. This is obvious once we realize that game sentences and their negations satisfy the downward Löwenheim-Skolem theorem and hence, ⊨′α is equivalent to ⊨α whenever α is a boolean combination of and game sentences.

We shall prove that if a model of cardinality κ can be expanded to a model of a sentence ψ of by adding a suitable predicate in more than κ ways, then, it has a submodel of power μ which can be expanded to a model of ψ in > μ ways provided that λ, κ, μ satisfy suitable conditions.

If two models of a first-order theory are isomorphic, then they remain isomorphic in any forcing extension of the universe of sets. In general however, such a forcing extension may create new isomorphisms. For example, any forcing that collapses cardinals may easily make formerly nonisomorphic models isomorphic. However, if we place restrictions on the partially-ordered set to ensure that the forcing extension preserves certain invariants, then the ability to force nonisomorphic models of some theory T to be isomorphic implies that the invariants are not sufficient to characterize the models of T.

A countable first-order theory is said to be classifiable if it is superstable and does not have either the dimensional order property (DOP) or the omitting types order property (OTOP). If T is not classifiable, Shelah has shown in [5] that sentences in L∞,λ do not characterize models of T of power λ. By contrast, in [8] Shelah showed that if a theory T is classifiable, then each model of cardinality λ is described by a sentence of L∞,λ. In fact, this sentence can be chosen in the . ( is the result of enriching the language by adding for each μ < λ a quantifier saying the dimension of a dependence structure is greater than μ) Further work ([3], [2]) shows that ⊐+ can be replaced by ℵ1.