bluuebunny/crossref_metadata_2025_split huggingface dataset:
On a question of G. E. Sacks
Authors: Ohashi Kempachiro 
Published: May 2006

In [1], Sacks points out that there is one fundamental question: which true statements of ordinary recursion theory remain true when appropriately extended to metarecursion theory?A particular interest is taken in the question [1]:Q6. How does one define the jump operator for metarecursion theory? (A satisfactory definition should have the property that if A is metarecursive in B, then the jump of A is metarecursive in the jump of B.)In [2], Kreisel and Sacks give some definitions of predicates and functions analogous to those of Kleene as follows:The T-predicate of [2] is analogous to that of Kleene [3]. Its definition iswhere e is the Gödel number of a finite system of equations E and t(e, s) is a special metarecursive function which indexes “deductions” from E.U(e, s) is a metarecursive function such that if t(e, s) = 〈e, M, N, x, y〉, then U(e,s) = y.Two partial functions {e}s and {e} areThen e is intrinsically consistent if for all x, s1 and s2, if t(e, S1) = 〈e, M1N1, x, y1〉, t(e, s2) = 〈e, M2, N2, x, y2〉 and (M1 ∪ M2) ∩ (N1 ∪ N2) = ∅, then y1 = y2.
A weak completeness theorem for infinite valued first-order logic
Authors: Belluce L. P. , Chang C. C. 
Published: May 2006

This paper contains some results concerning the completeness of a first-order system of infinite valued logicThere are under consideration two distinct notions of completeness corresponding to the two notions of validity (see Definition 3) and strong validity (see Definition 4). Both notions of validity, whether based on the unit interval [0, 1] or based on linearly ordered MV-algebras, use the element 1 as the designated truth value. Originally, it was thought by many investigators in the field that one should be able to prove that the set of valid sentences is recursively enumerable. It was first proved by Rutledge in [9] that the set of valid sentences in the monadic first-order infinite valued logic is recursively enumerable.
A note on modified abstraction principles
Authors: Lake John 
Published: May 2006

The abstraction principle isfor K any formula not involving x. This is well known to be inconsistent and in [1] Hintikka proposed two modified versions of (0) which we briefly describe. First, he suggestedwhere K is any formula not involving x, and K+ is obtained from K by replacing subformulae of the form ∃zL by ∃z(z ≠ x ∧ L) and those of the form ∀zL by ∀z(z ≠ x → L), etc. The second version iswhere K+ is a formula of the type described for (1) and z1 …, zk are all the free variables in (2).
Note on an induction axiom
Authors: Paris J. B. 
Published: May 2006

Let θ(ν) be a formula in the first-order language of arithmetic and letIn this note we study the relationship between the schemas I′ and I+.Our interest in I+ lies in the fact that it is ostensibly a more reasonable schema than I′. For, if we believe the hypothesis of I+(θ) then to verify θ(n) only requires at most 2log2(n) steps, whereas assuming the hypothesis of I′(θ) we require n steps to verify θ(n). In the physical world naturally occurring numbers n rarely exceed 10100. For such n applying 2log2(n) steps is quite feasible whereas applying n steps may well not be.Of course this is very much an anthropomorphic argument so we would expect that it would be most likely to be valid when we restrict our attention to relatively simple formulas θ. We shall show that when restricted to open formulas I+ does not imply I′ but that this fails for the classes Σn, Πn, n ≥ 0.We shall work in PA−, where PA− consists of Peano's Axioms less induction together with∀u, w(u + w = w + u ∧ u · w = w · u),∀u, w, t ((u + w) + t = u + (w + t) ∧ (u · w) · t = u · (w · t)),∀u, w, t(u · (w + t) = u · w + u · t),∀u, w(u ≤ w ↔ ∃t(u + t = w)),∀u, w(u ≤ w ∨ w ≤ u),∀u, w, t(u + w = u + t → w = t).The reasons for working with PA− rather than Peano's Axioms less induction is that our additional axioms, whilst intuitively reasonable, will not necessarily follow from some of the weaker forms of I+ which we shall be considering. Of course PA− still contains those Peano Axioms which define + andNotice that, trivially, PA− ⊦ I′(θ) → I+(θ) for any formula θ.
Undecidable properties of finite sets of equations
Authors: McNulty George F. 
Published: May 2006

Though equations are among the simplest sentences available in a first order language, many of the most familiar notions from algebra can be expressed by sets of equations. It is the task of this paper to expose techniques and theorems that can be used to establish that many collections of finite sets of equations characterized by common algebraic or logical properties fail to be recursive. The following theorem is typical.Theorem. In a language provided with an operation symbol of rank at least two, the collection of finite irredundant sets of equations is not recursive.Theorems of this kind are part of a pattern of research into decision problems in equational logic. This pattern finds its origins in the works of Markov [8] and Post [20] and in Tarski's development of the theory of relation algebras; see Chin [1], Chin and Tarski [2], and Tarski [23]. The papers of Mal′cev [7] and Perkins [16] are more directly connected with the present paper, which includes generalization of much of Perkins' work as well as extensions of a theorem of D. Smith [22]. V. L. Murskii [14] contains some of the results below discovered independently. Not all known results concerning undecidable properties of finite sets of equations seem to be susceptible to the methods presented here. R. McKenzie, for example, shows in [9] that for a language with an operation symbol of rank at least two, the collection of finite sets of equations with nontrivial finite models is not recursive. D. Pigozzi has extended and elaborated the techniques of this paper in [17], [18], and [19] to obtain new results concerning undecidable properties, particularly those of algebraic character.
On the first-order logic of terms
Authors: Svenonius Lars 
Published: May 2006

By an elementary condition in the variablesx1, …, xn, we mean a conjunction of the form x1 ≤ i < j ≤ naij where each aij is one of the formulas xi = xj or xi ≠ xj. (We should add that the formula x1 = x1 should be regarded as an elementary condition in the one variable x1.)Clearly, according to this definition, some elementary conditions are inconsistent, some are consistent. For instance (in the variables x1, x2, x3) the conjunction x1 = x2 & x1 = x3 & x2 ≠ x3 is inconsistent.By an elementary combinatorial function (ex. function) we mean any function which can be given a definition of the formwhere E1(x1, …, xn), …, Ek(x1, …, xn) is an enumeration of all consistent elementary conditions in x1, …, xn, and all the numbers d1, …, dk are among 1, …, n.Examples. (1) The identity function is the only 1-ary e.c. function.(2) A useful 3-ary e.c. function will be called J. The definition is
Compactness and transfer for a fragment of L2
Authors: Magidor M. , Malitz J. 
Published: May 2006

The language Ln is obtained from the first order predicate calculus by adjoining the quantifier Qn which binds n variables. The formula Qnυ1 … υnΨ is given a κ-interpretation for each infinite cardinal κ, namely, “there is a set X of power κ such that Ψx1 … xn holds for all distinct x1 … xn ϵ X”. L<ω is the result of adjoining all the Qn quantifiers for each n ϵ ω to the first order predicate calculus.In [4] we showed that under the assumption (cf. [3]) L<ω is countably compact under the ω1-interpretation, and that any sentence σ ϵ L<ω that has a model in some κ-interpretation where κ is a regular infinite cardinal has a model in the ω1 interpretation. However, compactness for L<ω in the κ-interpretation for κ an infinite successor cardinal other than ω1 and the transfer of satisfiability from ω1 to any higher power remain open questions under any set theoretic assumptions.Here we restrict our attention to a small fragment L2− of L2 consisting of universal first order formulas along with formulas of the kind Q2υ1υ2∀υ3 … υnΨ and ¬Q2υ1υ2∀υ3 … υnφ where Ψ and φ are open and no function symbol of arity > 1 occurs in any formula. Assuming the existence of a κ-Souslin tree, this language is λ compact in the κ-interpretation when λ < κ.
Craig interpolation theorem for intuitionistic logic and extensions Part III
Authors: Gabbay Dov M. 
Published: May 2006

This is a continuation of two previous papers by the same title [2] and examines mainly the interpolation property for the logic CD with constant domains, i.e., the extension of the intuitionistic predicate logic with the schemaIt is known [3], [4] that this logic is complete for the class of all Kripke structures with constant domains.Theorem 47. The strong Robinson consistency theorem is not true for CD.Proof. Consider the following Kripke structure with constant domains. The set S of possible worlds is ω0, the set of positive integers. R is the natural ordering ≤. Let ω0 0 = , Bn, is a sequence of pairwise disjoint infinite sets. Let L0 be a language with the unary predicates P, P1 and consider the
following extensions for P,P1 at the world m.(a) P is true on ⋃i≤2nBi, and P1 is true on ⋃i≤2n+1Bi for m = 2n.(b) P is true on ⋃i≤2nBi, and P1 for ⋃i≤2n+1Bi for m = 2n.Let (Δ,Θ) be the complete theory of this structure. Consider another unary predicate Q. Let L be the language with P, Q and let M be the language with P1, Q.
A lattice of interpretability types of theories
Authors: Mycielski Jan 
Published: May 2006

We consider first-order logic only. A theory S will be called locally interpretable in a theory T if every theorem of S is interpretable in T. If S is locally interpretable in T and T is consistent then S is consistent. Most known relative consistency proofs can be viewed as local interpretations. The classic examples are the cartesian interpretation of the elementary theorems of Euclidean n-dimensional geometry into the first-order theory of real closed fields, the interpretation of the arithmetic of integers (rational numbers) into the arithmetic of positive integers, the interpretation of ZF + (V = L) into ZF, the interpretation of analysis into ZFC, relative consistency proofs by forcing, etc. Those interpretations are global. Under fairly general conditions local interpretability implies global interpretability; see Remarks (7), (8), and (9) below.We define the type (interpretability type) of a theory S to be the class of all theories T such that S is locally interpretable in T and vice versa. There happen to be such types and they are partially ordered by the relation of local interpretability. This partial ordering is of lattice type and has the following form:The lattice is distributive and complete and satisfies the infinite distributivity law of Brouwerian lattices:We do not know if the dual lawis true. We will show that the lattice is algebraic and that its compact elements form a sublattice and are precisely the types of finitely axiomatizable theories, and several other facts.
Semi-minimal theories and categoricity
Authors: Andler Daniel 
Published: May 2006

The study of countable theories categorical in some uncountable power was initiated by Łoś and Vaught and developed in two stages. First, Morley proved (1962) that a countable theory categorical in some uncountable power is categorical in every uncountable power, a conjecture of Łoś. Second, Baldwin and Lachlan confirmed (1969) Vaught's conjecture that a countable theory categorical in some uncountable power has either one or countably many isomorphism types of countable models. That result was obtained by pursuing a line of research developed by Marsh (1966). For certain well-behaved theories, which he called strongly minimal, Marsh's method yielded a simple proof of Łoś's conjecture and settled Vaught's conjecture.In recent years efforts have been made to extend these results to uncountable theories. The generalized Łoś conjecture states that a theory T categorical in some power greater than ∣T∣ is categorical in every such power. It was settled by Shelah (1970). Shelah then raised the question of the models in power ∣T∣ = ℵα of a theory T categorical in ∣T∣+, conjecturing in [S3] that there are exactly ∣α∣ + ℵ0 such models, up to isomorphism. This conjecture provided the initial motivation for the present work. We define and study semi-minimal theories analogous in some ways to Marsh's strongly minimal (countable) theories. We describe the models of a semi-minimal theory T which contain an infinite indiscernible set. Besides throwing some light on Shelah's conjecture, our method gives simple proofs of the Łoś conjecture and of the Morley conjecture on categoricity in ∣T∣, in the case of a semi-minimal theory T. Other results as well as some examples are provided.
On characterizing Spector classes
Authors: Harrington Leo A. , Kechris Alexander. S. 
Published: May 2006

We study in this paper characterizations of various interesting classes of relations arising in recursion theory. We first determine which Spector classes on the structure of arithmetic arise from recursion in normal type 2 objects, giving a partial answer to a problem raised by Moschovakis [8], where the notion of Spector class was first essentially introduced. Our result here was independently discovered by S. G. Simpson (see [3]). We conclude our study of Spector classes by examining two simple relations between them and a natural hierarchy to which they give rise.The second part of our paper is concerned with finding structural characterizations of classes of relations on the reals in the spirit of Moschovakis [7]. Our main result provides a single abstract characterization for the class of relations on the reals and the 2-envelope of 3E, the first one being valid if projective determinacy is true, the second if V = L is true.
Omitting models
Authors: Snapper Ernest 
Published: May 2006

The purpose of this paper is to introduce the notion of “omitting models” and to derive a very natural theorem concerning it (Theorem 1). A corollary of this theorem is the remarkable theorem of Vaught [3] which states that a countable complete theory cannot have precisely two nonisomorphic countable models. In fact, we show that our theorem implies Rosenstein's theorem [2] which, in turn, implies Vaught's theorem.T stands for a countable complete theory whose (countable) language is denoted by L. Following [1], a countably homogeneous model of T is a countable model of T with the property that, for any two n-tuples a1, …, an and b1,…,bn of the universe of whose types are the same, there is an automorphism of which maps ai, on bi, for i = 1, …, n [1, p. 129 and Proposition 3.2.9, p. 131]. “Homogeneous model” always means “countably homogeneous model.” “Type of T” always stands for “n-type of T” where n ≥ s 0, i.e., for the type of some n-tuple of individuals of the universe of some model of T. We often use that two homogeneous models which realize the same types are isomorphic [1, Proposition 3.2.9, p. 131].It is well known that every type of T is realized by at least one countable model of T. The main definition of this paper is:Definition 1. A set of countable models of T is omissible or “may be omitted” if every type of T is realized by at least one countable model of T which is not isomorphic to a model in the set.The main theorem of the paper is:Theorem 1. If a countable complete theory is not ω-categorical, every finite set of its homogeneous models may be omitted.The theorem is proved in §1 and in §2 it is shown how Vaught's and Rosenstein's theorems follow from it. §3 discusses some general aspects of omitting models.
Primitive recursive ordinal functions with added constants
Authors: Stahl Stanley H. 
Published: May 2006

One of the basic differences between the primitive recursive functions on the natural numbers and the primitive recursive ordinal functions (PR) is the nearly complete absence of constant functions in PR. Since ω is closed under all of the functions in PR, if α is any infinite ordinal, then λξ·α is not in PR. It is easily seen, however, that if one adds to the initial functions of PR the constant function λξ·ω, then all of the ordinals up to ω#, the next largest PR-closed ordinal, have their constant functions in this class. Since, however, such collections of functions are always countable, it is also the case that if one adds to the initial functions of PR the function λξ. α for uncountable α, then there are ordinals β < α whose constant functions are not in this collection. Because of this, the following objects are of interest:Definition. For all α,(i)PR(α) is the collection of functions obtained by adding to the initial primitive recursive ordinal functions, the function λξ· α;(ii) PRsp(α), the primitive recursive spectrum of α, is the set {β < α ∣ λξβ ∈ PR(α);(iii) Λ (α)= μρ(ρ∉ PRsp(α)).
Logics containing K4. Part I
Authors: Fine Kit 
Published: May 2006

There are two main lacunae in recent work on modal logic: a lack of general results and a lack of negative results. This or that logic is shown to have such and such a desirable property, but very little is known about the scope or bounds of the property. Thus there are numerous particular results on completeness, decidability, finite model property, compactness, etc., but very few general or negative results.In these papers I hope to help fill these lacunae. This first part contains a very general completeness result. Let In be the axiom that says there are at most n incomparable points related to a given point. Then the result is that any logic containing K4 and In is complete.The first three sections provide background material for the rest of the papers. The fourth section shows that certain models contain no infinite ascending chains, and the fifth section shows how certain elements can be dropped from the canonical model. The sixth section brings the previous results together to establish completeness, and the seventh and last section establishes compactness, though of a weak kind. All of the results apply to the corresponding intermediate logics.
Sets constructible from sequences of ultrafilters
Authors: Mitchell William J. 
Published: May 2006

In [4], Kunen used iterated ultrapowers to show that ifUis a normalκ-complete nontrivial ultrafilter on a cardinalκthenL[U], the class of sets constructive fromU, has only the ultrafilterU∩L[U] and this ultrafilter depends only onκ. In this paper we extend Kunen's methods to arbitrary sequencesUof ultrafilters (provided that they fulfill a coherency condition) and obtain generalizations of these results (§3). In particular we answer Problem 1 of Kunen and Paris [5] which asks whether the number of ultrafilters onκcan be intermediate between 1 and 22κ. If there is a normalκ-complete ultrafilterUonκsuch that {α <κ: α is measurable} ∈Uthen there is an inner model with exactly two normal ultrafilters onκ, and ifκis super-compact then there are inner models havingκ+ +,κ+or any cardinal less than or equal toκnormal ultrafilters (§4).These methods also show that several properties ofLwhich had been shown to hold forL[U] also hold forL[U]: using an idea of Silver we show that inL[U] the generalized continuum hypothesis is true, there is a Souslin tree, and there is awell-ordering of the reals. In addition we generalize a result of Kunen to characterize the countaby complete ultrafilters ofL[U].
On deciding the truth of certain statements involving the notion of consistency
Authors: Boolos George 
Published: May 2006

Friedman has posed (see [F, p. 117]) the following problem: “35. Define the set E of expressions by (i) Con is an expression; (ii) if A, B are expressions so are (~ A), (A&B), and Con(A). Each expression ϕ in E determines a sentence ϕ in PA [classical first-order arithmetic] by taking Con* to be “PA is consistent,” ( ~ A) * to be ~ (A*), (A&B)* to be A*&B*, and Con(A)* to be “PA + ‘A*’ is consistent.” The set of expressions ϕ ∈ E such that ϕ* is true is recursive.The formalized second incompleteness theorem readsIn order to simplify notation, we will reformulate Friedman's problem slightly. Let Con be the usual sentence of PA expressing the consistency of PA, ~ A the negation of A, (A&B) the conjunction of A and B, etc., and Bew(A) the result of substituting the numeral for the Gödel number of A for the free variable in the usual provability predicate for PA. Let Con(A) = ~ Bew(~ A). (Con(A) is equivalent in PA to the usual sentence expressing the consistency of PA + A.) And let the class of F-sentences be the smallest class which contains Con and which also contains ~ A, (A&B) and Con(A) whenever it contains A and B. Since ⊦PA Bew(A) ↔ Bew(B) if ⊦PAA ↔ B, Friedman's problem is then the question whether the class of true F-sentences is recursive.The answer is that it is recursive. To see why, we need a definition and a theorem.Definition. An atom is a sentence Conn for some n ≥ 1, where Cont = Con and Conn + 1 = Con(Conn).
An extension of Ackermann's set theory
Authors: Perlis Donald 
Published: May 2006

Ackermann's set theory [1], called here A, involves a schemawhere φ is an ∈-formula with free variables among y1, …, yn and w does not appear in φ. Variables are thought of as ranging over classes and V is intended as the class of all sets.S is a kind of comprehension principle, perhaps most simply motivated by the following idea: The familiar paradoxes seem to arise when the class CP of all P-sets is claimed to be a set, while there exists some P-object x not in CP such that x would have to be a set if CP were. Clearly this cannot happen if all P-objects are sets.Now, Levy [2] and Reinhardt [3] showed that A* (A with regularity) is in some sense equivalent to ZF. But the strong replacement axiom of Gödel-Bernays set theory intuitively ought to be a theorem of A* although in fact it is not (Levy's work shows this). Strong replacement can be formulated asThis lack of A* can be remedied by replacing S above bywhere ψ and φ are ∈-formulas and x is not in ψ and w is not in φ. ψv is ψ with quantifiers relativized to V, and y and z stand for y1, …, yn and z1, …, zm.
Correction to ‘A model theoretic characterisation of effective operations’
Authors: Löb M. H. 
Published: May 2006

With the definition of effective operations as stated in the paper cited above (this Journal, vol. 35 (1970), p. 217), the last step of Lemma 1 does not appear to extend to types ≥ 3. This may be rectified by altering the second clause of the definition of effective operation (loc. cit. p. 217) to read:ℱ is an effective operation of type i + 2 with Gödel number f∈Ei+2, if for every g∈Ei+1 there is an effective operation of type i + 1 (not depending on ℱ and f) with Gödel number g such that ℱ() = p(f, g).With this definition the proofs go through without alteration.There are two other variants for representing an effective operation by higher type objects.I. We adopt the definition of effective as given in the text, and require the terms to satisfy the additional conditionII. Here we add to the definition of effective operations given in the text the condition:If ℱ and ℱ1 are effective operations of type i + 2 and for all effective operations of type i + 1, then ℱ = ℱ1.We now require terms s, t ∈ fi to satisfy the additional conditionThe proof of Lemmas 1 and 2 are easily modified to establish I and II.Perhaps II may be regarded as giving the most natural characterisation since in this case all terms represent continuous functionals.
Combinator realizability of a constructive Morse set theory
Authors: Staples John 
Published: May 2006

A constructive version of Morse set theory is given, based on Heyting's predicate calculus and with countable rather than full choice. An elaboration of the method of [5] is used to show that the theory is combinator-realizable in the sense defined there. The proof depends on the assumption of the syntactic consistency of the theory.The method is introduced by first treating a subtheory without countable choice of foundation.It is intended that the work can be read either classically or constructively, though whether the word constructive is correctly used as a description of either the theory or the metatheory is of course a matter of opinion.