bluuebunny/crossref_metadata_2025_split huggingface dataset:
Einkleidung der Mathematik in Schröderschen Relativkalkul
Authors: Löwenheim Leopold 
Published: May 2006

Bei dem Bestreben, die Mathematik zu logisieren, erschienen die von Russell u.a. entdeckten Paradoxieen als das größte Hindernis. Zu ihrer Überwindung wurde die Typentheorie von Russell aufgestellt, die aber auch in ihrer gemilderten Form die Mathematiker nicht befriedigt. Ich bin diesen Schwierigkeiten nie begegnet, und zwar deshalb nicht, weil logisieren für mich immer bedeutet hat: in Schröderschen Relativkalkul einkleiden.Ich bedaure es aus mehr als einem Grunde schwer, daß man von dem eleganten Peirce-Schröderschen Kalkul abgewichen ist und die Peano-Russellschen Zeichen benutzt, in denen aus bestimmten (m.A.n. nicht stichhaltigen) Gründen die sonst selbstverständliche Harmonie und Schönheit der Mathematik preisgegeben wurde, wodurch die Forschung ziemlich einseitig in eine bestimmte Richtung gedrängt wurde (in der freilich Hochbedeutendes geleistet wurde) während beim Peirce-Schröderschen Kalkul auf Schönheit besonderer Wert gelegt und mit wunderbarer Instinktsicherheit gerade das mathematisch Bedeutsame und Fruchtbare getroffen wurde. Ich bin der Überzeugung, daß in Wissenschaft und Technik das Zweckmäßige immer auch zugleich das Schöne ist. Mit Russells Zeichen hätte ich manches nicht entdeckt, was ich gefunden habe, und besäße jedenfalls nicht meine grosse Kalkulfreudigkeit. Ungünstige Zeichen lähmen die Produktivität. Der heutige Logikkalkul entbehrt daher jeder Eleganz und Geschmeidigkeit, was ganz und gar nicht in der Natur der Sache liegt. Meine Bemühungen, bestimmte Teile des Kalkuls flüssiger, geschmeidiger zu handhaben, sind unbeachtet geblieben.
Existence and feasibility in arithmetic
Authors: Parikh Rohit 
Published: May 2006

“From two integers k, l one passes immediately to kl; this process leads in a few steps to numbers which are far larger than any occurring in experience, e.g., 67(257729).Intuitionism, like ordinary mathematics, claims that this number can be represented by an arabic numeral. Could not one press further the criticism which intuitionism makes of existential assertions and raise the question: What does it mean to claim the existence of an arabic numeral for the foregoing number, since in practice we are not in a position to obtain it?
The substitution method
Authors: Tait W. W. 
Published: May 2006

This paper deals with Hilbert's substitution method for eliminating bound variables from first order proofs. With a first order system S framed in the ε-calculus [2] the problem is to associate a system S' without bound variables and an effective procedure for transforming derivations in S into derivations in S′. The transform of a formula A derived in S is to be an “ε-substitution instance” of A, i.e. it is obtained by replacing terms εxB(x) in A by terms of S′. In general the choice of these terms will depend on the particular derivation of A, and not on A alone. Cf. [4]. The present formulation sharpens Hilbert's original statement of the problem, i.e. that the transform of A should be finitistically verifiable, by making explicit the methods of verification used, namely those formalized in S′; on the other hand, it generalizes Hilbert's formulation since S′ need not be restricted to finitist systems.The bound variable elimination procedure can always be taken to be primitive recursive in (the Gödel number of) the derivation of A. Constructions which transcend primitive recursion can simply be built into S′.In this paper we show that if S′ is taken to be a second order system with constants for functionals, then the existence of suitable ε-substitution instances can be expressed by the solvability of certain functional equations in S′. We deal with two cases here. If S is number theory without induction, i.e. essentially predicate calculus with identity, then we can solve the equations in question by taking for S′ the free variable part S* of S with an added rule of definition of functionals by cases (recursive definition on finite ordinals), which is a conservative extension of S*.
Infinitary analogs of theorems from first order model theory
Authors: Malitz Jerome 
Published: May 2006

The material presented here belongs to the model theory of the Lκ, λ languages. Our results are either infinitary analogs of important theorems in finitary model theory, or else show that such analogs do not exist.For example, it is well known that whenever i, and , have the same true Lω, ω sentences (i.e., are elementarily equivalent) for i = 1, 2, then the cardinal sums 1 + 2 and + have the same true Lω, ω sentences, and the direct products 1 · 2 and · have the same true Lω, ω sentences [3]. We show that this is true when ‘Lω, ω’ is replaced by ‘Lκ, λ’ if and only if κ is strongly inaccessible. For Lω1, ω this settles a question, posed by Lopez-Escobar [7].In §3 we give a complete description of the expressive power of those sentences of Lκ, λ in which the identity symbol is the only relation symbol which occurs. This extends a result by Hanf [4].
A note on Quine's treatment of transfinite recursion
Authors: Parsons Charles 
Published: May 2006

In this note we point out a limitation of the treatment of transfinite recursion in Quine's Set Theory and its Logic2 and develop a method for overcoming it. We shall also mention and indicate how to overcome a second more trivial limitation. We assume familiarity with Set Theory and its Logic and use its notation and terminology. Numbered references are to Quine's numbered formulae. In our work we continue the numbering of § 26.The first difficulty is that the theorems which show that his device for defining functions by transfinite recursion (§ 25) accomplishes its purpose do not apply to functions defined by recursion over all the ordinals. Let γ be the function which gives the value of the function we want for an ordinal y from the sequence of its values for ordinals less than y.
Modus ponens under hypotheses
Authors: Bausch A. F. 
Published: May 2006

The Stoic “indemonstrables” were inference rules; a rule about rules was the synthetic theorem: if from certain premisses a conclusion follows and from that conclusion and certain further premisses a second conclusion follows, then the second conclusion follows from all the premisses together. Similar things occur as medieval “rules of consequence”, although not usually on a metametalevel; and (with the same proviso) the following might be deemed a contemporary avatar of that Stoic theorem.If every formula which occurs once or more often in the list A1, A2, …, An, B1, B2, …, Bm occurs also at least once in the list C1, C2, …, Cr then:This rule [Church: Introduction to Mathematical Logic, 1956, pp. 94, 165], which may be called the rule of modus ponens under hypotheses (MPH), is worthy of attention for the following reasons:A. MPH and the axioms A ⊃ A yield precisely the positive implicative calculus (and very easily, too).B. MPH and the axioms A ⊃ f ⊃ f ⊃ A yield a new formulation of the full classical propositional calculus (in terms of f and ⊃).C. MPH and the axioms ∼A ⊃ A ⊃ A and A ⊃. ∼A ⊃ B yield the classical calculus in terms of ∼ and ⊃.
An introduction to hyperarithmetical functions
Authors: Robinson Julia 
Published: May 2006

By functional equation we mean an equation of the form(1) A1 … Aκ = B1 … B1.Here the A's and B's are functions of one variable from and to the natural numbers and FG is the function obtained from F and G by composition, i.e. FG(x) = F(G(x)) for all natural numbers x. We wish to investigate finite systems of functional equations. Now if all the A's and B's of (1) are equal to the identity function I (or all equal to the zero function O), then the equation (1) is satisfied trivially. Thus, in order to make the problem of solvability of systems of equations interesting, we must have some function given which will be held fixed throughout. We take the successor function S to be this given function.
The number of countable models
Authors: Morley Michael 
Published: May 2006

A theory formulated in a countable predicate calculus can have at most nonisomorphic countable models. It has been conjected (e.g., in [4]) that if it has an uncountable number of such models then it has exactly such. Of course, this would follow immediately if one assumed the continuum hypothesis.In this paper we show that if a theory has more than ℵ1 (i.e., at least ℵ2) isomorphism types of countable models then it has exactly . Our results generalize immediately to theories in Lω1ω and even to pseudo-axiomatic classes in Lω1ω. In this last case, a result of H. Friedman shows that it is the best possible result.
A theorem on initial segments of degrees
Authors: Thomason S. K. 
Published: May 2006

A set S of degrees is said to be an initial segment if c ≤ d ∈ S→-c∈S. Shoenfield has shown that if P is the lattice of all subsets of a finite set then there is an initial segment of degrees isomorphic to P. Rosenstein [2] (independently) proved the same to hold of the lattice of all finite subsets of a countable set. We shall show that “countable set” may be replaced by “set of cardinality at most that of the continuum.” This result is also an extension of [3, Corollary 2 to Theorem 15], which states that there is a sublattice of degrees isomorphic to the lattice of all finite subsets of 2N. (A sublattice of degrees is a subset closed under ∪ and ∩; an initial segment closed under ∪ is necessarily a sublattice, but not conversely.)It seems worth noting that the proof of the present result was preceded in time by our proof [4] of the analogous theorem for hyperdegrees, and is in fact an adaptation of that proof. Thus the present work has been influenced much more directly by the Gandy-Sacks forcing construction of a minimal hyperdegree [1] than by previous work on initial segments of degrees.
Every analytic set is Ramsey
Authors: Silver Jack 
Published: May 2006

If X is a set, [Χ]ω will denote the set of countably infinite subsets of X. ω is the set of natural numbers. If S is a subset of [ω]ω, we shall say that S is Ramsey if there is some infinite subset X of ω such that either [Χ]ω ⊆ S or [Χ]ω ∩ S = 0. Dana Scott (unpublished) has asked which sets, in terms of logical complexity, are Ramsey.The principal theorem of this paper is: Every Σ11 (i.e., analytic) subset of [ω]ω is Ramsey (for the Σ, Π notations, see Addison [1]). This improves a result of Galvin-Prikry [2] to the effect that every Borel set is Ramsey. Our theorem is essentially optimal because, if the axiom of constructibility is true, then Gödel's Σ21 Π21 well-ordering of the set of reals [3], having the convenient property that the set of ω-sequences of reals enumerating initial segments is also Σ21 ∩ Π21, rather directly gives a Σ21 ∩ Π21 set which is not Ramsey. On the other hand, from the assumption that there is a measurable cardinal we shall derive the conclusion that every Σ21 (i.e., PCA) is Ramsey. Also, we shall explore the connection between Martin's axiom and the Ramsey property.
Tense logic for discrete future time
Authors: Schindler Patrick 
Published: May 2006

Prior has conjectured that the tense-logical system Gli obtained by adding to a complete basis for the classical propositional calculus the primitive symbol G, the definitionsDf. F: Fα = NGNαDf. L: Lα = KαGα,and the postulatesis complete for the logic of linear, infinite, transitive, discrete future time. In this paper it is demonstrated that that conjecture is correct and it is shown that Gli has the finite model property: see [4]. The techniques used are in part suggested by those used in Bull [2] and [3]:Gli can be shown to be complete for the logic of linear, infinite, transitive, discrete future time in the sense that every formula of Gli which is true of such time can be proved as a theorem of Gli. For this purpose the notion of truth needs to be formalized. This formalization is effected by the construction of a model for linear, infinite, transitive, discrete future time.
Persistence and Herbrand expansions
Authors: Wholey Joseph S. 
Published: May 2006

Following Robinson [3], we say that a first-order sentence S is persistent with respect to a set of sentences K if, whenever S is true in a model M of K, then S is true in every extension of M that is also a model of K. Robinson proved in [3] that:(T) In order that the sentence S be persistent with respect to the set K it is necessary and sufficient that there be some existential sentence Y such that the sentence S↔Y is deducible from K.
On the undecidability of finite planar graphs
Authors: Garfunkel Solomon , Shank Herbert 
Published: May 2006

In this paper we demonstrate the hereditary undecidability of finite planar graphs. In §2 we introduce the preliminary logical notions used and outline the Rabin–Scott method of semantic embedding. This method is illustrated in §3 by proving the undecidability of the theory of two finite equivalence relations of a special type. In §4 we give a proof of the main theorem by embedding these equivalence relations into finite planar graphs.The basic idea is first to form a graph which codes a pair of these relations and then to take a representative of it and “squish” it to the plane. This “squishing” requires the introduction of crossings; and edges of the original graph become paths in the new one. To distinguish the original edges we place two different types of “diamonds” about crossing points. We can then uncode our new graphs to recover the equivalence relations by means of simple first-order incidence properties.
Maximal vector spaces under automorphisms of the lattice of recursively enumerable vector spaces
Authors: Kalantari Iraj , Retzlaff Allen 
Published: May 2006

The area of interest of this paper is recursively enumerable vector spaces; its origins lie in the works of Rabin [16], Dekker [4], [5], Crossley and Nerode [3], and Metakides and Nerode [14]. We concern ourselves here with questions about maximal vector spaces, a notion introduced by Metakides and Nerode in [14]. The domain of discourse is V∞ a fully effective, countably infinite dimensional vector space over a recursive infinite field F.By fully effective we mean that V∞, under a fixed Gödel numbering, has the following properties:(i) The operations of vector addition and scalar multiplication on V∞ are represented by recursive functions.(ii) There is a uniform effective procedure which, given n vectors, determines whether or not they are linearly dependent (the procedure is called a dependence algorithm).We denote the Gödel number of x by ⌈x⌉ By taking {εn ∣ n > 0} to be a fixed recursive basis for V∞, we may effectively represent elements of V∞ in terms of this basis. Each element of V∞ may be identified uniquely by a finitely-nonzero sequence from F Under this identification, εn corresponds to the sequence whose n th entry is 1 and all other entries are 0. A recursively enumerable (r.e.) space is a subspace of V∞ which is an r.e. set of integers, ℒ(V∞) denotes the lattice of all r.e. spaces under the operations of intersection and weak sum. For V, W ∈ ℒ(V∞), let V mod W denote the quotient space. Metakides and Nerode define an r.e. space M to be maximal if V∞ mod M is infinite dimensional and for all V ∈ ℒ(V∞), if V ⊇ M then either V mod M or V∞ mod V is finite dimensional. That is, M has a very simple lattice of r.e. superspaces.
ℵ0-categorical modules
Authors: Baur Walter 
Published: May 2006

AbstractIt is shown that the first-order theory ThR(A) of a countable module over an arbitrary countable ring R is ℵ0-categorical if and only if Ai finite, n ∈ ω, κi ≤ ω. Furthermore, ThR(A) is ℵ0-categorical for all R-modules A if and only if R is finite and there exist only finitely many isomorphism classes of indecomposable R-modules.
Prefix classes of Krom formulas
Authors: Aanderaa Stål O. , Lewis Harry R. 
Published: May 2006

In this paper we consider decision problems for subclasses of Kr, the class of those formulas of pure quantification theory whose matrices are conjunctions of binary disjunctions of signed atomic formulas. If each of Q1, …, Qn is an ∀ or an ∃, then let Q1 … Qn be the class of those closed prenex formulas with prefixes of the form (Q1x1)… (Qnxn). Our results may then be stated as follows:Theorem 1. The decision problem for satisfiability is solvable for the class ∀∃∀ ∩ Kr.Theorem 2. The classes ∀∃∀∀ ∩ Kr and ∀∀∃∀ ∩ Kr are reduction classes for satisfiability.Maslov [11] showed that the class ∃…∃∀…∀∃…∃ ∩ Kr is solvable, while the first author [1, Corollary 4] showed ∃∀∃∀ ∩ Kr and ∀∃∃∀ ∩ Kr to be reduction classes. Thus the only prefix subclass of Kr for which the decision problem remains open is ∀∃∀∃…∃∩ Kr.The class ∀∃∀ ∩ Kr, though solvable, contains formulas whose only models are infinite (e.g., (∀x)(∃u)(∀y)[(Pxy ∨ Pyx) ∧ (¬ Pxy ∨ ¬Pyu)], which can be satisfied over the integers by taking P to be ≥). This is not the case for Maslov's class ∃…∃∀…∀∃…∃ ∩ Kr, which contains no formula whose only models are infinite ([2] [5]).Theorem 1 was announced in [1, Theorem 4], but the proof sketched there is defective: Lemma 4 (p. 17) is incorrectly stated. Theorem 2 was announced in [9].
On the complexity of the theories of weak direct powers
Authors: Rackoff Charles 
Published: May 2006

AbstractMostowski [11] shows that if a structure has a decidable theory, then its weak direct power has one as well; his proof however never produces decision procedures which are elementary recursive.Some very general results are obtained here about the nature of the weak direct power of a structure, which in most cases lead to elementary recursive decision procedures for weak direct powers of structures which themselves have elementary recursive procedures.In particular, it is shown that 〈N*, +〉, the weak direct power of 〈N, +〉, can be decided in spacefor some constant c. As corollaries, the same upper bound is obtained for the theory of the structure 〈N+, ·〉 of positive integers under multiplication, and for the theory of finite abelian groups. Fischer and Rabin [7] have shown that the theory of 〈N,* +〉 requires timeeven on nondeterministic Turing machines.
Hanf numbers for omitting types over particular theories
Authors: Knight Julia F. 
Published: May 2006

The main result of this paper is the fact that for T a complete extension of either P or ZF + V = L, with no new symbols, there is a type which is omitted in a model of T of power ℵ1 but which is realized in all models of higher power. Therefore, the “Hanf number” for omitting types over T is greater than ℵ2.The present section contains some basic definitions and a discussion of related results. §1 discusses generic relations on models of P and ZFC, and describes a special forcing technique due to Addison. In §2, this technique is used to obtain the main result.The use of forcing is not essential. Those who do not wish to read a forcing argument may skip §1. At the point in §2 where forcing is used, a proof without forcing is sketched. This proof was obtained only after a careful study of the forcing argument. The forcing argument is given because it is simple, and because the technique of forcing makes intuitively clear why this and other similar results should be true.All theories in the paper are assumed to be countable and to have infinite models. Let T be a complete theory in a language L. The Hanf number for omitting types over T, denoted by H(T), is the first infinite cardinal κ such that for all L-types, Σ, if T has models omitting Σ in all infinite powers less than κ, then T has models omitting Σ in all infinite powers.
Co-hypersimple structures
Authors: Remmel J. B. 
Published: May 2006

Priority arguments have been used to produce r.e. sets whose complements have various properties (e.g., maximal sets, hyperhypersimple sets, etc.). In this paper we use the priority method in the context of certain recursively presented models (e.g., dense unbordered linear orderings, countable atomless Boolean algebras, infinite dimensional vector spaces over a finite field) to produce hypersimple subsets of these models whose complements are closed under algebraic operations and/or whose complements are elementarily isomorphic to certain algebraic substructures. For example, it follows from the results of §3 that there are hypersimple subsets of a countable atomless Boolean algebra (of an infinite dimensional vector space over a finite field) in every nonzero r.e. degree whose complement is a subalgebra (subspace). Also, it follows from the same result that, given any subset P of the rationals Q, there is a hypersimple subset of Q whose complement is order isomorphic to P.A model M of a theory T in a countable language L is said to be recursively presented if the universe ∣M∣ of M is an initial segment of the natural numbers and the satisfaction relation “a satisfies Φ in M” is recursive (where a is a finite sequence of elements of ∣M∣ and Φ is a formula in L).
Noncomplex sequences: characterizations and examples
Authors: Daley Robert P. 
Published: May 2006

We are concerned in this paper with infinite binary sequences which are noncomplex in the sense that their minimal-program complexity (i.e., the lengths of shortest programs for computing their finite initial segments), as a function of the lengths of their initial segments, grows arbitrarily (in an effective sense) slowly. Indeed, the existence of such sequences which are also nonrecursive raises some interesting questions concerning the notion of computability itself. Our first task is to give a characterization of these sequences which does not directly involve the notions of complexity theory. Although these characterizations do involve the primitives of recursive function theory, they do not involve the types of properties which one usually encounters there. While a closer connection is still hoped for, the lack of one is not entirely unexpected. For example, except for the trivial case of degree 0, there is no general correlation between program complexity and degrees of unsolvability. The reason, roughly, is this: even though the inequality deg (f) ≤ deg (g) expresses the relative information between f and g (in the sense that if one knows g then one can compute f), it is a qualitative sort of information. The minimal-program complexity is used as a measure of algorithmic information content and as such is quantitative.The second task of this paper is to present an example of one of these sequences which to its credit possesses a fairly long list of interesting properties, not the least attractive of which is that, though nonrecursive, it is very simple to describe. In fact this sequence has occurred previously in the literature. It is the characteristic sequence of the set of busy beaver numbers first studied by T. Rado [13]. Of particular interest to the discussion in the last section of this paper concerning the notion of computability is the fact that all the initial segments of this sequence are computable by arbitrarily short programs each of which is defined on all inputs and runs very quickly.
Categoricity regained
Authors: Ellentuck Erik 
Published: May 2006

One of the earliest goals of modern logic was to characterize familiar mathematical structures up to isomorphism by means of properties expressed in a first order language. This hope was dashed by Skolem's discovery (cf. [6]) of a nonstandard model of first order arithmetic. A theory T such that any two of its models are isomorphic is called categorical. It is well known that if T has any infinite models then T is not categorical. We shall regain categoricity by(i) enlarging our language so as to allow expressions of infinite length, and(ii) enlarging our class of isomorphisms so as to allow isomorphisms existing in some Boolean valued extension of the universe of sets.