Boolean-valued models for first-order languages generalize two-valued models, in that the value range is allowed to be any complete Boolean algebra instead of just the Boolean algebra 2. Boolean-valued models are interesting in multiple aspects: philosophical, logical, and mathematical. The primary goal of this paper is to extend a number of critical model-theoretic notions and to generalize a number of important model-theoretic results based on these notions to Boolean-valued models. For instance, we will investigate (first-order) Boolean valuations, which are natural (...) generalizations of (first-order) theories, and prove that Boolean-valued models are sound and complete with respect to Boolean valuations. With the help of Boolean valuations, we will also discuss the Löwenheim-Skolem theorems on Boolean-valued models. (shrink)

Alberto Casullo ("Necessity, Certainty, and the A Priori", Canadian Journal of Philosophy 18, 1988) argues that arithmetical propositions could be disconfirmed by appeal to an invented scenario, wherein our standard counting procedures indicate that 2 + 2 != 4. Our best response to such a scenario would be, Casullo suggests, to accept the results of the counting procedures, and give up standard arithmetic. While Casullo's scenario avoids arguments against previous "disconfirming" scenarios, it founders on the assumption, common to scenario and (...) response, that arithmetic might be independent of standard counting procedures. Here I show, by attention to tallying as the simplest form of counting, that this assumption is incoherent: given standard counting procedures, then (on pain of irrationality) arithmetical theory follows. (shrink)

We establish several first- or second-order properties of models of first-order theories by considering their elements as atoms of a new universe of set theory and by extending naturally any structure of Boolean model on the atoms to the whole universe. For example, complete f-rings are "boundedly algebraically compact" in the language $(+,-,\cdot,\wedge,\vee,\leq)$ , and the positive cone of a complete l-group with infinity adjoined is algebraically compact in the language (+, ∨, ≤). We also give an example with any (...) first-order language. The proofs can be translated into "naive set theory" in a uniform way. (shrink)

Monoidal t-norm based logic $\mathbf {MTL}$ is the weakest t-norm based residuated fuzzy logic, which is a $[0,1]$ -valued propositional logical system having a t-norm and its residuum as truth function for conjunction and implication. Monadic fuzzy predicate logic $\mathbf {mMTL\forall }$ that consists of the formulas with unary predicates and just one object variable, is the monadic fragment of fuzzy predicate logic $\mathbf {MTL\forall }$, which is indeed the predicate version of monoidal t-norm based logic $\mathbf {MTL}$. The main (...) aim of this paper is to give an algebraic proof of the completeness theorem for monadic fuzzy predicate logic $\mathbf {mMTL\forall }$ and some of its axiomatic extensions. Firstly, we survey the axiomatic system of monadic algebras for t-norm based residuated fuzzy logic and amend some of them, thus showing that the relationships for these monadic algebras completely inherit those for corresponding algebras. Subsequently, using the equivalence between monadic fuzzy predicate logic $\mathbf {mMTL\forall }$ and S5-like fuzzy modal logic $\mathbf {S5(MTL)}$, we prove that the variety of monadic MTL-algebras is actually the equivalent algebraic semantics of the logic $\mathbf {mMTL\forall }$, giving an algebraic proof of the completeness theorem for this logic via functional monadic MTL-algebras. Finally, we further obtain the completeness theorem of some axiomatic extensions for the logic $\mathbf {mMTL\forall }$, and thus give a major application, namely, proving the strong completeness theorem for monadic fuzzy predicate logic based on involutive monoidal t-norm logic $\mathbf {mIMTL\forall }$ via functional representation of finitely subdirectly irreducible monadic IMTL-algebras. (shrink)

Let ℒ be a first-order language of cardinality κ++ with a distinguished unary predicate symbol U. In this paper we prove, working on L, the two cardinal transfer theorem (κ⁺,κ) ⇒ (κ++,κ⁺) for this language. This problem was posed by Chang and Keisler more than twenty years ago.

We generalize to theories of modules (complete or not) a result of U. Felgner stating that a complete theory of abelian groups is a Horn theory if and only if it is closed under products. To prove this we show that a reduced product of modules $\Pi_F M_i (i \in I)$ is elementarily equivalent to a direct product of ultraproducts of the modules $M_i (i \in I)$.

The relation between logic and philosophy of science, often taken for granted, is in fact problematic. Although current fashionable criticisms of the usefulness of logic are usually mistaken, there are indeed difficulties which should be taken seriously -- having to do, amongst other things, with different "scientific mentalities" in the two disciplines. Nevertheless, logic is, or should be, a vital part of the theory of science. To make this clear, the bulk of this paper is devoted to the key notion (...) of a "scientific theory" in a logical perspective. First, various formal explications of this notion are reviewed, then their further logical theory is discussed. In the absence of grand inspiring programs like those of Klein in mathematics or Hilbert in metamathematics, this preparatory ground-work is the best one can do here. The paper ends on a philosophical note, discussing applicability and merits of the formal approach to the study of science. (shrink)

In recent papers Hans Halvorson has offered a critique of the semantic view of theories, showing that theories may be the same although the corresponding sets of models are different and, conversely, that theories may be different although the corresponding sets of models are the same. This critique will be assessed, first, as it pertains to issues concerning scientific models in the empirical sciences and, second, independent of any concern with empirical science.

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)

A field K in a ring language $\mathcal {L}$ is finitely undecidable if $\mbox {Cons}(T)$ is undecidable for every nonempty finite $T \subseteq {\mathtt{Th}}(K; \mathcal {L})$. We extend a construction of Ziegler and (among other results) use a first-order classification of Anscombe and Jahnke to prove every NIP henselian nontrivially valued field is finitely undecidable. We conclude (assuming the NIP Fields Conjecture) that every NIP field is finitely undecidable. This work is drawn from the author’s PhD thesis [48, Chapter 3].

We discuss the possibility of applying the compactness theorem to the study of finite structures. Given a class of finite structures, it is important to determine whether it can be expressed by a particular category of sentences. We are interested in this type of problem, and use nonstandard method for showing the non‐expressibility of certain classes of finite graphs by an existential monadic second order sentence.

How can we be certain that software is reliable? Is there any method that can verify the correctness of software for all cases of interest? Computer scientists and software engineers have informally assumed that there is no fully general solution to the verification problem. In this paper, we survey approaches to the problem of software verification and offer a new proof for why there can be no general solution.

How can we be certain that software is reliable? Is there any method that can verify the correctness of software for all cases of interest? Computer scientists and software engineers have informally assumed that there is no fully general solution to the verification problem. In this paper, we survey approaches to the problem of software verification and offer a new proof for why there can be no general solution.

This paper argues for a representational semantic conception of scientific theories, which respects the bare claim of any semantic view, namely that theories can be characterised as sets of models. RSC must be sharply distinguished from structural versions that assume a further identity of ‘models’ and ‘structures’, which we reject. The practice-turn in the recent philosophical literature suggests instead that modelling must be understood in a deflationary spirit, in terms of the diverse representational practices in the sciences. These insights are (...) applied to some mathematical models, thus showing that the mathematical sciences are not in principle counterexamples to RSC. (shrink)

This paper defends the deflationary character of two recent views regarding scientific representation, namely RIG Hughes’ DDI model and the inferential conception. It is first argued that these views’ deflationism is akin to the homonymous position in discussions regarding the nature of truth. There, we are invited to consider the platitudes that the predicate “true” obeys at the level of practice, disregarding any deeper, or more substantive, account of its nature. More generally, for any concept X, a deflationary approach is (...) then defined in opposition to a substantive approach, where a substantive approach to X is an analysis of X in terms of some property P, or relation R, accounting for and explaining the standard use of X. It then becomes possible to characterize a deflationary view of scientific representation in three distinct senses, namely: a “no-theory” view, a “minimalist” view, and a “use-based” view – in line with three standard deflationary responses in the philosophical literature on truth. It is then argued that both the DDI model and the inferential conception may be suitably understood in any of these three different senses. The application of these deflationary ‘hermeneutics’ moreover yields significant improvements on the DDI model, which bring it closer to the inferential conception. It is finally argued that what these approaches have in common – the key to any deflationary account of scientific representation – is the denial that scientific representation may be ultimately reduced to any substantive explanatory property of sources, or targets, or their relations. (shrink)

A new method is presented for constructing models of set theory, using a technique of forming pseudo-ultrapowers. In the presence of the axiom of choice, the traditional ultrapower construction has proven to be extremely powerful in set theory and model theory; if the axiom of choice is not assumed, the fundamental theorem of ultrapowers may fail, causing the ultrapower to lose almost all of its utility. The pseudo-ultrapower is designed so that the fundamental theorem holds even if choice fails; this (...) is arranged by means of an application of the omitting types theorem. The general theory of pseudo-ultrapowers is developed. Following that, we study supercompactness in the absence of choice, and we analyze pseudo-ultrapowers of models of the axiom of determinateness and various infinite exponent partition relations. Relationships between pseudo-ultrapowers and forcing are also discussed. (shrink)

We initiate the study of model theory in the absence of the Axiom of Choice, using the Axiom of Determinateness as a powerful substitute. We first show that, in this context, L ω 1 ω is no more powerful than first-order logic. The emphasis then turns to upward Lowenhein-Skolem theorems; ℵ 1 is the Hanf number of first-order logic, of L ω 1 ω , and of a strong fragment of L ω 1 ω . The main technical innovation is (...) the development of iterated ultrapowers using infinite supports; this requires an application of infinite-exponent partition relations. All our theorems can be proven from hypotheses weaker than AD. (shrink)

M. H. A. Newman (1928) criticized Russell's structuralist philosophy of science. Demopoulos and Friedman have discussed Newman's critique, showing its relevance to the structuralist positions held by Schlick and Carnap, and to Putnam's argument against "metaphysical realism". I discuss Richard Braithwaite's (1940) appeal to Newman in a critique of Arthur Eddington. Braithwaite believed Newman had shown that "structure depends upon content". Eddington, in his reply, misunderstood the generality of Newman's argument.

We show that the countable universal ω‐categorical bowtie‐free graph admits generic automorphisms. Moreover, we show that this graph is not finitely homogenisable.

We study the computational complexity of the universal theory of residuated ordered groupoids, which are algebraic structures corresponding to Nonassociative Lambek Calculus. We prove that the universal theory is co $$\textsf {NP}$$ -complete which, as we observe, is the lowest possible complexity for a universal theory of a non-trivial class of structures. The universal theories of the classes of unital and integral residuated ordered groupoids are also shown to be co $$\textsf {NP}$$ -complete. We also prove the co $$\textsf {NP}$$ (...) -completeness of the universal theory of classes of residuated algebras, algebraic structures corresponding to Generalized Lambek Calculus. (shrink)

We prove there are theories (stable or countable) for which over every A there is a prime model but it is not necessarily unique. We also give a simplified proof of the uniqueness theorem for countable stable theories.

Let T be a complete countable first-order theory such that every ultrapower of a model of T is saturated. If T has a model omitting a type p in every cardinality $ then T has a model omitting p in every cardinality. There is also a related theorem, and an example showing the $\beth_\omega$ cannot be improved.

Zwart and Franssen’s impossibility theorem reveals a conflict between the possible-world-based content-definition and the possible-world-based likeness-definition of verisimilitude. In Sect. 2 we show that the possible-world-based content-definition violates four basic intuitions of Popper’s consequence-based content-account to verisimilitude, and therefore cannot be said to be in the spirit of Popper’s account, although this is the opinion of some prominent authors. In Sect. 3 we argue that in consequence-accounts , content-aspects and likeness-aspects of verisimilitude are not in conflict with each other, but (...) in agreement . We explain this fact by pointing towards the deep difference between possible-world- and the consequence-accounts, which does not lie in the difference between syntactic (object-language) versus semantic (meta-language) formulations, but in the difference between ‘disjunction-of-possible-worlds’ versus ‘conjunction-of-parts’ representations of theories. Drawing on earlier work, we explain in Sect. 4 how the shortcomings of Popper’s original definition can be repaired by what we call the relevant element approach. We propose a quantitative likeness-definition of verisimilitude based on relevant elements which provably agrees with the qualitative relevant content-definition of verisimilitude on all pairs of comparable theories. We conclude the paper with a plea for consequence-accounts and a brief analysis of the problem of language-dependence (Sect. 6). (shrink)