bluuebunny/crossref_metadata_2025_split huggingface dataset:
Amalgamations preserving ℵ1-categoricity
Authors: Pillay Anand , Tsuboi Akito 
Published: May 2006

Let L0, L1 and L2 be countable languages with L ∩ L1 = L0. Let M0 be an L0-structure and Mi, an expansion of M0 to an Li,-structure (i = 1,2). We will call an L1 ∪ L2-structure M an amalgamation of M1 and M2 if M∣Li ≅ Mi, (i = 1,2). Let's consider the following problem.(*) Suppose that both M1 and M2 belong to the class . Can we always find an amalgamation M in ?Of course the existence of such an amalgamation depends on the class L. Some examples of and the answers are given below.1. = Countably saturated strongly minimal structures with the DMP In [3], Hrushovski showed that any two strongly minimal theories formulated in totally different languages have a common extension which is still strongly minimal and with the DMP (DMP is the property that states that if a point is sufficiently close to ā, then φ(, ) has the same rank and the same degree as φ(, ā).) His proof essentially shows that if L0 = ∅ then any two countably saturated strongly minimal structures with the DMP have a strongly minimal amalgamation. Also he gave an example that shows the condition L0 = ∅ is necessary.2. = ℵ1-categorical countable structures. Let M1 be the structure (ℚ, +) and let M2 be the {E, F}-structure defined by: (i) E is an equivalence relation which divides the universe into two infinite classes A and B, (ii) F is a bijection between A and B.
The structure of intrinsic complexity of learning
Authors: Jain Sanjay , Sharma Arun 
Published: May 2006

AbstractLimiting identification of r.e. indexes for r.e. languages (from a presentation of elements of the language) and limiting identification of programs for computable functions (from a graph of the function) have served as models for investigating the boundaries of learnability. Recently, a new approach to the study of “intrinsic” complexity of identification in the limit has been proposed. This approach, instead of dealing with the resource requirements of the learning algorithm, uses the notion of reducibility from recursion theory to compare and to capture the intuitive difficulty of learning various classes of concepts. Freivalds, Kinber, and Smith have studied this approach for function identification and Jain and Sharma have studied it for language identification.The present paper explores the structure of these reducibilities in the context of language identification. It is shown that there is an infinite hierarchy of language classes that represent learning problems of increasing difficulty. It is also shown that the language classes in this hierarchy are incomparable, under the reductions introduced, to the collection of pattern languages.Richness of the structure of intrinsic complexity is demonstrated by proving that any finite, acyclic, directed graph can be embedded in the reducibility structure. However, it is also established that this structure is not dense. The question of embedding any infinite, acyclic, directed graph is open.
An Ulm-type classification theorem for equivalence relations in Solovay model
Authors: Kanovei Vladimir 
Published: May 2006

AbstractWe prove that in the Solovay model, every OD equivalence relation, Ε, over the reals, either admits an OD reduction to the equality relation on the set of all countable (of length < ω1) binary sequences, or continuously embeds Ε0, the Vitali equivalence.If Ε is a (resp. ) relation then the reduction above can be chosen in the class of all Δ1 (resp. Δ2) functions.The proofs are based on a topology generated by OD sets.
Wildness implies undecidability for lattices over group rings
Authors: Toffalori Carlo 
Published: May 2006

Let G be a finite group. A Z [G]-lattice is a finitely generated Z-torsionfree module over the group ring Z [G]. There is a general conjecture concerning classes of modules over sufficiently recursive rings, and linking wildness and undecidability. Given a finite group G, Z [G] is sufficiently recursive, and our aim here is just to investigate this conjecture for Z [G]-lattices. In this setting, the conjecture says thatif and only ifIn particular, we wish to deal here with the direction from the left to the right, so the one assuring that wildness implies undecidability. Of course, before beginning the analysis of this problem, one should agree upon a sharp definition of wildness for lattices. But, for our purposes, one might alternatively accept as a starting point a general classification of wild Z [G]-lattices when G is a finite p-group for some prime p, based on the isomorphism type of G. This is due to several authors and can be found, for instance, in [3]. It says that, when p is a prime and G is a finite p-group, thenif and only if.More precisely, the representation type of Z [G]-lattices is finite when G is cyclic of order ≤ p2, tame domestic when G is the Klein group [1], tame non-domestic when G is cyclic of order 8 [11].So our claim might be stated as follows.
Definability and decidability issues in extensions of the integers with the divisibility predicate
Authors: Cegielski Patrick , Matiyasevich Yuri , Richard Denis 
Published: May 2006

AbstractLet be a first-order structure; we denote by DEF() the set of all first-order definable relations and functions within . Let π be any one-to-one function from ℕ into the set of prime integers.Let ∣ and • be respectively the divisibility relation and multiplication as function. We show that the sets DEF(ℕ, π, ∣) and DEF(ℕ, π, •) are equal. However there exists function π such that the set DEF(ℕ, +, ∣), or, equivalently, DEF(ℕ, π, •) is not equal to DEF(ℕ, +, •). Nevertheless, in all cases there is an {π, •}-definable and hence also {π, |}-definable structure over π which is isomorphic to 〈ℕ, +, •〉. Hence theories TH(ℕ, π, ∣) and TH(ℕ, π, •) are undecidable.The binary relation of equipotence between two positive integers saying that they have equal number of prime divisors is not definable within the divisibility lattice over positive integers. We prove it first by comparing the lower bound of the computational complexity of the additive theory of positive integers and of the upper bound of the computational complexity of the theory of the mentioned lattice.The last section provides a self-contained alternative proof of this latter result based on a decision method linked to an elimination of quantifiers via specific tables.
Fine structure for tame inner models
Authors: Schimmerling E. , Steel J. R. 
Published: May 2006

In this paper, we solve the strong uniqueness problem posed in [St2]. That is, we extend the full fine structure theory of [MiSt] to backgrounded models all of whose levels are tame (defined in [St2] and below). As a consequence, more powerful large cardinal properties reflect to fine structural inner models. For example, we get the following extension to [MiSt, Theorem 11.3] and [St2, Theorem 0.3].Suppose that there is a strong cardinal that is a limit of Woodin cardinals. Then there is a good extender sequence such that(1) every level of is a sound, tame mouse, and(2) ⊨ “There is a strong cardinal that is a limit of Woodin cardinals”.Recall that satisfies GCH if all its levels are sound. Another consequence of our work is the following covering property, an extension to [St1, Theorem 1.4] and [St3, Theorem 1.10].Suppose that fi is a normal measure on Ω and that all premice are tame. Then Kc, the background certified core model, exists and is a premouse of height Ω. Moreover, for μ-almost every α < Ω.Ideas similar to those introduced here allow us to extend the fine structure theory of [Sch] to the level of tame mice. The details of this extension shall appear elsewhere. From the extension of [Sch] and Theorem 0.2, new relative consistency results follow. For example, we have the following application.If there is a cardinal κ such that κ is κ+-strongly compact, then there is a premouse that is not tame.
Strictly primitive recursive realizability, I
Authors: Damnjanovic Zlatan 
Published: May 2006

AbstractA realizability notion that employs only primitive recursive functions is defined, and, relative to it, the soundness of the fragment of Heyting Arithmetic (HA) in which induction is restricted to formulae is proved. A dual concept of falsifiability is proposed and an analogous soundness result is established for a further restricted fragment of HA.
Characterising subsets of ω1 constructible from a real
Authors: Welch P. D. 
Published: May 2006

AbstractA small large cardinal upper bound in V for proving when certain subsets of ω1 (including the universally Baire subsets) are precisely those constructible from a real is given. In the core model we find an exact equivalence in terms of the length of the mouse order; we show that ∀B ⊆ ω1 [B is universally Baire ⇔ B ϵ L[r] for some real r] is preserved under set-sized forcing extensions if and only if there are arbitrarily large “admissibly measurable” cardinals.
On o-minimal expansions of Archimedean ordered groups
Authors: Laskowski Michael C. , Steinhorn Charles 
Published: May 2006

AbstractWe study o-minimal expansions of Archimedean totally ordered groups. We first prove that any such expansion must be elementarily embeddable via a unique (provided some nonzero element is 0-definable) elementary embedding into a unique o-minimal expansion of the additive ordered group of real numbers . We then show that a definable function in an o-minimal expansion of enjoys good differentiability properties and use this to prove that an Archimedean real closed field is definable in any nonsemilinear expansion of . Combining these results, we obtain several restrictions on possible o-minimal expansions of arbitrary Archimedean ordered groups and in particular of the rational ordered group.
Storage operators and directed lambda-calculus
Authors: David René , Nour Karim 
Published: May 2006

AbstractStorage operators have been introduced by J. L. Krivine in [5] they are closed λ-terms which, for a data type, allow one to simulate a “call by value” while using the “call by name” strategy. In this paper, we introduce the directed λ-calculus and show that it has the usual properties of the ordinary λ-calculus. With this calculus we get an equivalent—and simple—definition of the storage operators that allows to show some of their properties:• the stability of the set of storage operators under the β-equivalence (Theorem 5.1.1);• the undecidability (and semidecidability) of the problem “is a closed λ-term t a storage operator for a finite set of closed normal λ-terms?” (Theorems 5.2.2 and 5.2.3);• the existence of storage operators for every finite set of closed normal λ-terms (Theorem 5.4.3);• the computation time of the “storage operation” (Theorem 5.5.2).
A modal view of linear logic
Authors: Martini Simone , Masini Andrea 
Published: May 2006

AbstractWe present a sequent calculus for the modal logic S4, and building on some relevant features of this system (the absence of contraction rules and the confinement of weakenings into axioms and modal rules) we show how S4 can easily be translated into full prepositional linear logic, extending the Grishin-Ono translation of classical logic into linear logic. The translation introduces linear modalities (exponentials) only in correspondence with S4 modalities. We discuss the complexity of the decision problem for several classes of linear formulas naturally arising from the proposed translations.
Combinatorics on ideals and axiom A
Authors: Sharp James D. 
Published: May 2006

Throughout this paper denotes a nonprincipal ultrafilter and ℐ denotes the dual ideal. ℙ(ℐ) is the poset of all partial functions p: ω → 2 such that dom(p) ∈ ℐ. In [2], Grigorieff proved that ω1 is preserved in the corresponding generic extension if and only if is a P-point. Later, when Shelah introduced the notion of a proper poset, many people observed that if is a P-point, then ℙ(ℐ) is proper. One way of proving this is to show that player II has a winning strategy in the game for ℙ(ℐ) (see [3, p. 91].)The notion of an Axiom A poset was introduced by Baumgartner [1]. If a poset satisfies Axiom A, then player II has a winning strategy in the game for ℙ, and thus, ℙ is proper. Indeed most of the naturally occurring proper posets satisfy Axiom A (e.g., Mathias's poset and Laver's poset). Thus, it is natural to ask whether or not ℙ(ℐ) satisfies Axiom A. The main result of this paper is a negative answer to this question. We will prove this by introducing another game and showing that is a P-point if and only if the corresponding game is undetermined. We will then show that if ℙ(ℐ) satisfied Axiom A, then player II would have a winning strategy in the corresponding game .We let [X]<ω = {s ⊆ X∣ ∣s∣ < ω}. We let Seq(X) denote the set of finite sequences of elements of X. If s = 〈x0, …, xn〉 ∈ Seq(X) and y ∈ X, then s * 〈y〉 = 〈x0,…,xn,y〉 ∈ Seq(X).
A guide to truth predicates in the modern era
Authors: Sheard Michael 
Published: May 2006

A reader coming anew to the recent work on languages which contain their own truth predicates may be perplexed by the simple question of where to begin. A first approach to the literature suggests a field which is alive and busy with investigations heading in many different directions, but there is much less indication of how various pieces fit together. There are at least two sources of this confusion. First, the literature is large and diffuse (as befits a subject which goes back over 2000 years); Visser's survey [33] aptly describes the literature as “vast but scattered, repetitive, and disconnected.” Moreover, recent interest in the field has led to a proliferation of research and publication; it seems that almost any issue of any philosophical logic journal from the mid-1980s contains some article on the topic. The second reason, in part a consequence of the first, is that while a typical article in print usually presents a good internal motivation, with clear reference to its immediate intellectual antecedents, its place in the broader picture may not be so easily discerned. The problem can be especially acute in presentations of axiomatic approaches, because decisions on certain basic questions can lie hidden in the formal and notational details which abound in any axiomatization.In fact, though, the recent research on methods for handling self-referential truth can be seen as a body of work which is very well structured, one in which a few fundamental decisions suffice to locate any particular approach in its appropriate place on the landscape. My goal is to describe this structure and in particular to stress a few critical forks in the road, which will be the recurring metaphor throughout this paper. I will also pay particular attention to pointing out where the interesting technical and mathematical questions lie.
Actions by the classical Banach spaces
Authors: Hjorth G. 
Published: May 2006

The study of continuous group actions is ubiquitous in mathematics, and perhaps the most general kinds of actions for which we can hope to prove theorems in just ZFC are those where a Polish group acts on a Polish space.For this general class we can find works such as [29] that build on ideas from ergodic theory and examine actions of locally compact groups in both the measure theoretic and topological contexts. On the other hand a text in model theory, such as [12], will typically consider issues bearing on the actions by the symmetric group of all permutations of the integers. More generally [1] shows that the orbit equivalence relations induced by closed subgroups of the infinite symmetric group can be reduced to the isomorphism relation on corresponding classes of countable models.This paper considers a third category formed by the continuous actions of separable Banach spaces on Polish spaces. These examples cannot be subsumed under the two earlier headings, and it is known from [10] that theBorel cardinalitiesof the quotient spaces that arise from such actions are incomparable with the equivalence relations induced by the symmetric group or any locally compact Polish group action.One of the first things to be addressed concerns the complexity of these equivalence relations. This question forappears in [1].
Implicational F-structures and implicational relevance logics
Authors: Avron A. 
Published: May 2006

AbstractWe describe a method for obtaining classical logic from intuitionistic logic which does not depend on any proof system, and show that by applying it to the most important implicational relevance logics we get relevance logics with nice semantical and proof-theoretical properties. Semantically all these logics are sound and strongly complete relative to classes of structures in which all elements except one are designated. Proof-theoretically they correspond to cut-free hypersequential Gentzen-type calculi. Another major property of all these logics is that the classical implication can faithfully be translated into them.
A completeness theorem for higher order logics
Authors: Sági Gábor 
Published: May 2006

AbstractHere we investigate the classes of representable directed cylindric algebras of dimension α introduced by Németi [12]. can be seen in two different ways: first, as an algebraic counterpart of higher order logics and second, as a cylindric algebraic analogue of Quasi-Projective Relation Algebras. We will give a new, “purely cylindric algebraic” proof for the following theorems of Németi: (i) is a finitely axiomatizable variety whenever α ≥ 3 is finite and (ii) one can obtain a strong representation theorem for if one chooses an appropriate (non-well-founded) set theory as foundation of mathematics. These results provide a purely cylindric algebraic solution for the Finitization Problem (in the sense of [11]) in some non-well-founded set theories.
Foundation versus induction in Kripke-Platek set theory
Authors: Zambella Domenico 
Published: May 2006

We denote by KP_ the fragment of set-theory containing the axioms of extensionality, pairing, union and foundation as well as the schemas of ∆0-comprehension and ∆0-collection, that is: Kripke-Platek set-theory (KP) with the axiom of foundation in place of the ∈-induction schema. The theory KP is obtained by adding to KP_ the schema of ∈-inductionUsing ∈-induction it is possible to prove the existence of the transi tive closure without appealing to the axiom of infinity (see, e.g., [1]). Vice versa, when a theory proves the existence of the transitive closure, some induction is immediately ensured (by foundation and comprehension). This is not true in general: e.g., the whole of Zermelo-Fraenkel set-theory without the axiom of infinity does not prove ∈-induction (in fact, it does not prove the existence of the transitive closure; see, e.g., [3]). Open-induction is the schema of ∈-induction restricted to open formulas. We prove the following theorem.KP_ proves open-induction.We reason in a fixed but arbitrary model of KP_ whom we refer to as the model. The language is extended with a name for every set in the model. We call this constants parameters. Let φ(x) be a satisfiable open-formula possibly depending on parameters and with no free variable but x. We show that φ(x) is satisfied by an ∈-minimal set, that is, a set a such that φ(a) and (∀x ∈ a) ¬φ(x). We assume that no ordinal satisfies φ(x), otherwise the existence of a ∈-minimal set follows from foundation and comprehension.
CM-triviality and stable groups
Authors: Wagner Frank O. 
Published: May 2006

AbstractWe define a generalized version of CM-triviality, and show that in the presence of enough regular types, or solubility, a stable CM-trivial group is nilpotent-by-finite. A torsion-free small CM-trivial stable group is abelian and connected. The first result makes use of a generalized version of the analysis of bad groups.
On closed unbounded sets consisting of former regulars
Authors: Gitik Moti 
Published: May 2006

AbstractA method of iteration of Prikry type forcing notions as well as a forcing for adding clubs is presented. It is applied to construct a model with a measurable cardinal containing a club of former regulars, starting with ο(κ) = κ + 1. On the other hand, it is shown that the strength of above is at leastο(κ) = κ.
Finite algebras of relations are representable on finite sets
Authors: Andréka H. , Hodkinson I. , Németi I. 
Published: May 2006

AbstractUsing a combinatorial theorem of Herwig on extending partial isomorphisms of relational structures, we give a simple proof that certain classes of algebras, including Crs, polyadic Crs, and WA, have the ‘finite base property’ and have decidable universal theories, and that any finite algebra in each class is representable on a finite set.
Deduction theorems within RM and its extensions
Authors: Czelakowski J. , Dziobiak W. 
Published: May 2006

AbstractIn [13], M. Tokarz specified some infinite family of consequence operations among all ones associated with the relevant logic RM or with the extensions of RM and proved that each of them admits a deduction theorem scheme. In this paper, we show that the family is complete in a sense that if C is a consequence operation with CRM ≤ C and C admits a deduction theorem scheme, then C is equal to a consequence operation specified in [13]. In algebraic terms, this means that the only quasivarieties of Sugihara algebras with the relative congruence extension property are the quasivarieties corresponding, via the algebraization process, to the consequence operations specified in [13].
Finite sets and frege structures
Authors: Bell John L. 
Published: May 2006

Call a family of subsets of a set E inductive if and is closed under unions with disjoint singletons, that is, ifA Frege structure is a pair (E, ν) with ν a map to E whose domain dom(ν) is an inductive family of subsets of E such thatIn [2] it is shown in a constructive setting that each Frege structure determines a subset which is the domain of a model of Peano's axioms. In this note we establish, within the same constructive setting, three facts. First, we show that the least inductive family of subsets of a set E is precisely the family of decidable Kuratowski finite subsets of E. Secondly, we establish that the procedure presented in [2] can be reversed, that is, any set containing the domain of a model of Peano's axioms determines a map which turns the set into a minimal Frege structure: here by a minimal Frege structure is meant one in which dom(ν) is the least inductive family of subsets of E. And finally, we show that the procedures leading from minimal Frege structures to models of Peano's axioms and vice-versa are mutually inverse. It follows that the postulation of a (minimal) Frege structure is constructively equivalent to the postulation of a model of Peano's axioms.All arguments will be formulated within constructive (intuitionistic) set theory.
Adjoining cofinitary permutations
Authors: Zhang Yi 
Published: May 2006

AbstractWe show that it is consistent with ZFC + ¬CH that there is a maximal cofinitary group (or, maximal almost disjoint group) G ≤ Sym(ω) such that G is a proper subset of an almost disjoint family A ⊆ Sym(ω) and ‖G‖ < ‖A‖. We also ask several questions in this area.
The representation theories of elementarily equivalent rings
Authors: Prest Mike 
Published: May 2006

Two rings are elementarily equivalent if and only if they satisfy the same sentences in the language of rings. To some extent this is reflected in the representation theories of the two rings (one may see both positive and negative results along these lines in [5]). Here we concentrate on the case of a ring S and an elementary subring R of S.We show that if R is an elementary subring of S then the lattice of pp formulas for R-modules embeds in that for S-modules. These lattices, moreover, have the same finite sub-posets. From this we derive some corollaries. Then we consider to what extent the compositions of induction and restriction between R- and S-modules preserve elementary equivalence.