bluuebunny/crossref_metadata_2025_split huggingface dataset:
On finite lattices of degrees of constructibility
Authors: Adamowicz Zofia 
Published: May 2006

We shall prove the following theorem:Theorem. For any finite lattice there is a model of ZF in which the partial ordering of the degrees of constructibility is isomorphic with the given lattice.Let M be a standard countable model of ZF satisfying V = L. Let K be the given finite lattice. We shall extend M by forcing.The paper is divided into two parts. The first part concerns the definition of the set of forcing conditions and some properties of this set expressible without the use of generic filters.We define first a representation of a lattice and then the set of conditions. In Lemmas 1, 2 we show that there are some canonical isomorphisms between some conditions and that a single condition has some canonical automorphisms.In Lemma 3 and Definition 7 we show some methods of defining conditions. We shall use those methods in the second part to define certain conditions with special properties.Lemma 4 gives a connection between the sets P and Pk (see Definitions 4 and 5). It is next employed in the second part in Lemma 10 in an essential way.Indeed, Lemma 10 is necessary for Lemma 13, which is the crucial point of the whole construction. Lemma 5 is also employed in Lemma 13 (exactly in its Corollary).The second part of the paper is devoted to the examination of the structure of degrees of constructibility in a generic model. First, we show that degrees of some “sections” of a generic real (Definition 9) form a lattice isomorphic with K. Secondly, we show that there are no other degrees in the generic model; this is the most difficult property to obtain by forcing. We prove, in two stages, that it holds in our generic models. We first show, by using special properties of the forcing conditions, that sets of ordinal numbers have no other degrees. Then we show that the degrees of sets of ordinals already determine the degrees of other sets.
A Δ02 theory of regressive isols
Authors: Ellentuck Erik 
Published: May 2006

AbstractWe examine the action of unary functions on the regressive isols. A manageable theory is produced and we find that such a function maps ⋀R into ⋀ if and only if it is eventually R↑ increasing and maps ⋀R into ⋀R if and only if it is eventually recursive increasing. Our paper concludes with a discussion of other methods for extending functions to ⋀R.
Intensional logic in extensional language
Authors: Parsons Charles 
Published: May 2006

Frege's conception of reference has been interpreted as calling for a completely extensional language, on the grounds that according to it the reference of a complex expression is a function of the references of its parts. To meet this demand and still allow for oblique contexts, one uses Frege's idea that in an oblique context an expression has as reference what is ordinarily its sense.A purely extensional formalized intensional logic was constructed in the 1940s by Alonzo Church: his logic of sense and denotation [2], [3]. The ambiguity of the “direct” and “oblique” reference of an expression is avoided. For each denoting expression A there is an expression A denoting its sense, which then replaces A in “oblique” contexts. A consequence of this approach is that for each natural number n, in a context with n-fold embedding of intensional operators A is paraphrased by the result of iterating the operation Ã n times, so that A is treated as if it were infinitely ambiguous. Church's underlying logic is a simple theory of types, in fact just an expansion of the extensional typed λ-calculus so as to contain ωth-order predicate logic.In this paper we study a variant of Church's logic that admits a possible-worlds semantics, i.e. a version of Church's Alternative (2) [3, pp. 4–5], [4]. This type of logic has been perspicuously formulated by David Kaplan [11], [12], and we follow his version.In §1 we formulate Kaplan's logic L-Church-O with two alterations: the typed λ-calculus is replaced by combinators, and unlike Kaplan (but like Church) we allow concepts (that is, senses) that are not concepts of anything.
A classification of jump operators
Authors: Steel John R. 
Published: May 2006

The structure (D, ≤) of the Turing degrees under Turing reducibility is quite complicated. This is true even if we restrict our attention to the substructure (R, ≤) of r.e. degrees. However, the theorems which imply that these structures are complicated all involve ad hoc constructions of sets having the desired reducibility relations. The complexity disappears when we turn to degrees occurring in nature. Of the degrees in R, only 0 and 0′ seem natural. In D, only 0, 0′, 0″, …, 0ω, 0ω+1, … (and on into the transfinite) seem natural. Thus the natural degrees appear to be wellordered, with successors given by Turing jump.If this is true, one would like to prove it. Of course the first problem is to make the concept of naturalness more precise. The following requirements seem plausible: a natural degree should be definable, its definition should relativise to an arbitrary degree, and this relativisation should preserve reducibility relations among natural degrees. Thus to each natural degree c is associated a definable fc: D → D so that fc(0) = c and ∀d(d ≤ fc(d)). Moreover, b ≤ c iff ∀d(fb(d) ≤, fc(d)). To be specific, let us take the definability of fc to mean that fc ∈ L(R).If P is a property of degrees, we say P holds almost everywhere (a.e.) iff ∃c∀d ≥: c P(d). For f, g: D → D, let f ≤mg iff f(d) ≤ g(d) a.e. Define f′ by f′(d) = f{d)′, and let M = {f: D → D/f ∈ L(R) ∧ d ≤ f(d) a.e.}. The following conjecture is due to D. A. Martin:Conjecture. M is prewellordered by ≤m. If f ∈ M has rank α in ≤m, then f′ has rank α + 1.
La logique des topos
Authors: Boileau André , Joyal André 
Published: May 2006

Les synthèses nouvelles par le rapprochement de disciplines mathématiques différentes constituent des événements remarquables dans l'histoire des mathématiques. Une telle synthèse semble émerger actuellement du rapprochement de:(1) La géométrie algébrique sous la forme élaborée par Grothendieck.(2) La logique formelle.Le point de contact s'est effectué aux environs de 1970 par W. Lawvere et M. Tierney et l'instrument de rapprochement a été la théorie des catégories, plus particulièrement la théorie des faisceaux. Depuis ce moment, une dialectique incessante imprime un mouvement dynamique à toute une série de recherches qui visent à rapprocher les méthodes suivantes:(1) Mathématique intuitionniste.(2) Forcing de Cohen et Robinson.(3) Logique algébrique.(4) Géométrie algébrique.(5) Géométrie différentielle et analytique.(6) Topologie algébrique: cohomologie, homotopie.(7) Théorie de Galois.Certains rapprochements sont dans un stade avancé, d'autres encore embryonnaires: (6) ↔ (3).La structure centrale qui joue le rôle d'élément provocateur et unificateur est celle de topos. Avant d'être axiomatisée par Lawvere, celle-ci a été étudiée systématiquement par l'école de Grothendieck (voir [1]) et c'est dans le contexte de la géométrie algébrique qu'elle fit son apparition. Dans cet article nous utiliserons cependant la définition de Lawvere telle qu'améliorée par Mikkelsen [12] et Kock [8].Le but de ce travail est de présenter une version (au sens de la logique formelle) du concept de topos et d'examiner brièvement les rapports entre la théorie des topos, la logique et les mathématiques. Cette version a déjà été exposée par l'un des auteurs lors du Séminaire de Mathématiques Supérieures de l'Université de Montréal, à l'été 1974. Depuis elle a fait l'objet d'une thèse où elle a été améliorée et sa cohérence vérifiée [2]. Des systèmes différents ont été proposés simultanément par Fourman [4] et Coste [3].
On amalgamations of languages with Magidor-Malitz quantifiers
Authors: Morgenstern Carl F. 
Published: May 2006

In this paper we indicate how compact languages containing the Magidor-Malitz quantifiers Qκn in different cardinalities can be amalgamated to yield more expressive, compact languages.The language Lκ<ω, originally introduced by Magidor and Malitz [9], is a natural extension of the language L(Q) introduced by Mostowski and investigated by Fuhrken [6], [7], Keisler [8] and Vaught [13]. Intuitively, Lκ<ω is first-order logic together with quantifiers Qκn (n ∈ ω) binding n free variables which express “there is a set X of cardinality κ such than any n distinct elements of X satisfy …”, or in other words, iff the relation on determined by φ contains an n-cube of cardinality κ. With these languages one can express a variety of combinatorial statements of the type considered by Erdös and his colleagues, as well as concepts in universal algebra which are beyond the scope of first-order logic. The model theory of Lκ<ω has been further developed by Badger [1], Magidor and Malitz [10] and Shelah [12].We refer to a language as being < κ compact if, given any set of sentences Σ of the language, if Σ is finitely satisfiable and ∣Σ∣ < κ, then Σ has a model. The phrase countably compact is used in place of <ℵ1 compact.
Antitheses in systems of relevant implication
Authors: Porte Jean 
Published: May 2006

There are several ways for a formula to be “the contrary” of a thesis. When there is a negation we could call a formula an “antithesis” if it is the negation of a thesis—or its negation is a thesis—both properties being equivalent when the negation is classical.When there is no negation or when the connective called “negation” is very different from classical negation, we are forced to look for a different notion.Whence:Definition 1. In a propositional calculus, a substitution antithesis—or, for short, an s-antithesis—is a formula no instance of which is a thesis.There is another kindred notion, but only for calculi for which a deducibility has been defined:Definition 2. A deduction antithesis—for short, a d-antithesis—is a formula from which every formula is deducible.Both notions have been used in the study of the deducibility of certain systems (see below, §4).In the classical propositional calculus, the s-antitheses are simply the formulas which are negations of theses (and whose negations are theses).In S5 and in all the weaker modal propositional calculi, there are s-antitheses which are not negations of theses (and whose negations are not theses); typical examples are ¬(Mp ⊃ Lp) and ¬(p ⊃ Lp) where p is a propositional variable, and ⊃, ¬, M and L are respectively material implication, negation, possibility and necessity (see [8]).
A consistent combinatory logic with an inverse to equality
Authors: Fitch Frederic B. 
Published: May 2006

In a previous paper [9] a demonstrably consistent type-free system of combinatory logic CΔ was presented. This system contained a moderately strong exten-sionality principle, the usual equations of combinatory logic, Boolean propositional connectives, unrestricted quantifiers, an unrestricted abstraction principle (“comprehension axiom”), and a limited principle of excluded middle. It also contained elementary arithmetic in its entirety, avoiding arithmetical Gödel incompleteness [14] by being ω-complete. CΔ probably can be shown to contain certain important parts of mathematical analysis, such as the theory of continuous functions, which are contained by the somewhat similar (but nonextensional) system K′ [6], [7]. A stronger system CΓ, having these same properties and more, will be formulated in the present paper. Elsewhere [13] it will be shown that the system Q of my book, Elements of combinatory logic (Yale University Press, New Haven and London, 1974), referred to below as ECL, is essentially a subsystem of CΓ, so that the consistency of CΓ guarantees that of Q.CΓ will be stronger than both CΔ and Q in having an operator ‘ɿ’ (inverted Greek iota) which denotes the inverse of equality in the sense that ‘ɿ(= a) = a’ is a theorem of the system. Thus ‘ɿ’ denotes a function or operator which operates on a unit class to give the only member of that class. (Here ‘=a’ denotes the unit class whose only member is denoted by ‘a’.) If uninverted Greek iota, ‘ι’, is used as an abbreviation for ‘=’, the above equation could be written as ‘ɿ(ιa) = a’. Here ‘ιa’ is analogous to Bertrand Russell's well-known notation ‘ιa’, denoting a unit class. This same operator ‘ɿ’ makes it possible to transform one-many or many-one relations into the corresponding functions or operators, a kind of transformation not usually available in systems of combinatory logic [1], [2]. It also provides a method for restricting functions by restricting the corresponding relations.
Classifying positive equivalence relations
Authors: Bernardi Claudio , Sorbi Andrea 
Published: May 2006

AbstractGiven two (positive) equivalence relations ~1, ~2 on the set ω of natural numbers, we say that ~1 is m-reducible to ~2 if there exists a total recursive function h such that for every x, y ∈ ω, we have x ~1y iff hx ~2hy. We prove that the equivalence relation induced in ω by a positive precomplete numeration is complete with respect to this reducibility (and, moreover, a “uniformity property” holds). This result allows us to state a classification theorem for positive equivalence relations (Theorem 2). We show that there exist nonisomorphic positive equivalence relations which are complete with respect to the above reducibility; in particular, we discuss the provable equivalence of a strong enough theory: this relation is complete with respect to reducibility but it does not correspond to a precomplete numeration.From this fact we deduce that an equivalence relation on ω can be strongly represented by a formula (see Definition 8) iff it is positive. At last, we interpret the situation from a topological point of view. Among other things, we generalize a result of Visser by showing that the topological space corresponding to a partition in e.i. sets is irreducible and we prove that the set of equivalence classes of true sentences is dense in the Lindenbaum algebra of the theory.
Degrees of recursively enumerable topological spaces
Authors: Kalantari Iraj , Remmel J. B. 
Published: May 2006

In [5], Metakides and Nerode introduced the study of recursively enumerable (r.e.) substructures of a recursively presented structure. The main line of study presented in [5] is to examine the effective content of certain algebraic structures. In [6], Metakides and Nerode studied the lattice of r.e. subspaces of a recursively presented vector space. This lattice was later studied by Kalantari, Remmel, Retzlaff and Shore. Similar studies have been done by Metakides and Nerode [7] for algebraically closed fields, by Remmel [10] for Boolean algebras and by Metakides and Remmel [8] and [9] for orderings. Kalantari and Retzlaff [4] introduced and studied the lattice of r.e. subsets of a recursively presented topological space. Kalantari and Retzlaff consideredX, a topological space with ⊿, a countable basis. This basis is coded into integers and with the help of this coding, r.e. subsets ofωgive rise to r.e. subsets ofX. The notion of “recursiveness” of a topological space is the natural next step which gives rise to the question of what should be the “degree” of an r.e. open subset ofX? It turns out that any r.e. open set partitions ⊿; into four sets whose Turing degrees become central in answering the question raised above.In this paper we show that the degrees of the elements of the partition of ⊿ imposed by an r.e. open set can be “controlled independently” in a sense to be made precise in the body of the paper. In [4], Kalantari and Retzlaff showed that givenAany r.e. set andany r.e. open subset ofX, there exists an r.e. open set ℋ which is a subset ofand is dense in(in a topological sense) and in whichAis coded. This shows that modulo a nowhere dense set, an r.e. open set can become as complicated as desired. After giving the general technical and notational machinery in §1, and giving the particulars of our needs in §2, in §3 we prove that the set ℋ described above could be made to be precisely of degree ofA. We then go on and establish various results (both existential and universal) on the mentioned partitioning of ⊿. One of the surprising results is that there are r.e. open sets such that every element of partitioning of ⊿ is of a different degree. Since the exact wording of the results uses the technical definitions of these partitioning elements, we do not summarize the results here and ask the reader to examine §3 after browsing through §§1 and 2.
Prime and atomic models
Authors: Knight Julia F. 
Published: May 2006

This paper gives some simple existence results on prime and atomic models over sets. It also contains an example in which there is no prime model over a certain set even though there is an atomic model over the set. The existence results are “local” in that they deal with just one set rather than all sets contained in models of some theory. For contrast, see the “global” results in [6] or [7, p. 200].Throughout the paper, L is a countable language, and T is a complete L-theory with infinite models. There is a “large” model of T that contains the set X and any other sets and models to be used in a particular construction of a prime or atomic model over X.A model is said to be prime over X if and every elementary monomorphism on X can be extended to an elementary embedding on all of . This notion is used in a variety of ways in model theory. It aids in distinguishing between models that are not isomorphic, as in Vaught [10]. It also aids in showing that certain models are isomorphic, as in Baldwin and Lachlan [1].
Σ1-compactness in languages stronger than
Authors: Cutland Nigel 
Published: May 2006

One of the main results of Barwise [2] (see also [7, Chapter VIII]) showed that the s – reflection principle for a set A is equivalent to Σ1-compactness of . Here A is any transitive p.r. closed set, and is the infinitary language on A which allows conjunction and disjunction over arbitrary sets Φ Є A, and finite quantification.In this paper we consider languages , where B is a Δ0 subset of A, which is like but we allow quantifiers ∀x and ∃x where x is any set of variables indexed by an element of B. A treatment similar to that of [2] for establishes a sufficient, and in some cases necessary, condition for to be Σ1-compact. The use of infinitary Skolem functions is intrinsic to the method, so to avoid a separate development of the rudiments of the Skolem language we actually define to have b-ary relation and function symbols for every b Є B.
More about uniform upper bounds on ideals of turing degrees
Authors: Hodes Harold T. 
Published: May 2006

AbstractLet I be a countable jump ideal in = 〈The Turing degrees, ≤〉. The central theorem of this paper is:a is a uniform upper bound on I iff a computes the join of an I-exact pair whose double jump a(1) computes.We may replace “the join of an I-exact pair” in the above theorem by “a weak uniform upper bound on I”.We also answer two minimality questions: the class of uniform upper bounds on I never has a minimal member; if ⋃I = Lα[A] ⋂ ωω for α admissible or a limit of admissibles, the same holds for nice uniform upper bounds.The central technique used in proving these theorems consists in this: by trial and error construct a generic sequence approximating the desired object; simultaneously settle definitely on finite pieces of that object; make sure that the guessing settles down to the object determined by the limit of these finite pieces.
A filter lambda model and the completeness of type assignment
Authors: Barendregt Henk , Coppo Mario , Dezani-Ciancaglini Mariangiola 
Published: May 2006

In [6, p. 317] Curry described a formal system assigning types to terms of the type-free λ-calculus. In [11] Scott gave a natural semantics for this type assignment and asked whether a completeness result holds.Inspired by [4] and [5] we extend the syntax and semantics of the Curry types in such a way that filters in the resulting type structure form a domain in the sense of Scott [12]. We will show that it is possible to turn the domain of types into a λ-model, among other reasons because all λ-terms possess a type. This model gives the completeness result for the extended system. By a conservativity result the completeness for Curry's system follows.Independently Hindley [8], [9] has proved both completeness results using term models. His method of proof is in some sense dual to ours.For λ-calculus notation see [1].
Modal analysis of generalized rosser sentences
Authors: Švejdar Vítězslav 
Published: May 2006

AbstractA modal theory Z using the Guaspari witness comparison signs ≤, < is developed. The theory Z is similar to, but weaker than, the theory R of Guaspari and Solovay. Nevertheless, Z proves the independence of the Rosser fixed-point. A Kripke semantics for Z is presented and some arithmetical interpretations of Z are investigated. Then Z is enriched to ZI by adding a new modality sign for interpretability and by axioms expressing some facts about interpretability of theories. Two arithmetical interpretations of ZI are presented. The proofs of the validity of the axioms of ZI in arithmetical interpretations use some strengthening of Solovay's result about interpretability in Gödel-Bernays set theory.
Random models and the Gödel case of the decision problem
Authors: Gurevich Yuri , Shelah Saharon 
Published: May 2006

AbstractIn a paper of 1933 Gödel proved that every satisfiable first-order ∀2∃* sentence has a finite model. Actually he constructed a finite model in an ingenious and sophisticated way. In this paper we use a simple and straightforward probabilistic argument to establish existence of a finite model of an arbitrary satisfiable ∀2∃* sentence.
The relative efficiency of propositional proof systems
Authors: Cook Stephen A. , Reckhow Robert A. 
Published: May 2006

We are interested in studying the length of the shortest proof of a propositional tautology in various proof systems as a function of the length of the tautology. The smallest upper bound known for this function is exponential, no matter what the proof system. A question we would like to answer (but have not been able to) is whether this function has a polynomial bound for some proof system. (This question is motivated below.) Our results here are relative results.In §§2 and 3 we indicate that all standard Hilbert type systems (or Frege systems, as we call them) and natural deduction systems are equivalent, up to application of a polynomial, as far as minimum proof length goes. In §4 we introduce extended Frege systems, which allow introduction of abbreviations for formulas. Since these abbreviations can be iterated, they eliminate the need for a possible exponential growth in formula length in a proof, as is illustrated by an example (the pigeonhole principle). In fact, Theorem 4.6 (which is a variation of a theorem of Statman) states that with a penalty of at most a linear increase in the number of lines of a proof in an extended Frege system, no line in the proof need be more than a constant times the length of the formula proved.
Failures of the interpolation lemma in quantified modal logic
Authors: Fine Kit 
Published: May 2006

Beth's Definability Theorem, and consequently the Interpolation Lemma, fail for the version of quantified S5 that is presented in Kripke's [6]. These failures persist when the constant domain axiom-scheme ∀x□φ ≡ □∀xφ is added to S5 or, indeed, to any weaker extension of quantificational K.§1 reviews some standard material on quantificational modal logic. This is in contrast to quantified intermediate logics for, as Gabbay [6] has shown, the Interpolation Lemma holds for the logic CD with constant domains and for several of its extensions. §§2—4 establish the negative results for the systems based upon S5. §5 establishes a more general negative result and, finally, §6 considers some positive results and open problems. A basic knowledge of classical and modal quantificational logic is presupposed.Let me briefly review the relevant model theory for quantified modal logic. Further details can be found in [3] or [7].The language is obtained from the language for classical first-order logic with identity by adding a unary operator □ for necessity. The atomic formula ‘Ex’ is used as an abbreviation for ‘∃y(y = x)’ and may be read as ‘x exists’.