bluuebunny/crossref_metadata_2025_split huggingface dataset:
Principal type-schemes and condensed detachment
Authors: Hindley J. Roger , Meredith David 
Published: May 2006

The condensed detachment rule, or ruleD, was first proposed by Carew Meredith in the 1950's for propositional logic based on implication. It is a combination of modus ponens with a “minimal” amount of substitution. We shall give a precise detailed statement of rule D. (Some attempts in the published literature to do this have been inaccurate.)The D-completeness question for a given set of logical axioms is whether every formula deducible from the axioms by modus ponens and substitution can be deduced instead by rule D alone. Under the well-known formulae-as-types correspondence between propositional logic and combinator-based type-theory, rule D turns out to correspond exactly to an algorithm for computing principal type-schemes in combinatory logic. Using this fact, we shall show that D is complete for intuitionistic and classical implicational logic. We shall also show that D is incomplete for two weaker systems, BCK- and BCI-logic.In describing the formulae-as-types correspondence it is common to say that combinators correspond to proofs in implicational logic. But if “proofs” means “proofs by the usual rules of modus ponens and substitution”, then this is not true. It only becomes true when we say “proofs by rule D”; we shall describe the precise correspondence in Corollary 6.7.1 below.This paper is written for readers in propositional logic and in combinatory logic. Since workers in one field may not feel totally happy in the other, we include short introductions to both fields.We wish to record thanks to Martin Bunder, Adrian Rezus and the referee for helpful comments and advice.
On the formalization of semantic conventions
Authors: Williams James G. 
Published: May 2006

AbstractThis paper discusses six formalization techniques, of varying strengths, for extending a formal system based on traditional mathematical logic. The purpose of these formalization techniques is to simulate the introduction of new syntactic constructs, along with associated semantics for them. We show that certain techniques (among the six) subsume others. To illustrate sharpness, we also consider a selection of constructs and show which techniques can and cannot be used to introduce them. The six studied techniques were selected on the basis of actual practice in logic and computing. They do not form an exhaustive list.
Subgroups of small index in infinite symmetric groups. II
Authors: Shelah Saharon , Thomas Simon 
Published: May 2006

Throughout this paper κ denotes an infinite cardinal, S = Sym(κ) and G is a subgroup of S. We shall be seeking the subgroups G with [S: G] < 2κ. In [2], the following result was proved.Theorem 1. If [S: G] ≤ κthen there exists a subset Δ of k such that ∣Δ∣ < k and S(Δ) ≤ G.Here S(Δ) = Sym(K/⊿) is the pointwise stabilizer of Δ in S.However, the converse of Theorem 1 is not true. For if cf(κ) ≤ ∣Δ∣ < κ, then [S: S(Δ)] ≥ κcf(κ) > κ. This suggests that a substantially sharpened version of Theorem 1 may be true.Question 1 [2]. Is it provable in ZFC, or even in ZFC with GCH, that if [S: G] ≤ κ then there is a subset Δ of κ such that ∣Δ∣ < cf(κ) and S(Δ) ≤ G?At least two of the authors of [2] made a serious attempt to answer the above question positively. In §3, we shall see that they were essentially trying to prove that measurable cardinals do not exist.The following result, due independently to Semmes [5] and Neumann [2], suggests a second way in which Theorem 1 might be improved.Theorem 2. If k = ℵ0andthen there is a finite subset Δ of k such thatS(Δ) ≤ G.Question 2 [2]. Is it provable in ZFC that if [S: G] < 2κ then there is a subset Δ of κ such that ∣Δ∣ < κ and S(Δ) < G?This question will be answered negatively in §4.
Generalizations of the one-dimensional version of the Kruskal-Friedman theorems
Authors: Gordeev L. 
Published: May 2006

The paper [Schütte + Simpson] deals with the following one-dimensional case of Friedman's extension (see in [Simpson 1]) of Kruskal's theorem ([Kruskal]). Given a natural number n, let Sn+1 be the set of all finite sequences of natural numbers <n + 1. If s1 = (a0,…,ak) ∈Sn+1 and s2 = (b0,…,bm) ∈Sn + 1, then a strictly monotone function f: {0,…, k} → {0,…, m} is called an embedding of s1 into s2 if the following two assertions are satisfied:1) ai, = bf(i), for all i < k;2) if f(i) < j < f(i + 1) then bj > bf(i+1), for all i < k, j < m.Then for every infinite sequence s1, s2,…,sk,… of elements of Sn + 1 there exist indices i < j and an embedding of si into Sj. That is, Sn+1 forms a well-quasi-ordering (wqo) with respect to embeddability. For each n, this statement W(Sn+1) is provable in the standard second order conservative extension of Peano arithmetic. On the other hand, the proof-theoretic strength of the statements W(Sn+1) grows so fast that this formal theory cannot prove the limit statement ∀nW(Sn+1). The appropriate first order -versions of these combinatory statements preserve their proof-theoretic strength, so that actually one can speak in terms of provability in Peano arithmetic. These are the main conclusions from [Schütte + Simpson].We wish to extend this into the transfinite. That is, we take an arbitrary countable ordinal τ > 0 instead of n + 1 and try to obtain an analogous “strong” combinatory statement about finite sequences of ordinals < τ.
Complementation in the Turing degrees
Authors: Slaman Theodore A. , Steel John R. 
Published: May 2006

AbstractPosner [6] has shown, by a nonuniform proof, that every degree has a complement below 0′. We show that a 1-generic complement for each set of degree between 0 and 0′ can be found uniformly. Moreover, the methods just as easily can be used to produce a complement whose jump has the degree of any real recursively enumerable in and above ∅′. In the second half of the paper, we show that the complementation of the degrees below 0′ does not extend to all recursively enumerable degrees. Namely, there is a pair of recursively enumerable degrees a above b such that no degree strictly below a joins b above a. (This result is independently due to S. B. Cooper.) We end with some open problems.
Model-theoretic properties characterizing Peano arithmetic
Authors: Kaye Richard 
Published: May 2006

AbstractLet= {0,1, +,·,<} be the usual first-order language of arithmetic. We show that Peano arithmetic is the least first-order-theory containingIΔ0+ exp such that every complete extensionTof it has a countable modelKsatisfying(i)Khas no proper elementary substructures, and(ii) wheneverL≻Kis a countable elementary extension there isandsuch that.Other model-theoretic conditions similar to (i) and (ii) are also discussed and shown to characterize Peano arithmetic.
Small stable groups and generics
Authors: Wagner Frank O. 
Published: May 2006

AbstractWe define an ℜ-group to be a stable group with the property that a generic element (for any definable transitive group action) can only be algebraic over a generic. We then derive some corollaries for ℜ-groups and fields, and prove a decomposition theorem and a field theorem. As a nonsuperstable example, we prove that small stable groups are ℜ-groups.
Stationary subsets of [ℵω]<ωn
Authors: Liu Kecheng 
Published: May 2006

AbstractIn this paper, assuming large cardinals, we prove the consistency of the following:Let n ∈ ω and k1, k2 ≤ n. Let f: ω → {k1, k2} be such that for all n1 < n2 ∈ f−1{k1},n2 − n1 ≥ 4. Then the setis stationary in The above is equivalent to the statement that for any structure on on ℵω, there is ≺ A such that ∣∣ = ωn and for all m > n, cf( ∩ ωm) = ωf(m).
A very discontinuous Borel function
Authors: Steprāns Juris 
Published: May 2006

AbstractIt is shown to be consistent that the reals are covered by ℵ1, meagre sets yet there is a Baire class 1 function which cannot be covered by fewer than ℵ2, continuous functions. A new cardinal invariant is introduced which corresponds to the least number of continuous functions required to cover a given function. This is characterized combinatorially. A forcing notion similar to, but not equivalent to, superperfect forcing is introduced.
The Bass-Milnor-Serre theorem for nonstandard models in Peano arithmetic
Authors: Khelif Anatole 
Published: May 2006

The aim of this paper is to extend the Bass-Milnor-Serre theorem to the nonstandard rings associated with nonstandard models of Peano arithmetic, in brief to Peano rings.First, we recall the classical setting. Let k be an algebraïc number field, and let θ be its ring of integers. Let n be an integer ≥ 3, and let G be the group Sln(θ) of (n, n) matrices of determinant 1 with coefficients in θ.The profinite topology in G is the topology having as fundamental system of open subgroups the subgroups of finite index.Congruence subgroups of finite index of G are the kernels of the maps Sln(θ) → Sln(θ/I) for which all ideals I of θ are of finite index. By taking these subgroups as a fundamental system of open subgroups, one obtains the congruence topology on G. Every open set for this topology is open in the profinite topology.We denote by Ḡ (resp., Ĝ) the completion of G for the congruence (resp., profinite) topology.The Bass-Milnor-Serre theorem [1] consists of the two following statements:(A) If k admits a real embedding, then we have an exact sequenceThat is, Ĝ and Ḡ are isomorphic.(B) If k is totally imaginary, then one has an exact sequencewhere μ(k)is the group of the roots of unity of k.
On a topological construction of Juhasz and Shelah
Authors: Velleman Dan 
Published: May 2006

In [2], Juhasz and Shelah use a forcing argument to show that it is consistent with GCH that there is a 0-dimensional T2 topological space X of cardinality ℵ3 such that every partition of the triples of X into countably many pieces has a nondiscrete (in the topology) homogeneous set. In this paper we will show how to construct such a space using a simplified (ω2, 1)-morass with certain additional structure added to it. The additional structure will be a slight strengthening of a built-in ◊ sequence, analogous to the strengthening of ordinary ◊k to ◊S for a stationary set S ⊆ k.Suppose 〈〈θα∣ ∝ ≤ ω2〉, 〈∝β∣α < β ≤ ω2〉〉 is a neat simplified (ω2, 1)-morass (see [3]). Let ℒ be a language with countably many symbols of all types, and suppose that for each α < ω2, α is an ℒ-structure with universe θα. The sequence 〈α∣α < ω2 is called a built-in ◊ sequence for the morass if for every ℒ-structure with universe ω3 there is some α < ω2 and some f ∈αω2 such that f(α) ≺ , where f(α) is the ℒ-structure isomorphic to α under the isomorphism f. We can strengthen this slightly by assuming that α is only defined for α ∈ S, for some stationary set S ⊆ ω2. We will then say that is a built-in ◊ sequence on levels in S if for every ℒ-structure with universe ω3 there is some α ∈ S and some f ∈ αω2 such that f(α) ≺ .
Torre models in the isols
Authors: Barback Joseph 
Published: May 2006

AbstractIn [14] J. Hirschfeld established the close connection of models of the true AE sentences of Peano Arithmetic and homomorphic images of the semiring of recursive functions. This fragment of Arithmetic includes most of the familiar results of classical number theory. There are two nice ways that such models appear in the isols. One way was introduced by A. Nerode in [20] and is referred to in the literature as Nerode Semirings. The other way is called a tame model. It is very similar to a Nerode Semiring and was introduced in [6]. The model theoretic properties of Nerode Semirings and tame models have been widely studied by T. G. McLaughlin ([16], [17], and [18]).In this paper we introduce a new variety of tame model called a torre model. It has as a generator an infinite regressive isol with a nice structural property relative to recursively enumerable sets and their extensions to the isols. What is then obtained is a nonstandard model in the isols of the fragment of Peano Arithmetic with the following property: Let T be a torre model. Let f be any recursive function, and let fΛ be its extension to the isols. If there is an isol A with fΛ(A) ϵ T, then there is also an isol B ϵ T with fΛ(B) = fΛ(A).
Strong ultrapowers and long core models
Authors: Cummings James 
Published: May 2006

In his paper [7] Steel asked whether there can exist a normal measure U on a cardinal κ such thatWe use Reverse Easton forcing to show that this is consistent from a P2κ hypermeasure; we also show that the result is sharp, using the core model for nonoverlapping coherent extender sequences.The proof uses forcing technology due to Woodin.In this section we collect some facts that are useful in the forcing constructions of the next section. None of them are due to us, and we are unsure to whom they should be attributed for the most part. We give sketchy proofs; the reader who wants to see more details is referred to [2].
Extending the Curry-Howard interpretation to linear, relevant and other resource logics
Authors: Gabbay Dov M. , de Queiroz Ruy J. G. B. 
Published: May 2006

The so-called Curry-Howard interpretation (Curry [1934], Curry and Feys [1958], Howard [1969], Tait [1965]) is known to provide a rather neat term-functional account of intuitionistic implication. Could one refine the interpretation to obtain an almost as good account of other neighbouring implications, including the so-called ‘resource’ implications (e.g. linear, relevant, etc.)?We answer this question positively by demonstrating that just by working with side conditions on the rule of assertability conditions for the connective representing implication (‘→’) one can characterise those ‘resource’ logics. The idea stems from the realisation that whereas the elimination rule for conditionals (of which implication is a particular case) remains virtually unchanged no matter what kind of conditional one has (i.e. linear, relevant, intuitionistic, classical, etc., all have modus ponens), the corresponding introduction rule carries an element of vagueness which can be explored in the characterisation of several sorts of conditionals. The rule of →-introduction is classified as an ‘improper’ inference rule, to use a terminology from Prawitz [1965]. Now, the so-called improper rules leave room for manoeuvre as to how a particular logic can be obtained just by imposing conditions on the discharge of assumptions that would correspond to the particular logical discipline one is adopting (linear, relevant, ticket entailment, intuitionistic, classical, etc.). The side conditions can be ‘naturally’ imposed, given that a degree of ‘vagueness’ is introduced by the presentation of those improper inference rules, such as the rule of →-introduction:which says: starting from assumption ‘A’, and arriving at ‘B’ via an unspecified number of steps, one can discharge the assumption and conclude that ‘A’ implies ‘B’.
The Härtig quantifier: a survey
Authors: Herre Heinrich , Krynicki Michał , Pinus Alexandr , Väänänen Jouko 
Published: May 2006

AbstractA fundamental notion in a large part of mathematics is the notion of equicardinality. The language with Härtig quantifier is, roughly speaking, a first-order language in which the notion of equicardinality is expressible. Thus this language, denoted byLI, is in some sense very natural and has in consequence special interest. Properties ofLIare studied in many papers. In [BF, Chapter VI] there is a short survey of some known results aboutLI. We feel that a more extensive exposition of these results is needed.The aim of this paper is to give an overview of the present knowledge about the languageLIand list a selection of open problems concerning it.After the Introduction (§1), in §§2 and 3 we give the fundamental results aboutLI. In §4 the known model-theoretic properties are discussed. The next section is devoted to properties of mathematical theories inLI. In §6 the spectra of sentences ofLIare discussed, and §7 is devoted to properties ofLIwhich depend on set-theoretic assumptions. The paper finishes with a list of open problem and an extensive bibliography. The bibliography contains not only papers we refer to but also all papers known to us containing results about the language with Härtig quantifier.Contents. §1. Introduction. §2. Preliminaries. §3. Basic results. §4. Model-theoretic properties ofLI. §5. Decidability of theories withI. §6. Spectra ofLI-sentences. §7. Independence results. §8. What is not yet known aboutLI. Bibliography.
Scott incomplete Boolean ultrapowers of the real line
Authors: Ozawa Masanao 
Published: May 2006

AbstractAn ordered field is said to be Scott complete iff it is complete with respect to its uniform structure. Zakon has asked whether nonstandard real lines are Scott complete. We prove in ZFC that for any complete Boolean algebra B which is not (ω, 2)-distributive there is an ultrafilter of B such that the Boolean ultrapower of the real line modulo is not Scott complete. We also show how forcing in set theory gives rise to examples of Boolean ultrapowers of the real line which are not Scott complete.
Requirement systems
Authors: Knight Julia F. 
Published: May 2006

Methods for carrying out transfinitely nested priority constructions have been developed by Harrington [7] and by Ash [2, 1, 3, 4]. Ash's method has different versions, with later ones becoming simpler. Lemmp and Lerman [11] have also developed a method, for finitely nested constructions. Ash formulated abstractly the object of a nested priority construction, and he proved a metatheorem for what he called “α-systems”, listing conditions which guarantee the success of the construction. Harrington's method of “workers”, at least in its original, informal state, seems more flexible than Ash's α-systems.In [10, 9], there are finite and transfinite versions of a metatheorem for workers. The statements are complicated, and these metatheorems have not proved to be very useful. The present paper gives a new transfinite metatheorem. The statement is considerably simpler than the one in [9], although not so simple as that in [3]. The new metatheorem grew, in part, out of an effort to find a new proof of Ash's metatheorem. The new metatheorem yields the one in [3], and it seems more flexible. A different generalization of Ash's metatheorem will be given in [5].Ash's metatheorem is easier to use than the one in the present paper, and the result in [3] is certainly the one to use wherever it applies. Here we give one application of the new metatheorem which does not seem to follow from the result in [3]. This is a theorem on models “representing” a given Scott set, which implies one half of a recent result of Solovay [18], on Turing degrees of models of particular completions of Peano arithmetic (PA).
Canonical seeds and Prikry trees
Authors: Hamkins Joel David 
Published: May 2006

AbstractApplying the seed concept to Prikry tree forcing ℙμ, I investigate how well ℙμ preserves the maximality property of ordinary Prikry forcing and prove that ℙμ, Prikry sequences are maximal exactly when μ admits no non-canonical seeds via a finite iteration. In particular, I conclude that if μ is a strongly normal supercompactness measure, then ℙμ Prikry sequences are maximal, thereby proving, for a large class of measures, a conjecture of W. Hugh Woodin's.
On the complexity of propositional quantification in intuitionistic logic
Authors: Kremer Philip 
Published: May 2006

AbstractWe define a propositionally quantified intuitionistic logic Hπ+ by a natural extension of Kripke's semantics for propositional intuitionistic logic. We then show that Hπ+ is recursively isomorphic to full second order classical logic. Hπ+ is the intuitionistic analogue of the modal systems S5π+, S4π+, S4.2π+, K4π+, Tπ+, Kπ+ and Bπ+, studied by Fine.
Finitary sketches
Authors: Adámek J. , Johnstone P. T. , Makowsky J. A. , Rosický J. 
Published: May 2006

AbstractFinitary sketches, i.e., sketches with finite-limit and finite-colimit specifications, are proved to be as strong as geometric sketches, i.e., sketches with finite-limit and arbitrary colimit specifications. Categories sketchable by such sketches are fully characterized in the infinitary first-order logic: they are axiomatizable by σ-coherent theories, i.e., basic theories using finite conjunctions, countable disjunctions, and finite quantifications. The latter result is absolute; the equivalence of geometric and finitary sketches requires (in fact, is equivalent to) the non-existence of measurable cardinals.
Compact bracket abstraction in combinatory logic
Authors: Broda Sabine , Damas Luís 
Published: May 2006

AbstractTranslations from Lambda calculi into combinatory logics can be used to avoid some implementational problems of the former systems. However, this scheme can only be efficient if the translation produces short output with a small number of combinators, in order to reduce the time and transient storage space spent during reduction of combinatory terms. In this paper we present a combinatory system and an abstraction algorithm, based on the original bracket abstraction operator of Schönfinkel [9]. The algorithm introduces at most one combinator for each abstraction in the initial Lambda term. This avoids explosive term growth during successive abstractions and makes the system suitable for practical applications. We prove the correctness of the algorithm and establish some relations between the combinatory system and the Lambda calculus.
A new deconstructive logic: linear logic
Authors: Danos Vincent , Joinet Jean-Baptiste , Schellinx Harold 
Published: May 2006

AbstractThe main concern of this paper is the design of a noetherian and confluent normalization for LK2 (that is, classical second order predicate logic presented as a sequent calculus).The method we present is powerful: since it allows us to recover as fragments formalisms as seemingly different as Girard's LC and Parigot's λμ, FD ([10, 12, 32, 36]), delineates other viable systems as well, and gives means to extend the Krivine/Leivant paradigm of ‘programming-with-proofs’ ([26, 27]) to classical logic; it is painless: since we reduce strong normalization and confluence to the same properties for linear logic (for non-additive proof nets, to be precise) using appropriate embeddings (so-called decorations); it is unifying: it organizes known solutions in a simple pattern that makes apparent the how and why of their making.A comparison of our method to that of embedding LK into LJ (intuitionistic sequent calculus) brings to the fore the latter's defects for these ‘deconstructive purposes’.
Lower bounds for resolution and cutting plane proofs and monotone computations
Authors: Pudlák Pavel 
Published: May 2006

AbstractWe prove an exponential lower bound on the length of cutting plane proofs. The proof uses an extension of a lower bound for monotone circuits to circuits which compute with real numbers and use nondecreasing functions as gates. The latter result is of independent interest, since, in particular, it implies an exponential lower bound for some arithmetic circuits.
Defining relevant implication in a propositionally quantified S4
Authors: Kremer Philip 
Published: May 2006

AbstractR. K. Meyer once gave precise form to the question of whether relevant implication can be defined in any modal system, and his answer was ‘no’. In the present paper, we extend S4, first with propositional quantifiers, to the system S4π+; and then with definite propositional descriptions, to the system S4π+ip. We show that relevant implication can in some sense be defined in the modal system S4π+ip, although it cannot be defined in S4π+.