Adding Skolem functions to simple theories

We examine the conditions under which we can keep simplicity or categoricity after adding a Skolem function to the theory.Mathematics Subject Classification (2000): 03C45, 03C50     

Automorphisms of Models of True Arithmetic: Subgroups which Extend to a Maximal Subgroup Uniquely

We show that if M is a countable recursively saturated model of True Arithmetic, then G = Aut(M) has nonmaximal open subgroups with unique extension to a maximal subgroup of Aut(M). Mathematics Subject Classification: 03C62, 03C50.     

Ultrapowers as sheaves on a category of ultrafilters

In the paper we investigate the topos of sheaves on a category of ultrafilters. The category is described with the help of the Rudin-Keisler ordering of ultrafilters. It is shown that the topos is Boolean and two-valued and that the axiom of choice does not hold in it. We prove that the internal logic in the topos does not coincide with that in any of the ultrapowers. We also show that internal set theory, an axiomatic nonstandard set theory, can be modeled in the topos.Mathematics Subject Classification (2000): Primary 03G30, 03C20, Secondary 03E05, 03E70, 03H05The author would like to thank the Mittag-Leffler Institute for partial suport.     

Abelian-by-G Groups,for G Finite,from the Model Theoretic Point of View

Let G be a finite group. We prove that the theory af abelian-by-G groups is decidable if and only if the theory of modules over the group ring ?[G] is decidable. Then we study some model theoretic questions about abelian-by-G groups, in particular we show that their class is elementary when the order of G is squarefree. Mathematics Subject Classification: 03C60, 03B25.     

Decidability for ℤ[G]-Modules when G is Cyclic of Prime Order

We consider the decision problem for modules over a group ring ?[G], where G is a cyclic group of prime order. We show that it reduces to the same problem for a class of certain abelian structures, and we obtain some partial decidability results for this class. Mathematics Subject Classification: 03C60, 03B25.     

A new correctness criterion for multiplicative non-commutative proof nets

 We introduce a new correctness criterion for multiplicative non commutative proof nets which can be considered as the non-commutative counterpart to the Danos-Regnier criterion for proof nets of linear logic. The main intuition relies on the fact that any switching for a proof net (obtained by mutilating one premise of each disjunction link) can be naturally viewed as a series-parallel order variety (a cyclic relation) on the conclusions of the proof net. Received: 8 November 2000 / Revised version: 21 June 2001 / Published online: 2 September 2002 Research supported by the EU TMR Research Programme ``Linear Logic and Theoretical Computer Science'. Mathematics Subject Classification (2000): 03F03, 03F07, 03F52, 03B70 Key words or phrases: Linear and non-commutative logic – Proof nets – Series-parallel orders and order varieties     

Reflection of Long Game Formulas

We study game formulas the truth of which is determined by a semantical game of uncountable length. The main theme is the study of principles stating reflection of these formulas in various admissible sets. This investigation leads to two weak forms of strict-II¹₁ reflection (or ∑₁-compactness). We show that admissible sets such as H(ω₂) and L_ω2 which fail to have strict-II¹₁ reflection, may or may not, depending on set-theoretic hypotheses satisfy one or both of these weaker forms. Mathematics Subject Classification : 03C70, 03C75.     

Relating Categorical Semantics for Intuitionistic Linear Logic

There are several kinds of linear typed calculus in the literature, some with their associated notion of categorical model. Our aim in this paper is to systematise the relationship between three of these linear typed calculi and their models. We point out that mere soundness and completeness of a linear typed calculus with respect to a class of categorical models are not sufficient to identify the most appropriate class uniquely. We recommend instead to use the notion of internal language when relating a typed calculus to a class of models. After clarifying the internal languages of the categories of models in the literature we relate these models via reflections and coreflections. Mathematics Subject Classifications (2000) 03G30, 03B15, 18C50, 03B20.     

On Preservation of Stability for Finite Extensions of Abelian Groups

We characterize preservation of superstability and ω-stability for finite extensions of abelian groups and reduce the general case to the case of p-groups. In particular we study finite extensions of divisible abelian groups. We prove that superstable abelian-by-finite groups have only finitely many conjugacy classes of Sylow p-subgroups. Mathematics Subject Classification: 03C60, 20C05.     

Some Decidability Results for ℤ[G]-Modules when G is Cyclic of Squarefree Order

We extend the analysis of the decision problem for modules over a group ring ?[G] to the case when G is a cyclic group of squarefree order. We show that separated ?[G]-modules have a decidable theory, and we discuss the model theoretic role of these modules within the class of all ?[G]-modules. The paper includes a short analysis of the decision problem for the theories of (finitely generated) modules over ?[ζ_m], where m is a positive integer and ζ_m is a primitive mth root of 1. Mathematics Subject Classification: 03C60, 03B25.     

Forking and Incomplete Types

Let Δ be a set of formulas. In this paper we study the following question: under what assumptions on Δ, the concept “a complete Δ-type p over B does not fork over A ? B” behaves well. We apply the results to the structure theory of ω₁-saturated models. Mathematics Subject Classification: 03C45.     

A Tauberian Theorem for Ergodic Averages,Spectral Decomposability,and the Dominated Ergodic Estimate for Positive Invertible Operators

Suppose that (,) is a -finite measure space, and 1 < p < . Let T:L^p( L ^p() be a bounded invertible linear operator such that T and T ^–1 are positive. Denote by _n(T) the nth two-sided ergodic average of T, taken in the form of the nth (C,1) mean of the sequence {T^j+T^–j}_{j =1} . Martín-Reyes and de la Torre have shown that the existence of a maximal ergodic estimate for T is characterized by either of the following two conditions: (a) the strong convergence of E_n(T)_n=1 ; (b) a uniform A _p p estimate in terms of discrete weights generated by the pointwise action on of certain measurable functions canonically associated with T. We show that strong convergence of the (C,2) means of {T^j+T^–j}_j=1 already implies (b). For this purpose the (C,2) means are used to set up an `averaged' variant of the requisite uniform A _p weight estimates in (b). This result, which can be viewed as a Tauberian-Type replacement of (C,1) means by (C,2) means in (a), leads to a spectral-theoretic characterization of the maximal ergodic estimate by application of a recent result of the authors establishing the strong convergence of the (C,2)-weighted ergodic means for all trigonometrically well-bounded operators. This application also serves to equate uniform boundedness of the rotated Hilbert averages of T with the uniform boundedness of the ergodic averages E_n(T)_{n = 1} .     

Quasimaximality and principal filters isomorphism between

Let I be a quasimaximal subset of a computable basis of the fully efective vector space V . We give a necessary and sufficient condition for the existence of an isomorphism between the principal filter respectivelly. We construct both quasimaximal sets that satisfy and quasimaximal sets that do not satisfy this condition. With the latter we obtain a negative answer to Question 5.4 posed by Downey and Remmel in [3].Based on the authors Ph.D. dissertation.Mathematics Subject Classification (2000): 03D25, 03C57     

K-generic Projective Planes have Morley Rank Two or Infinity

We show that K-generic projective planes have Morley rank either two or infinity. We also show give a direct argument that such planes are not Desarguesian. Mathematics Subject Classification: 03C45, 05C90, 51A35.     

Effectively and Noneffectively Nowhere Simple Sets

R. Shore proved that every recursively enumerable (r. e.) set can be split into two (disjoint) nowhere simple sets. Splitting theorems play an important role in recursion theory since they provide information about the lattice ? of all r. e. sets. Nowhere simple sets were further studied by D. Miller and J. Remmel, and we generalize some of their results. We characterize r. e. sets which can be split into two (non) effectively nowhere simple sets, and r. e. sets which can be split into two r. e. non-nowhere simple sets. We show that every r. e. set is either the disjoint union of two effectively nowhere simple sets or two noneffectively nowhere simple sets. We characterize r. e. sets whose every nontrivial splitting is into nowhere simple sets, and r. e. sets whose every nontrivial splitting is into effectively nowhere simple sets. R. Shore proved that for every effectively nowhere simple set A, the lattice L* (A) is effectively isomorphic to ?*, and that there is a nowhere simple set A such that L*(A) is not effectively isomorphic to ?*. We prove that every nonzero r. e. Turing degree contains a noneffectively nowhere simple set A with the lattice L*(A) effectively isomorphic to ?*. Mathematics Subject Classification: 03D25, 03D10.     

Bit-parallel -matching and suffix automata

(δ,γ)-matching is a string matching problem with applications to music retrieval. The goal is, given a pattern P_1…m and a text T_1…n on an alphabet of integers, find the occurrences P^′ of the pattern in the text such that (i) , and (ii) . The problem makes sense for δγδm. Several techniques for (δ,γ)-matching have been proposed, based on bit-parallelism or on skipping characters. We first present an O(mnlog(γ)/w) worst-case time and O(n) average-case time bit-parallel algorithm (being w the number of bits in the computer word). It improves the previous O(mnlog(δm)/w) worst-case time algorithm of the same type. Second, we combine our bit-parallel algorithm with suffix automata to obtain the first algorithm that skips characters using both δ and γ. This algorithm examines less characters than any previous approach, as the others do just δ-matching and check the γ-condition on the candidates. We implemented our algorithms and drew experimental results on real music, showing that our algorithms are superior to current alternatives with high values of δ.     

On End-Extensions of Models of ¬exp

Every model of IΔ₀ is the tally part of a model of the stringlanguage theory Th-FO (a main feature of which consists in having induction on notation restricted to certain AC⁰. sets). We show how to “smoothly” introduce in Th-FO the binary length function, whereby it is possible to make exponential assumptions in models of Th-FO. These considerations entail that every model of IΔ₀ + ¬exp is a proper initial segment of a model of Th-FO and that a modicum of bounded collection is true in these models. Mathematics Subject Classification: 03F30, 03C62, 68Q15.     

Automorphisms with only infinite orbits on non-algebraic elements

 This paper generalizes results of F. K?rner from [4] where she established the existence of maximal automorphisms (i.e. automorphisms moving all non-algebraic elements). An ω-maximal automorphism is an automorphism whose powers are maximal automorphisms. We prove that any structure has an elementary extension with an ω-maximal automorphism. We also show the existence of ω-maximal automorphisms in all countable arithmetically saturated structures. Further we describe the pairs of tuples (ˉa,ˉb) for which there is an ω-maximal automorphism mapping ˉa to ˉb. Received: 12 December 2001 / Published online: 10 October 2002 Supported by the ``Fonds pour la Formation à la Recherche dans l'Industrie et dans l'Agriculture' Mathematics Subject Classification (2000): Primary: 03C50; Secondary: 03C57 Key words or phrases: Automorphism – Recursively saturated structure     

Weak dividing,chain conditions,and simplicity

We study the properties of the independence relation given by weak dividing in simple theories. We also analyze abstract independence notions satisfying various axioms and relate these to the simple case. Mathematics Subject Classification (2000): 03C45     

On approximation of analytic sets

We give conditions sufficient for the existence of a sequence of Nash sets convergent to a given analytic set. Moreover, for limit sets which are k-sheeted analytic covers we additionally require that sets in approximating sequence are also k-sheeted analytic covers. Then we present examples of applications of the developed theory.Research partially supported by KBN Grant no. 2P03A 015 22Mathematics Subject Classification (2000): 32E30, 32C07, 32C25