bluuebunny/crossref_metadata_2025_split huggingface dataset:
On the number of models of uncountable theories
Authors: Chowdhury Ambar , Pillay Anand 
Published: May 2006

AbstractIn this paper we establish the following theorems.Theorem A. Let T be a complete first-order theory which is uncountable, Then:(i) I(∣T∣, T) ≥ ℵ0(ii) If T is not unidimensional, then for any λ ≥ ∣T∣, I(λ, T) ≥ ℵ0.Theorem B. Let T be superstable, not totally transcendental and nonmultidimensional. Let θ(x) be a formula of least R∞ rank which does not have Morley rank, and let p be any stationary completion of θ which also fails to have Morley rank. Then p is regular and locally modular.
A very weak square principle
Authors: Foreman Matthew , Magidor Menachem 
Published: May 2006

In this paper we explicate a very weak version of the principle □ discovered by Jensen who proved it holds in the constructible universe L. This principle is strong enough to include many of the known applications of □, but weak enough that it is consistent with the existence of very large cardinals. In this section we show that this principle is equivalent to a common combinatorial device, which we call a Jensen matrix. In the second section we show that our principle is consistent with a supercompact cardinal. In the third section of this paper we show that this principle is exactly equivalent to the statement that every torsion free Abelian group has a filtration into σ-balanced subgroups. In the fourth section of this paper we show that this principle fails if you assume the Chang's Conjecture:In the fifth section of the paper we review the proofs that the various weak squares we consider are strictly decreasing in strength. Section 6 was added in an ad hoc manner after the rest of the paper was written, because the subject matter of Theorem 6.1 fit well with the rest of the paper. It deals with a principle dubbed “Not So Very Weak Square”, which appears close to Very Weak Square but turns out not to be equivalent.
Asymptotic probabilities for second-order existential Kahr-Moore-Wang sentences
Authors: Vedø Anne 
Published: May 2006

AbstractWe show that the 0-1 law does not hold for the class(∀∃∀ without = ) by finding a sentence in this class which almost surely expresses parity. We also show that every recursive real in the unit interval is the asymptotic probability of a sentence in this class. This expands a result by Lidia Tendera, who in 1994 proved that everyrationalnumber in the unit interval is the asymptotic probability of a sentence in the class∀∃∀withequality.
Ultrafilters on ω
Authors: Baumgartner James E. 
Published: May 2006

AbstractWe study the I-ultrafilters on ω, where I is a a collection of subsets of a set X, usually ℝ or ω1. The I-ultrafilters usually contain the P-points, often as a small proper subset. We study relations between I-ultrafilters for various I, and closure of I-ultrafilters under ultrafilter sums. We consider, but do not settle, the question whether I-ultrafilters always exist.
The geometry of forking and groups of finite Morley rank
Authors: Pillay Anand 
Published: May 2006

AbstractThe notion of CM-triviality was introduced by Hrushovski, who showed that his new strongly minimal sets have this property. Recently Baudisch has shown that his new ω1-categorical group has this property. Here we show that any group of finite Morley rank definable in a CM-trivial theory is nilpotent-by-finite, or equivalently no simple group of finite Morley rank can be definable in a CM-trivial theory.
An analogue of Hilbert's tenth problem for p-adic entire functions
Authors: Lipshitz Leonard , Pheidas Thanases 
Published: May 2006

Let p be a fixed prime integer, other than 2, Qp the field of p-adic numbers, and Ωp the completion of the algebraic closure of Qp. Let Rp be the ring of entire functions in one variable t over Ωp; that is, Rp is the ring of functions f: Ωp → Qp such that f(t) is given by a power series around 0, of infinite radius of convergence:and where ∣a∣p is the p-adic norm of a in Ωp. We prove:Theorem A. The positive existential theory of Rp in the language L = {0, 1, t, +, ·} is undecidable.Theorem A gives a negative answer to the analogue of Hilbert's tenth problem for Rp in the language L. Related results include those of [2] where it is shown that the first-order theory of entire functions on the complex plane is undecidable and the similar result for analytic functions on the open unit disk (this is due to Denef and Gromov, communicated to us by Cherlin and is as of now unpublished).It would be desirable to have a similar result in the language which, instead of the variable t, has a predicate for the transcendental (that is, nonconstant) elements of Rp. A related problem is the similar problem for meromorphic functions on the real or p-adic plane or on the unit open or closed disk. These problems seem for the moment rather hard in view of the fact that the analogue of Hilbert's Tenth Problem for the field of rational functions over the complex numbers (or any algebraically closed field of characteristic zero) is an open problem.
The topological Vaught's conjecture and minimal counterexamples
Authors: Becker Howard 
Published: May 2006

Let G be a Polish topological group, let X be a Polish space, let J: G × X → X be a Borel-measurable action of G on X, and let A ⊂ X be a Borel set which is invariant with respect to J, i.e., a Borel set of orbits. The following statement, or various equivalent versions of it, is known as the Topological Vaught's Conjecture.Let (G, X, J, A) be as above. Either A contains only countably many orbits, or else, A contains perfectly many orbits.We say that A contains perfectly many orbits if there is a perfect set P ⊂ A such that no two elements of P are in the same orbit. (Assuming ¬CH, A contains perfectly many orbits iff it contains 2ℵ0 orbits.) The Topological Vaught's Conjecture implies the usual, model theoretic, Vaught's Conjecture for Lω1ω, since the isomorphism classes are the orbits of an action of the group of permutations of ω; we give details in §0. The “Borel” assumption cannot be weakened for either A or J.Given a Borel-measurable Polish action (G,X,J) and an invariant Borel set B ⊂ X, we say that B is a minimal counterexample if (G,X,J,B) is a counterexample to the Topological Vaught's Conjecture and for every invariant Borel C ⊂ B, either C or B\C contains only countably many orbits. This paper is concerned with counterexamples to the Topological Vaught's Conjecture (of course, there may not be any), and in particular, with minimal counterexamples. First, there is a theorem on the existence of minimal counterexamples. This theorem was known for the model theoretic case (it is due to Harnik and Makkai), and is here generalized to arbitrary Borel-measurable Polish actions. Second, we study the properties of minimal counterexamples. We give two different necessary and sufficient conditions for a counterexample to be minimal, as well as some consequences of minimality. Some of these results are proved assuming determinacy axioms.This second part seems to be new even in the model theoretic case.
Bisimulations and predicate logic
Authors: Fernando Tim 
Published: May 2006

AbstractElementary (first-order) and nonelementary (set-theoretic) aspects of the largest bisimulation are considered with a view toward analyzing operational semantics from the perspective of predicate logic. The notion of a bisimulation is employed in two distinct ways: (i) as an extensional notion of equivalence on programs (or processes) generalizing input/output equivalence (at a cost exceedingover certain transition predicates computable in log space), and (ii) as a tool for analyzing the dependence of transitions on data (which can be shown to be elementary or nonelementary, depending on the formulation of the transitions).
The cupping theorem in R/M
Authors: Yuefei Sui , Zaiyue Zhang 
Published: May 2006

AbstractIt will be proved that the Shoenfield cupping conjecture holds in R/M, the quotient of the recursively enumerable degrees modulo the cappable r.e. degrees. Namely, for any [a], [b] ∈ R/M such that [0] ≺ [b] ≺ [a] there exists [c] ∈ R/M such that [c] ≺ [a] and [a] = [b] ∨ [c].
Common knowledge logic and game logic
Authors: Kaneko Mamoru 
Published: May 2006

AbstractWe show the faithful embedding of common knowledge logic CKL into game logic GL, that is, CKL is embedded into GL and GL is a conservative extension of the fragment obtained by this embedding. Then many results in GL are available in CKL, and vice versa. For example, an epistemic consideration of Nash equilibrium for a game with pure strategies in GL is carried over to CKL. Another important application is to obtain a Gentzen-style sequent calculus formulation of CKL and its cut-elimination. The faithful embedding theorem is proved for the KD4–type propositional CKL and GL, but it holds for some variants of them.
Yet another hierarchy theorem
Authors: Kubierschky Max 
Published: May 2006

Abstractn + 1 nested k-ary fixed point operators are more expressive than n. This holds on finite structures for all sublogics of partial fixed point logic PFP that can express conjunction, existential quantification and deterministic transitive closure of binary relations using at most k-ary fixed point operators and that are closed against subformulas. Among those are a lot of popular fixed point logics.
Heights of models of ZFC and the existence of end elementary extensions II
Authors: Villaveces Andrés 
Published: May 2006

AbstractThe existence of End Elementary Extensions of modelsM of ZFC is related to the ordinal height of M, according to classical results due to Keisler, Morley and Silver. In this paper, we further investigate the connection between the height of M and the existence of End Elementary Extensions of M. In particular, we prove that the theory ‘ZFC + GCH + there exist measurable cardinals + all inaccessible non weakly compact cardinals are possible heights of models with no End Elementary Extensions’ is consistent relative to the theory ‘ZFC + GCH + there exist measurable cardinals + the weakly compact cardinals are cofinal in ON’. We also provide a simpler coding that destroys GCH but otherwise yields the same result.
Hyperfinite type structures
Authors: Normann Dag , Palmgren Erik , Stoltenberg-Hansen Viggo 
Published: May 2006

The notion of a hyperfinite set comes from nonstandard analysis. Such a set has the internal cardinality of a nonstandard natural number. By a transfer principle such sets share many properties of finite sets. Here we apply this notion to give a hyperfinite model of the Kleene-Kreisel continuous functionals. We also extend the method to provide a hyperfinite characterisation of certain transfinite type structures, thus, through the work of Waagbø [14], constructing a hyperfinite model for Martin-Löf type theory.This kind of application is not new. Normann [6] gave a characterisation of the Kleene-Kreisel continuous functionals using ‘hyperfinitary’ functionals. The novelty here is that we use a constructive version of hyperfinite functionals and also generalise the method to transfinite types. Many of the results of this paper are constructive, though not the characterisation theorems themselves.Our characterisation of the Kleene-Kreisel continuous functionals is a supplement to a number of previous characterisations of topological and recursion-theoretical nature, see [6] for a brief survey. Altogether these characterisations show that the original concept of Kleene and Kreisel forms the correct mathematical model of the idea of finitely based functions of finite types.There is, however, no a priori reason to believe that there is a canonical way to extend the continuous functionals to cover transfinite objects of transfinite type used in, e.g., type theory. Our characterisation of Waagbø's model indicates that the model is natural, not only seen from domain theory but from a higher perspective. Normann and Waagbø (unpublished) have subsequently obtained a limit-space characterisation that further supports this view.
Combinatorial properties of filters and open covers for sets of real numbers
Authors: Laflamme Claude , Scheepers Marion 
Published: May 2006

AbstractWe analyze combinatorial properties of open covers of sets of real numbers by using filters on the natural numbers. In fact, the goal of this paper is to characterize known properties related to ω-covers of the space in terms of combinatorial properties of filters associated with these ω-covers. As an example, we show that all finite powers of a setof real numbers have the covering property of Menger if, and only if, each filter on ω associated with its countable ω-cover is a P+filter.
The least measurable can be strongly compact and indestructible
Authors: Apter Arthur W. , Gitik Moti 
Published: May 2006

AbstractWe show the consistency, relative to a supercompact cardinal, of the least measurable cardinal being both strongly compact and fully Laver indestructible. We also show the consistency, relative to a supercompact cardinal, of the least strongly compact cardinal being somewhat supercompact yet not completely supercompact and having both its strong compactness and degree of supercompactness fully Laver indestructible.
Discretely ordered modules as a first-order extension of the cutting planes proof system
Authors: Krajíček Jan 
Published: May 2006

AbstractWe define a first-order extension LK(CP) of the cutting planes proof system CP as the first-order sequent calculus LK whose atomic formulas are CP-inequalities ∑i ai · xi ≥ b (xi's variables, ai's and b constants). We prove an interpolation theorem for LK(CP) yielding as a corollary a conditional lower bound for LK(CP)-proofs. For a subsystem R(CP) of LK(CP), essentially resolution working with clauses formed by CP-inequalities, we prove a monotone interpolation theorem obtaining thus an unconditional lower bound (depending on the maximum size of coefficients in proofs and on the maximum number of CP-inequalities in clauses). We also give an interpolation theorem for polynomial calculus working with sparse polynomials.The proof relies on a universal interpolation theorem for semantic derivations [16, Theorem 5.1].LK(CP) can be viewed as a two-sorted first-order theory of Z considered itself as a discretely ordered Z-module. One sort of variables are module elements, another sort are scalars. The quantification is allowed only over the former sort. We shall give a construction of a theory LK(M) for any discretely ordered module M (e.g., LK(Z) extends LK(CP)). The interpolation theorem generalizes to these theories obtained from discretely ordered Z-modules. We shall also discuss a connection to quantifier elimination for such theories.We formulate a communication complexity problem whose (suitable) solution would allow to improve the monotone interpolation theorem and the lower bound for R(CP).
Topological completeness for higher-order logic
Authors: Awodey S. , Butz C. 
Published: May 2006

AbstractUsing recent results in topos theory, two systems of higher-order logic are shown to be complete with respect to sheaf models over topological spaces—so-called “topological semantics”. The first is classical higher-order logic, with relational quantification of finitely high type; the second system is a predicative fragment thereof with quantification over functions between types, but not over arbitrary relations. The second theorem applies to intuitionistic as well as classical logic.
Interpretability over peano arithmetic
Authors: Strannegård Claes 
Published: May 2006

AbstractWe investigate the modal logic of interpretability over Peano arithmetic. Our main result is a compactness theorem that extends the arithmetical completeness theorem for the interpretability logic ILMω. This extension concerns recursively enumerable sets of formulas of interpretability logic (rather than single formulas). As corollaries we obtain a uniform arithmetical completeness theorem for the interpretability logic ILM and a partial answer to a question of Orey from 1961. After some simplifications, we also obtain Shavrukov's embedding theorem for Magari algebras (a.k.a. diagonalizable algebras).
A hierarchy of maps between compacta
Authors: Bankston Paul 
Published: May 2006

AbstractLet CH be the class of compacta (i.e., compact Hausdorff spaces), with BS the subclass of Boolean spaces. For each ordinal α and pair (K, L) of subclasses of CH, we define Lev≥α(K, L), the class of maps of level at least α from spaces in K to spaces in L, in such a way that, for finite α, Lev≥α(BS, BS) consists of the Stone duals of Boolean lattice embeddings that preserve all prenex first-order formulas of quantifier rank α. Maps of level ≥ 0 are just the continuous surjections, and the maps of level ≥ 1 are the co-existential maps introduced in [8]. Co-elementary maps are of level ≥ω a for all ordinals α: of course in the Boolean context, the co-elementary maps coincide with the maps of level ≥ ω. The results of this paper include:(i) every map of level ≥ ωis co-elementary;(ii) the limit maps of an co-indexed inverse system of maps of level ≥ α are also of level ≥ α; and(iii) if K is a co-elementary class, k > ω and Lev≥k(K,K) = Lev≥k+1(K,K), then Lev≥1(K,K) = Lev≥(K,K).A space X ∈ K is co-existentially closed inK if Lev≥0(K, X) = Lev≥1(K,X). Adapting the technique of “adding roots,” by which one builds algebraically closed extensions of fields (and, more generally, existentially closed extensions of models of universal-existential theories), we showed in [8] that every infinite member of a co-inductive co-elementary class (such as CH itself, BS, or the class CON of continua) is a continuous image of a space of the same weight that is co-existentially closed in that class. We show here that every compactum that is co-existentially closed in CON (a co-existentially closed continuum) is both indecomposable and of covering dimension one.
Strong axioms of infinity inNFU
Authors: Holmes M. Randall 
Published: May 2006

This paper discusses a sequence of extensions ofNFU, Jensen's improvement of Quine's set theory “New Foundations” (NF) of [16].The original theoryNFof Quine continues to present difficulties. After 60 years of intermittent investigation, it is still not known to be consistent relative to any set theory in which we have confidence. Specker showed in [20] thatNFdisproves Choice (and so proves Infinity). Even if one assumes the consistency ofNF, one is hampered by the lack of powerful methods for proofs of consistency and independence such as are available for use withZFC; very clever work has been done with permutation methods, starting with [18] and [5], and exemplified more recently by [14], but permutation methods can only be applied to show the consistency or independence of unstratified sentences (see the definition ofNFUbelow for a definition of stratification). For example, there is no method available to determine whether the assertion “the continuum can be well-ordered” is consistent with or independent ofNF. There is one substantial independence result for an assertion with nontrivial stratified consequences, using metamathematical methods: this is Orey's proof of the independence of the Axiom of Counting fromNF(see below for a statement of this axiom).We mention these difficulties only to reassure the reader of their irrelevance to the present work. Jensen's modification of “New Foundations” (in [13]), which was to restrict extensionality to sets, allowing many non-sets (urelements) with no elements, has almost magical effects.
Modèles saturés et modèles engendrés par des indiscernables
Authors: Mariou Benoît 
Published: May 2006

AbstractIn the early eighties, answering a question of A. Macintyre, J. H. Schmerl ([13]) proved that every countable recursively saturated structure, equipped with a functionβencoding the finite functions, is theβ-closure of an infinite indiscernible sequence. This result implies that every countably saturated structure, in a countable but not necessarily recursive language, is an Ehrenfeucht-Mostowski model, by which we mean that the structureexpands, in a countable language, to the Skolem hull of an infinite indiscernible sequence (in the new language).More recently, D. Lascar ([5]) showed that the saturated model of cardinality ℵ1of anω-stable theory is also an Ehrenfeucht-Mostowski model.These results naturally raise the following problem: which (countable) complete theories have an uncountably saturated Ehrenfeucht-Mostowski model. We study a generalization of this question. Namely, we call ACI-model a structure which can be expanded, in a countable languageL′, to the algebraic closure (inL′) of an infinite indiscernible sequence (inL′). And we try to characterize theλ-saturated structures which are ACI-models.The main results are the following. First it is enough to restrict ourselves to ℵ1-saturated structures:if T has anℵ1-saturated ACI-model then, for every infinite λ, T has a λ-saturated ACI-model. We obtain a complete answer in the case of stable theories:if T is stable then the three following properties are equivalent: (a)T is ω-stable, (b)T has an ℵ1-saturated ACI-model, (c)every saturated model of T is an Ehrenfeucht-Mostowski model. The unstable case is more complicated, however we show thatif T has an ℵ1-saturated ACI-model then T doesn't have the independence property.
A new correctness criterion for the proof nets of non-commutative multiplicative linear logics
Authors: Nagayama Misao , Okada Mitsuhiro 
Published: May 2006

Abstract.This paper presents a new correctness criterion for marked Danos-Reginer graphs (D-R graphs, for short) of Multiplicative Cyclic Linear Logic MCLL and Abrusci's non-commutative Linear Logic MNLL.As a corollary we obtain an affirmative answer to the open question whether a known quadratic-time algorithm for the correctness checking of proof nets for MCLL and MNLL can be improved to linear-time.
Expansions of dense linear orders with the intermediate value property
Authors: Miller Chris 
Published: May 2006

Let ℜ be an expansion of a dense linear order (R, <) without endpoints having theintermediate value property, that is, for alla, b∈R, every continuous (parametrically) definable functionf: [a, b] →Rtakes on all values inRbetweenf(a) andf(b). Every expansion of the real line (ℝ, <), as well as every o-minimal expansion of (R, <), has the intermediate value property. Conversely, some nice properties, often associated with expansions of (ℝ, <) or with o-minimal structures, hold for sets and functions definable in ℜ. For example, images of closed bounded definable sets under continuous definable maps are closed and bounded (Proposition 1.10).Of particular interest is the case that ℜ expands an ordered group, that is, ℜ defines a binary operation * such that (R, <, *) is an ordered group. Then (R, *) is abelian and divisible (Proposition 2.2). Continuous nontrivial definable endo-morphisms of (R, *) are surjective and strictly monotone, and monotone nontrivial definable endomorphisms of (R, *) are strictly monotone, continuous and surjective (Proposition 2.4). There is a generalization of the familiar result that every proper noncyclic subgroup of (ℝ, +) is dense and codense in ℝ: IfGis a proper nontrivial subgroup of (R, *) definable in ℜ, then eitherGis dense and codense inR, orGcontains an elementusuch that (R, <, *,e, u, G) is elementarily equivalent to (ℚ, <, +, 0, 1, ℤ), whereedenotes the identity element of (R, *) (Theorem 2.3).Here is an outline of this paper. First, we deal with some basic topological results. We then assume that ℜ expands an ordered group and establish the results mentioned in the preceding paragraph. Some examples are then given, followed by a brief discussion of analytic results and possible limitations. In an appendix, an explicit axiomatization (used in the proof of Theorem 2.3) is given for the complete theory of the structure (ℚ, <, +, 0, 1, ℤ).