bluuebunny/crossref_metadata_2025_split huggingface dataset:
Some remarks on nonmultidimensional superstable theories
Authors: Pillay Anand 
Published: May 2006

In this paper we study nonmultidimensional superstable theories T, possibly in an uncountable language, and develop some techniques permitting the generalisation of certain results from the finite rank (and/or countable language) context to the general case.We prove, among other things, the following: there is a set A0 of parameters, which has cardinality at most ∣T∣, and in the finite-dimensional case is finite, such that over any B ⊇ A0 there is a locally atomic model. One of the consequences of this is that if C is the monster model of T, φ(x) is a formula over A0, φC ⊇ X and (X, φC) satisfies the Tarski-Vaught condition after adding names for A0, then there is an elementary substructure M of C containing A0 such that φM = X. Applications to the spectrum problem will appear in [Ch-P].In fact, all the components of the machinery we develop are already present in the general theory. One such component involves a stratification of the regular types of T using a generalized notion of weakly minimal formula. This appears in [Sh, Chapter V and the proof of IX.2.4] and also in [P2]. A second component involves definable groups which arise as ‘binding” groups. The existence of such groups, under certain hypotheses on the behavior of nonorthogonality, is due to Hrushovski [Hr1], and our use of them to help obtain “j-constructible” models is similar to their use in [Bu-Sh].
A quantitative analysis of modal logic
Authors: Fagin Ronald 
Published: May 2006

AbstractWe do a quantitative analysis of modal logic. For example, for each Kripke structure M, we study the least ordinal μ such that for each state of M, the beliefs up to level μ characterize the agents' beliefs (that is, there is only one way to extend these beliefs to higher levels). As another example, we show the equivalence of three conditions, that on the face of it look quite different, for what it means to say that the agents' beliefs have a countable description, or putting it another way, have a “countable amount of information”. The first condition says that the beliefs of the agents are those at a state of a countable Kripke structure. The second condition says that the beliefs of the agents can be described in an infinitary language, where conjunctions of arbitrary countable sets of formulas are allowed. The third condition says that countably many levels of belief are sufficient to capture all of the uncertainty of the agents (along with a technical condition). The fact that all of these conditions are equivalent shows the robustness of the concept of the agents' beliefs having a “countable description”.
On the degrees of unsolvability of modal predicate logics of provability
Authors: McGee Vann 
Published: May 2006

The modal predicate logic of provability identifies the “□” of modal logic with the “Bew” of proof theory, so that, where “Bew” is a formula representing, in the usual way, provability in a consistent, recursively axiomatized theory Γ extending Peano arithmetic (PA), an interpretation of a language for the modal predicate calculus is a map * which associates with each modal formula an arithmetical formula with the same free variables which commutes with the Boolean connectives and the quantifiers and which sets (□ϕ)* equal to Bew(⌈ϕ*⌉). Where Δ is an extension of PA (all the theories we discuss will be extensions of PA), MPL(Δ) will be the set of modal formulas ϕ such that, for every interpretation *, ϕ* is a theorem of Δ. Most of what is currently known about the modal predicate logic of provability consists in demonstrations that MPL(Δ) must be computationally highly complex. Thus Vardanyan [11] shows that, provided that Δ is 1-consistent and recursively axiomatizable, MPL(Δ) will be complete , and Boolos and McGee [5] show that MPL({true arithmetical sentences}) is complete in {true arithmetical sentences}. All of these results take as their starting point Artemov's demonstration in [1] that {true arithmetical sentences} is 1-reducible to MPL({true arithmetical sentences}).The aim here is to consolidate these results by providing a general theorem which yields all the other results as special cases. These results provide a striking contrast with the situation in modal sentential logic (MSL); according to fundamental results of Solovay [8], provided Γ does not entail any falsehoods, MSL({true arithmetical sentences}) and MSL(PA) (which is the same as MSL(Γ)) are both decidable.
Some remarks on openly generated Boolean algebras
Authors: Fuchino Sakaé 
Published: May 2006

AbstractA Boolean algebra B is said to be openly generated if {A : A ≤rcB, ∣A∣ = ℵ0} includes a club subset of . We show:(V = L). For any cardinal κ there exists an L∞κ-free Boolean algebra which is not openly generated (Proposition 4.1).(MA+(σ-closed)). Every -free Boolean algebra is openly generated (Theorem 4.2).The last assertion follows from a characterization of openly generated Boolean algebras under MA+(σ-closed) (Theorem 3.1). Using this characterization we also prove the independence of problem 7 in Ščepin [15] (Proposition 4.3 and Theorem 4.4).
Failure of Cartesian closedness in NF
Authors: McLarty Colin 
Published: May 2006

On any reasonable definition of functions, neither the category of sets nor the category of small categories is cartesian closed in New Foundations (NF). The latter category is sometimes proposed as a foundation for category theory since it is among its own objects. Our result shows it is a poor one.In NF, as in other set theories, a "function" f from a set A to a set B is defined to be a set f of ordered pairs 〈x, y〉 with x in A and y in B, such that (a) if 〈x, y〉 ∈ f and 〈x, y′〉 ∈ f then y = y′, and (b) for every x in A there is some y in B with 〈x, y〉 ∈ f. But in NF different definitions of ordered pairs give significantly different functions. I say a reasonable definition must give:1. The formula z = 〈x, y〉 is stratifiable.2. For every set S there is a set {〈x, x〉 ∣ x ∈ S}.3. If f is a function from A to B, and g one from B to C, there is a set {〈x, z〉∣(∃y)〈x, y〉∈ f & 〈y, z〉∈ g}.Principles 2 and 3 are needed for identity functions and composites. By principle 1, any sets A and B have a set A × B of all ordered pairs 〈x, y〉 with x in A and y in B, but it does not follow that functions exist making A × B a categorical product of A and B.
Zero-one laws with variable probability
Authors: Spencer Joel 
Published: May 2006

One of this author's favorite theorems has long been the Zero-One law discovered independently by Glebskii et al. [12] and Ron Fagin [10]. Let A be any first-order property of graphs and let µn(A) be the proportion of labelled graphs on n vertices for which A holds. ThenThis result has inspired much work by logicians, generally in the direction of showing (1) for some powerful languages. Thus it is known [5] that (1) holds when A is a sentence in fixed point logic and it is known [13] that (1) does not always hold when A is a sentence in second-order monadic logic. Here, however, we explore recent work in a totally different direction. Let G(n, p) denote the random graph on n vertices with edge probability p. (In §2 we define the random structures we will deal with.) A property A is an event in the probability space and Pr[G(n, p) ╞ A] is well defined. When p = 1/2, each labelled graph on n vertices has equal weight so that (1) may be rewrittenFagin's proof actually gives that (2) holds for any constant 0 < p < 1.
On coherent families of finite-to-one functions
Authors: Koszmider Piotr 
Published: May 2006

AbstractWe consider the existence of coherent families of finite-to-one functions on countable subsets of an uncountable cardinal κ. The existence of such families for κ implies the existence of a winning 2-tactic for player TWO in the countable-finite game on κ. We prove that coherent families exist on κ = ωn, where n ∈ ω, and that they consistently exist for every cardinal κ. We also prove that iterations of Axiom A forcings with countable supports are Axiom A.
Canonical formulas for K4. Part I: Basic results
Authors: Zakharyaschev Michael 
Published: May 2006

This paper presents a new technique for handling modal logics with transitive frames, i.e. extensions of the modal system K4. In effect, the technique is based on the following fundamental result, to be obtained below in §3.Given a formula φ, we can effectively construct finite frames 1, …, n which completely characterize the set of all transitive general frames refuting φ. More exactly, an arbitrary general frame refutes φ iff contains a (not necessarily generated) subframe such that (1) i, for some i ϵ {1, …, n}, is a p-morphic image of (after Fine [1985] we say is subreducible to i), (2) is cofinal in , and (3) every point in that is not in does not get into “closed domains” which are uniquely determined in i, by φ.This purely technical result has, as it turns out, rather unexpected and profound consequences. For instance, it follows at once that if φ determines no closed domains in the frames 1, …, n associated with it, then the normal extension of K4 generated by φ has the finite model property and so is decidable. Moreover, every normal logic axiomatizable by any (even infinite) set of such formulas φ also has the finite model property. This observation would not possibly merit any special attention, were it not for the fact that the class of such logics contains almost all the standard systems within the field of K4 (at least all those mentioned by Segerberg [1971] or Bull and Segerberg [1984]), all logics containing S4.3, all subframe logics of Fine [1985], and a continuum of other logics as well.
The isomorphism property versus the special model axiom
Authors: Jin Renling 
Published: May 2006

AbstractThis paper answers some questions of D. Ross in [R]. In §1, we show that some consequences of the ℵ1- or ℵ1-special model axiom in [R] cannot be proved by the κ-isomorphism property for any cardinal κ. In §2, we show that with one exception, the ℵ0-isomorphism property does imply the remaining consequences of the special model axiom in [R]. In §3, we improve a result in [R] by showing that the κ-special model axiom is equivalent to the ℵ0-special model axiom plus κ-saturation.
On decidable varieties of Heyting algebras
Authors: Dubhashi Devdatt P. 
Published: May 2006

In this paper we present a new proof of a decidability result for the firstorder theories of certain subvarieties of Heyting algebras. By a famous result of Grzegorczyk, the full first-order theory of Heyting algebras is undecidable. In contrast, the first-order theory of Boolean algebras and of many interesting subvarieties of Boolean algebras is decidable by a result of Tarski [8]. In fact, Kozen [6] gives a comprehensive quantitative classification of the complexities of the first-order theories of various subclasses of Boolean algebras (including the full variety).This stark contrast may be reconciled from the standpoint of universal algebra as arising out of the byplay between structure and decidability: A good structure theory entails positive decidability results. Boolean algebras have a well-developed structure theory [5], while the corresponding theory for Heyting algebras is quite meagre. Viewed in this way, we may hope to obtain decidability results if we focus attention on subclasses of Heyting algebras with good structural properties.K. Idziak and P. M. Idziak [4] have considered an interesting subvariety of Heyting algebras, , which is the variety generated by all linearly-ordered Heyting algebras. This variety is shown to be the largest subvariety of Heyting algebras with a decidable theory of its finite members. However their proof is rather indirect, proceeding via semantic interpretation into the monadic second order theory of trees. The latter is a powerful theory—it interprets many other theories—but is computationally highly infeasible. In fact, by a celebrated theorem of Rabin, its complexity is not bounded by any elementary recursive function. Consequently, the proof of [4], besides being indirect, also gives no information on the quantitative computational complexity of the theory of .Here we pursue the theme of structure and decidability. We isolate the indecomposable algebras in and use this to prove a theorem on the structure of if -algebras. This theorem relates the -algebras structurally to Boolean algebras. This enables us to bootstrap the known decidability results for Boolean algebras to the variety if .
Pseudoprojective strongly minimal sets are locally projective
Authors: Buechler Steven 
Published: May 2006

AbstractLet D be a strongly minimal set in the language L, and D′ ⊃ D an elementary extension with infinite dimension over D. Add to L a unary predicate symbol D and let T′ be the theory of the structure (D′, D), where D interprets the predicate D. It is known that T′ is ω-stable. We proveTheorem A. If D is not locally modular, then T′ has Morley rank ω.We say that a strongly minimal set D is pseudoprojective if it is nontrivial and there is a k < ω such that, for all a, b ∈ D and closed X ⊂ D, a ∈ cl(Xb) ⇒ there is a Y ⊂ X with a ∈ cl(Yb) and ∣Y∣ ≤ k. Using Theorem A, we proveTheorem B. If a strongly minimal set D is pseudoprojective, then D is locally projective.The following result of Hrushovski's (proved in §4) plays a part in the proof of Theorem B.Theorem C. Suppose that D is strongly minimal, and there is some proper elementary extension D1 of D such that the theory of the pair (D1, D) is ω1-categorical. Then D is locally modular.
Countable structures, Ehrenfeucht strategies, and Wadge reductions
Authors: Linton Tom 
Published: May 2006

AbstractFor 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.
Uniqueness, collection, and external collapse of cardinals in IST and models of Peano arithmetic
Authors: Kanovei V. 
Published: May 2006

AbstractWe prove that in IST, Nelson's internal set theory, the Uniqueness and Collection principles, hold for all (including external) formulas. A corollary of the Collection theorem shows that in IST there are no definable mappings of a set X onto a set Y of greater (not equal) cardinality unless both sets are finite and #(Y) ≤ n #(X) for some standard n. Proofs are based on a rather general technique which may be applied to other nonstandard structures. In particular we prove that in a nonstandard model of PA, Peano arithmetic, every hyperinteger uniquely definable by a formula of the PA language extended by the predicate of standardness, can be defined also by a pure PA formula.
Polynomial time operations in explicit mathematics
Authors: Strahm Thomas 
Published: May 2006

AbstractIn this paper we study (self-)applicative theories of operations and binary words in the context of polynomial time computability. We propose a first order theory PTO which allows full self-application and whose provably total functions on = {0, 1}* are exactly the polynomial time computable functions. Our treatment of PTO is proof-theoretic and very much in the spirit of reductive proof theory.
Infinitary logics and very sparse random graphs
Authors: Lynch James F. 
Published: May 2006

AbstractLet be the infinitary language obtained from the first-order language of graphs by closure under conjunctions and disjunctions of arbitrary sets of formulas, provided only finitely many distinct variables occur among the formulas. Let p(n) be the edge probability of the random graph on n vertices. It is shown that if p(n) ≪ n−1 satisfies certain simple conditions on its growth rate, then for every , the probability that σ holds for the random graph on n vertices converges. In fact, if p(n) = n−α, α > 1, then the probability is either smaller than for some d > 0, or it is asymptotic to cn−d for some c > 0, d ≥ 0. Results on the difficulty of computing the asymptotic probability are given.
On the unification problem for Cartesian closed categories
Authors: Narendran Paliath , Pfenning Frank , Statman Richard 
Published: May 2006

AbstractCartesian closed categories (CCCs) have played and continue to play an important role in the study of the semantics of programming languages. An axiomatization of the isomorphisms which hold in all Cartesian closed categories discovered independently by Soloviev and Bruce, Di Cosmo and Longo leads to seven equalities. We show that the unification problem for this theory is undecidable, thus settling an open question. We also show that an important subcase, namely unification modulo thelinear isomorphisms, is NP-complete. Furthermore, the problem of matching in CCCs is NP-complete when the subject term is irreducible.CCC-matching and unification form the basis for an elegant and practical solution to the problem of retrieving functions from a library indexed by types investigated by Rittri. It also has potential applications to the problem of polymorphic type inference and polymorphic higher-order unification, which in turn is relevant to theorem proving and logic programming.
Bimodal logics for extensions of arithmetical theories
Authors: Beklemishev Lev D. 
Published: May 2006

AbstractWe characterize the bimodal provability logics for certain natural (classes of) pairs of recursively enumerable theories, mostly related to fragments of arithmetic. For example, we shall give axiomatizations, decision procedures, and introduce natural Kripke semantics for the provability logics of (IΔ0 + EXP, PRA); (PRA, IΣn); (IΣm, IΣn) for 1 ≤ m < n; (PA, ACA0); (ZFC, ZFC + CH); (ZFC, ZFC + ¬CH) etc. For the case of finitely axiomatized extensions of theories these results are extended to modal logics with propositional constants.
Mathias absoluteness and the Ramsey property
Authors: Halbeisen Lorenz , Judah Haim 
Published: May 2006

AbstractIn this article we give a forcing characterization for the Ramsey property of -Sets of reals. This research was motivated by the well-known forcing characterizations for Lebesgue measurability and the Baire property of -sets of reals. Further we will show the relationship between higher degrees of forcing absoluteness and the Ramsey property of projective sets of reals.
The complexity of the modal predicate logic of “true in every transitive model of ZF”
Authors: McGee Vann 
Published: May 2006

Robert Solovay [8] investigated the version of the modal sentential calculus one gets by taking “□ϕ” to mean “ϕis true in every transitive model of Zermelo-Fraenkel set theory (ZF).” Defining aninterpretationto be a function * taking formulas of the modal sentential calculus to sentences of the language of set theory that commutes with the Boolean connectives and sets (□ϕ)* equal to the statement thatϕ* is true in every transitive model of ZF, and stipulating that a modal formulaϕisvalidif and only if, for every interpretation *,ϕ* is true in every transitive model of ZF, Solovay obtained a complete and decidable set of axioms.In this paper, we stifle the hope that we might continue Solovay's program by getting an analogous set of axioms for the modal predicate calculus. The set of valid formulas of the modal predicate calculus is not axiomatizable; indeed, it is complete.We also look at a variant notion of validity according to which a formulaϕcounts as valid if and only if, for every interpretation *,ϕ* is true. For this alternative conception of validity, we shall obtain a lower bound of complexity: every set which isin the set of sentences of the language of set theory true in the constructible universe will be 1-reducible to the set of valid modal formulas.
On external Scott algebras in nonstandard models of Peano arithmetic
Authors: Kanovei Vladimir 
Published: May 2006

AbstractWe prove that a necessary and sufficient condition for a countable set of sets of integers to be equal to the algebra of all sets of integers definable in a nonstandard elementary extension of ω by a formula of the PA language which may include the standardness predicate but does not contain nonstandard parameters, is as follows: is closed under arithmetical definability and contains 0(ω) the set of all (Gödel numbers of) true arithmetical sentences.Some results related to definability of sets of integers in elementary extensions of ω are included.
Completeness and decidability of tense logics closely related to logics above K4
Authors: Wolter Frank 
Published: May 2006

AbstractTense logics formulated in the bimodal propositional language are investigated with respect to Kripke-completeness (completeness) and decidability. It is proved that all minimal tense extensions of modal logics of finite width (in the sense of K. Kine) as well as all minimal tense extensions of cofinal subframe logics (in the sense of M. Zakharyaschev) are complete. The decidability of all finitely axiomatizable minimal tense extensions of cofinal subframe logics is shown. A number of variations and extensions of these results are also presented.
The combinatorics of the splitting theorem
Authors: Kontostathis Kyriakos 
Published: May 2006

The complexity of priority proofs in recursion theory has been growing since the first priority proofs in [1] and [11]. Refined versions of classic priority proofs can be found in [18]. To this date, this part of recursion theory is at about the same stage of development as real analysis was in the early days, when the notions of topology, continuity, compactness, vector space, inner product space, etc., were not invented. There were no general theorems involving these concepts to prove results about the real numbers and the proofs were repetitive and lengthy.The priority method contains an unprecedent wealth of combinatorics which is used to answer questions in recursion theory and is bound to have applications in many other fields as well. Unfortunately, very little progress has been made in finding theorems to formulate the combinatorial part of the priority method so as to answer questions without having to reprove the combinatorics in each case.Lempp and Lerman in [10] provide an overview of the subject. The entire edifice of definitions and theorems which formulate the combinatorics of the priority method has acquired the name Priority Theory. From a different vein, Groszek and Slaman in [2] have initiated a program to classify priority constructions in terms of how much induction or collection is needed to carry them out. This program studies the complexity of priority proofs and can be called Complexity Theory of Priority Proofs or simply Complexity.