bluuebunny/crossref_metadata_2025_split huggingface dataset:
Free-variable axiomatic foundations of infinitesimal analysis: A fragment with finitary consistency proof
Authors: Chuaqui Rolando , Suppes Patrick 
Published: May 2006

In treatises or advanced textbooks on theoretical physics, it is apparent that the way mathematics is used is very different from what is to be found in books of mathematics. There is, for example, no close connection between books on analysis, on the one hand, and any classical textbook in quantum mechanics, for example, Schiff, [11], or quite recent books, for example Ryder, [10], on quantum field theory. The differences run a good deal deeper than the fact that the books on theoretical physics are not written in the definition-theorem-proof style characteristic of pure mathematics. Although a good many propositions are proved in the books on physics, there are almost with exception no existential proofs, and consequently there is no really serious systematic use of quantifiers. Another important characteristic is the free use of infinitesimals. In fact, most results would not lose anything, from a physicist's point of view, by leaving them in approximate form, i.e., instead of strict equalities or inequalities, using equalities or inequalities only up to an infinitesimal.The discrepancy between the way mathematics is ordinarily done in theoretical physics and the way it is built up from a foundational standpoint in any of the standard modern views raises the question of whether it might be possible to construct quite directly a rigorous foundation that reflects a significant part of this standard practice in theoretical physics. Other parts of standard practice in physics, for example, the use of physically intuitive but nonrigorous arguments, are not present in our system.
y= 2xVS.y= 3x
Authors: Stolboushkin Alexei , Niwiński Damian 
Published: May 2006

AbstractWe show that no formula of first order logic using linear ordering and the logical relationy= 2xcan define the property that the size of a finite model is divisible by 3. This answers a long-standing question which may be of relevance to certain open problems in circuit complexity.
Rothberger's property and partition relations
Authors: Scheepers Marion 
Published: May 2006

Let X be an infinite but separable metric space. An open cover of X is said to be large if for each x ϵ X the set {U ϵ : x ϵ U} is infinite. The symbol Λ denotes the collection of large open covers of X. An open cover of X is said to be an ω-cover if for each finite subset F of X there is a U ϵ such that F ⊆ U, and X is not a member of , X is said to have Rothberger's property if there is for every sequence (n : n = 1,2,3,…) of open covers of X a sequence (Un : n = 1,2,3,…) such that:(1) for each n, Un is a member of n, and(2) {Un: n = 1,2,3,…} is a cover of X.Rothberger introduced this property in his paper [2]. For convenience we let denote the collection of all open covers of X.In [3] it was shown that X has Rothberger's property if, and only if, the following partition relation is true for large open covers of X:This partition relation means:for every large cover of X, for every coloringsuch that for each U ϵ and each large cover there is an i with a large cover of X,either there is a large cover such that f({A, B}) = 0 whenever {A,B} ϵ ,or else there is a which is not point–finite such that f{{A, B}) = 1 whenever {A, B} ϵ .
Asymptotic conditional probabilities: The non-unary case
Authors: Grove Adam J. , Halpern Joseph Y. , Koller Daphne 
Published: May 2006

AbstractMotivated by problems that arise in computing degrees of belief, we consider the problem of computing asymptotic conditional probabilities for first-order sentences. Given first-order sentences φ and θ, we consider the structures with domain {1, …, N} that satisfy θ, and compute the fraction of them in which φ is true. We then consider what happens to this fraction as N gets large. This extends the work on 0-1 laws that considers the limiting probability of first-order sentences, by considering asymptotic conditional probabilities. As shown by Liogon'kiĭ [24], if there is a non-unary predicate symbol in the vocabulary, asymptotic conditional probabilities do not always exist. We extend this result to show that asymptotic conditional probabilities do not always exist for any reasonable notion of limit. Liogon'kiĭ also showed that the problem of deciding whether the limit exists is undecidable. We analyze the complexity of three problems with respect to this limit: deciding whether it is well-defined, whether it exists, and whether it lies in some nontrivial interval. Matching upper and lower bounds are given for all three problems, showing them to be highly undecidable.
A version of o-minimality for the p-adics
Authors: Haskell Deirdre , Macpherson Dugald 
Published: May 2006

In this paper we formulate a notion similar to o-minimality but appropriate for the p-adics. The paper is in a sense a sequel to [11] and [5]. In [11] a notion of minimality was formulated, as follows. Suppose that L, L+ are first-order languages and + is an L+-structure whose reduct to L is . Then + is said to be -minimal if, for every N+ elementarily equivalent to +, every parameterdefinable subset of its domain N+ is definable with parameters by a quantifier-free L-formula. Observe that if L has a single binary relation which in is interpreted by a total order on M, then we have just the notion of strong o-minimality, from [13]; and by a theorem from [6], strong o-minimality is equivalent to o-minimality. If L has no relations, functions, or constants (other than equality) then the notion is just strong minimality.In [11], -minimality is investigated for a number of structures . In particular, the C-relation of [1] was considered, in place of the total order in the definition of strong o-minimality. The C-relation is essentially the ternary relation which naturally holds on the maximal chains of a sufficiently nice tree; see [1], [11] or [5] for more detail, and for axioms. Much of the motivation came from the observation that a C-relation on a field F which is preserved by the affine group AGL(1,F) (consisting of permutations (a,b) : x ↦ ax + b, where a ∈ F \ {0} and b ∈ F) is the same as a non-trivial valuation: to get a C-relation from a valuation ν, put C(x;y,z) if and only if ν(y − x) < ν(y − z).
Nondefinability results for expansions of the field of real numbers by the exponential function and by the restricted sine function
Authors: Bianconi Ricardo 
Published: May 2006

AbstractWe prove that no restriction of the sine function to any (open and nonempty) interval is definable in 〈R, +, ·, ×, <, exp, constants〉, and that no restriction of the exponential function to an (open and nonempty) interval is definable in 〈R, +, ·, <, sin0, constants〉, where sin0(x) = sin(x) for x ∈ [—π, π], and sin0(x) = 0 for all x ∉ [—π, π].
Boolean operations, Borel sets, and Hausdorff's question
Authors: Dasgupta Abhijit 
Published: May 2006

The study of infinitary Boolean operations was undertaken by the early researchers of descriptive set theory soon after Suslin's discovery of the important operation. The first attempt to lay down their theory in a systematic fashion was the work of Kantorovich and Livenson [5], where they call these the analytical operations. Earlier, Hausdorff had introduced the δs operations — essentially same as the monotoneω-ary Boolean operations, and Kolmogorov, independently of Hausdorff, had discovered the same objects, which were used in his study of the R operator.The ω-ary Boolean operations turned out to be closely related to most of the classical hierarchies over a fixed Polish space X, including, e. g., the Borel hierarchy (), the difference hierarchies of Hausdorff (Dη()), the C-hierarchy (Cξ) of Selivanovski, and the projective hierarchy (): for each of these hierarchies, every level can be expressed as the range of an ω-ary Boolean operation applied to all possible sequences of open subsets of X. In the terminology of Dougherty [3], every level is “open-ω-Boolean” (if and are collections of subsets of X and I is any set, is said to be -I-Boolean if there exists an I-ary Boolean operation Φ such that = Φ, i. e. is the range of Φ restricted to all possible I-sequences of sets from ). If in addition, the space X has a basis consisting of clopen sets, then the levels of the above hierarchies are also “clopen-ω-Boolean.”
On the equivalence of certain consequences of the proper forcing axiom
Authors: Nyikos Peter , Piątkiewicz Leszek 
Published: May 2006

AbstractWe prove that a number of axioms, each a consequence of PFA (the Proper Forcing Axiom) are equivalent. In particular we show that TOP (the Thinning-out Principle as introduced by Baumgartner in the Handbook of set-theoretic topology), is equivalent to the following statement: If I is an ideal on ω1 with ω1 generators, then there exists an uncountable X ⊆ ω1, such that either [X]ω ∩ I = ∅ or [X]ω ⊆ I.
On the basic logic ofSTITwith a single agent
Authors: Xu Ming 
Published: May 2006

AbstractWe present in this paper an axiomatization of Belnap and Perloff'sstittheory (a logic of “seeing to it that”) with a single agent. The idea of the proof is to apply the notion of companion sets—the same notion as used in another paper by the author that showed the decidability ofstittheory with a single agent andRefrefequivalence.
Élimination des quantificateurs dans des paires de corps
Authors: Leloup G. 
Published: May 2006

On sait que par le choix d’ un langage suffisamment complexe, toute structure peut admettre une élimination des quantificateurs, malheureusement cette extension du langage peut nous éloigner des phénomènes algébriques. Nous allons nous intéresser à l’ élimination des quantificateurs pour des paires de corps. Dans le cas des paires de corps algébriquement clos et des paires denses de corps réel clos, on obtient une élimination en ajoutant au langage des prédicats ayant une signification algébrique: on peut les exprimer en disant que pour deux ensembles algébriques et donnés, il existe des points du sous-corps rationnels pour et pas pour , ou qu’ un ensemble semi-algébrique donné a des points rationnels sur le sous-corps. Robinson avait déjà abordé de façon informelle le cas des paires denses de corps réel-clos (cf. [Ro 2, p. 198]). Partant du langage des paires de corps ordonnés, enrichi de symboles de relations correspondant à l’ indépendance algébrique, il proposait d’ ajouter pas à pas des fonctions de Skolem Herbrand pour faire disparaitre les quantificateurs existentiels des formules, mais sans préciser le langage obtenu. Ici nous approchons le problème différemment en explicitant dès le départ le langage utilisé.Grâce à ces résultats nous pourrons étudier le cas des paires séparées de corps réels clos ainsi que des paires de corps valués henseliens. En élargissant la définition d’ ensemble algébrique à tous les symboles du langage, les prédicats relationnels ajoutés ont la même signification que dans le cas des paires de corps algébriquement clos.En comparant les techniques employées ici avec celles déjà utilisées dans [K], [B], [D 1] et [L], on remarque qu’il est possible de traîter une grande partie de l’ étude (complétude, modèle complétude, élimination des quantificateurs) des paires de corps algébriquement clos, réel-clos ou henseliens en se basant sur des prolongements d’ isomorphismes entre sous-structures dénombrables où l’ une des deux est contenue dans une structure ω1-saturée.
Embeddability and the word problem
Authors: Dekov Deko V. 
Published: May 2006

Let be a finitely presented variety with operations Ω and let be the variety having the same set of operations Ω but defined by the empty set of identities. A partial-algebra is a set P with a set of mappings containing for each n-ary operation f of Ω a mapping , where D ⊆ Pn. An incomplete -algebra is a partial -algebra which satisfies the defining identities of , insofar as they can be applied to the partial operations of (Trevor Evans [4, p. 67]). We call an incomplete -algebra a partial Evans-algebra if it can be embedded in a member of the variety .If the class of all partial Evans -algebras is (first-order) finitely axiomatizable, then the word problem for the variety is solvable. (Evans [4, 5]). In 1953 Evans [5, p. 79] raised the question of whether the converse is true. In this paper we show that the answer is in the negative.Let CSg denote the variety of commutative semigroups. We call an incomplete CSg-algebra an incomplete commutative semigroup and we call a partial Evans CSg-algebra a partial Evans commutative semigroup. It is known (A. I. Malcev [9] see also Evans [6]) that the variety of commutative semigroups has solvable word problem. We show (Theorem 1) that the class of all partial Evans commutative semigroups is not finitely axiomatizable. Therefore the solvability of the word problem for the variety of commutative semigroups does not imply finite axiomatizability of the class of all partial Evans commutative semigroups.
A small reflection principle for bounded arithmetic
Authors: Verbrugge Rineke , Visser Albert 
Published: May 2006

AbstractWe investigate the theory IΔ0+Ω1 and strengthen [Bu86, Theorem 8.6] to the following: if NP ≠ co-NP, then Σ-completeness for witness comparison foumulas is not provable in bounded arithmetic. i.e.,Next we study a “small reflection principle” in bounded arithmetic. We prove that for all sentences φThe proof hinges on the use of definable cuts and partial satisfaction predicates akin to those introduced by Pudlák in [Pu86].Finally, we give some applications of the small reflection principle, showing that the principle can sometimes be invoked in order to circumvent the use of provable Σ-completeness for witness comparison formulas.
A logic for approximate reasoning
Authors: Ying Mingsheng 
Published: May 2006

Classical logic is not adequate to face the essential vagueness of human reasoning, which is approximate rather than precise in nature. The logical treatment of the concepts of vagueness and approximation is of increasing importance in artificial intelligence and related research. Consequently, many logicians have proposed different systems of many-valued logic as a formalization of approximate reasoning (see, for example, Goguen [G], Gerla and Tortora [GT], Novak [No], Pavelka [P], and Takeuti and Titani [TT]). As far as we know, all the proposals are obtained by extending the range of truth values of propositions. In these logical systems reasoning is still exact and to make a conclusion the antecedent clause of its rule must match its premise exactly. In addition. Wang [W] pointed out: “If we compare calculation with proving,... Procedures of calculation... can be made so by fairly well-developed methods of approximation; whereas... we do not have a clear conception of approximate methods in theorem proving.... The concept of approximate proofs, though undeniably of another kind than approximations in numerical calculations, is not incapable of more exact formulation in terms of, say, sketches of and gradual improvements toward a correct proof” (see pp, 224–225). As far as the author is aware, however, no attempts have been made to give a conception of approximate methods in theorem proving.The purpose of this paper is. unlike all the previous proposals, to develop a propositional calculus, a predicate calculus in which the truth values of propositions are still true or false exactly and in which the reasoning may be approximate and allow the antecedent clause of a rule to match its premise only approximately. In a forthcoming paper we shall establish set theory, based on the logic introduced here, in which there are ∣L∣ binary predicates ∈λ, λ ∈ L such that R(∈, ∈λ) = λ where ∈ stands for ∈1 and 1 is the greatest element in L, and x ∈λy is interpreted as that x belongs to y in the degree of λ, and relate it to intuitionistic fuzzy set theory of Takeuti and Titani [TT] and intuitionistic modal set theory of Lano [L]. In another forthcoming paper we shall introduce the resolution principle under approximate match and illustrate its applications in production systems of artificial intelligence.
Frege's theorem in a constructive setting
Authors: Bell John L. 
Published: May 2006

By Frege's Theorem is meant the result, implicit in Frege's Grundlagen, that, for any set E, if there exists a map υ from the power set of E to E satisfying the conditionthen E has a subset which is the domain of a model of Peano's axioms for the natural numbers. (This result is proved explicitly, using classical reasoning, in Section 3 of [1].) My purpose in this note is to strengthen this result in two directions: first, the premise will be weakened so as to require only that the map υ be defined on the family of (Kuratowski) finite subsets of the set E, and secondly, the argument will be constructive, i.e., will involve no use of the law of excluded middle. To be precise, we will prove, in constructive (or intuitionistic) set theory, the followingTheorem. Let υ be a map with domain a family of subsets of a set E to E satisfying the following conditions:(i) ø ϵdom(υ)(ii)∀U ϵdom(υ)∀x ϵ E − UU ∪ x ϵdom(υ)(iii)∀UV ϵdom(5) υ(U) = υ(V) ⇔ U ≈ V.Then we can define a subset N of E which is the domain of a model of Peano's axioms.
Gödel sentences of bounded arithmetic
Authors: Takeuti Gaisi 
Published: May 2006

In [1], S. Buss introduced the systems of Bounded Arithmetic for (i = 0,1,2,…) which has a close relationship to classes in polynomial hierarchy.In [4], we defined a very special kind of proof-predicate Prfi for which gives detailed information on bounds of free variables used in the proof. There we also introduced infinitely many Gödel sentences for Prfi (k = 0, 1, 2, …) and showed that the properties of Prfi and are closely related to the P ≠ NP problem. Then we presented many conjectures on Prfi and which imply P ≠ NP.Now in [2], Feferman emphasized that the arithmetization of metamathematics must be carried out intensionally. Bounded Arithmetic is a very interesting case in this sense.In this paper, we also introduce the usual proof-predicate PRFi for and infinitely many Gödel sentences for PRFi(k= 0, 1, 2, …). Then we show that (Prfi, )and (PRFi, ) form a good contrast, this contrast is also closely related to the P ≠ NP problem, and present more conjectures which imply P ≠ NP.As in [4] we define to be the following extension of Buss' original .(1) We add finitely many function symbols which express polynomial time computable functions to Buss' original language of .(2) All basic axioms on function symbols and ≤ can be expressed by initial sequents without logical symbols.
Variations on a theme by Weiermann
Authors: Arai Toshiyasu 
Published: May 2006

AbstractWeiermann [18] introduces a new method to generate fast growing functions in order to get an elegant and perspicuous proof of a bounding theorem for provably total recursive functions in a formal theory, e.g., in PA. His fast growing function θαη is described as follows. For each ordinal a and natural number n let denote a finitely branching, primitive recursive tree of ordinals, i.e., an ordinal as a label is attached to each node in the tree so that the labelling is compatible with the tree ordering. Then the tree is well founded and hence finite by König's lemma. Define θαηn =the depth of the tree =the length of the longest branch in .We introduce new fast and slow growing functions in this mode of definitions and show that each of these majorizes provably total recursive functions in PA.
Normal monomodal logics can simulate all others
Authors: Kracht Marcus , Wolter Frank 
Published: May 2006

AbstractThis paper shows that non-normal modal logics can be simulated by certain polymodal normal logics and that polymodal normal logics can be simulated by monomodal (normal) logics. Many properties of logics are shown to be reflected and preserved by such simulations. As a consequence many old and new results in modal logic can be derived in a straightforward way, sheding new light on the power of normal monomodal logic.
Quine's ‘limits of decision’
Authors: Purdy William C. 
Published: May 2006

AbstractIn a 1969 paper, Quine coined the term ‘limits of decision”. This term evidently refers to limits on the logical vocabulary of a logic, beyond which satisfiability is no longer decidable. In the same paper, Quine showed that not only monadic formulas, but homogeneous k -adic formulas for arbitrary k lie on the decidable side of the limits of decision. But the precise location of the limits of decision has remained an open question. The present paper answers that question. It addresses the question of decidability of those sublogics of first-order logic that are defined in terms of their logical vocabularies. A complete answer is obtained, thus locating exactly Quine's limits of decision.
Amalgamation in relation algebras
Authors: Marx Maarten 
Published: May 2006

We investigate amalgamation properties of relational type algebras. Besides purely algebraic interest, amalgamation in a class of algebras is important because it leads to interpolation results for the logic corresponding to that class (cf. [15]). The multi-modal logic corresponding to relational type algebras became known under the name of “arrow logic” (cf. [18, 17]), and has been studied rather extensively lately (cf. [10]). Our research was inspired by the following result of Andréka et al. [1].Let K be a class of relational type algebras such that(i) composition is associative,(ii) K is a class of boolean algebras with operators, and(iii) K contains the representable relation algebras RRA.Then the equational theory of K is undecidable.On the other hand, there are several classes of relational type algebras (e.g., NA, WA denned below) whose equational (even universal) theories are decidable (cf. [13]). Composition is not associative in these classes. Theorem 5 indicates that also with respect to amalgamation (a very weak form of) associativity forms a borderline. We first recall the relevant definitions.
Fibring: completeness preservation
Authors: Zanardo Alberto , Sernadas Amilcar , Sernadas Cristina 
Published: May 2006

AbstractA completeness theorem is established for logics with congruence endowed with general semantics (in the style of general frames). As a corollary, completeness is shown to be preserved by fibring logics with congruence provided that congruence is retained in the resulting logic. The class of logics with equivalence is shown to be closed under fibring and to be included in the class of logics with congruence. Thus, completeness is shown to be preserved by fibring logics with equivalence and general semantics. An example is provided showing that completeness is not always preserved by fibring ligics endowed with standard (non general) semantics. A categorial characterization of fibring is provided using coproducts and cocartesian liftings.
Monoid based semantics for linear formulas
Authors: Mitchell W. P. R. , Simmons H. 
Published: May 2006

Abstract.Each Girard quantale (i.e., commutative quantale with a selected dualizing element) provides a support for a semantics for linear propositional formulas (but not for linear derivations). Several constructions of Girard quantales are known. We give two more constructions, one using an arbitrary partially ordered monoid and one using a partially ordered group (both commutative). In both cases the semantics can be controlled be a relation between pairs of elements of the support and formulas. This gives us a neat way of handling duality.
Realization of analysis into Explicit Mathematics
Authors: Tupailo Sergei 
Published: May 2006

Abstract.We define a novel interpretation of second order arithmetic into Explicit Mathematics. As a difference from standard -interpretation, which was used before and was shown to interpret only subsystems proof-theoretically weaker than T0. our interpretation can reach the full strength of T0. The -interpretation is an adaptation of Kleene's recursive readability, and is applicable only to intuitionistic theories.