bluuebunny/crossref_metadata_2025_split huggingface dataset:
Abstract logic and set theory. II. Large cardinals
Authors: Väänänen Jouko 
Published: May 2006

AbstractThe following problem is studied: How large and how small can the Löwenheim and Hanf numbers of unbounded logics be in relation to the most common large cardinals? The main result is that the Löwenheim number of the logic with the Härtig-quantifier can be consistently put in between any two of the first weakly inaccessible, the first weakly Mahlo, the first weakly compact, the first Ramsey, the first measurable and the first supercompact cardinals.
Beth's property fails in L<ω
Authors: Badger Lee 
Published: May 2006

In this paper we prove that Beth's property does not hold in L<ω. This answers a question posed by Magidor and Malitz in [8]. Beth's property is a natural closure condition on a language which says that everything implicitly definable in the language is also explicitly definable in the language. That the first-order predicate calculus (L0) has the property was first shown by Beth [4]. Lopez-Escobar proved that also has Beth's property [7]. Malitz [9] showed the Beth's property fails in Lκλ where κ ≥ λ ≥ ω1. Friedman and Silver showed that the property fails in Lκλ for κ > ω1. Also Friedman [5] showed that extensions of elementary logic using cardinality quantifiers (L)1κ do not have Beth's property.The undefined notation used here is standard. If further clarification is needed, we refer the reader to [3]. κ and λ denote infinite cardinals. cX and ȣX∣ denote the cardinality of X. cfμ will denote the cofinality of the order μ. All languages discussed are assumed to have no function or constant symbols. All structures are relational. The type of a formula is the set of relation symbols appearing in the formula (excluding equality). The type of a set of formulas is the set of all relation symbols appearing in some formula of the set of formulas. For purpose of this paper we will assume that to each n-ary relation in a structure there is associated an n-ary relation symbol and that in any given structure this association is one-to-one. Using this convention we can define the type of a structure to be the set of those relation symbols to which there is associated a relation in the structure. Sometimes we use the term predicate instead of relation.
Forcing with Δ perfect trees and minimal Δ-degrees
Authors: Kechris Alexander S. 
Published: May 2006

This paper is a sequel to [3] and it contains, among other things, proofs of the results announced in the last section of that paper.In §1, we use the general method of [3] together with reflection arguments to study the properties of forcing with Δ perfect trees, for certain Spector pointclasses Γ, obtaining as a main result the existence of a continuum of minimal Δ-degrees for such Γ's, under determinacy hypotheses. In particular, using PD, we prove the existence of continuum many minimal Δ½n+1-degrees, for all n.Following an idea of Leo Harrington, we extend these results in §2 to show the existence of minimal strict upper bounds for sequences of Δ-degrees which are not too far apart. As a corollary, it is computed that the length of the natural hierarchy of Δ½n+1-degrees is equal to ω when n ≥ 1. (By results of Sacks and Richter the length of the natural hierarchy of -degrees is known to be equal to the first recursively inaccessible ordinal.)We will follow in this paper standard notation and terminology, as in Moschovakis' book [7]. Letters e, i, j, k, l, m, n vary over the set of natural numbers ω, a, b, c over the Cantor space 2ω and α, β, γ, δ, … over the set of reals ωω. Finally ξ, η, κ, λ always denote ordinals.
A proof of the associated sheaf theorem by means of categorical logic
Authors: Veit Barbara 
Published: May 2006

The double nature, both logical and geometrical, of topos theory is one of the most fascinating aspects of this discipline. Consequently, it might be of some interest that an essentially “geometric” fact such as the associated sheaf theorem admits a proof entirely based on methods of categorical logic.The idea of this proof comes from a previous paper [V], where the same technique was used in the context of Grothendieck topoi. That paper used a generalized notion of forcing which leads directly from classical Tarski semantics in sets to Kripke-Joyal semantics in an arbitrary Grothendieck topos and gives a precise description of the links between the two. On account of this very close relationship, we thus could establish various basic facts on Grothendieck topoi without an extensive use of categorical methods, simply by viewing given subobjects as interpretations of appropriate formulas written in the formal language that had been used all along.
A Gentzen- or Beth-type system, a practical decision procedure and a constructive completeness proof for the counterfactual logics VC and VCS
Authors: de Swart H. C. M. 
Published: May 2006

In [1] and [2] D. Lewis formulates his counterfactual logic VC as follows. The language contains the connectives ∧, ∨, ⊃, ¬ and the binary connective ≤. A ≤ B is read as “A is at least as possible as B”. The following connectives are defined in terms of ≤.A < B: = ¬(B ≤ A) (it is more possible that A than that B).◊ A ≔ ¬(⊥ ≤ A) (⊥ is the false formula; A is possible).□ A ≔ ⊥ ≤ ¬A (A is necessary). (if A were the case, then B would be the case). (if A were the case, then B might be the case). and are two counterfactual conditional operators. (AB) iff ¬(A ¬B).The following axiom system VC is presented by D. Lewis in [1] and [2]: V: (1) Truthfunctional classical propositional calculus.
Recursion theory and the lambda-calculus
Authors: Byerly Robert E. 
Published: May 2006

AbstractA semantics for the lambda-calculus due to Friedman is used to describe a large and natural class of categorical recursion-theoretic notions. It is shown that if e1 and e2 are gödel numbers for partial recursive functions in two standard ω-URS's which both act like the same closed lambda-term, then there is an isomorphism of the two ω-URS's which carries e1 to e2.
Intermediate β-r.e. degrees and the half-jump
Authors: Homer Steven 
Published: May 2006

In his thesis [2] Sy Friedman showed that for any inadmissible ordinal β there is an easily definable β-r.e. degree, 01/2, with β-degree strictly between 0 and 0′. In this paper we define, for some weakly admissible β, a β-r.e. degree 03/4 intermediate between 01/2 and 0′. This definition is given using the machinery developed by Maass [6], [7] to study the β-r.e. degrees.A weak jump for β-recursion theory, the ½-jump, was first defined by Friedman [4] and has been studied by Sacks and Homer [5]. The degree 03/4 is of interest because of the way it interacts with the half-jump. In particular 03/4 forms the boundary between the half-jump of “hyperregular” and “nonhyperregular” β-r.e. degrees less than 01/2. One consequence of these results is that there are weakly inadmissible β for which either the jump theorem or the density theorem fails.Much of this paper is based on earlier work in this area by Sy Friedman and Wolfgang Maass. I would like to thank Gerald Sacks for many helpful conversations and comments concerning this work.
Analytic determinacy and 0#
Authors: Harrington Leo 
Published: May 2006

Martin [12] has shown that the determinacy of analytic games is a consequence of the existence of sharps. Our main result is the converse of this:Theorem. If analytic games are determined, then x2 exists for all reals x.This theorem answers question 80 of Friedman [5]. We actually obtain a somewhat sharper result; see Theorem 4.1. Martin had previously deduced the existence of sharps from 3 − Π11-determinacy (where α − Π11 is the αth level of the difference hierarchy based on − Π11 see [1]). Martin has also shown that the existence of sharps implies < ω2 − Π11-determinacy.Our method also produces the following:Theorem. If all analytic, non-Borel sets of reals are Borel isomorphic, then x* exists for all reals x.The converse to this theorem had been previously proven by Steel [7], [18].We owe a debt of gratitude to Ramez Sami and John Steel, some of whose ideas form basic components in the proofs of our results.For the various notation, definitions and theorems which we will assume throughout this paper, the reader should consult [3, §§5, 17], [8], [13] and [14, Chapter 16].Throughout this paper we will concern ourselves only with methods for obtaining 0# (rather than x# for all reals x). By relativizing our arguments to each real x, one can produce x2.
Interpolation theorems for Lk,k2+
Authors: Ferro Ruggero 
Published: May 2006

Chang, in [1], proves an interpolation theorem (Theorem I, remark b)) for a first-order language. The proof of Chang's theorem uses essentially nonsimple devices, like special and ω1-saturated models.In remark e) in [1], Chang asks if there is a simpler proof of his Theorem I.In [1], Chang proves also another interpolation theorem (Theorem II), which is not an extension of his Theorem I, but extends Craig's interpolation theorem to Lα+,ω languages with interpolant in Lα+,α where α is a strong limit cardinal of cofinality ω.In remark k) in [1], Chang asks if there is a generalization of both Theorems I and II in [1], or at least a generalization of both Theorem I in [1] and Lopez-Escobar's interpolation theorem in [7].Maehara and Takeuti, in [8], show that there is a completely different proof of Chang's interpolation Theorem I as a consequence of their interpolation theorems. The proofs of these theorems of Maehara and Takeuti are proof theoretical in character, involving the notion of cut-free natural deduction, and it uses devices as simple as those needed for the usual Craig's interpolation theorem. Hence this can be considered as a positive answer to Chang's question in remark e) in [1].
Forcing and reducibilities
Authors: Odifreddi Piergiorgio 
Published: May 2006

We see far away, Newton said, if we stand on giants' shoulders. We take him seriously here and moreover (as appropriate to recursion-theorists) we will jump from one giant to another, since this paper is mostly an exegesis of two fundamental works: Feferman's Some applications of the notions of forcing and generic sets [4] and Sacks' Forcing with perfect closed sets [19]. We hope the reader is not afraid of heights: our exercises are risky ones, since the two giants are in turn on the shoulders of others! Feferman [4] rests on the basic works of Cohen [2], who introduced forcing with finite conditions in the context of set theory; Sacks [19] relies on Spector [24], who realized—in recursion theory—the necessity of more powerful approximations than the finite ones.To minimize the risk we will try to keep technicalities to a minimum, choosing to give priority to the methodology of forcing. We do not suppose any previous knowledge of forcing in the reader, but we do require some acquaintance with recursion theory. After all, our interest lies in the applications of the forcing method to the study of various recursion-theoretic notions of degrees. The farther we go, the deeper we plunge into recursion theory.In Part I only very basic notions and results are used, like the definitions of the arithmetical hierarchy and of the jump operator and their relationships.
A certain class of models of Peano arithmetic
Authors: Kossak Roman 
Published: May 2006

This paper is devoted to the study of recursively and short recursively saturated models of PA by means of so-called nonstandard satisfaction methods. The paper is intended to be self-contained. In particular, no knowledge of nonstandard satisfaction classes is assumed. In fact we shall not use this notion explicitly.We define a certain property of models of PA which we call the S-property and prove that properly short recursively saturated models (see Definition 2.1. below) are exactly short models with the S-property. The main result is that all properly short recursively saturated models are elementary cuts of recursively saturated models. This is a generalization to the uncountable case of the theorem of C. Smorynski [9] and is an easy application of some general results concerning cofinal extensions of models of PA which we discuss in §3.On the way we obtain another proof of the result of Smorynski and Stavi [10] which says that short recursive and recursive saturation is preserved under cofinal extensions.The author wants to thank H. Kotlarski and W. Marek for valuable suggestions concerning the subject of the paper.Special thanks must also go to J. Paris for the lemma used in the proof of Theorem 3.5.
Boolean sentence algebras: Isomorphism constructions
Authors: Hanf William P. , Myers Dale 
Published: May 2006

AbstractAssociated with each first-order theory is a Boolean algebra of sentences and a Boolean space of models. Homomorphisms between the sentence algebras correspond to continuous maps between the model spaces. To what do recursive homomorphisms correspond? We introduce axiomatizable maps as the appropriate dual. For these maps we prove a Cantor-Bernstein theorem. Duality and the Cantor-Bernstein theorem are used to show that the Boolean sentence algebras of any two undecidable languages or of any two functional languages are recursively isomorphic where a language is undecidable iff it has at least one operation or relation symbol of two or more places or at least two unary operation symbols, and a language is functional iff it has exactly one unary operation symbol and all other symbols are for unary relations, constants, or propositions.
On sets of relations definable by addition
Authors: Lynch James F. 
Published: May 2006

AbstractFor every κ ∈ ω, there is an infinite set Aκ ⊆ ω and a d(κ) ∈ ω such that for all Q0, Q1, ⊆ Aκ where ∣Q0∣ = ∣ Q1∣, or d(κ) < ∣Q0∣, Q1∣ < ℵ0, the structures ‹ω, +, Q0› and ‹ω, +, Q1› are indistinguishable by first-order sentences of quantifier depth κ whose atomic formulas are of the form u = v, u + v = w, and Q(u), where u, v, and w are variables.
Two further combinatorial theorems equivalent to the 1-consistency of peano arithmetic
Authors: Clote Peter , Mcaloon Kenneth 
Published: May 2006

We give two new finite combinatorial statements which are independent of Peano arithmetic, using the methods of Kirby and Paris [6] and Paris [12]. Both are in fact equivalent over Peano arithmetic (denoted by P) to its 1-consistency. The first involves trees and the second linear orderings. Both were “motivated” by anti-basis theorems of Clote (cf. [1], [2]). The one involving trees, however, is not unrelated to the Kirby-Paris characterization of strong cuts in terms of the tree property [6], but, in fact, comes directly from König's lemma, of which it is a miniaturization. (See the remark preceding Theorem 3 below.) The resulting combinatorial statement is easily seen to imply the independent statement discovered by Mills [11], but it is not clear how to show their equivalence over Peano arithmetic without going through 1-consistency. The one involving linear orderings miniaturizes the property of infinite sets X that any linear ordering of X is isomorphic to ω or ω* on some infinite subset of X. Both statements are analogous to Example 2 of [12] and involve the notion of dense [12] or relatively large [14] finite set.We adopt the notations and definitions of [6] and [12]. We shall in particular have need of the notions of semiregular, regular and strong initial segments and of indicators.
The measure quantifier
Authors: Morgenstern Carl F. 
Published: May 2006

Originally generalized quantifiers were introduced to specify that a given formula was true for “many x's” e.g. ⊨ Qxφ(x) iff card{x ∈ ∣∣ ∣ ⊨ φ[x]} ≥ ℵ0, ℵ1, or some fixed cardinal κ. In this paper we formalize the notion that φ{x) is true “for almost all x”. This is accomplished by referring to structures = (′, μ) where ′ is a first-order structure and μ is a measure of a suitable type on the universe of ′. We will prove that the language Lμ obtained from first-order logic by adjoining a quantifier Qμ, which ranges over the measure μ, is fully compact if we assume the existence of a proper class of measurable cardinals. As a corollary to the compactness theorem we obtain the recursive enumerability of the validities of Lμ. Finally, the Magidor-Malitz quantifiers Qkn (n ∈ ω) will be added to Lμ together with analogous quantifiers Qμm (m ∈ ω) to form Lκμ<ω,<ω, which is compact for sets of sentences of cardinality < κ, where κ is a measurable cardinal > ℵ0.An alternate approach to formalizing “for almost all” has been recently developed by Barwise, Kaufmann and Makkai [1] who follow a suggestion of Shelah [5].
Reducibilities in two models for combinatory logic
Authors: Sanchis Luis E. 
Published: May 2006

This paper proposes a generalization of several reducibilities in the sense of recursive function theory. For this purpose two structures are introduced as models of combinatory logic and reducibilities are defined in a rather natural way by means of the application operation in each model. The first model we consider is called the graph model and was introduced by Dana Scott in [11]. Reducibilities in this model are generalizations of enumeration and Turing reducibilities. The second model is called the hypergraph model and induces reducibilities which are generalizations of hyperenumeration and hyperarithmetical reducibilities.The possibility of formulating reducibilities in this way is not new. For the graph model it is implicit in [7] and for the hypergraph model in [9]. On the other hand it is possible to look at the present method as a variant of the well-known technique of relativization in recursive function theory. We think that this does not exhaust the power of the method, which is conceptually elegant and provides a natural frame for the results of this paper.In the first part of the paper we discuss the definition and general properties of the models. Then we introduce the reducibilities in the graph model and prove several theorems which are generalizations of properties already Known for enmeration and Turing reducibilities. Next we define reducibilities in the hypergraph model and try to extend the preceding results. For this purpose we prove two theorems showing significant relations between the operators in both models. In fact we prove that each operator in the hypergraph model can be simulated on a comeager set by an operator of the graph model.
On the proof theory of the modal logic for arithmetic provability
Authors: Leivant Daniel 
Published: May 2006

The modal logic GL has been found by Solovay [13] to formalize the provable propositional properties of the provability-predicate for Peano's Arithmetic PA (cf. §1 below). We give several sequential calculi for GL, compare their merits, and use one calculus to syntactically derive several metamathematical results about GL.Some of our results have been proved model theoretically, and similar proofs are fairly straightforward for several of the remaining ones (G. Boolos and the referee have provided such proofs for 4.1, 4.3 and 5.1 below). However, our syntactic techniques often yield more concise and obviously constructive proofs, they offer additional insight into the nature of the systems considered, and are easily adaptable to systems for which semantical analysis is problematic.I am indebted to G. Boolos and to the referee for their valuable advice. The referee has suggested the rule GL of §3 below as an axiomatization of GL; the resulting sequential calculus has allowed a definite improvement of our original presentation.
Sequent-systems for modal logic
Authors: Došen Kosta 
Published: May 2006

AbstractThe purpose of this work is to present Gentzen-style formulations of S5 and S4 based on sequents of higher levels. Sequents of level 1 are like ordinary sequents, sequents of level 2 have collections of sequents of level 1 on the left and right of the turnstile, etc. Rules for modal constants involve sequents of level 2, whereas rules for customary logical constants of first-order logic with identity involve only sequents of level 1. A restriction on Thinning on the right of level 2, which when applied to Thinning on the right of level 1 produces intuitionistic out of classical logic (without changing anything else), produces S4 out of S5 (without changing anything else).This characterization of modal constants with sequents of level 2 is unique in the following sense. If constants which differ only graphically are given a formally identical characterization, they can be shown inter-replaceable (not only uniformly) with the original constants salva provability. Customary characterizations of modal constants with sequents of level 1, as well as characterizations in Hilbert-style axiomatizations, are not unique in this sense. This parallels the case with implication, which is not uniquely characterized in Hilbert-style axiomatizations, but can be uniquely characterized with sequents of level 1.These results bear upon theories of philosophical logic which attempt to characterize logical constants syntactically. They also provide an illustration of how alternative logics differ only in their structural rules, whereas their rules for logical constants are identical.
Partition properties of M-ultrafilters and ideals
Authors: Takahashi Joji 
Published: May 2006

As is well known, the following are equivalent for any uniform ultrafilter U on an uncountable cardinal:(i) U is selective;(ii) U → ;(iii) U → .In §1 of this paper, we consider this result in terms of M-ultrafilters (Definition 1.1), where M is a transitive model of ZFC (Zermelo-Fraenkel set theory with the axiom of choice). We define the partition properties and for M-ultrafilters (Definition 1.3), and characterize those M-ultrafilters that possess these properties (Theorem 1.5) so that the result mentioned at the beginning is subsumed as the special case that M is V, the universe of all sets. It turns out that the two properties have to be handled separately, and that, besides selectivity, we need to formulate additional conditions (Definition 1.4). The extra conditions become superfluous when M = V because they are then trivially satisfied. One of them is nothing new; it is none other than Kunen's iterability-of-ultrapowers condition.In §2, we obtain characterizations of the partition properties I+ → and I+ → (Definition 2.3) of uniform ideals I on an infinite cardinal κ (Theorem 2.6). This is done by applying the main results of §1 to the canonical -ultrafilter in the Boolean-valued model constructed from the completion of the quotient algebra P(κ)/I. They are related to certain known characterizations of weakly compact and of Ramsey cardinals.Our basic set theory is ZFC. In §1, it has to be supplemented by a new unary predicate symbol M and new nonlogical axioms that make M look like a transitive model of ZFC.
Polynomial size proofs of the propositional pigeonhole principle
Authors: Buss Samuel R. 
Published: May 2006

AbstractCook and Reckhow defined a propositional formulation of the pigeonhole principle. This paper shows that there are Frege proofs of this propositional pigeonhole principle of polynomial size. This together with a result of Haken gives another proof of Urquhart's theorem that Frege systems have an exponential speedup over resolution. We also discuss connections to provability in theories of bounded arithmetic.