In this paper a unified framework for dealing with a broad family of propositional multimodal logics is developed. The key tools for presentation of the logics are the notions of closure relation operation and monotonous relation operation. The two classes of logics: FiRe-logics (finitely reducible logics) and LaFiRe-logics (FiRe-logics with local agreement of accessibility relations) are introduced within the proposed framework. Further classes of logics can be handled indirectly by means of suitable translations. It is shown that the logics from (...) these classes have the finite model property with respect to the class of -formulae, i.e. each -formula has a -model iff it has a finite -model. Roughly speaking, a -formula is logically equivalent to a formula in negative normal form without occurrences of modal operators with necessity force. In the proof we introduce a substantial modification of Claudio Cerrato's filtration technique that has been originally designed for graded modal logics. The main core of the proof consists in building adequate restrictions of models while preserving the semantics of the operators used to build terms indexing the modal operators. (shrink)

In this paper a unified framework for dealing with a broad family of propositional multimodal logics is developed. The key tools for presentation of the logics are the notions of closure relation operation and monotonous relation operation. The two classes of logics: FiRe-logics (finitely reducible logics) and LaFiRe-logics (FiRe-logics with local agreement of accessibility relations) are introduced within the proposed framework. Further classes of logics can be handled indirectly by means of suitable translations. It is shown that the logics from (...) these classes have the finite model property with respect to the class of ♦-formulae, i.e. each ♦-formula has a ℒ-model iff it has a finite ℒ-model. Roughly speaking, a ♦-formula is logically equivalent to a formula in negative normal form without occurrences of modal operators with necessity force. In the proof we introduce a substantial modification of Claudio Cerrato's filtration technique that has been originally designed for graded modal logics. The main core of the proof consists in building adequate restrictions of models while preserving the semantics of the operators used to build terms indexing the modal operators. (shrink)

Let , be a sequence of pseudo-metric spaces, and let p≥1. For , let . For Borel reducibility between equivalence relations , we show it is closely related to finitely Hölder embeddability between pseudo-metric spaces.

In this paper we deepen Mundici's analysis on reducibility of the decision problem from infinite-valued ukasiewicz logic to a suitable m-valued ukasiewicz logic m , where m only depends on the length of the formulas to be proved. Using geometrical arguments we find a better upper bound for the least integer m such that a formula is valid in if and only if it is also valid in m. We also reduce the notion of logical consequence in to the (...) same notion in a suitable finite set of finite-valued ukasiewicz logics. Finally, we define an analytic and internal sequent calculus for infinite-valued ukasiewicz logic. (shrink)

We provide a canonical construction of conformal covers for finite hypergraphs and present two immediate applications to the finite model theory of relational structures. In the setting of relational structures, conformal covers serve to construct guarded bisimilar companion structures that avoid all incidental Gaifman cliques-thus serving as a partial analogue in finite model theory for the usually infinite guarded unravellings. In hypergraph theoretic terms, we show that every finite hypergraph admits a bisimilar cover by a (...) class='Hi'>finite conformal hypergraph. In terms of relational structures, we show that every finite relational structure admits a guarded bisimilar cover by a finite structure whose Gaifman cliques are guarded. One of our applications answers an open question about a clique constrained strengthening of the extension property for partial automorphisms (EPPA) of Hrushovski, Herwig and Lascar. A second application provides an alternative proof of the finite model property (FMP) for the clique guarded fragment of first-order logic CGF, by reducing (finite) satisfiability in CGF to (finite) satisfiability in the guarded fragment, GF. (shrink)

The present study addresses the fluid transport behaviour of the flow of gold -copper /biomagnetic blood hybrid nanofluid in an inclined irregular stenosis artery as a consequence of varying viscosity and Lorentz force. The nonlinear flow equations are transformed into dimensionless form by using nonsimilar variables. The finite-difference technique is involved in computing the nonlinear transport dimensionless equations. The significant parameters like angle parameter, the Hartmann number, changing viscosity, constant heat source, the Reynolds number, and nanoparticle volume fraction on (...) the flow field are exhibited through figures. Present results disclose that the Lorentz force strongly lessens the hybrid nanofluid velocity. Elevating the Grashof number values enhances the rate of blood flow. Growing values of the angle parameter cause to reduce the resistance impedance on the wall. Hybrid nanoparticles have a superior wall shear stress than copper nanoparticles. The heat transfer rate is amplifying at the axial direction with the growing values of nanoparticles concentration. The applied Lorentz force significantly reduces the hybrid and unitary nanofluid flow rate in the axial direction. The hybrid nanoparticles expose a supreme rate of heat transfer than the copper nanoparticles in a blood base fluid. Compared to hybrid and copper nanofluid, the blood base fluid has a lower temperature. (shrink)

We prove that NIP valued fields of positive characteristic are henselian, and we begin to generalize the known results on dp-minimal fields to dp-finite fields. On any unstable dp-finite field K, we define a type-definable group of “infinitesimals,” corresponding to a canonical group topology on (K, +). We reduce the classification of positive characteristic dp-finite fields to the construction of non-trivial Aut(K/A)-invariant valuation rings.

Given a finite relational language L is there an algorithm that, given two finite sets A and B of structures in the language, determines how many homogeneous L structures there are omitting every structure in B and embedding every structure in A? For directed graphs this question reduces to: Is there an algorithm that, given a finite set of tournaments Γ, determines whether QΓ, the class of finite tournaments omitting every tournament in Γ, is well-quasi-order? First, (...) we give a nonconstructive proof of the existence of an algorithm for the case in which Γ consists of one tournament. Then we determine explicitly the set of tournaments each of which does not have an antichain omitting it. Two antichains are exhibited and a summary is given of two structure theorems which allow the application of Kruskal's Tree Theorem. Detailed proofs of these structure theorems will be given elsewhere. The case in which Γ consists of two tournaments is also discussed. (shrink)

Finite-state methods are applied to the Russell-Wiener notion of time (based on events) and developed into an account of interval relations and temporal propositions. Strings are formed and collected in regular languages and regular relations that are argued to embody temporal relations in their various underspecified guises. The regular relations include retractions that reduce computations by projecting strings down to an appropriate level of granularity, and non-deterministic relations defining notions of partiality within and across such levels.

Finite-state methods are applied to the Russell-Wiener-Kamp notion of time (based on events) and developed into an account of interval relations and semi-intervals. Strings are formed and collected in regular languages and regular relations that are argued to embody temporal relations in their various underspecified guises. The regular relations include retractions that reduce computations by projecting strings down to an appropriate level of granularity, and notions of containment for partiality within and across such levels.

In this paper we present a method to reduce the decision problem of several infinite-valued propositional logics to their finite-valued counterparts. We apply our method to Łukasiewicz, Gödel and Product logics and to some of their combinations. As a byproduct we define sequent calculi for all these infinite-valued logics and we give an alternative proof that their tautology problems are in co-NP.

This essay considers social science as a finite province of meaning. It is argued that teasing out common-sense meanings from social scientific conceptions is difficult because the meanings of scientific concepts are often veiled in life-worldly taken-for-grantedness. If social scientists have successfully created a scientific province of meaning, attempts to communicate findings outside of this reduced sphere of science should be somewhat problematic.

For Savage (1954) as for de Finetti (1974), the existence of subjective (personal) probability is a consequence of the normative theory of preference. (De Finetti achieves the reduction of belief to desire with his generalized Dutch-Book argument for Previsions.) Both Savage and de Finetti rebel against legislating countable additivity for subjective probability. They require merely that probability be finitely additive. Simultaneously, they insist that their theories of preference are weak, accommodating all but self-defeating desires. In this paper we dispute these (...) claims by showing that the following three cannot simultaneously hold: (i) Coherent belief is reducible to rational preference, i.e. the generalized Dutch-Book argument fixes standards of coherence. (ii) Finitely additive probability is coherent. (iii) Admissible preference structures may be free of consequences, i.e. they may lack prizes whose values are robust against all contingencies. (shrink)

When I undertook to write an article for mathematical laymen on the mathematical infinite. I did not realize the depths of my own layness, I do now. Having refreshed my memory of the classics of infinity by re-reading among other things the famous papers of Cantor and Zermelo, and having struggled like a boa constrictor to swallow the latest papal bull on the human significance of the infinite, I am completely reduced to what Professor E. W. Hobson aptly and somewhat (...) indignantly calls Mathematical Nihilism. (shrink)

It is shown that the class of reduced matrices of a logic is a 1 st order -class provided the variety associated with has the finite replacement property in the sense of [7]. This applies in particular to all 2-valued logics. For 3-valued logics the class of reduced matrices need not be 1 st order.

Let A and B be subsets of the space 2 N of sets of natural numbers. A is said to be Wadge reducible to B if there is a continuous map Φ from 2 N into 2 N such that A = Φ -1 (B); A is said to be monotone reducible to B if in addition the map Φ is monotone, that is, $a \subset b$ implies $\Phi (a) \subset \Phi(b)$ . The set A is said to be monotone (...) if a ∈ A and $a \subset b$ imply b ∈ A. For monotone sets, it is shown that, as for Wadge reducibility, sets low in the arithmetical hierarchy are nicely ordered. The ▵ 0 1 sets are all reducible to the (Σ 0 1 but not ▵ 0 1 ) sets, which are in turn all reducible to the strictly ▵ 0 2 sets, which are all in turn reducible to the strictly Σ 0 2 sets. In addition, the nontrivial Σ 0 n sets all have the same degree for n ≤ 2. For Wadge reducibility, these results extend throughout the Borel hierarchy. In contrast, we give two natural strictly Π 0 2 monotone sets which have different monotone degrees. We show that every Σ 0 2 monotone set is actually Σ 0 2 positive. We also consider reducibility for subsets of the space of compact subsets of 2 N . This leads to the result that the finitely iterated Cantor-Bendixson derivative D n is a Borel map of class exactly 2n, which answers a question of Kuratowski. (shrink)

Polynomial clone reducibilities are generalizations of the truth-table reducibilities. A polynomial clone is a set of functions over a finite set X that is closed under composition and contains all the constant and projection functions. For a fixed polynomial clone ${\fancyscript{C}}$ , a sequence ${B\in X^{\omega}}$ is ${\fancyscript{C}}$ -reducible to ${A \in {X}^{\omega}}$ if there is an algorithm that computes B from A using only effectively selected functions from ${\fancyscript{C}}$ . We show that if A is Kurtz random and (...) ${\fancyscript{C}_{1} \nsubseteq \fancyscript{C}_{2}}$ are polynomial clones, then there is a B that is ${\fancyscript{C}_{1}}$ -reducible to A but not ${\fancyscript{C}_{2}}$ -reducible to A. This implies a generalization of a result first proved by Lachlan (Z Math Logik Grundlagen Math 11:17–44, 1965) for the case |X| = 2. We also show that the same result holds if Kurtz random is replaced by Kolmogorov–Loveland stochastic. (shrink)

Familiar proof theoretical and especially automated deduction methods sometimes accept infinity where, in fact, it can be omitted. Our first example deals with the infinite supply of individual variables admitted in 1-order deductions, the second one deals with infinite-branching rules in sequent calculi with number-theoretical induction. The contents of Section 1 summarize and extend basic ideas and results published elsewhere, whereas basic ideas and results of Section 2 are exposed for the first time in the present paper. We consider classical (...) formalisms only, to which constructive formalisms can be reduced by Shanin-style interpretations. (shrink)

We investigate strong versions of enumeration reducibility, the most important one being s-reducibility. We prove that every countable distributive lattice is embeddable into the local structure $L(\mathfrak D_s)$ of the s-degrees. However, $L(\mathfrak D_s)$ is not distributive. We show that on $\Delta^{0}_{2}$ sets s-reducibility coincides with its finite branch version; the same holds of e-reducibility. We prove some density results for $L(\mathfrak D_s)$ . In particular $L(\mathfrak D_s)$ is upwards dense. Among the results about reducibilities (...) that are stronger than s-reducibility, we show that the structure of the $\Delta^{0}_{2}$ bs-degrees is dense. Many of these results on s-reducibility yield interesting corollaries for Q-reducibility as well. (shrink)

Thermodynamic macro variables, such as the temperature or volume macro variable, can take on a continuum of allowable values, called thermodynamic macro values. Although referring to the same macro phenomena, the macro variables of Boltzmannian Statistical Mechanics (BSM) differ from thermodynamic macro variables in an important respect: within the framework of BSM the evolution of macro values of systems with finite available phase space is invariably modelled as discontinuous, due to the method of partitioning phase space into macro regions (...) with sharp, fixed boundaries. Conceptually, this is at odds with the continuous evolution of macro values as described by thermodynamics, as well as with the continuous evolution of the micro state assumed in BSM. This discrepancy I call the discontinuity problem. I show how it arises from BSM’s framework and demonstrate its consequences, in particular for the foundational project of reducing thermodynamics to BSM: thermodynamic macro values are shown to not supervene on the corresponding BSM macro values. With supervenience being a conditio sine qua non for the kind of reduction envisaged by the foundational project, the latter is in jeopardy. (shrink)

Analogical transfer in sequence learning is presented as an example of how the type-2 problem of learning an unbounded number of isomorphic sequences is reduced to the type-1 problem of learning a small finite set of sequences. The commentary illustrates how the difficult problem of appropriate analogical filter creation and selection is addressed while avoiding the trap of strong nativism, and it provides theoretical and experimental evidence for the existence of dissociable mechanisms for type-1 learning and type-2 recoding.

In the current paper we consider theories with vocabulary containing a number of binary and unary relation symbols. Binary relation symbols represent labeled edges of a graph and unary relations represent unique annotations of the graph's nodes. Such theories, which we call annotation theories^ can be used in many applications, including the formalization of argumentation, approximate reasoning, semantics of logic programs, graph coloring, etc. We address a number of problems related to annotation theories over finite models, including satisfiability, querying (...) problem, specification of preferred models and model checking problem. We show that most of considered problems are NPTime- or co-NPTime-complete. In order to reduce the complexity for particular theories, we use second-order quantifier elimination. To our best knowledge none of existing methods works in the case of annotation theories. We then provide a new second-order quantifier elimination method for stratified theories, which is successful in the considered cases. The new result subsumes many other results, including those of [2, 28, 21]. (shrink)

The investigation of computational properties of discontinuous functions is an important concern in computable analysis. One method to deal with this subject is to consider effective variants of Borel measurable functions. We introduce such a notion of Borel computability for single-valued as well as for multi-valued functions by a direct effectivization of the classical definition. On Baire space the finite levels of the resulting hierarchy of functions can be characterized using a notion of reducibility for functions and corresponding (...) complete functions. We use this classification and an effective version of a Selection Theorem of Bhattacharya-Srivastava in order to prove a generalization of the Representation Theorem of Kreitz-Weihrauch for Borel measurable functions on computable metric spaces: such functions are Borel measurable on a certain finite level, if and only if they admit a realizer on Baire space of the same quality. This Representation Theorem enables us to introduce a realizer reducibility for functions on metric spaces and we can extend the completeness result to this reducibility. Besides being very useful by itself, this reducibility leads to a new and effective proof of the Banach-Hausdorff-Lebesgue Theorem which connects Borel measurable functions with the Baire functions. Hence, for certain metric spaces the class of Borel computable functions on a certain level is exactly the class of functions which can be expressed as a limit of a pointwise convergent and computable sequence of functions of the next lower level. (shrink)

We study the notion of polynomial-time relation reducibility among computable equivalence relations. We identify some benchmark equivalence relations and show that the reducibility hierarchy has a rich structure. Specifically, we embed the partial order of all polynomial-time computable sets into the polynomial-time relation reducibility hierarchy between two benchmark equivalence relations Eλ and id. In addition, we consider equivalence relations with finitely many nontrivial equivalence classes and those whose equivalence classes are all finite.

We present integral equations for the scattering amplitudes of three scalar particles, using the Faddeev channel decomposition, which can be readily extended to any finite number of particles of any helicity. The solution of these equations, which have been demonstrated to be calculable, provide a nonperturbative way of obtaining relativistic scattering amplitudes for any finite number of particles that are Lorentz invariant, unitary, cluster decomposable and reduce unambiguously in the nonrelativistic limit to the nonrelativistic Faddeev equations. The aim (...) of this program is to develop equations which explicitly depend upon physically observable input variables, and do not require “renormalization” or “dressing” of these parameters to connect them to the boundary states. As a unitary, cluster decomposible, multichannel theory, physical systems whose constituents are confined can be readily described. (shrink)

We explicitly compute, following the method of Weyl, the commutator [Q, P] of the position operatorQ and the momentum operatorP of a particle when the dimension of the space on which they act is finite with a discrete spectrum; and we show that in the limit of a continuous spectrum with the dimension going to infinity this reduces to the usual relation of Heisenberg.

We show that the existence of an infinite set can be reduced to the existence of finite sets “as big as we will”, provided that a multivalued extension of the relation of equipotence is admitted. In accordance, we modelize the notion of infinite set by a fuzzy subset representing the class of wide sets.

We investigate the theory of finite observables, i.e., resolutions of the finite-dimensional identity by means of positive operators, that have a physical interpretation in terms of measurement schemes. We focus on extremal and rank-one observables and consider various constructions that reduce observables to simpler ones. However, these constructions do not suffice to generate all finite extremal observables, as we show by means of counter-examples.

Multiple contraction (simultaneous contraction by several sentences) and iterated contraction are investigated in the framework of specified meet contraction (s.m.c.) that is extended for this purpose. Multiple contraction is axiomatized, and so is finitely multiple contraction (contraction by a finite set of sentences). Two ways to reduce finitely multiple contraction to contraction by single sentences are introduced. The reduced operations are axiomatically characterized and their properties are investigated. Furthermore, it is shown how iterated contraction can be reduced to single-step, (...) single-sentence contraction. However, in this framework the outcome of iterated contraction depends unavoidably on the order in which the inputs are received. This order-dependence makes it impossible to treat two inputs on an equal footing. Therefore it is often preferable to perform changes involving several pieces of information as multiple rather than iterated change. (shrink)

Degtev, A.N., On p-reducibility of numerations, Annals of Pure and Applied Logic 63 57–60. If α and β are two numerations of a set S, then αpβ if there exists a total recursive function f such that [s ε S][α-1=[x:[y ε Df][Dyβ-1]]], where Dn is a finite set with canonical number n. It is proved that if α and β are two computable numerations of some family of recursively enumerable sets A and αpβ, then there is a computable (...) numeration, γ, of S such that αpγ and βshrink)

The concepta question is reducible to a non-empty set of questions is defined and examined. The basic results are: (1) each question which is sound relative to some of its presuppositions is reducible to some set of binary (i.e. having exactly two direct answers) questions; (b) each question which has a finite number of direct answers is reducible to some finite set of binary questions; (c) if entailment is compact, then each normal question (i.e. sound relative to its (...) presuppositions) is reducible to some finite set of binary questions. (shrink)

In this article I intend to show that certain aspects of the axiomatical structure of mathematical theories can be, by a phenomenologically motivated approach, reduced to two distinct types of idealization, the first-level idealization associated with the concrete intuition of the objects of mathematical theories as discrete, finite sign-configurations and the second-level idealization associated with the intuition of infinite mathematical objects as extensions over constituted temporality. This is the main standpoint from which I review Cantor’s conception of infinite cardinalities (...) and also the metatheoretical content of some later well-known theorems of mathematical foundations. These are, the Skolem-Löwenheim Theorem which, except for its importance as such, it is also chosen for an interpretation of the associated metatheoretical paradox (Skolem Paradox), and Gödel’s (first) incompleteness result which, notwithstanding its obvious influence in the mathematical foundations, is still open to philosophical inquiry. On the phenomenological level, first-level and second-level idealizations, as above, are associated respectively with intentional acts carried out in actual present and with certain modes of a temporal constitution process. (shrink)

On the rise over the past 20 years has been ‘moderate supernaturalism’, the view that while a meaningful life is possible in a world without God or a soul, a much greater meaning would be possible only in a world with them. William Lane Craig can be read as providing an important argument for a version of this view, according to which only with God and a soul could our lives have an eternal, as opposed to temporally limited, significance, by (...) virtue of our moral choices then making an ultimate difference. I present two major objections to this position. On the one hand, I contend that if God existed and we had souls that lived forever, then, in fact, all our lives would turn out the same. On the other hand, I maintain that, if this objection is wrong, so that our moral choices would indeed make an ultimate difference and thereby confer an eternal significance on our lives (only) in a supernatural realm, then Craig could not capture the view, aptly held by moderate supernaturalists, that a meaningful life is possible in a purely natural world. An eternal significance would be ‘too big’, reducing any meaning possible during an earthly life to nothing by comparison. I conclude that moderate supernaturalists would be wise to avoid appealing to eternal (or infinite) meaning when spelling out the way God and a soul could alone impart a great meaning to our lives; some other notion of greatness should be considered, perhaps one involving a temporary afterlife. (shrink)

Special groups [M. Dickmann, F. Miraglia, Special Groups : Boolean-Theoretic Methods in the Theory of Quadratic Forms, Memoirs Amer. Math. Soc., vol. 689, Amer. Math. Soc., Providence, RI, 2000] are a first-order axiomatization of the theory of quadratic forms. In Section 2 we investigate reduced special groups which are a lattice under their natural representation partial order ; we show that this lattice property is preserved under most of the standard constructions on RSGs; in particular finite RSGs and RSGs (...) of finite chain length are lattice ordered. We prove that the lattice property fails for the RSGs of function fields of real algebraic varieties over a uniquely ordered field dense in its real closure, unless their stability index is 1 . We show that Open Problem 1 has a positive answer for the RSG of the field Q . In the final section we explore the meaning of Open Problem 1 for formally real fields, in terms of their orders and real valuations; we introduce the notion of “parameter-rank” of a positive-primitive first-order formula of the language for special groups. (shrink)

We study the finitely repeated prisoner’s dilemma in which the players are restricted to choosing strategies which are implementable by a machine with a bound on its complexity. One player has to use a finite automaton while the other player has to use a finite perceptron. Some examples illustrate that the sets of strategies which are induced by these two types of machines are different and not ordered by set inclusion. Repeated game payoffs are evaluated according to the (...) limit of means. The main result establishes that a cooperation at almost all stages of the game is an equilibrium outcome if the complexity of the machines the players may use is limited enough and if the length T of the repeated game is sufficiently large. This result persists when more than T states are allowed in the player’s automaton. We further consider a variant of the model in which the two players are restricted to choosing strategies which are implementable by perceptrons and prove that the players can cooperate at most of the stages provided that the complexity of their perceptrons is sufficiently reduced. (shrink)

We examine the degree structure $\operatorname {\mathrm {\mathbf {ER}}}$ of equivalence relations on $\omega $ under computable reducibility. We examine when pairs of degrees have a least upper bound. In particular, we show that sufficiently incomparable pairs of degrees do not have a least upper bound but that some incomparable degrees do, and we characterize the degrees which have a least upper bound with every finite equivalence relation. We show that the natural classes of finite, light, and (...) dark degrees are definable in $\operatorname {\mathrm {\mathbf {ER}}}$. We show that every equivalence relation has continuum many self-full strong minimal covers, and that $\mathbf {d}\oplus \mathbf {\operatorname {\mathrm {\mathbf {Id}}}_1}$ needn’t be a strong minimal cover of a self-full degree $\mathbf {d}$. Finally, we show that the theory of the degree structure $\operatorname {\mathrm {\mathbf {ER}}}$ as well as the theories of the substructures of light degrees and of dark degrees are each computably isomorphic with second-order arithmetic. (shrink)

: The paper presents some mathematical aspects of the question of reducibility of relations. After giving a formal definition of reducibility we present the basic result (due to Herzberger) to the effect that relations of valency at least 3 are always reducible if the cardinality of the relation is at most equal to the cardinality of the underlying set (which is automatically the case if this set is infinite). In contrast to this, if the term "reduction" is given (...) a practicable form, relations on finite sets are "generically" irreducible, as is shown by a simple counting argument. Next we discuss the question of an "intrinsic" criterion for reducibility. Finally we propose a scheme for the graphic representation of reductions. (shrink)

We characterize preservation of superstability and ω-stability for finite extensions of abelian groups and reduce the general case to the case of p-groups. In particular we study finite extensions of divisible abelian groups. We prove that superstable abelian-by-finite groups have only finitely many conjugacy classes of Sylow p-subgroups.

We consider Borel sets of finite rank $A \subseteq\Lambda^\omega$ where cardinality of Λ is less than some uncountable regular cardinal K. We obtain a "normal form" of A, by finding a Borel set Ω, such that A and Ω continuously reduce to each other. In more technical terms: we define simple Borel operations which are homomorphic to ordinal sum, to multiplication by a countable ordinal, and to ordinal exponentiation of base K, under the map which sends every Borel set (...) A of finite rank to its Wadge degree. (shrink)

Starting from a unitary, Lorentz invariant two-particle scattering amplitude, we show how to use an identification and replacement process to construct a unique, unitary particle–antiparticle amplitude. This process differs from conventional on-shell Mandelstam s, t, u crossing in that the input and constructed amplitudes can be off-diagonal and off-energy shell. Further, amplitudes are constructed using the invariant parameters which are appropriate to use as driving terms in the multi-particle, multichannel non-perturbative, cluster decomposable, relativistic scattering equations of the Faddeev-type integral equations (...) recently presented by Alfred, Kwizera, Lindesay and Noyes. It is therefore anticipated that when so employed, the resulting multi-channel solutions will also be unitary. The process preserves the usual particle–antiparticle symmetries. To illustrate this process, we construct a J=0 scattering length model chosen for simplicity. We also exhibit a class of physical models which contain a finite quantum mass parameter and are Lorentz invariant. These are constructed to reduce in the appropriate limits, and with the proper choice of value and sign of the interaction parameter, to the asymptotic solution of the non-relativistic Coulomb problem, including the forward scattering singularity, the essential singularity in the phase, and the Bohr bound-state spectrum. (shrink)

To each computable enumerable (c.e.) set A with a particular enumeration {As}s∈ω, there is associated a settling function mA(x), where mA(x) is the last stage when a number less than or equal to x was enumerated into A. One c.e. set A is settling time dominated by another set B (B >st A) if for every computable function f, for all but finitely many x, mB(x) > f(m₄(x)). This settling-time ordering, which is a natural extension to an ordering of the (...) idea of domination, was first introduced by Nabutovsky and Weinberger in [3] and Soare [6]. They desired a sequence of sets descending in this relationship to give results in differential geometry. In this paper we examine properties of the <st ordering. We show that it is not invariant under computable isomorphism, that any countable partial ordering embeds into it, that there are maximal and minimal sets, and that two c.e. sets need not have an inf or sup in the ordering. We also examine a related ordering, the strong settling-time ordering where we require for all computable f and g, for almost all x, mB(x) > f(mA(g(x))). (shrink)

It is consistent that each union of many families in the Baire space which are not finitely dominating is not dominating. In particular, it is consistent that for each nonprincipal ultrafilter , the cofinality of the reduced ultrapower is greater than . The model is constructed by oracle chain condition forcing, to which we give a self-contained introduction.

The large-structure tools of cohomology including toposes and derived categories stay close to arithmetic in practice, yet published foundations for them go beyond ZFC in logical strength. We reduce the gap by founding all the theorems of Grothendieck’s SGA, plus derived categories, at the level of Finite-Order Arithmetic, far below ZFC. This is the weakest possible foundation for the large-structure tools because one elementary topos of sets with infinity is already this strong.

We use certain strong Q-reducibilities, and their corresponding strong positive reducibilities, to characterize the hyperimmune sets and the hyperhyperimmune sets: if A is any infinite set then A is hyperimmune (respectively, hyperhyperimmune) if and only if for every infinite subset B of A, one has \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\overline{K}\not\le_{\rm ss} B}$$\end{document} (respectively, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\overline{K}\not\le_{\overline{\rm s}} B}$$\end{document}): here \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\le_{\overline{\rm (...) s}}}$$\end{document} is the finite-branch version of s-reducibility, ≤ss is the computably bounded version of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\le_{\overline{\rm s}}}$$\end{document}, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\overline{K}}$$\end{document} is the complement of the halting set. Restriction to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma^0_2}$$\end{document} sets provides a similar characterization of the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma^0_2}$$\end{document} hyperhyperimmune sets in terms of s-reducibility. We also show that no \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${A \geq_{\overline{\rm s}}\overline{K}}$$\end{document} is hyperhyperimmune. As a consequence, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\deg_{\rm s}(\overline{K})}$$\end{document} is hyperhyperimmune-free, showing that the hyperhyperimmune s-degrees are not upwards closed. (shrink)

We investigate the upper semilattice Eq* of recursively enumerable equivalence relations modulo finite differences. Several natural subclasses are shown to be first-order definable in Eq*. Building on this we define a copy of the structure of recursively enumerable many-one degrees in Eq*, thereby showing that Th has the same computational complexity as the true first-order arithmetic.

The problem of computational complexity of semantics for some natural language constructions – considered in [M. Mostowski, D. Wojtyniak 2004] – motivates an interest in complexity of Ramsey quantifiers in finite models. In general a sentence with a Ramsey quantifier R of the following form Rx, yH(x, y) is interpreted as ∃A(A is big relatively to the universe ∧A2 ⊆ H). In the paper cited the problem of the complexity of the Hintikka sentence is reduced to the problem of (...) computational complexity of the Ramsey quantifier for which the phrase “A is big relatively to the universe” is interpreted as containing at least one representative of each equivalence class, for some given equvalence relation. In this work we consider quantifiers Rf, for which “A is big relatively to the universe” means “card(A) > f (n), where n is the size of the universe”. Following [Blass, Gurevich 1986] we call R mighty if Rx, yH(x, y) defines N P – complete class of finite models. Similarly we say that Rf is N P –hard if the corresponding class is N P –hard. We prove the following theorems. (shrink)

In order to apply known general theorems about the effective properties of recursive structures in a particular recursive structure, it is necessary to verify that certain decidability conditions are satisfied. This requires the determination of when certain relations, called back and forth relations, hold between finite strings of elements from the structure. Here we determine this for recursive reduced abelian p-groups, thus enabling us to apply these theorems.

We present a completeness proof for Propositional Interval Temporal Logic with finite time which avoids certain difficulties of conventional methods. It is more gradated than previous efforts since we progressively reduce reasoning within the original logic to simpler reasoning in sublogics. Furthermore, our approach benefits from being less constructive since it is able to invoke certain theorems about regular languages over finite words without the need to explicitly describe the associated intricate proofs. A modified version of regular expressions (...) called Fusion Expressions is used as part of an intermediate logic called Fusion Logic. Both have the same expressiveness as PITL but are lower-level notations which play an important role in the hierarchical structure of the overall completeness proof. In particular, showing completeness for PITL is reduced to showing completeness for Fusion Logic. This in turn is shown to hold relative to completeness for conventional linear-time temporal logic with finite time. Logics based on regular languages over finite words and!-words offer a promising but elusive framework for formal specification and verification. A number of such logics and decision procedures have been proposed. In addition, various researchers have obtained complete axiom systems by embedding and expressing the decision procedures directly within the logics. The work described here contributes to this topic by showing how to exploit some interesting links between regular languages and interval-based temporal logics. (shrink)

In the present article, we consider the question of the primary elements in Plato’s Timaeus, the components of the whole universe reduced, by an extraordinarily elegant construction, to two right triangles. But how does he reconcile such a model with the infinite diversity of the universe? A large part of this study is devoted to Cornford’s explanation in his commentary of the Timaeus and its shortcomings, in order to finally propose a revised one, which we think to be entirely consistent (...) with Plato’s text. This analysis is an essential step for the understanding of the connection between the sensible world and the mathematical principles that underlies Timaeus’ cosmological account. (shrink)

Let ≤r and ≤sbe two binary relations on 2ℕ which are meant as reducibilities. Let both relations be closed under finite variation and consider the uniform distribution on 2ℕ, which is obtained by choosing elements of 2ℕ by independent tosses of a fair coin.Then we might ask for the probability that the lower ≤r-cone of a randomly chosen set X, that is, the class of all sets A with A ≤rX, differs from the lower ≤s-cone of X. By c (...) osure under finite variation, the Kolmogorov 0-1 aw yields immediately that this probability is either 0 or 1; in case it is 1, the relations are said to be separable by random oracles.Again by closure under finite variation, for every given set A, the probability that a randomly chosen set X is in the upper ≤r-cone of A is either 0 or 1; let Almostr be the class of sets for which the upper ≤r-cone has measure 1. In the following, results about separations by random oracles and about Almost classes are obtained in the context of generalized reducibilities, that is, for binary relations on 2ℕ which can be defined by a countable set of total continuous functionals on 2ℕ in the same way as the usual resource-bounded reducibilities are defined by an enumeration of appropriate oracle Turing machines. The concept of generalized reducibility comprises a natura resource-bounded reducibilities, but is more general; in particular, it does not involve any kind of specific machine model or even effectivity. The results on generalized reducibilities yield corollaries about specific resource-bounded reducibilities, including several results which have been shown previously in the setting of time or space bounded Turing machine computations. (shrink)