A number of philosophers have attempted to solve the problem of null-probability possible events in Bayesian epistemology by proposing that there are infinitesimal probabilities. Hájek and Easwaran have argued that because there is no way to specify a particular hyperreal extension of the real numbers, solutions to the regularity problem involving infinitesimals, or at least hyperreal infinitesimals, involve an unsatisfactory ineffability or arbitrariness. The arguments depend on the alleged impossibility of picking out a particular hyperreal extension of the real numbers (...) and/or of a particular value within such an extension due to the use of the Axiom of Choice. However, it is false that the Axiom of Choice precludes a specification of a hyperreal extension—such an extension can indeed be specified. Moreover, for all we know, it is possible to explicitly specify particular infinitesimals within such an extension. Nonetheless, I prove that because any regular probability measure that has infinitesimal values can be replaced by one that has all the same intuitive features but other infinitesimal values, the heart of the arbitrariness objection remains. (shrink)

Operators which map subsets of a given set to the set of their minimal elements with respect to some relation R form the basis of a semanticapproach in non-monotonic logic, belief revision, conditional logic and updating. In this paper we investigate operators of this type from an algebraicviewpoint. A representation theorem is proved and various properties of theresulting algebras are investigated. It is shown that they behave quite differently from known algebras related to logics, e.g. modal algebras and Heytingalgebras.

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)

Frege’s project has been characterized as an attempt to formulate a complete system of logic adequate to characterize mathematical theories such as arithmetic and set theory. As such, it was seen to fail by Gödel’s incompleteness theorem of 1931. It is argued, however, that this is to impose a later interpretation on the word ‘complete’ it is clear from Dedekind’s writings that at least as good as interpretation of completeness is categoricity. Whereas few interesting first-order mathematical theories are categorical or (...) complete, there are logical extensions of these theories into second-order and by the addition of generalized quantifiers which are categorical. Frege’s project really found success through Gödel’s completeness theorem of 1930 and the subsequent development of first- and higher-order model theory. (shrink)

This paper is essentially the author's Gödel Lecture at the ASL Logic Colloquium '09 in Sofia extended and supplemented by material from some other papers. After a brief description of traditional reverse mathematics, a computational approach to is presented. There are then discussions of some interactions between reverse mathematics and the major branches of mathematical logic in terms of the techniques they supply as well as theorems for analysis. The emphasis here is on ones that lie outside the usual main (...) systems of reverse mathematics. While retaining the usual base theory and working still within second order arithmetic, theorems are described that range from those far below the usual systems to ones far above. (shrink)

Khoussainov and Nerode [14] posed various open questions on model-theoretic properties of automatic structures. In this work we answer some of these questions by showing the following results: There is an uncountably categorical but not countably categorical theory for which only the prime model is automatic; There are complete theories with exactly 3,4,5,…3,4,5,… countable models, respectively, and every countable model is automatic; There is a complete theory for which exactly 2 models have an automatic presentation; If LOGSPACE=PLOGSPACE=P then there is (...) an uncountably categorical but not countably categorical theory for which the prime model does not have an automatic presentation but all the other countable models are automatic; There is a complete theory with countably many countable models for which the saturated model has an automatic presentation but the prime model does not have one. (shrink)

Many important concepts of the calculus are difficult to grasp, and they may appear epistemologically unjustified. For example, how does a real function appear in “small” neighborhoods of its points? How does it appear at infinity? Diagrams allow us to overcome the difficulty in constructing representations of mathematical critical situations and objects. For example, they actually reveal the behavior of a real function not “close to” a point (as in the standard limit theory) but “in” the point. We are interested (...) in our research in the diagrams which play an optical role –microscopes and “microscopes within microscopes”, telescopes, windows, a mirror role (to externalize rough mental models), and an unveiling role (to help create new and interesting mathematical concepts, theories, and structures). In this paper we describe some examples of optical diagrams as a particular kind of epistemic mediator able to perform the explanatory abductive task of providing a better understanding of the calculus, through a non-standard model of analysis. We also maintain they can be used in many other different epistemological and cognitive situations. (shrink)

I provide an explicit formulation of empirical adequacy, the central concept of constructive empiricism, and point out a number of problems. Based on one of the inspirations for empirical adequacy, I generalize the notion of a theory to avoid implausible presumptions about the relation of theoretical concepts and observations, and generalize empirical adequacy with the help of approximation sets to allow for lack of knowledge, approximations, and successive gain of knowledge and precision. As a test case, I provide an application (...) of these generalizations to a simple interference phenomenon. (shrink)

We give Scott sentences for certain computable groups, and we use index set calculations as a way of checking that our Scott sentences are as simple as possible. We consider finitely generated groups and torsion-free abelian groups of finite rank. For both kinds of groups, the computable ones all have computable \ Scott sentences. Sometimes we can do better. In fact, the computable finitely generated groups that we have studied all have Scott sentences that are “computable d-\” sentence and a (...) computable \ sentence). In [9], this was shown for the finitely generated free groups. Here we show it for all finitely generated abelian groups, and for the infinite dihedral group. Among the computable torsion-free abelian groups of finite rank, we focus on those of rank 1. These are exactly the additive subgroups of \. We show that for some of these groups, the computable \ Scott sentence is best possible, while for others, there is a computable d-\ Scott sentence. (shrink)

In this paper we consider the normal modal logics of elementary classes defined by first-order formulas of the form \. We prove that many properties of these logics, such as finite axiomatisability, elementarity, axiomatisability by a set of canonical formulas or by a single generalised Sahlqvist formula, together with modal definability of the initial formula, either simultaneously hold or simultaneously do not hold.

A conjecture of Gabbay (1981) states that any class of flows of time having the property known as finite H-dimension admits a finite set of expressively complete one-dimensional temporal connectives. Here we show that the class of 'circular' structures refutes the generalisation of this conjecture to Kripke frames. We then construct from this class, by a general method, a new class of irreflexive transitive flows of time that refutes the original conjecture. Our paper includes full descriptions of a method for (...) establishing finite H-dimension for a class of structures and of the technique for extending finite H-dimension to other classes, and an introduction surveying the area of expressive completeness. (shrink)

We exploit properties of certain directed graphs, obtained from the families of sets with special effective enumeration properties, to generalize several results in computable model theory to higher levels of the hyperarithmetical hierarchy. Families of sets with such enumeration features were previously built by Selivanov, Goncharov, and Wehner. For a computable successor ordinal α, we transform a countable directed graph into a structure such that has a isomorphic copy if and only if has a computable isomorphic copy.A computable structure is (...) categorical if for all computable isomorphic copies of , there is an isomorphism from onto , which is . We prove that for every computable successor ordinal α, there is a computable, categorical structure, which is not relatively categorical. This generalizes the result of Goncharov that there is a computable, computably categorical structure, which is not relatively computably categorical.An additional relation R on the domain of a computable structure is intrinsically on if in all computable isomorphic copies of , the image of R is . We prove that for every computable successor ordinal α, there is an intrinsically relation on a computable structure, which not relatively intrinsically . This generalizes the result of Manasse that there is an intrinsically computably enumerable relation on a computable structure, which is not relatively intrinsically computably enumerable.The dimension of a structure is the number of computable isomorphic copies, up to isomorphisms. We prove that for every computable successor ordinal α and every n≥1, there is a computable structure with dimension n. This generalizes the result of Goncharov that there is a structure of computable dimension n for every n≥1.Finally, we prove that for every computable successor ordinal α, there is a countable structure with isomorphic copies in just the Turing degrees of sets X such that relative to X is not . In particular, for every finite n, there is a structure with isomorphic copies in exactly the non- Turing degrees. This generalizes the result obtained by Wehner, and independently by Slaman, that there is a structure with isomorphic copies in exactly the nonzero Turing degrees. (shrink)

We prove an institutional version of A. Robinson ’s Consistency Theorem. This result is then appliedto the institution of many-sorted first-order predicate logic and to two of its variations, infinitary and partial, obtaining very general syntactic criteria sufficient for a signature square in order to satisfy the Robinson consistency and Craig interpolation properties.

We prove a completeness theorem for Kmath image, the infinitary extension of the graded version K0 of the minimal normal logic K, allowing conjunctions and disjunctions of countable sets of formulas. This goal is achieved using both the usual tools of the normal logics with graded modalities and the machinery of the predicate infinitary logics in a version adapted to modal logic.

Saturated models constitute one of the powerful methods of conventional model theory, with many applications. Here we develop a categorical abstract model theoretic approach to saturated models within the theory of institutions. The most important consequence is that the method of saturated models becomes thus available to a multitude of logical systems from logic or from computing science. In this paper we define the concept of saturated model at an abstract institution-independent level and develop the fundamental existence and uniqueness theorems. (...) As an application we prove a general institution-independent version of the Keisler–Shelah isomorphism theorem “any two elementarily equivalent models have isomorphic ultrapowers” (assuming Generalized Continuum Hypothesis). (shrink)

We extend the concept of quasi-variety of first-order models from classical logic to multiple valued logic and study the relationship between quasi-varieties and existence of initial models in MVL. We define a concept of ‘Horn sentence’ in MVL and based upon our study of quasi-varieties of MVL models we derive the existence of initial models for MVL ‘Horn theories’. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.

Although expected utility theory has proven a fruitful and elegant theory in the finite realm, attempts to generalize it to infinite values have resulted in many paradoxes. In this paper, we argue that the use of John Conway's surreal numbers shall provide a firm mathematical foundation for transfinite decision theory. To that end, we prove a surreal representation theorem and show that our surreal decision theory respects dominance reasoning even in the case of infinite values. We then bring our theory (...) to bear on one of the more venerable decision problems in the literature: Pascal's Wager. Analyzing the wager showcases our theory's virtues and advantages. To that end, we analyze two objections against the wager: Mixed Strategies and Many Gods. After formulating the two objections in the framework of surreal utilities and probabilities, our theory correctly predicts that (1) the pure Pascalian strategy beats all mixed strategies, and (2) what one should do in a Pascalian decision problem depends on what one's credence function is like. Our analysis therefore suggests that although Pascal's Wager is mathematically coherent, it does not deliver what it purports to, a rationally compelling argument that people should lead a religious life regardless of how confident they are in theism and its alternatives. (shrink)

We present a semantics for a language that includes sentences that can talk about their own probabilities. This semantics applies a fixed point construction to possible world style structures. One feature of the construction is that some sentences only have their probability given as a range of values. We develop a corresponding axiomatic theory and show by a canonical model construction that it is complete in the presence of the ω-rule. By considering this semantics we argue that principles such as (...) introspection, which lead to paradoxical contradictions if naively formulated, should be expressed by using a truth predicate to do the job of quotation and disquotation and observe that in the case of introspection the principle is then consistent. (shrink)

Classification is an important goal in many branches of mathematics. The idea is to describe the members of some class of mathematical objects, up to isomorphism or other important equivalence, in terms of relatively simple invariants. Where this is impossible, it is useful to have concrete results saying so. In model theory and descriptive set theory, there is a large body of work showing that certain classes of mathematical structures admit classification while others do not. In the present paper, we (...) describe some recent work on classification in computable structure theory.Section 1 gives some background from model theory and descriptive set theory. From model theory, we give sample structure and non-structure theorems for classes that include structures of arbitrary cardinality. We also describe the notion of Scott rank, which is useful in the more restricted setting of countable structures. From descriptive set theory, we describe the basic Polish space of structures for a fixed countable language with fixed countable universe. We give sample structure and non-structure theorems based on the complexity of the isomorphism relation, and on Borel embeddings.Section 2 gives some background on computable structures. We describe three approaches to classification for these structures. The approaches are all equivalent. However, one approach, which involves calculating the complexity of the isomorphism relation, has turned out to be more productive than the others. Section 3 describes results on the isomorphism relation for a number of mathematically interesting classes—various kinds of groups and fields. In Section 4, we consider a setting similar to that in descriptive set theory. We describe an effective analogue of Borel embedding which allows us to make distinctions even among classes of finite structures. Section 5 gives results on computable structures of high Scott rank. Some of these results make use of computable embeddings. Finally, in Section 6, we mention some open problems and possible directions for future work. (shrink)

The Clauser–Horne–Shimony–Holt (CHSH) inequality is a constraint that local hidden variable theories must obey. Quantum Mechanics predicts a violation of this inequality in certain experimental settings. Treatments of this subject frequently make simplifying assumptions about the probability spaces available to a local hidden variable theory, such as assuming the state of the system is a discrete or absolutely continuous random variable, or assuming that repeated experimental trials are independent and identically distributed. In this paper, we do two things: first, show (...) that the CHSH inequality holds even for completely general state variables in the measure-theoretic setting, and second, demonstrate how to drop the assumption of independence of subsequent trials while still being able to perform a hypothesis test that will distinguish Quantum Mechanics from local theories. The statistical strength of such a test is computed. (shrink)

The languages of finitary and infinitary logic over the alphabet of bounded lattices have proven to be of considerable use in the study of compacta. Significant among the sentences of these languages are the ones that are base free, those whose truth is unchanged when we move among the lattice bases of a compactum. In this paper we define syntactically the expansive sentences, and show each of them to be base free. We also show that many well-known properties of compacta (...) may be expressed using expansive sentences; and that any property so expressible is closed under inverse limits and co-existential images. As a byproduct, we conclude that co-existential images of pseudo-arcs are pseudo-arcs. This is of interest because the corresponding statement for confluent maps is still open, and co-existential maps are often—but not always—confluent. (shrink)

In update logic as studied by Baltag, Moss, Solecki and van Benthem, little attention is paid to the interpretation of an action by an agent, which is just assumed to depend on the situation. This is actually a complex issue that nevertheless complies to some logical dynamics. In this paper, we tackle this topic. We also deal with actions that change propositional facts of the situation. In parallel, we propose a formalism to accurately represent an agent's epistemic state based on (...) hyperreal numbers. In that respect, we use infinitesimals to express what would surprise the agents (and by how much) by contradicting their beliefs. We also use a subjective probability to model the notion of belief. It turns out that our probabilistic update mechanism satisfies the AGM postulates of belief revision. (shrink)

Quantified hybrid logic is quantified modal logic extended with apparatus for naming states and asserting that a formula is true at a named state. While interpolation and Beth's definability theorem fail in a number of well-known quantified modal logics , their counterparts in quantified hybrid logic have these properties. These are special cases of the main result of the paper: the quantified hybrid logic of any class of frames definable in the bounded fragment of first-order logic has the interpolation property, (...) irrespective of whether varying, constant, expanding, or contracting domains are assumed. (shrink)

Traditionally, expressions in formal systems have been regarded as signifying finite inscriptions which are—at least in principle—capable of actually being written out in primitive notation. However, the fact that (first-order) formulas may be identified with natural numbers (via "Gödel numbering") and hence with finite sets makes it no longer necessary to regard formulas as inscriptions, and suggests the possibility of fashioning "languages" some of whose formulas would be naturally identified as infinite sets . A "language" of this kind is called (...) an infinitary language : in this article I discuss those infinitary languages which can be obtained in a straightforward manner from first-order languages by allowing conjunctions, disjunctions and, possibly, quantifier sequences, to be of infinite length. In the course of the discussion it will be seen that, while the expressive power of such languages far exceeds that of their finitary (first-order) counterparts, very few of them possess the "attractive" features (e.g., compactness and completeness) of the latter. Accordingly, the infinitary languages that do in fact possess these features merit special attention. (shrink)

A definition of nonstandard universe which gets over the limitation to the finite levels of the cumulative hierarchy is proposed. Though necessarily nonwellfounded, nonstandard universes are arranged in strata in the likeness of superstructures and allow a rank function taking linearly ordered values. Nonstandard universes are also constructed which model the whole ZFC theory without regularity and satisfy the $\kappa$-saturation property.

We propose an alternative approach to probability theory closely related to the framework of numerosity theory: non-Archimedean probability (NAP). In our approach, unlike in classical probability theory, all subsets of an infinite sample space are measurable and only the empty set gets assigned probability zero (in other words: the probability functions are regular). We use a non-Archimedean field as the range of the probability function. As a result, the property of countable additivity in Kolmogorov’s axiomatization of probability is replaced by (...) a different type of infinite additivity. (shrink)

Taking into account some basic epistemological considerations on psychoanalysis by Ignacio Matte Blanco, it is possible to deduce some first simple remarks on certain logical aspects of schizophrenic reasoning. Further remarks on mathematical thought are also made in the light of what established, taking into account the comparison with the schizophrenia pattern.