This note proves two theorems. The first is that it is consistent to have for every n, but not have . This is done by carefully collapsing a supercompact cardinal and adding square sequences to each ωn. The crux of the proof is that in the resulting model every stationary subset of ℵω+1 ⋂ cof(ω) reflects to an ordinal of cofinality ω1, that is to say it has stationary intersection with such an ordinal.

This result contrasts with compactness properties of square shown in [3]. In that paper it is shown that if one has square at every ωn, then there is a square type sequence on the points of cofinality ωk, k > 1 in ℵω+1. In particular at points of cofinality greater than ω1 there is a strongly non-reflecting stationary set of points of countable cofinality.

The second result answers a question of Džamonja, by showing that there can be no squarelike sequence above a supercompact cardinal, where “squarelike” means that one replaces the requirement that the cofinal sets be closed and unbounded by the requirement that they be stationary at all points of uncountable cofinality.

We define an interpretation of modal languages with polyadic operators in modal languages that use monadic operators (diamonds) only. We also define a simulation operator which associates a logic Λsim in the diamond language with each logic Λ in the language with polyadic modal connectives. We prove that this simulation operator transfers several useful properties of modal logics, such as finite/recursive axiomatizability, frame completeness and the finite model property, canonicity and first-order definability.

We show that each non-compact Polish group admits a continuous action on a Polish space with non-smooth orbit equivalence relation. We actually construct a free such action. Thus for a Polish group compactness is equivalent to all continuous free actions of this group being smooth. This answers a question of Kechris. We also establish results relating local compactness of the group with its inability to induce orbit equivalence relations not reducible to countable Borel equivalence relations. Generalizing a result of Hjorth, we prove that each non-locally compact, that is, infinite dimensional, separable Banach space has a continuous action on a Polish space with non-Borel orbit equivalence relation, thus showing that this property characterizes non-local compactness among Banach spaces.

A generator program for a computable function (by definition) generates an infinite sequence of programs all but finitely many of which compute that function. Machine learning of generator programs for computable functions is studied. To motivate these studies partially, it is shown that, in some cases, interesting global properties for computable functions can be proved from suitable generator programs which cannot be proved from any ordinary programs for them. The power (for variants of various learning criteria from the literature) of learning generator programs is compared with the power of learning ordinary programs. The learning power in these cases is also compared to that of learning limiting programs, i.e., programs allowed finitely many mind changes about their correct outputs.

This paper continues the study of existentially complete nilpotent groups initiated in [6]. Following [6], we let Kn denote the theory of groups nilpotent of class ≤ n and let Kn+ denote the theory of torsion-free groups nilpotent of class ≤ n. The principal results of [6] were that for n ≥ 2, neither Kn nor Kn+ has a model companion, and the classes E, F, and G of existentially complete, finitely generic and infinitely generic models of Kn are all distinct. The question of the relationships between these classes in the context of Kn was left open, however, and the proof of their distinctness for Kn+ obviously did not carry over to Kn+, because it made strong use of torsion elements.

In this paper we establish the relationships between E, F, and G for K2+. We show that all three classes are distinct. We also show that there is only one countable finitely generic model, and only one countable infinitely generic model, and that all the countable existentially complete models can be arranged in a sequence N1 ⊆ N2 ⊆ N3 ⊆ … ⊆ Nω, where Z(Nn) is the direct sum of n copies of Q. Another result is that the finite and infinite forcing companions of K2+ differ by an ∀∃∀ sentence. Finally, we show that there exist finitely generic models of K2+ in all infinite cardinalities.

We study interpolation for elementary fragments of classical linear logic. Unlike in intuitionistic logic (see [Renardel de Lavalette, 1989]) there are fragments in linear logic for which interpolation does not hold. We prove interpolation for a lot of fragments and refute it for the multiplicative fragment (→, +), using proof nets and quantum graphs. We give a separate proof for the fragment with implication and product, but without the structural rule of permutation. This is nearly the Lambek calculus. There is an appendix explaining what quantum graphs are and how they relate to proof nets.

In spite of the fact that true arithmetic reduces to the monadic second-order theory of the real line, Peano arithmetic cannot be interpreted in the monadic second-order theory of the real line.

We consider the language L(Q), where L is a countable first-order language and Q is an additional generalized quantifier. A weak model for L(Q) is a pair 〈, q〉 where is a first-order structure for L and q is a family of subsets of its universe. In case that q is the set of classes of some equivalence relation the weak model 〈, q〉 is called a partition model. The interpretation of Q in partition models was studied by Szczerba [3], who was inspired by Pawlak's paper [2]. The corresponding set of tautologies in L(Q) is called rough logic. In the following we will give a set of axioms of rough logic and prove its completeness. Rough logic is designed for creating partition models.

The partition models are the weak models arising from equivalence relations. For the basic properties of the logic of weak models the reader is referred to Keisler's paper [1]. In a weak model 〈, q〉 the formulas of L(Q) are interpreted as usual with the additional clause for the quantifier Q: 〈, q〉 ⊨ Qx φ(x) iff there is some X ∊ q such that 〈, q〉 ⊨ φ(a) for all a ∊ X.

In case X satisfies the right side of the above equivalence we say that X is contained in φ(x) or, equivalently, φ(x) contains X.

We give an alternative proof of the stability of separably closed fields of fixed Éršov invariant to the one given in [W]. We show that in case the Éršov invariant is finite, the theory is in fact equational. We also characterize the independence relation in those theories.

We characterize Maharam spectra of Loeb probability spaces and give some applications of the results.

Les arbres sont les ordres partiels qui vérifient l'axiome supplémental ∀x∀y∀z(y ≤x ∧z ≤ x → y ≤ z ∨ z ≤ y), i.e. l'ensemble des minorants de chaque élément est totalement ordonné.

Le principal résultat de cet article concerne l'instabilité des arbres: nous prouvons (§2) qu'aucune théorie d'arbre n'a la propriété d'indépendance, ce qui généralise un theoreme de Poizat [3] sur les ordres totaux. II s'en suit au moyen d'un resultat d'interprétation [4] qu'aucune théorie de structure arborescente n'a la propriété d'indépendance; en particulier ceci vaut pour les arbres colorés.

Le §3 est consacré aux arbres stables. II est prouvé qu'un arbre est stable ssi il est superstable ssi il est de hauteur bornée. Sous l'hypothèse de stabilité, les arbres premiers, minimaux, et strictement minimaux sont caractérisés en termes d'al-gébricité.

We show that for every c.e. degree a > 0 there exists an intrinsically c.e. relation on the domain of a computable structure whose degree spectrum is {0, a}. This result can be extended in two directions. First we show that for every uniformly c.e. collection of sets S there exists an intrinsically c.e. relation on the domain of a computable structure whose degree spectrum is the set of degrees of elements of S. Then we show that if α ∈ ω ∪ {ω} then for any α-c.e. degree a > 0 there exists an intrinsically α-c.e. relation on the domain of a computable structure whose degree spectrum {0, a}. All of these results also hold for m-degree spectra of relations.

The theory of (ℝ, <, +, ℤ, ℤa) is decidable if a is quadratic. If a is the golden ratio, (ℝ, <, +, ℤ, ℤa) defines multiplication by a. The results are established by using the Ostrowski numeration system based on the continued fraction expansion of a to define the above structures in monadic second order logic of one successor. The converse that (ℝ, <, +, ℤ, ℤa) defines monadic second order logic of one successor, will also be established.

A set X of nonnegative integers is computably enumerable (c.e.), also called recursively enumerable (r.e.), if there is a computable method to list its elements. Let ε denote the structure of the computably enumerable sets under inclusion, ε = ({We}eϵω,⊆). We previously exhibited a first order ε-definable property Q(X) such that Q(X) guarantees that X is not Turing complete (i.e., does not code complete information about c.e. sets).

Here we show first that Q(X) implies that X has a certain “slowness” property whereby the elements must enter X slowly (under a certain precise complexity measure of speed of computation) even though X may have high information content. Second we prove that every X with this slowness property is computable in some member of any nontrivial orbit, namely for any noncomputable A ϵ ε there exists B in the orbit of A such that X ≤TB under relative Turing computability (≤T). We produce B using the -automorphism method we introduced earlier.

In this paper first order theories for nonmonotone inductive definitions are introduced, and a proof-theoretic analysis for such theories based on combined operator forms à la Richter with recursively inaccessible and Mahlo closure ordinals is given.

Any two models of arithmetic can be jointly embedded in a third with any prescribed isomorphic submodels as intersection and any prescribed relative ordering of the skies above the intersection. Corollaries include some known and some new theorems about ultrafilters on the natural numbers, for example that every ultrafilter with the “4 to 3” weak Ramsey partition property is a P-point. We also give examples showing that ultrafilters with the “5 to 4” partition property need not be P-points and that the main theorem cannot be improved to allow a prescribed ordering of lower skies.

i) We show for each context-free language L that by considering each word of L as a structure in a natural way, one turns L into a finite union of classes which satisfy a finitary analog of the characteristic properties of complete universal first order classes of structures equipped with elementary embeddings. We show this to hold for a much larger class of languages which we call free local languages, ii) We define local languages, a class of languages between free local and context-sensitive languages. Each local language L has a natural extension L ∞ to infinite words, and we prove a series of “pumping lemmas”, analogs for each local language L of the “uvxyz theorem” of context free languages: they relate the existence of large words in L or L ∞ to the existence of infinite “progressions” of words included in L, and they imply the decidability of various questions about L or L ∞. iii) We show that the pumping lemmas of ii) are independent from strong axioms, ranging from Peano arithmetic to ZF + Mahlo cardinals.

We hope that these results are useful for a model-theoretic approach to the theory of formal languages.

Our unexplained notation is that of Rogers [4]. Let P ⊆ 2N × 2N. We call a sequence <An: n ∈ N> of subsets of N a P-sequence iff ∀n(An+1 = the unique B such that P(An, B)).

Theorem. Let P ⊆ 2N × 2N be arithmetical. Then there is no P-sequence <An: n ∈ N> such that ∀n(A′n+1 ≤T An).

This theorem improves a result of Friedman [2] who showed that for no arithmetical P is there a P-sequence <An: n ∈ N> such that An + 1 is a code for an ω-model of the relative arithmetic comprehension schema, and An + 1 is present in the model coded by An, for all n. Other related results are those of Harrison [3], who showed there is a sequence <An: n ∈ N> such that ∀n<A′n + 1 ≤T An>, and of Enderton and Putnam [1], who showed there is no sequence <An: n ∈ N> with ∀n(A′n + 1 ≤T An) and A0 hyperarithmetic.

Our theorem is closely connected to Gödel's second incompleteness theorem. Its proof is a recursion theoretic parallel to the proof of Gödel's theorem. In §2 we draw a version of Gödel's theorem as a corollary to ours.