bluuebunny/crossref_metadata_2025_split huggingface dataset:
Sur l'Existence de Fonctions Récurrentes
Authors: de Barros Constantino M. 
Published: May 2007

AbstractDans le présent travail, on introduit la notion de schéma de récurrence associé à un modèle et on démontre un résultat assez géneral (Théorème 1) assurant l'existence et l'unicité de fonctions récurrentes sous‐jacentes à des schémas de récurrence associés à des modèles naturels. L'application de ce résultat à des schémas de récurrence particuliers donne, comme une conséquence immédiate, parmi d'autres, le théorème de la definition par récurrence et le théorème de l'obtention de fonctions par récurrence primitive.
TERNARY OPERATIONS AS PRIMITIVE NOTIONS FOR PLANE GEOMETRY II
Authors: Pambuccian Victor 
Published: May 2007

AbstractWe proved in the first part [1] that plane geometry over Pythagorean fields is axiomatizable by quantifier‐free axioms in a language with three individual constants, one binary and three ternary operation symbols. In this paper we prove that two of these operation symbols are superfluous.
An order‐theoretic characterization of the Schütte‐Veblen‐Hierarchy
Authors: Weiermann Andreas 
Published: May 2007

AbstractFor f: On → On let supp(f): = ξ: 0, and let S := {f : On → On : supp(f) finite}. For f,g ϵ S definef ≤ g : ↔ (∃h : On → On)[h one‐to‐one ⁁ (∀ξ)f(ξ) ≤ g(h(ξ))].A function ψ : S → On is called monotonic increasing, if f(ξ)≤ψ(f) and if f ≤ g implies ψ (f) ≤ ψ(g). For a mapping ψ : S → On let Clψ(0) be the least set T of ordinals which contains 0 as an element and which is closed under the following rule: If f ϵ S, range(f) ⊆ T and supp(f) ⊆ T, then ψ(f) ϵ T. Let φ be the enumeration function of the class {ξ: (∃n)[ξ = ωn]}. Let φ be the induced Schütte‐Klammerterm‐function (see [11]) which generates the Schütte‐Veblen‐hierarchy of ordinals. Then φ is monotonic increasing. We show: If ψ: S → On is monotonic increasing, then otyp(Clφ(0)) ≤ min {ξ : ξ = Φ, where 1ξ(α) = 1 if α = ξ and 1ξ(α) = 0 if α ↔ = 0 if α ≠ ξ. For τ an ordinal let Sτ := {f ϵ S : supp(f) ⊆ τ}. A function ψ : Sτ → On is called τ‐monotonic increasing if fξ (f) and if f ≤ g implies ψ (f) ≤ (g). For a function ψ Sτ → On let Clψ(0) ↔ τ be the least set T of ordinals, which contains 0 as an element, such that if f ϵ Sτ and range (f) ϵ T, then ψ (f) ϵ T. We show: if ≥2 and if ψ Sτ → On is τ‐monotonic increasing, then otyp(Clψ(0) ↔ τ) ≤(1ψ). We also prove a generalization of this theorem in terms of well‐partial orderings. MSC: 03F15, 03E10, 06A06.
Measure independent Gödel speed‐ups and the relative difficulty of recognizing sets
Authors: Solomon Martin K. 
Published: May 2007

AbstractWe provide and interpret a new measure independent characterization of the Gödel speed‐up phenomenon. In particular, we prove a theorem that demonstrates the indifference of the concept of a measure independent Gödel speed‐up to an apparent weakening of its definition that is obtained by requiring only those measures appearing in some fixed Blum complexity measure to participate in the speed‐up, and by deleting the “for all r” condition from the definition so as to relax the required amount of speed‐up. We interpret our results as correlating the relative difficulty of mechanically recognizing theories with the relative power and the relative abstractness of the theories. We conclude by providing two open problems concerning possible similarities and relationships between the Blum speedability and Gödel speed‐up phenomena. MSC: 03D15, 03F20.
Ternary operations as primitive notions for constructive plane geometry III
Authors: Pambuccian Victor 
Published: May 2007

AbstractThis paper continues the investigations begun in [6] and continued in [7] about quantifier‐free axiomatizations of plane Euclidean geometry using ternary operations. We show that plane Euclidean geometry over Archimedean ordered Euclidean fields can be axiomatized using only two ternary operations if one allows axioms that are not first‐order but universal Lw1,w sentences. The operations are: the transport of a segment on a halfline that starts at one of the endpoints of the given segment, and the operation which produces one of the intersection points of a perpendicular on a diameter of a circle (which intersects that diameter at a point inside the circle) with that circle. MSC: 03F65, 51M05, 51M15.
Intermediate logics preserving admissible inference rules of heyting calculus
Authors: Rybakov Vladimir V. 
Published: May 2007

AbstractThe aim of this paper is to look from the point of view of admissibility of inference rules at intermediate logics having the finite model property which extend Heyting's intuitionistic propositional logic H. A semantic description for logics with the finite model property preserving all admissible inference rules for H is given. It is shown that there are continuously many logics of this kind. Three special tabular intermediate logics λ, 1 ≥ i ≥ 3, are given which describe all tabular logics preserving admissibility: a tabular logic λ preserves all admissible rules for H iff 7λ has width not more than 2 and is not included in each λ. MSC: 03B55, 03B20.
Finitary sequence spaces
Authors: Mandelkern Mark 
Published: May 2007

AbstractThis paper studies the metric structure of the space Hr of absolutely summable sequences of real numbers with at most r nonzero terms. Hr is complete, and is located and nowhere dense in the space of all absolutely summable sequences. Totally bounded and compact subspaces of Hr are characterized, and large classes of located, totally bounded, compact, and locally compact subspaces are constructed. The methods used are constructive in the strict sense. MSC: 03F65, 54E50.
A note on effective ultrapowers: Uniform failure of bounded collection
Authors: McLaughlin Thomas 
Published: May 2007

AbstractBy suitably adapting an argument of Hirschfeld (see [2, Chapter 9]), we show that there is a single Δ1 formula that defeats “bounded collection” for any model of II2 Arithmetic that is either a recursive ultrapower or an existentially complete model. Some related facts are noted. MSC: 03F30, 03C62.
Typical ambiguity and elementary equivalence
Authors: Dzierzgowski Daniel 
Published: May 2007

AbstractA sentence of the usual language of set theory is said to be stratified if it is obtained by “erasing” type indices in a sentence of the language of Russell's Simple Theory of Types. In this paper we give an alternative presentation of a proof the ambiguity theorem stating that any provable stratified sentence has a stratified proof. To this end, we introduce a new set of ambiguity axioms, inspired by Fraïssé's characterization of elementary equivalence; these axioms can be naturally used to give different proofs of the ambiguity theorem (semantic or syntactic, classical or intuitionistic). MSC: 03B15, 03F50, 03F55.
Derived sequences and reverse mathematics
Authors: Hirst Jeffry L. 
Published: May 2007

AbstractOne of the earliest applications of transfinite numbers is in the construction of derived sequences by Cantor [2]. In [6], the existence of derived sequences for countable closed sets is proved in ATR0. This existence theorem is an intermediate step in a proof that a statement concerning topological comparability is equivalent to ATR0. In actuality, the full strength of ATR0 is used in proving the existence theorem. To show this, we will derive a statement known to be equivalent to ATR0, using only RCA0 and the assertion that every countable closed set has a derived sequence. We will use three of the subsystems of second order arithmetic defined by H. Friedman ([3], [4]), which can be roughly characterized by the strength of their set comprehension axioms. RCA0 includes comprehension for Δ definable sets, ACA0 includes comprehension for arithmetical sets, and ATR0 appends to ACA0 a comprehension scheme for sets defined by transfinite recursion on arithmetical formulas. MSC: 03F35, 54B99.
Non‐circular, non‐well‐founded set universes
Authors: Tzouvaras Athanassios 
Published: May 2007

AbstractWe show that there are universes of sets which contain descending ϵ‐sequences of length α for every ordinal α, though they do not contain any ϵ‐cycle. It is also shown that there is no set universe containing a descending ϵ‐sequence of length On. MSC: 03E30; 03E65.
On the predecessor relation in abstract algebras
Authors: Diener Karl‐Heinz 
Published: May 2007

AbstractIn this paper we generalize the Dedekind theory of order for the natural numbers N to abstract algebras with arbitrarily many finitary or infinitary operations. For any algebra 𝔜, we introduce an algebraic predecessor relation P𝔜 and its transitive hull P*𝔜 coinciding in N with the unary injective successor function' resp. the >‐relation. For some important classes of algebras 𝔜, including Peano algebras (absolutely free algebras, word algebras), the algebraic predecessor relation is well‐founded. Hence, its transitive hull, the natural ordering >𝔜 of 𝔜, is a well‐founded partial order, which turns out to be a convenient device for classifying Peano algebras with respect to the number of operations and their arities. Moreover, the property of well‐foundedness is an efficient tool for giving simple proofs of structure theorems as, e. g., that the class of all Peano algebras is closed under subalgebras and non‐void direct products. ‐ Finally, we will show how in the case of a formal language ℒ︁, i. e., the Peano algebra ℒ︁ of expressions (= terms & formulas), relations Pℒ︁, resp. P*ℒ︁ can be used to define basic syntactical notions as occurences of free and bound variables etc. without any reference to a particular representation (“coding”) of the formal language. MSC: 03B22, 03E30, 03E75, 03F35, 08A55, 08B20.
A cohesive set which is not high
Authors: Jockusch Carl , Stephan Frank 
Published: May 2007

AbstractWe study the degrees of unsolvability of sets which are cohesive (or have weaker recursion‐theoretic “smallness” properties). We answer a question raised by the first author in 1972 by showing that there is a cohesive set A whose degree a satisfies a' = 0″ and hence is not high. We characterize the jumps of the degrees of r‐cohesive sets, and we show that the degrees of r‐cohesive sets coincide with those of the cohesive sets. We obtain analogous results for strongly hyperimmune and strongly hyperhyperimmune sets in place of r‐cohesive and cohesive sets, respectively. We show that every strongly hyperimmune set whose degree contains either a Boolean combination of ∑2 sets or a 1‐generic set is of high degree. We also study primitive recursive analogues of these notions and in this case we characterize the corresponding degrees exactly. MSC: 03D30, 03D55.
On the structure of kripke models of heyting arithmetic
Authors: Marković Zoran 
Published: May 2007

AbstractSince in Heyting Arithmetic (HA) all atomic formulas are decidable, a Kripke model for HA may be regarded classically as a collection of classical structures for the language of arithmetic, partially ordered by the submodel relation. The obvious question is then: are these classical structures models of Peano Arithmetic (PA)? And dually: if a collection of models of PA, partially ordered by the submodel relation, is regarded as a Kripke model, is it a model of HA? Some partial answers to these questions were obtained in [6], [3], [1] and [2]. Here we present some results in the same direction, announced in [7]. In particular, it is proved that the classical structures at the nodes of a Kripke model of HA must be models of IΔ1 (PA‐ with induction for provably Δ1 formulas) and that the relation between these classical structures must be that of a Δ1‐elementary submodel. MSC: 03F30, 03F55.
A proof of the normal form theorem for the closed terms of Girard's system F by means of computability
Authors: Valentini Silvio 
Published: May 2007

AbstractIn this paper a proof of the normal form theorem for the closed terms of Girard's system F is given by using a computability method à la Tait. It is worth noting that most of the standard consequences of the normal form theorem can be obtained using this version of the theorem as well. From the proof‐theoretical point of view the interest of the proof is that the definition of computable derivation here used does not seem to be well founded. MSC: 03F05, 03B15.
Automorphisms of Models of True Arithmetic: Subgroups which Extend to a Maximal Subgroup Uniquely
Authors: Kotlarski Henryk , Piekart Bożena 
Published: May 2007

AbstractWe show that ifMis a countable recursively saturated model of True Arithmetic, thenG= Aut(M) has nonmaximal open subgroups with unique extension to a maximal subgroup of Aut(M).Mathematics Subject Classification:03C62, 03C50.
Abelian‐by‐G Groups, for G Finite, from the Model Theoretic Point of View
Authors: Marcja Annalisa , Toffalori Carlo 
Published: May 2007

AbstractLet G be a finite group. We prove that the theory af abelian‐by‐G groups is decidable if and only if the theory of modules over the group ring ℤ[G] is decidable. Then we study some model theoretic questions about abelian‐by‐G groups, in particular we show that their class is elementary when the order of G is squarefree.Mathematics Subject Classification: 03C60, 03B25.
Monotonicity and the Expressibility of NP Operators
Authors: Stewart Iain A. 
Published: May 2007

AbstractWe investigate why similar extensions of first‐order logic using operators (that is, generalized quantifiers) corresponding to NP‐complete decision problems apparently differ in expressibility: the logics capture either NP or LNP. It had been conjectured that the complexity class captured is NP if and only if the operator is monotone. We show that this conjecture is false. However, we provide evidence supporting a revised conjecture involving finite variations of monotone problems.Mathematics Subject Classification: 68Q15, 03D15, 03C13.
K‐generic Projective Planes have Morley Rank Two or Infinity
Authors: Baldwin John T. , Itai Masanori 
Published: May 2007

AbstractWe show that K‐generic projective planes have Morley rank either two or infinity. We also show give a direct argument that such planes are not Desarguesian.Mathematics Subject Classification: 03C45, 05C90, 51A35.
Cut‐Elimination Theorem for the Logic of Constant Domains
Authors: Kashima Ryo , Shimura Tatsuya 
Published: May 2007

AbstractThe logic CD is an intermediate logic (stronger than intuitionistic logic and weaker than classical logic) which exactly corresponds to the Kripke models with constant domains. It is known that the logic CD has a Gentzen‐type formulation called LD (which is same as LK except that (→) and (⊃–) rules are replaced by the corresponding intuitionistic rules) and that the cut‐elimination theorem does not hold for LD. In this paper we present a modification of LD and prove the cut‐elimination theorem for it. Moreover we prove a “weak” version of cut‐elimination theorem for LD, saying that all “cuts” except some special forms can be eliminated from a proof in LD. From these cut‐elimination theorems we obtain some corollaries on syntactical properties of CD: fragments collapsing into intuitionistic logic. Harrop disjunction and existence properties, and a fact on the number of logical symbols in the axiom of CD.Mathematics Subject Classification: 03B55. 03F05.
A Completeness Theorem for Certain Classes of Recursive Infinitary Formulas
Authors: Ash Christopher J. , Knight Julia F. 
Published: May 2007

AbstractWe consider the following generalization of the notion of a structure recursive relative to a set X. A relational structure A is said to be a Γ(X)‐structure if for each relation symbol R, the interpretation of R in A is ∑ relative to X, where β = Γ(R). We show that a certain, fairly obvious, description of classes ∑ of recursive infinitary formulas has the property that if A is a Γ(Ø)‐structure and S is a further relation on A, then the following are equivalent: (i) For every isomorphism F from A to a Γ(X)‐structure, F(S) is ∑ relative to X, (ii) The relation is defined in A by a ∑ formula with parameters.Mathematics Subject Classification: 03D45, 03C57, 03C75.
Representation Theorems for Quantales
Authors: Valentini Silvio 
Published: May 2007

AbstractIn this paper we prove that any quantale Q is (isomorphic to) a quantale of suitable relations on Q. As a consequence two isomorphism theorems are also shown with suitable sets of functions of Q into Q. These theorems are the mathematical background one needs in order to give natural and complete semantics for (non‐commutative) Linear Logic using relations.Mathematics Subject Classification: 06D05, 06D10, 06D20, 03G25.
The Elementary Classes of Direct and Boolean Products
Authors: Gluschankof Daniel 
Published: May 2007

AbstractWe characterize the elementary classes generated from a distinguished subclass closing by taking direct products and elementary equivalence. In the second part we give the same characterization in terms of atomic Boolean products. In the last part, we study the cases when the class of Boolean products is elementary but is not given by a discriminator.Mathematics Subject Classification: 03C30, 08C10, 03C05, 03C60.
Bounding and Dominating Number of Families of Functions on ω
Authors: Laflamme Claude 
Published: May 2007

AbstractWe pursue the study of families of functions on the natural numbers, with emphasis here on the bounded families. The situation being more complicated than the unbounded case, we attack the problem by classifying the families according to their bounding and dominating numbers, the traditional scheme for gaps. Many open questions remain.Mathematics Subject Classification: 03E35, 04A20.
Effective Search Problems
Authors: Kummer Martin , Stephan Frank 
Published: May 2007

AbstractThe task of computing a function F with the help of an oracle X can be viewed as a search problem where the cost measure is the number of queries to X. We ask for the minimal number that can be achieved by a suitable choice of X and call this quantity the query complexity of F. This concept is suggested by earlier work of Beigel, Gasarch, Gill, and Owings on “Bounded query classes”. We introduce a fault tolerant version and relate it with Ulam's game. For many natural classes of functions F we obtain tight upper and lower bounds on the query complexity of F. Previous results like the Nonspeedup Theorem and the Cardinality Theorem appear in a wider perspective.Mathematics Subject Classification: 03D20, 68Q15, 68R05.
Navigation Without Perception of Coordinates and Distances
Authors: Hemmerling Armin 
Published: May 2007

AbstractWe consider the target‐reaching problem in plane scenes for a point robot which has a tactile sensor and can locate the target ray. It might have a compass, too, but it is not able to perceive the coordinates of its position nor to measure distances. The complexity of an algorithm is measured by the number of straight moves until reaching the target, as a function of the number of vertices of the (polygonal) scene. It is shown how the target point can be reached by exhaustive search without using a compass, with the complexity exp(O(n2)). Using a compass, there is a target‐reaching algorithm, based on rotation counting, with the complexityO(n2). The decision problem, to recognize if the target cannot be reached because it belongs to an obstacle, cannot be solved by our type of robot. If the behaviour of a robot without compass is periodic in a homogeneous environment, it cannot solve the target‐reaching problem.Mathematics Subject Classification:68Q20, 68U05, 03D15.
A Note on Relative Efficiency of Axiom Systems
Authors: Fontani Sandra , Montagna Franco , Sorbi Andrea 
Published: May 2007

AbstractWe introduce a notion of relative efficiency for axiom systems. Given an axiom system Aβ for a theory T consistent with S12, we show that the problem of deciding whether an axiom system Aα for the same theory is more efficient than Aβ is II2‐hard. Several possibilities of speed‐up of proofs are examined in relation to pairs of axiom systems Aα, Aβ, with Aα ⊇ Aβ, both in the case of Aα, Aβ having the same language, and in the case of the language of Aα extending that of Aβ: in the latter case, letting Prα, Prβ denote the theories axiomatized by Aα, Aβ, respectively, and assuming Prα to be a conservative extension of Prβ, we show that if Aα — Aβ contains no nonlogical axioms, then Aα can only be a linear speed‐up of Aβ; otherwise, given any recursive function g and any Aβ, there exists a finite extension Aα of Aβ such that Aα is a speed‐up of Aβ with respect to g.Mathematics Subject Classification: 03F20, 03F30.
A Uniform Approach to Fundamental Sequences and Hierarchies
Authors: Buchholz Wilfried , Cichon Adam , Weiermann Andreas 
Published: May 2007

AbstractIn this article we give a unifying approach to the theory of fundamental sequences and their related Hardy hierarchies of number‐theoretic functions and we show the equivalence of the new approach with the classical one.Mathematics Subject Classification: 03D20, 03F15, 03E10.
Discontinuity of Cappings in the Recursively Enumerable Degrees and Strongly Nonbranching Degrees
Authors: Ambos‐Spies Klaus , Decheng Ding 
Published: May 2007

AbstractWe construct an r. e. degree a which possesses a greatest a‐minimal pair b0, b1, i.e., r. e. degrees b0 and b1 such that b0, b1 < a, b0 ∩ b1 = a, and, for any other pair c0, c1 with these properties, c0 ≤ bi and c1 ≤ b1‐i for some i ≤ 1. By extending this result, we show that there are strongly nonbranching degrees which are not strongly noncappable. Finally, by introducing a new genericity concept for r. e. sets, we prove a jump theorem for the strongly nonbranching and strongly noncappable r. e. degrees.Mathematics Subject Classification: 03D25.
Finite Homogeneous 3‐Graphs
Authors: Lachlan Alistair H. , Tripp Allyson 
Published: May 2007

AbstractBy “3‐graph” we mean a pair (V, E) such that E ⊆ [V]3. We show that the only non‐trivial finite 3‐graphs homogeneous in the sense of Fraïssé are those associated with the projective planes over GF(2) and GF(3), and with the projective lines over GF(5) and GF(9). To exclude other possibilities we use the classification of doubly transitive finite permutation groups.
The Friedman‐Translation for Martin‐Löf's Type Theory
Authors: Palmgren Erik 
Published: May 2007

AbstractIn this note we show that Friedman's syntactic translation for intuitionistic logical systems can be carried over to Martin‐Löf's type theory, inlcuding universes provided some restrictions are made. Using this translation we show that the theory is closed under a higher type version of Markov's rule.
Some Solved and Unsolved Remainder Equations
Authors: Hansson Sven Ove 
Published: May 2007

AbstractThe remainder set A⟂B of a set of sentences A modulo a set of sentences B is the set of all maximal subsets of A not implying any element of B. A remainder equation is an expression containing remainder sets, such as {A} = B⟂X, in which at least one set is unknown. Solutions to some classes of remainder equations are reported, and some unsolved problems are listed.
Loeb Measure from the Point of View of a Coin Flipping Game
Authors: Kanovei Vladimir , Reeken Michael 
Published: May 2007

AbstractA hyperfinitely long coin flipping game between the Gambler and the Casino, associated with a given set A, is considered. It turns out that the Gambler has a winning strategy if and only if A has Loeb measure 0. The Casino has a winning strategy if and only if A contains an internal subset of positive Loeb measure.Mathematics Subject Classification: 03H05, 03E15.