The article deals with finding finite total equivalence systems for formulas based on an arbitrary closed class of functions of several variables defined on the set {0, 1, 2} and taking values in the set {0,1} with the property that the restrictions of its functions to the set {0, 1} constitutes a closed class of Boolean functions. We consider all classes whose restriction closure is either the set of all functions of two-valued logic or the set T (...) a of functions preserving \. In each of these cases, we find a finite total equivalence system, construct a canonical type for formulas, and present a complete algorithm for determining whether any two formulas are equivalent. (shrink)

Clinical guidelines summarise available evidence on medical treatment, and provide recommendations about the most effective and cost-effective options for patients with a given condition. However, sometimes patients do not desire the best available treatment. Should doctors in a publicly-funded healthcare system ever provide sub-optimal medical treatment? On one view, it would be wrong to do so, since this would violate the ethical principle of beneficence, and predictably lead to harm for patients. It would also, potentially, be a misuse of (...) finite health resources. In this paper, we argue in favour of permitting sub-optimal choices on the basis of value pluralism, uncertainty, patient autonomy and responsibility. There are diverse views about how to evaluate treatment options, and patients’ right to self-determination and taking responsibility for their own lives should be respected. We introduce the concept of cost-equivalence, as a way of defining the boundaries of permissible pluralism in publicly-funded healthcare systems. As well as providing the most effective, available treatment for a given condition, publicly-funded healthcare systems should provide reasonable suboptimal medical treatments that are equivalent in cost to the optimal treatment. We identify four forms of cost-equivalence, and assess the implications of CE for decision-making. We evaluate and reject counterarguments to CE. Finally, we assess the relevance of CE for other treatment decisions including requests for potentially superior treatment. (shrink)

We show that a finitely generated protoalgebraic strict universal Horn class that is filter-distributive is finitely based. Equivalently, every protoalgebraic and filter-distributive multidimensional deductive system determined by a finite set of finite matrices can be presented by finitely many axioms and rules.

We show that a finitely generated protoalgebraic strict universal Horn class that is filter-distributive is finitely based. Equivalently, every protoalgebraic and filter-distributive multidimensional deductive system determined by a finite set of finite matrices can be presented by finitely many axioms and rules.

Notice that this paper has not claimed that all natural languages are CFL's. What it has shown is that every published argument purporting to demonstrate the non-context-freeness of some natural language is invalid, either formally or empirically or both.18 Whether non-context-free characteristics can be found in the stringset of some natural language remains an open question, just as it was a quarter century ago.Whether the question is ultimately answered in the negative or the affirmative, there will be interesting further questions (...) to ask. If it turns out that natural languages are indeed always CFL's, it will be reasonable to ask whether this helps to explain why speakers apparently recognize so quickly whether a presented utterance corresponds to a grammatical sentence or not, and to associate structural and semantic details with it. It might also be reasonable to speculate about the explanation for the universally context-free character of the languages used by humans, and to wonder whether evolutionary biological factors are implicated in some way (Sampson (1979) could be read in this light). And naturally, it will be reasonable to pursue the program put forward by Gazdar (1981, in press) to see to what extent CFL-inducing grammatical devices can be exploited to yield insightful descriptions of natural languages that capture generalizations in revealing ways.If a human language that is not a CFL is proved to exist, on the other hand, a different question will be raised: give the non-context-free character of human languages in general, why has this property been so hard to demonstrate that it has taken over twenty-five years to bring it to light since the issue was first explicitly posed? If human languages do not have to be CFL's, why do so many (most?) of them come so close to having the property of context-freeness? And, since the CFL's certainly constitute a very broad class of mathematically natural and computationally tractable languages, what property of human beings or their communicative or cognitive needs is it that has caused some linguistic communities to reach beyond the boundaries of this class in the course of evolving a linguistic system?Either way, we shall be interested to see our initial question resolved, and further questions raised. One cautionary word should be said, however, about the implications (or lack of them) that the answer will have for grammatical studies. Chomsky has repeatedly stated that he does not see weak generative capacity as a theme of central importance in the theory of grammar, and we agree. It is very far from being the case that the recent resurgence of interest in exploring the potential of CF-PSG or equivalent systems will, or should, be halted dead in its tracks by the discovery (if it is ever forthcoming) that some natural language is not a CFL. In the area of parsing, for instance, it seems possible that natural languages are not only parsed on the basis of constituent structure such as a CF-PSG would assign, but are parsed as if they were finite state languages (see Langendoen (1975) and Church (1980) for discussion along these lines). That is, precisely those construction-types that figure in the various proofs that English is not an FSL appear to cause massive difficulty in the human processing system; the sentences crucial to the proofs are for the most part unprocessable unless they are extremely short (yet the arguments for English not being and FSL only go through if length is not an issue). This means that in practice properties of finite state grammars are still of great potential importance to linguistic theory despite the fact that they do not provide the framework for defining the total class of grammatical sentences. The same would almost certannly be true of CF-PSG's if they were shown to be inadequate in a similar sense. It is highly unlikely that the advances made so far in far in phrase structure description could be nullified by a discovery about weak generative capacity. Moreover, there are known to be numerous ways in which the power of CF-PSG's can be marginally enhanced to permit, for example, xx languages to be generated without allowing anything like the full class of recursively enumerable or even context-sensitive languages (see Hopcroft and Ullmann (1979), Chapter 14) for an introduction to this topic, noting especially Figure 14.7 on p. 393. The obvious thing to do if natural languages were ever shown not to be CFL's in the general case would be to start exploring such minimal enhancements of expressive power to determine exactly what natural languages call for in this regard and how it could be effectively but parsimoniously provided in a way that closely modelled human linguistic capacities.In the meantime, it seems reasonable to assume that the natural languages are a proper subset of the infinite-cardinality CFL's until such time as they are validly shown not to be. (shrink)

In this note we develop a method for constructing finite totally-ordered m-zeroids and prove that there exists a categorical equivalence between the category of finite, totally-ordered m-zeroids and the category of pseudo Łukasiewicz-like implicators.

The paper continues a series of results on cut-rule axiomatizability of the Lambek calculus. It provides a complete solution of a problem which was solved partially in one of the author''s earlier papers. It is proved that the product-free Lambek Calculus with the empty string (L 0) is not finitely axiomatizable if the only rule of inference admitted is Lambek''s cut rule. The proof makes use of the (infinitely) cut-rule axiomatized calculus C designed by the author exactly for this purpose.

We explore the finite model theory of the characterisation theorems for modal and guarded fragments of first-order logic over transition systems and relational structures of width two. A new construction of locally acyclic bisimilar covers provides a useful analogue of the well known tree-like unravellings that can be used for the purposes of finite model theory. Together with various other finitary bisimulation respecting model transformations, and Ehrenfeucht–Fraïssé game arguments, these covers allow us to upgrade finite approximations for (...) full bisimulation equivalence towards approximations for elementary equivalence. These techniques are used to prove several ramifications of the van Benthem–Rosen characterisation theorem of basic modal logic for refinements of ordinary bisimulation equivalence, both in the sense of classical and of finite model theory. (shrink)

This paper investigates when two abstract logic-based argumentation systems are equivalent. It defines various equivalence criteria, investigates the links between them, and identifies cases where two systems are equivalent with respect to each of the proposed criteria. In particular, it shows that under some reasonable conditions on the logic underlying an argumentation system, the latter has an equivalent finite subsystem, called core. This core constitutes a threshold under which arguments of the system have not yet attained (...) their final status and consequently adding a new argument may result in status change. From that threshold, the statuses of all arguments become stable. (shrink)

We say that a linear ordering is extendible if every partial ordering that does not embed can be extended to a linear ordering which does not embed either. Jullien’s theorem is a complete classification of the countable extendible linear orderings. Fraïssé’s conjecture, which is actually a theorem, is the statement that says that the class of countable linear ordering, quasiordered by the relation of embeddability, contains no infinite descending chain and no infinite antichain. In this paper we study the strength (...) of these two theorems from the viewpoint of Reverse Mathematics and Effective Mathematics. As a result of our analysis we get that they are equivalent over the basic system of .We also prove that Fraïssé’s conjecture is equivalent, over , to two other interesting statements. One that says that the class of well founded labeled trees, with labels from {+,−}, and with a very natural order relation, is well quasiordered. The other statement says that every linear ordering which does not contain a copy of the rationals is equimorphic to a finite sum of indecomposable linear orderings.While studying the proof theoretic strength of Jullien’s theorem, we prove the extendibility of many linear orderings, including ω2 and η, using just . Moreover, for all these linear orderings, , we prove that any partial ordering, , which does not embed has a linearization, hyperarithmetic in , which does not embed. (shrink)

The open-domain Frame Problem is the problem of determining what features of an open task environment need to be updated following an action. Here we prove that the open-domain Frame Problem is equivalent to the Halting Problem and is therefore undecidable. We discuss two other open-domain problems closely related to the Frame Problem, the system identification problem and the symbol-grounding problem, and show that they are similarly undecidable. We then reformulate the Frame Problem as a quantum decision problem, and (...) show that it is undecidable by any finite quantum computer. (shrink)

Suppose one accepts the argument that past infinity is not acceptable. This does not eliminate the possibility that the beginning of time is not equivalent across objects. Along with breakdown of absolute simultaneity of events in relativity, there may even be no agreement on whether an event existed. There may be no consistent way to totally order events. In such a case, despite every object, conscious or not, having finite lifetime, there may be no single point called “the beginning,” (...) and the universe stays as it is without requiring a cause of existence. (shrink)

A cornerstone of physics, Maxwell‘s theory of electromagnetism, apparently contains a fatal flaw. The standard expressions for the electromagnetic field energy and the self-mass of an electron of finite extension do not obey Einstein‘s famous equation, \, but instead fulfill this relation with a factor 4/3 on the left-hand side. Furthermore, the energy and momentum of the electromagnetic field associated with the charge fail to transform as a four-vector. Many famous physicists have contributed to the debate of this so-called (...) 4/3-problem without arriving at a complete solution. It has generally been assumed that, as originally suggested by Poincaré, the problems are connected to the question of stability of the charge distribution, and that relativistic equivalence between energy and self-mass can only be restored by inclusion of stabilizing forces. Alternative solutions to the problems have also been proposed. Nearly a century ago Fermi suggested a covariant definition of the electromagnetic energy and momentum, and sixty years later Kalckar et al. argued that the 4/3 problem is caused by omission of a relativistic correction in the standard evaluation of the self-force from Coulomb self-interaction. However, the relation between these suggestions has not been clear. We show that the relativistic correction implies that the mechanical momentum of an accelerated rigid body must be defined as the sum of the momenta of its parts for fixed time in the momentary rest frame of the body. For the total momentum of particles and field to be conserved, the total energy–momentum tensor must be divergence free, and this then requires that the momentum of the associated electromagnetic field be defined in the same way, consistent with the suggestion by Fermi. This comprehensive solution of the 4/3-problem demonstrates that there is no conflict of Maxwell‘s theory with special relativity and the questions of equivalence of electromagnetic energy and self-mass and of stability of a classical charge distribution are independent. In appendices we discuss the relations of our treatment with Fermi‘s seminal paper and with a classic paper by Dirac where he evaluated the damping self-force on a point electron from transport of energy and momentum in the electromagnetic field. (shrink)

Local sentences and the formal languages they define were introduced by Ressayre in. We prove that locally finite ω‐languages and effective analytic sets have the same topological complexity: the Borel and Wadge hierarchies of the class of locally finite ω‐languages are equal to the Borel and Wadge hierarchies of the class of effective analytic sets. In particular, for each non‐null recursive ordinal there exist some ‐complete and some ‐complete locally finite ω‐languages, and the supremum of the set (...) of Borel ranks of locally finite ω‐languages is the ordinal, which is strictly greater than the first non‐recursive ordinal. This gives an answer to the question of the topological complexity of locally finite ω‐languages, which was asked by Simonnet and also by Duparc, Finkel, and Ressayre in. Moreover we show that the topological complexity of a locally finite ω‐language defined by a local sentence φ may depend on the models of the Zermelo‐Fraenkel axiomatic system. Using similar constructions as in the proof of the above results we also show that the equivalence, the inclusion, and the universality problems for locally finite ω‐languages are ‐complete, hence highly undecidable. (shrink)

We analyze the axiomatic strength of the following theorem due to Rival and Sands [28] in the style of reverse mathematics. Every infinite partial order P of finite width contains an infinite chain C such that every element of P is either comparable with no element of C or with infinitely many elements of C. Our main results are the following. The Rival–Sands theorem for infinite partial orders of arbitrary finite width is equivalent to $\mathsf {I}\Sigma ^0_{2} + (...) \mathsf {ADS}$ over $\mathsf {RCA}_0$. For each fixed $k \geq 3$, the Rival–Sands theorem for infinite partial orders of width $\leq \!k$ is equivalent to $\mathsf {ADS}$ over $\mathsf {RCA}_0$. The Rival–Sands theorem for infinite partial orders that are decomposable into the union of two chains is equivalent to $\mathsf {SADS}$ over $\mathsf {RCA}_0$. Here $\mathsf {RCA}_0$ denotes the recursive comprehension axiomatic system, $\mathsf {I}\Sigma ^0_{2}$ denotes the $\Sigma ^0_2$ induction scheme, $\mathsf {ADS}$ denotes the ascending/descending sequence principle, and $\mathsf {SADS}$ denotes the stable ascending/descending sequence principle. To the best of our knowledge, these versions of the Rival–Sands theorem for partial orders are the first examples of theorems from the general mathematics literature whose strength is exactly characterized by $\mathsf {I}\Sigma ^0_{2} + \mathsf {ADS}$, by $\mathsf {ADS}$, and by $\mathsf {SADS}$. Furthermore, we give a new purely combinatorial result by extending the Rival–Sands theorem to infinite partial orders that do not have infinite antichains, and we show that this extension is equivalent to arithmetical comprehension over $\mathsf {RCA}_0$. (shrink)

. The paper presents a method for transforming a given sound and complete n-sequent proof system into an equivalent sound and complete system of ordinary sequents. The method is applicable to a large, central class of (generalized) finite-valued logics with the language satisfying a certain minimal expressiveness condition. The expressiveness condition decrees that the truth-value of any formula φ must be identifiable by determining whether certain formulas uniformly constructed from φ have designated values or not. The transformation (...) preserves the general structure of proofs in the original calculus in a way ensuring preservation of the weak cut elimination theorem under the transformation. The described transformation metod is illustrated on several concrete examples of many-valued logics, including a new application to information sources logics. (shrink)

Labeled transition systems are key structures for modeling computation. In this paper, we show how they lend themselves to ordinary logical analysis (without any special new formalisms), by introducing their standard first-order theory. This perspective enables us to raise several basic model-theoretic questions of definability, axiomatization and preservation for various notions of process equivalence found in the computational literature, and answer them using well-known logical techniques (including the Compactness theorem, Saturation and Ehrenfeucht games). Moreover, we consider what happens to (...) this general theory when one restricts attention to special classes of transition systems (in particular, finite ones), as well as extended logical languages (in particular, infinitary first-order logic). We hope that this puts standard logical formalisms on the map as a serious option for a theory of computational processes. As a side benefit, our approach increases comparability with several other existing formalisms over labeled transition systems (such as Process Algebra or Modal Logic). We provide some pointers to this effect, too. (shrink)

of monadic or relational predicate calculus (Fa, Gb, Rab, Hcd, etc.). • The Boolean Algebra BL set-up by such a language will be such that: – BL will have 2 n states (corresponding to the state descriptions of L) – BL will contain 2 2n propositions, in total. ∗ This is because each proposition p in BL is equivalent to a disjunction of state descriptions. Thus, each subset of the set of..

There is a constructive method to define a structure of simple k -cyclic Post algebra of order p , L p , k , on a given finite field F ( p k ), and conversely. There exists an interpretation Φ 1 of the variety $${\mathcal{V}(L_{p,k})}$$ generated by L p , k into the variety $${\mathcal{V}(F(p^k))}$$ generated by F ( p k ) and an interpretation Φ 2 of $${\mathcal{V}(F(p^k))}$$ into $${\mathcal{V}(L_{p,k})}$$ such that Φ 2 Φ 1 ( B (...) ) = B for every $${B \in \mathcal{V}(L_{p,k})}$$ and Φ 1 Φ 2 ( R ) = R for every $${R \in \mathcal{V}(F(p^k))}$$. In this paper we show how we can solve an algebraic system of equations over an arbitrary cyclic Post algebra of order p, p prime, using the above interpretation, Gröbner bases and algorithms programmed in Maple. (shrink)

Labeled transition systems are key structures for modeling computation. In this paper, we show how they lend themselves to ordinary logical analysis (without any special new formalisms), by introducing their standard first-order theory. This perspective enables us to raise several basic model-theoretic questions of definability, axiomatization and preservation for various notions of process equivalence found in the computational literature, and answer them using well-known logical techniques (including the Compactness theorem, Saturation and Ehrenfeucht games). Moreover, we consider what happens to (...) this general theory when one restricts attention to special classes of transition systems (in particular, finite ones), as well as extended logical languages (in particular, infinitary first-order logic). We hope that this puts standard logical formalisms on the map as a serious option for a theory of computational processes. As a side benefit, our approach increases comparability with several other existing formalisms over labeled transition systems (such as Process Algebra or Modal Logic). We provide some pointers to this effect, too. (shrink)

It is an old idea, lately out of fashion but now experiencing a revival, that quantum mechanics may best be understood, not as a physical theory with a problematic probabilistic interpretation, but as something closer to a probability calculus per se. However, from this angle, the rather special C *-algebraic apparatus of quantum probability theory stands in need of further motivation. One would like to find additional principles, having clear physical and/or probabilistic content, on the basis of which this apparatus (...) can be reconstructed. In this paper, I explore one route to such a derivation of finite-dimensional quantum mechanics, by means of a set of strong, but probabilistically intelligible, axioms. Stated very informally, these require that systems appear completely classical as restricted to a single measurement, that different measurements, and likewise different pure states, be equivalent (up to the action of a compact group of symmetries), and that every state be the marginal of a bipartite non-signaling state perfectly correlating two measurements. This much yields a mathematical representation of (basic, discrete) measurements as orthonormal subsets of, and states, by vectors in, an ordered real Hilbert space – in the quantum case, the space of Hermitian operators, with its usual tracial inner product. One final postulate (a simple minimization principle, still in need of a clear interpretation) forces the positive cone of this space to be homogeneous and self-dual and hence, to be the state space of a formally real Jordan algebra. From here, the route to the standard framework of finite-dimensional quantum mechanics is quite short. (shrink)

A partition $\{C_i\}_{i\in I}$ of a Boolean algebra $\cS$ in a probability measure space $(\cS,p)$ is called a Reichenbachian common cause system for the correlated pair $A,B$ of events in $\cS$ if any two elements in the partition behave like a Reichenbachian common cause and its complement, the cardinality of the index set $I$ is called the size of the common cause system. It is shown that given any correlation in $(\cS,p)$, and given any finite size $n>2$, (...) the probability space $(\cS,p)$ can be embedded into a larger probability space in such a manner that the larger space contains a Reichenbachian common cause system of size $n$ for the correlation. It also is shown that every totally ordered subset in the partially ordered set of all partitions of \cS$ contains only one Reichenbachian common cause system. Some open problems concerning Reichenbachian common cause systems are formulated. (shrink)

BackgroundThe principle of equivalence in prison health has been established for nearly four decades. It seeks to ensure that prisoners have access to the same level of healthcare as members of society at large, which is entrenched within the international legal framework and England’s national health policies.AimsThis study examined how key policymakers interpret and implement the principle of equivalence in English prisons. It also identified opportunities and threats associated with the application of the principle.MethodsIn total, 30 policymakers (...) took part in this research. These participants engaged in policymaking activities and occupied positions of authority in the prison field.ResultsDespite the policymakers’ consensus on the importance of the equivalence principle, there was a varying degree of understanding regarding what constitutes ‘equivalence’. Participants described how the security culture impedes prisoners’ access to healthcare services. Additionally, the increasing size and complexity of the prison population, coupled with a diminishing level of resources, reduce the level of care being provided in prisons and thus compromise implementation of equivalence in English prisons.ConclusionsInconsistent interpretation of equivalence, the prevailing security drive, increasing numbers and health complexities of prisoners and fiscal austerity threaten the implementation of equivalence in English prisons. This research calls for new guidance on how to interpret and implement equivalence, along with measures to educate prison governors and staff on the prison rehabilitation value, ensure greater investment in prison health and consider alternatives to imprisonment to future-proof the principle of equivalence in the English prison system. (shrink)

Peter Kosso discusses the weak gravitational lensing observations of the Bullet Cluster and argues that dark matter can be detected in this system solely through the equivalence principle without the need to specify a full theory of gravity. This paper argues that Kosso gets some of the details wrong in his analysis of the implications of the Bullet Cluster observations for the Dark Matter Double Bind and the possibility of constructing robust tests of theories of gravity at galactic (...) and greater scales. Even the Bullet Cluster evidence is not sufficiently detailed to allow precision tests of General Relativity that would distinguish it from its rivals at galactic and greater scales. Taking into account the total evidence available, we cannot rule out “ugly” solutions to the dynamical discrepancy in astrophysics that involve both a large quantity of dark matter and a theory of gravity whose predictions differ significantly from those of General Relativity for interactions taking place at galactic and greater scales. (shrink)

We present a version of arithmetic in all finite types based on a systematic use of an internally definable notion of observational equivalence for dealing with equalities at higher types. For this system both intensional and extensional models are possible, the deduction theorem holds and the soundness of the Dialectica interpretation is provable inside the system itself.

A fundamental link between system theory and statistical mechanics has been found to be established by the Kolmogorov entropy K. By this quantity the temporal evolution of dynamical systems can be classified into regular, chaotic, and stochastic processes. Since K represents a measure for the internal information creation rate of dynamical systems, it provides an approach to irreversibility. The formal relationship to statistical mechanics is derived by means of an operator formalism originally introduced by Prigogine. For a Liouville operator (...) L and an information operator $\tilde M$ acting on a distribution in phase space, it is shown that i[L, $\tilde M$ ]≡KI (I=identity operator). As a first consequence of this equivalence, a relation is obtained between the chaotic correlation time of a system and Prigogine's concept of a “finite duration of presence.” Finally, the existence of chaos in quantum systems is discussed with respect to the existence of a quantum mechanical time operator. (shrink)

I wish to discuss some rather incomplete ideas concerning difficulties that arise in some parts of quantum mechanics. In general there have been no serious difficulties when we are dealing with a finite number of particles, but very essential difficulties arise as soon as we treat a system having an infinite number of degrees of freedom; for example, the theory of holes, which, because of the pair generation, requires an indefinite number of particles; also the Dirac non-relativistic theory (...) of light and the Pauli-Heisenberg relativistic quantum electro-dynamics, these being equivalent to systems consisting of an infinite number of particles. (shrink)

Computers are increasingly interactive. They are no more transformational systems producing a final output after a finite execution. Instead, they continuously react in time to external events that modify the course of computing execution. While philosophers have been interested in conceptualizing computers for a long time, they seem to have paid little attention to the specificities of interactive computing. We propose to tackle this issue by surveying the literature in theoretical computer science, where one can find explicit proposals for (...) a model of interactive computing. In that field, the formal modelling of interactive computing systems has been brought down to whether the new interaction models are reducible to Turing Machines. There are three areas where interaction models are framed. The comparison between TMs and interactive system models is at stake in all of them. These areas are namely some works on concurrency by Milner, on Reactive Turing Machines, and on interaction as a new computing paradigm. For each of the three identified models, we present its motivation, sum up its account for interaction and its legacy, and point out issues regarding the understanding of computers. The survey shows difficulties for epistemologists. The reason is that these analyses focus on the formal equivalence between interactive models of computation and classic ones. Such a project is different from addressing how a computing machine can be interactive: in other words, which mechanisms allow it. (shrink)

An Ackermann constant is a formula of sentential logic built up from the sentential constant t by closing under connectives. It is known that there are only finitely many non-equivalent Ackermann constants in the relevant logic R. In this paper it is shown that the most natural systems close to R but weaker than it-in particular the non-distributive system LR and the modalised system NR-allow infinitely many Ackermann constants to be distinguished. The argument in each case proceeds by (...) construction of an algebraic model, infinite in the case of LR and of arbitrary finite size in the case of NR. The search for these models was aided by the computer program MaGIC (Matrix Generator for Implication Connectives) developed by the author at the Australian National University. (shrink)

We here present explicit relational theories of a class of geometrical systems (namely, inner product spaces) which includes Euclidean space and Minkowski spacetime. Using an embedding approach suggested by the theory of measurement, we prove formally that our theories express the entire empirical content of the corresponding geometric theory in terms of empirical relations among a finite set of elements (idealized point-particles or events) thought of as embedded in the space. This result is of interest within the general phenomenalist (...) tradition as well as the theory of space and time, since it seems to be the first example of an explicit phenomenalist reconstruction of a realist theory which is provably equivalent to it in observational consequences. The interesting paper "On the Space-Time Ontology of Physical Theories" by Ken Manders, Philosophy of Science, vol. 49, number 4, December 1982, p. 575-590, has significant affinities to this one. We both, in a sense, try to formally vindicate Leibniz's notion of a relational theory of space, by constructing theories of spatial relations among physical objects which are provably equivalent to the standard absolutist theories. The essential difference between our approaches is that Manders retains Leibniz's explicitly modal framework, whereas I do not. Manders constructs a spacetime theory which explicitly characterizes the totality of possible configurations of physical objects, using a modal language in which the notion of a possible configuration occurs as a primitive. There is no doubt that this is a more accurate realization of Leibniz's own conception of space than the embedding-based approach developed here. However, it also remains open to objections (such as those cited here from Sklar) on account of the special appeal to modal notions. Our approach here, by contrast, aims to avoid the special appeal to modal notions by giving directly a set of laws which are satisfied by a configuration individually, if and only if it is one of the allowable ones. One thus avoids the need for reference to possible but not actual configurations or objects, in the statement of the spacetime laws. We may then take this alternative set of laws as the actual geometric theory, and do away with the hypothetical entity called 'space'. Yet at the same time there is no invocation of modality, except in the ordinary sense in which every physical theory constrains what is possible. So that a relationalist is not forced to utilize a modal language (though Leibniz certainly does.). (shrink)

.A term rewrite system is called simply terminating if its termination can be shown by means of a simplification ordering. According to a result of Weiermann, the derivation length function of any simply terminating finite rewrite system is eventually dominated by a Hardy function of ordinal less than the small Veblen ordinal. This bound had appeared to be of rather theoretical nature, because all known examples had had multiple recursive complexities, until recently Touzet constructed simply terminating examples (...) with complexities beyond multiple recursion. This was established by simulating the Hydra battle for all ordinal segments below the proof-theoretic ordinal of Peano arithmetic. By extending this result to the small Veblen ordinal we prove the huge bound of Weiermann to be sharp. As a spin-off we can show that total termination allows for complexities as high as those of simple termination. (shrink)

It has often been argued that Gödel’s first incompleteness theorem has major implications for our understanding of the human mind. Gödel himself hoped that the results of his theorem, combined with Turning’s work on computers and phenomenological analysis, would establish that the human mind contains an element totally different from a finite combinatorial mechanism. Decades of attempts to establish this by reasoning about Gödel’s theorem and Turing’s work are now widely taken to be unsuccessful. The present article, in accord (...) with Gödel’s suggestion, adds extended phenomenological analysis to the discussion. It also focuses on the “going outside the system” step central to Gödel’s method of proof, rather than on the implications of the theorem itself. Analysis of the “I-it” intentional structure, held by phenomenology to underlie all ordinary experience, yields a simple model that (i) resolves long-standing conceptual problems associated with the “I-it”, the most basic structure of phenomenology, (ii) clarifies the “going outside” step crucial to Gödel’s method of proof, (iii) avoids conceptual problems associated with this step, (iv) identifies the step as an instance of a natural pre-mathematical operation of ordinary thought, and (v) suggests that the step itself is intrinsically non-algorithmic. Logical analysis of role of this step in Gödel’s proof then shows, independently of phenomenological considerations, that anything (human or not) that can prove Gödel’s theorem soundly by his method cannot be entirely algorithmic. Further implications for the nature of the mind are then suggested. (shrink)

Logic is traditionally considered to be a purely syntactic discipline, at least in principle. However, prof. David Isles has shown that this ideal is not yet met in traditional logic. Semantic residue is present in the assumption that the domain of a variable should be fixed in advance of a derivation, and also in the notion that a numerical notation must refer to a number rather than be considered a mathematical object in and of itself. Based on his work, the (...) central question of this thesis is what kind of logic, if any, results from removing this semantic residue from traditional logic.We differ from traditional logic in two significant ways. The first is that the assumption that a numerical notation must refer to a number is denied. Numerical notations are considered as mathematical objects in their own right, related to each other by means of rewrite rules. The traditional notion of reference is then replaced by the notion of reduction (by means of the rewrite rules) to a normal form. Two numerical notations that reduce to the same normal form would traditionally be considered identical, as they would refer to the same number, and hence they would be interchangeable salva veritate. In the new system, called Buridan-Volpin (BV), the numerical notations themselves are the elements of the domains of variables, and two numerical notations that reduce to the same normal form need not be interchangeable salva veritate, except when they are syntactically identical (i.e., have the same Gödel number).The second is that we do away with the assumption that the domains of variables need to be fixed in advance of a derivation. Instead we focus on what is needed to guarantee preservation of truth in every step of a derivation. These conditions on the domains of the variables, accumulated in the course of a derivation, are combined in a reference grammar. Whereas traditionally a derivation is considered valid when the conclusion follows from the premisses by way of the derivation rules (and possibly axioms), in the BV system a derivation must meet the extra condition that no inconsistency occurs within the reference grammar. For if the reference grammar were to give rise to inconsistency (i.e., it would be impossible to assign domains to all the variables without breaking at least one of the conditions placed on them in the reference grammar), there is no longer a guarantee that truth has been preserved in every step of the derivation, and hence the truth of the conclusion is not guaranteed by the derivation.In Chapter 2 the BV system is introduced in some formal detail. Chapter 3 gives some examples of derivations, notably totality of addition, multiplication and exponentiation, as well as a lemma needed for the proof of Euclid’s Theorem. These examples, taken from prof. Isles’ First-Order Reasoning and Primitive Recursive Natural Number Notations, show that there is a real proof-theoretical difference between traditional logic and the BV system. Here we also find the first major point of departure between myself and prof. Isles, centered on the notion of inheritance of conditions in the reference grammar by way of lemmata. These different points of view are best illustrated in the sections on the totality of exponentiation and on Euclid’s Lemma: prof. Isles maintains that the proof of totality of exponentiation is not BV valid, while I maintain that it is. But I do agree with him that the traditional proof of Euclid’s Lemma is not BV valid. Chapter 6 also expands the arguments for my choice in this matter.Now that it has been shown that there is a difference between traditional logic and BV, the properties of BV need to be examined. In Chapter 4 we give a proof of Cut-elimination for BV minus induction and the subformula property for BV, which allows us to prove the consistency of BV minus induction. We also expand on the reasons for excluding induction. In Chapter 5 we consider in detail the proof of a finite analog to the Löwenheim–Skolem theorem given by prof. Isles in his article with the same title. He proves that under certain conditions it is always possible, given the existence of a (possibly uncountable) model for a derivation, to give a finite model for this derivation. The system he considers deviates from BV as considered in this thesis in two significant ways: it does not contain the induction rule and the domains contain numbers instead of numerical notations. We then go on to show that it is possible to extend the result to include induction, in the sense that the existence of a possibly uncountable model for a derivation guarantees the existence of a model that is at most countable. We also consider the complications that arise from taking numerical expressions instead of numbers as the elements of domains.Finally, in Chapter 6 we consider the philosophical consequences of the BV system, informed by the formal results from the previous chapters. In particular we discuss the relation between reduction and reference, the status of reference grammars, the notion of induction and its function within BV, and some brief considerations on the consequences of the BV system for the discussion regarding nominalism and realism with regard to mathematical objects. The object of the chapter is twofold. On the one hand applying the formal results to philosophical questions, on the other hand arguing that BV is not just a theoretically acceptable alternative to traditional logic, but is in fact deserving of further development and research into its properties. The latter will probably appeal most to those of a nominalist and/or finitist bent.Abstract prepared by Harrie de Swart and Sven Storms.E-mail:[email protected]:https://research.tilburguniversity.edu/files/6170 1294/Storms_The_Buridan_Volpin_04_05_2022.pdf. (shrink)

A fast consistency prover is a consistent polytime axiomatized theory that has short proofs of the finite consistency statements of any other polytime axiomatized theory. Krajíček and Pudlák have proved that the existence of an optimal propositional proof system is equivalent to the existence of a fast consistency prover. It is an easy observation that NP = coNP implies the existence of a fast consistency prover. The reverse implication is an open question. In this paper we define the (...) notion of an unlikely fast consistency prover and prove that its existence is equivalent to NP = coNP. Next it is proved that fast consistency provers do not exist if one considers RE axiomatized theories rather than theories with an axiom set that is recognizable in polynomial time. (shrink)

C I Lewis showed up Down Under in 2005, in e-mails initiated by Allen Hazen of Melbourne. Their topic was the system Hazen called FL (a Funny Logic), axiomatized in passing in Lewis 1921. I show that FL is the system MEN of material equivalence with negation. But negation plays no special role in MEN. Symbolizing equivalence with → and defining ∼A inferentially as A→f, the theorems of MEN are just those of the underlying theory ME (...) of pure material equivalence. This accords with the treatment of negation in the Abelian l-group logic A of Meyer and Slaney (Abelian logic. Abstract, Journal of Symbolic Logic 46, 425–426, 1981), which also defines ∼A inferentially with no special conditions on f. The paper then concentrates on the pure implicational part AI of A, the simple logic of Abelian groups. The integers Z were known to be characteristic for AI, with every non-theorem B refutable mod some Zn for finite n. Noted here is that AI is pre-tabular, having the Scroggs property that every proper extension SI of AI, closed under substitution and detachment, has some finite Zn as its characteristic matrix. In particular FL is the extension for which n = 2 (Lewis, The structure of logic and its relation to other systems. The Journal of Philosophy 18, 505–516, 1921; Meyer and Slaney, Abelian logic. Abstract. Journal of Symbolic Logic 46, 425–426, 1981; This is an abstract of the much longer paper finally published in 1989 in G. G. Priest, R. Routley and J. Norman, eds., Paraconsistent logic: essays on the inconsistent, Philosophica Verlag, Munich, pp. 245–288, 1989). (shrink)

C I Lewis showed up Down Under in 2005, in e-mails initiated by Allen Hazen of Melbourne. Their topic was the system Hazen called FL (a Funny Logic), axiomatized in passing in Lewis 1921. I show that FL is the system MEN of material equivalence with negation. But negation plays no special role in MEN. Symbolizing equivalence with → and defining ∼A inferentially as A→f, the theorems of MEN are just those of the underlying theory ME (...) of pure material equivalence. This accords with the treatment of negation in the Abelian l-group logic A of Meyer and Slaney (Abelian logic. Abstract, Journal of Symbolic Logic 46, 425–426, 1981), which also defines ∼A inferentially with no special conditions on f. The paper then concentrates on the pure implicational part AI of A, the simple logic of Abelian groups. The integers Z were known to be characteristic for AI, with every non-theorem B refutable mod some Zn for finite n. Noted here is that AI is pre-tabular, having the Scroggs property that every proper extension SI of AI, closed under substitution and detachment, has some finite Zn as its characteristic matrix. In particular FL is the extension for which n = 2 (Lewis, The structure of logic and its relation to other systems. The Journal of Philosophy 18, 505–516, 1921; Meyer and Slaney, Abelian logic. Abstract. Journal of Symbolic Logic 46, 425–426, 1981; This is an abstract of the much longer paper finally published in 1989 in G. G. Priest, R. Routley and J. Norman, eds., Paraconsistent logic: essays on the inconsistent, Philosophica Verlag, Munich, pp. 245–288, 1989). (shrink)

There exist two conjectures for constraint satisfaction problems of reducts of finitely bounded homogeneous structures: the first one states that tractability of the CSP of such a structure is, when the structure is a model-complete core, equivalent to its polymorphism clone satisfying a certain nontrivial linear identity modulo outer embeddings. The second conjecture, challenging the approach via model-complete cores by reflections, states that tractability is equivalent to the linear identities satisfied by its polymorphisms clone, together with the natural uniformity on (...) it, being nontrivial. We prove that the identities satisfied in the polymorphism clone of a structure allow for conclusions about the orbit growth of its automorphism group, and apply this to show that the two conjectures are equivalent. We contrast this with a counterexample showing that [Formula: see text]-categoricity alone is insufficient to imply the equivalence of the two conditions above in a model-complete core. Taking another approach, we then show how the Ramsey property of a homogeneous structure can be utilized for obtaining a similar equivalence under different conditions. We then prove that any polymorphism of sufficiently large arity which is totally symmetric modulo outer embeddings of a finitely bounded structure can be turned into a nontrivial system of linear identities, and obtain nontrivial linear identities for all tractable cases of reducts of the rational order, the random graph, and the random poset. Finally, we provide a new and short proof, in the language of monoids, of the theorem stating that every [Formula: see text]-categorical structure is homomorphically equivalent to a model-complete core. (shrink)

We introduce a second-order system V1-Horn of bounded arithmetic formalizing polynomial-time reasoning, based on Grädel's 35) second-order Horn characterization of P. Our system has comprehension over P predicates , and only finitely many function symbols. Other systems of polynomial-time reasoning either allow induction on NP predicates , and hence are more powerful than our system , or use Cobham's theorem to introduce function symbols for all polynomial-time functions . We prove that our system is equivalent to (...) QPV and Zambella's P-def. Using our techniques, we also show that V1-Horn is finitely axiomatizable, and, as a corollary, that the class of Σ1b consequences of S21 is finitely axiomatizable as well, thus answering an open question. (shrink)

Robust techniques critically improve bearing-only target localization when the relevant measurements are being corrupted by impulsive noise. Resistance to isolated gross errors refers to the conventional least absolute residual method, and its estimate can be determined by linear programming when pseudolinear equations are set. The LAR approach, however, cannot reduce the bias attributed to the correlation between system matrices and noise vectors. In the present study, perturbations are introduced into the elements of the system matrix and the data (...) vector simultaneously, and the total optimization problem is formulated based on least absolute deviations. Subsequently, an equivalent form of total least absolute residuals is obtained, and an algorithm is developed to calculate the robust estimate by dual ascent algorithms. Moreover, the performance of the proposed method is verified through the numerical simulations by using two types of localization geometries, i.e., random and linear. As revealed from the results, the TLAR algorithm is capable of exhibiting significantly higher localization accuracy as compared with the LAR method. (shrink)

We investigate the substitution Frege () proof system and its relationship to extended Frege () in the context of modal and superintuitionistic propositional logics. We show that is p-equivalent to tree-like , and we develop a “normal form” for -proofs. We establish connections between for a logic L, and for certain bimodal expansions of L.We then turn attention to specific families of modal and si logics. We prove p-equivalence of and for all extensions of , all tabular logics, (...) all logics of finite depth and width, and typical examples of logics of finite width and infinite depth. In most cases, we actually show an equivalence with the usual system for classical logic with respect to a naturally defined translation.On the other hand, we establish exponential speed-up of over for all modal and si logics of infinite branching, extending recent lower bounds by P. Hrubeš. We develop a model-theoretical characterization of maximal logics of infinite branching to prove this result. (shrink)

The aim of this paper is to give one kind of internal proportional systems with general representation and without closure and finiteness assumptions. First, we introduce the notions of internal proportional system and of general representation. Second, we briefly review the existing results which motivate our generalization. Third, we present the new systems, characterized by the fact that the linear order induced by the comparison weak order ≥ at the level of equivalence classes is also a weIl order. (...) We prove the corresponding representation theorem and make some comments on strong limitations of uniqueness; we present in an informal way a positive result, restricted uniqueness for what we call connected objects. We conclude with some final remarks on the property that characterizes these systems and on three possible empirical applications. (shrink)

The aim of this paper is to give one kind of internal proportional systems with general representation and without closure and finiteness assumptions. First, we introduce the notions of internal proportional system and of general representation. Second, we briefly review the existing results which motivate our generalization. Third, we present the new systems, characterized by the fact that the linear order induced by the comparison weak order ≥ at the level of equivalence classes is also a weIl order. (...) We prove the corresponding representation theorem and make some comments on strong limitations of uniqueness; we present in an informal way a positive result, restricted uniqueness for what we call connected objects. We conclude with some final remarks on the property that characterizes these systems and on three possible empirical applications. (shrink)

We investigate sequent calculi for the weak modal (propositional) system reduced to the equivalence rule and extensions of it up to the full Kripke system containing monotonicity, conjunction and necessitation rules. The calculi have cut elimination and we concentrate on the inversion of rules to give in each case an effective procedure which for every sequent either furnishes a proof or a finite countermodel of it. Applications to the cardinality of countermodels, the inversion of rules and (...) the derivability of Löb rules are given. (shrink)

This paper proposes an extension of Chaitin's halting probability Ω to a measurement operator in an infinite dimensional quantum system. Chaitin's Ω is defined as the probability that the universal self-delimiting Turing machine U halts, and plays a central role in the development of algorithmic information theory. In the theory, there are two equivalent ways to define the program-size complexity H of a given finite binary string s. In the standard way, H is defined as the length of (...) the shortest input string for U to output s. In the other way, the so-called universal probability m is introduced first, and then H is defined as –log2m without reference to the concept of program-size.Mathematically, the statistics of outcomes in a quantum measurement are described by a positive operator-valued measure in the most general setting. Based on the theory of computability structures on a Banach space developed by Pour-El and Richards, we extend the universal probability to an analogue of POVM in an infinite dimensional quantum system, called a universal semi-POVM. We also give another characterization of Chaitin's Ω numbers by universal probabilities. Then, based on this characterization, we propose to define an extension of Ω as a sum of the POVM elements of a universal semi-POVM. The validity of this definition is discussed.In what follows, we introduce an operator version equation image of H in a Hilbert space of infinite dimension using a universal semi-POVM, and study its properties. (shrink)

The theory of rough sets starts with the notion of an approximation space , which is a pair ( U , R ), U being the domain of discourse, and R an equivalence relation on U . R is taken to represent the knowledge base of an agent, and the induced partition reflects a granularity of U that is the result of a lack of complete information about the objects in U . The focus then is on approximations of (...) concepts on the domain, in the context of the granularity. The present article studies the theory in the situation where information is obtained from different sources. The notion of approximation space is extended to define a multiple-source approximation system with distributed knowledge base , which is a tuple , where N is a set of sources and P ranges over all finite subsets of N . Each R P is an equivalence relation on U satisfying some additional conditions, representing the knowledge base of the group P of sources. Thus each finite group of sources and hence individual source perceives the same domain differently (depending on what information the group/individual source has about the domain), and the same concept may then have approximations that differ with the groups. In order to express the notions and properties related with rough set theory in this multiple-source situation, a quantified modal logic LMSAS D is proposed. In LMSAS D , quantification ranges over modalities, making it different from modal predicate logic and modal logic with propositional quantifiers. Some fragments of LMSAS D are discussed and it is shown that the modal system KTB is embedded in LMSAS D . The epistemic logic is also embedded in LMSAS D , and cannot replace the latter to serve our purpose. The relationship of LMSAS D with first and second-order logics is presented. Issues of expressibility, axiomatization and decidability are addressed. (shrink)

A proof-theoretical analysis of finite-valuedness in the domain of cumulative inference systems is presented.