Alfred Tarski’s influence on computer science was indirect but significant in a number of directions and was in certain respects fundamental. Here surveyed is Tarski’s work on the decision procedure for algebra and geometry, the method of elimination of quantifiers, the semantics of formal languages, model-theoretic preservation theorems, and algebraic logic; various connections of each with computer science are taken up.

Much of the inspiration for structuralist approaches to mathematics can be found in the late nineteenth- and early twentieth-century program of characterizing various mathematical systems upto isomorphism. From the perspective of this program, differences between isomorphic systems are irrelevant. It is argued that a different view of the import of the differences between isomorphic systems can be obtained from the perspective of contemporary discussions of representation theorems and that from this perspective both the identification of isomorphic systems and the reduction (...) to abstract structures or patterns should be resisted. (shrink)

In this essay, I discuss some observations by Peirce which suggest he had some idea of the substantive metalogical differences between logics which permit both quantifiers and relations, and those which do not. Peirce thus seems to have had arguments?which even De Morgan and Frege lacked?that show the superior expressiveness of relational logics.

Dynamic algebras combine the classes of Boolean (B 0) and regular (R ; *) algebras into a single finitely axiomatized variety (B R ) resembling an R-module with scalar multiplication . The basic result is that * is reflexive transitive closure, contrary to the intuition that this concept should require quantifiers for its definition. Using this result we give several examples of dynamic algebras arising naturally in connection with additive functions, binary relations, state trajectories, languages, and flowcharts. The main result (...) is that free dynamic algebras are residually finite (i.e. factor as a subdirect product of finite dynamic algebras), important because finite separable dynamic algebras are isomorphic to Kripke structures. Applications include a new completeness proof for the Segerberg axiomatization of prepositional dynamic logic, and yet another notion of regular algebra. (shrink)

For a Peirce algebra \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}${\mathcal P}$\end{document}, lattices \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathrm{Cong}\mathcal {P}$\end{document} of all heterogenous Peirce congruences and \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathrm{Ide}\mathcal {P}$\end{document} of all heterogenous Peirce ideals are presented. The notions of kernel of a Peirce congruence and the congruence induced by a Peirce ideal are introduced to describe an isomorphism between \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathrm{Cong}\mathcal {P}$\end{document} and \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathrm{Ide}\mathcal {P}$\end{document}. This isomorphism leads us to conclude that the class of the Peirce algebras is ideal determined. Opposed to Boolean modules case, each part of a Peirce ideal I = (...) (I1, I2) determines the other one. A similar result is valid to Peirce congruences. A characterization of the simple Peirce algebras is presented coinciding to that given by Brink, Britz and Schmidt in a homogeneous approach. (shrink)

Definitions for heterogeneous congruences and heterogeneous ideals on a Boolean module equation image are given and the respective lattices equation image and equation image are presented. A characterization of the simple bijective Boolean modules is achieved differing from that given by Brink in a homogeneous approach. We construct the smallest and the greatest modular congruence having the same Boolean part. The same is established for modular ideals. The notions of kernel of a modular congruence and the congruence induced by a (...) modular ideal are introduced to describe an isomorphism between equation image and equation image. This isomorphism leads us to conclude that the class of the Boolean module is ideal determined. (shrink)

Being is said and interpreted in various ways. These are studied in ontology. Ontology is concerned with both particular beings of several sorts as well as with the being and Being itself — respectively beings’ collection and unification into one.

ABSTRACT Propositional dynamic logic with converse and test, is enriched with complement, intersection and relational operations of weakest prespecification and weakest postspecification. Relational deduction system for the logic is given based on its interpretation in the relational calculus. Relational interpretation of the operators ?repeat? and ?loop? is given.

Epistemic Logic is our basic universal science, the method of our cognitive confrontation in reality to prove the truth of our basic cognitions and theories. Hence, by proving their true representation of reality we can self-control ourselves in it, and thus refuting the Berkeleyian solipsism and Kantian a priorism. The conception of epistemic logic is that only by proving our true representation of reality we achieve our knowledge of it, and thus we can prove our cognitions to be either true (...) or rather false, and otherwise they are doubtful. Therefore, truth cannot be separated from being proved and we cannot hold anymore the principle of excluded middle, as it is with formal semantics of metaphysical realism. In distinction, the intuitionistic logic is based on subjective intellectual feeling of correctness in constructing proofs, and thus it is epistemologically encapsulated in the metaphysical subject. However, epistemic logic is our basic science which enable us to prove the truth of our cognitions, including the epistemic logic itself. (shrink)

The axiomatic presentation of modal systems and the standard formulations of natural deduction and sequent calculus for modal logic are reviewed, together with the difficulties that emerge with these approaches. Generalizations of standard proof systems are then presented. These include, among others, display calculi, hypersequents, and labelled systems, with the latter surveyed from a closer perspective.

In this paper it is shown that Heyting and Co-Heyting mereological systems provide a convenient conceptual framework for spatial reasoning, in which spatial concepts such as connectedness, interior parts, (exterior) contact, and boundary can be defined in a natural and intuitively appealing way. This fact refutes the wide-spread contention that mereology cannot deal with the more advanced aspects of spatial reasoning and therefore has to be enhanced by further non-mereological concepts to overcome its congenital limitations. The allegedly unmereological concept of (...) boundary is treated in detail and shown to be essentially affected by mereological considerations. More precisely, the concept of boundary turns out to be realizable in a variety of different mereologically grounded versions. In particular, every part K of a Heyting algebra H gives rise to a well-behaved K-relative boundary operator. (shrink)

The middle years of the nineteenth century saw two crucial develop ments in the history of modern logic: George Boole's algebraic treat ment of logic and Augustus De Morgan's formulation of the logic of relations. The former episode has been studied extensively; the latter, hardly at all. This is a pity, for the most central feature of modern logic may well be its ability to handle relational inferences. De Morgan was the first person to work out an extensive logic of (...) relations, and the purpose of this book is to study this attempt in detail. Augustus De Morgan (1806-1871) was a British mathematician and logician who was Professor of Mathematics at the University of London (now, University College) from 1828 to 1866. A prolific but not highly original mathematician, De Morgan devoted much of his energies to the rather different field of logic. In his Formal Logic (1847) and a series of papers "On the Syllogism" (1846-1862), he attempted with great ingenuity to reformulate and extend the tradi tional syllogism and to systematize modes of reasoning that lie outside its boundaries. Chief among these is the logic of relations. De Mor gan's interest in relations culminated in his important memoir, "On the Syllogism: IV and on the Logic of Relations," read in 1860. (shrink)

In Computer Science stepwise refinement of algebraic specifications is a well-known formal methodology for rigorous program development. This paper illustrates how techniques from Algebraic Logic, in particular that of interpretation, understood as a multifunction that preserves and reflects logical consequence, capture a number of relevant transformations in the context of software design, reuse, and adaptation, difficult to deal with in classical approaches. Examples include data encapsulation and the decomposition of operations into atomic transactions. But if interpretations open such a new (...) research avenue in program refinement, (conceptual) tools are needed to reason about them. In this line, the paper’s main contribution is a study of the correspondence between logical interpretations and morphisms of a particular kind of coalgebras. This opens way to the use of coalgebraic constructions, such as simulation and bisimulation, in the study of interpretations between (abstract) logics. (shrink)

The period from 1900 to 1935 was particularly fruitful and important for the development of logic and logical metatheory. This survey is organized along eight "itineraries" concentrating on historically and conceptually linked strands in this development. Itinerary I deals with the evolution of conceptions of axiomatics. Itinerary II centers on the logical work of Bertrand Russell. Itinerary III presents the development of set theory from Zermelo onward. Itinerary IV discusses the contributions of the algebra of logic tradition, in particular, Löwenheim (...) and Skolem. Itinerary V surveys the work in logic connected to the Hilbert school, and itinerary V deals specifically with consistency proofs and metamathematics, including the incompleteness theorems. Itinerary VII traces the development of intuitionistic and many-valued logics. Itinerary VIII surveys the development of semantical notions from the early work on axiomatics up to Tarski's work on truth. (shrink)

The calculus of relations was created and developed in the second half of the nineteenth century by Augustus De Morgan, Charles Sanders Peirce, and Ernst Schröder. In 1940 Alfred Tarski proposed an axiomatization for a large part of the calculus of relations. In the next decade Tarski's axiomatization led to the creation of the theory of relation algebras, and was shown to be incomplete by Roger Lyndon's discovery of nonrepresentable relation algebras. This paper introduces the calculus of relations and the (...) theory of relation algebras through a review of these historical developments. (shrink)

Sound and complete semantics for classical propositional logic can be obtained by interpreting sentences as sets. Replacing sets with commuting dense binary relations produces an interpretation that turns out to be sound but not complete for R. Adding transitivity yields sound and complete semantics for RM, because all normal Sugihara matrices are representable as algebras of binary relations.

Relation algebras were invented by Tarski and his collaborators in the middle of the 20th century. The concept of integrality arose naturally early in the history of the subject, as did various constructions of finite integral relation algebras. Later the concept of finite-dimensionality was introduced for classifying nonrepresentable relation algebras. This concept is closely connected to the number of variables used in proofs in first-order logic. Some results on these topics are presented in chronological order.

Relation algebras were invented by Tarski and his collaborators in the middle of the 20th century. The concept of integrality arose naturally early in the history of the subject, as did various constructions of finite integral relation algebras. Later the concept of finite-dimensionality was introduced for classifying nonrepresentable relation algebras. This concept is closely connected to the number of variables used in proofs in first-order logic. Some results on these topics are presented in chronological order.

The aim of this paper is to introduce a new member of the family of the modal interpretations of quantum mechanics. In this modal-Hamiltonian interpretation, the Hamiltonian of the quantum system plays a decisive role in the property-ascription rule that selects the definite-valued observables whose possible values become actual. We show that this interpretation is effective for solving the measurement problem, both in its ideal and its non-ideal versions, and we argue for the physical relevance of the property-ascription rule by (...) applying it to well-known physical situations. Moreover, we explain how this interpretation supplies a description of the elemental categories of the ontology referred to by the theory, where quantum systems turn out to be bundles of possible properties. (shrink)

The aim of this paper is to introduce a new member of the family of the modal interpretations of quantum mechanics. In this modal-Hamiltonian interpretation, the Hamiltonian of the quantum system plays a decisive role in the property-ascription rule that selects the definite-valued observables whose possible values become actual. We show that this interpretation is effective for solving the measurement problem, both in its ideal and its non-ideal versions, and we argue for the physical relevance of the property-ascription rule by (...) applying it to well-known physical situations. Moreover, we explain how this interpretation supplies a description of the elemental categories of the ontology referred to by the theory, where quantum systems turn out to be bundles of possible properties. (shrink)

A network of aligned ontologies is a distributed system, whose components are interacting and interoperating, the result of this interaction being, either the extension of local assertions, which are valid within each individual ontology, to global assertions holding between remote ontology syntactic entities through a network path, or to local assertions holding between local entities of an ontology, but induced by remote ontologies, through a cycle in the network. The mechanism for achieving this interaction is the composition of relations. In (...) this perspective, we introduce the notions of local composable relations, which relate ontology entities belonging to the same ontology, remotely induced composable relations, which relate ontology entities belonging to remote ontologies through a path of ontologies and alignments in the network, and network induced local composable relations, which relate ontology entities belonging to the same ontology, but through a path of ontologies and alignments forming a cycle starting and ending at the same ontology, to characterize the logical consequences extracted from a network of aligned ontologies, and we propose a category-based methodology for detecting semantic inconsistencies in networks of aligned ontologies, which is based on contravariant representable functors and on the definition of two composition operators suitable for propagating local knowledge through the network. (shrink)

Built on the foundations laid by Peirce, Schröder, and others in the 19th century, the modern development of relation algebras started with the work of Tarski and his colleagues [21, 22]. They showed that relation algebras can capture strong first‐order theories like ZFC, and so their equational theory is undecidable. The less expressive class WA of weakly associative relation algebras was introduced by Maddux [7]. Németi [16] showed that WA's have a decidable universal theory. There has been extensive research on (...) increasing the expressive power of WA by adding new operations [1, 4, 11, 13, 20]. Extensions of this kind usually also have decidable universal theories. Here we give an example – extending WA's with set‐theoretic projection elements – where this is not the case. These “logical” connectives are set‐theoretic counterparts of the axiomatic quasi‐projections that have been investigated in the representation theory of relation algebras [22, 6, 19]. We prove that the quasi‐equational theory of the extended class PWA is not recursively enumerable. By adding the difference operator D one can turn WA and PWA to discriminator classes where each universal formula is equivalent to some equation. Hence our result implies that the projections turn the decidable equational theory of “WA + D ” to non‐recursively enumerable (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

We will show that almost all nonassociative relation algebras are symmetric and integral (in the sense that the fraction of both labelled and unlabelled structures that are symmetric and integral tends to $1$ ), and using a Fraïssé limit, we will establish that the classes of all atom structures of nonassociative relation algebras and relation algebras both have $0$ – $1$ laws. As a consequence, we obtain improved asymptotic formulas for the numbers of these structures and broaden some known probabilistic (...) results on relation algebras. (shrink)

We provide complete classifications of algebras of partial maps for a significant swathe of combinations of operations not previously classified. Our focus is the many subsidiary operations that arise in recent considerations of the ‘override’ and ‘update’ operations arising in specification languages. These other operations turn out to have an older pedigree: domain restriction, set subtraction and intersection. All signatures considered include domain restriction, at least as a term. Combinations of the operations are classified and given complete axiomatizations with and (...) without the presence of functional composition. Each classification is achieved by way of providing a concrete representation of the corresponding abstract algebras as partial maps acting on special kinds of filters determined with respect to various induced orders. In contrast to many negative results in the broader area, all of the considered combinations lead to finite axiomatizations. (shrink)

We consider algebras on binary relations with two main operators: relational composition and dynamic negation. Relational composition has its standard interpretation, while dynamic negation is an operator familiar to students of Dynamic Predicate Logic (DPL) (Groenendijk and Stokhof, 1991): given a relation R its dynamic negation R is a test that contains precisely those pairs (s,s) for which s is not in the domain of R. These two operators comprise precisely the propositional part of DPL.This paper contains a finite equational (...) axiomatization for these dynamic relation algebras. The completenessresult uses techniques from modal logic. We also lookat the variety generated by the class of dynamic relation algebras and note that there exist nonrepresentable algebras in this variety, ones which cannot be construedas spaces of relations. These results are also proved for an extension to a signature containing atomic tests and union. (shrink)

In this article we establish the undecidability of representability and of finite representability as algebras of binary relations in a wide range of signatures. In particular, representability and finite representability are undecidable for Boolean monoids and lattice ordered monoids, while representability is undecidable for Jónsson's relation algebra. We also establish a number of undecidability results for representability as algebras of injective functions.

For every finite n ≥ 4 there is a logically valid sentence φ n with the following properties: φ n contains only 3 variables (each of which occurs many times); φ n contains exactly one nonlogical binary relation symbol (no function symbols, no constants, and no equality symbol): φ n has a proof in first-order logic with equality that contains exactly n variables, but no proof containing only n - 1 variables. This result was first proved using the machinery of (...) algebraic logic developed in several research monographs and papers. Here we replicate the result and its proof entirely within the realm of (elementary) first-order binary predicate logic with equality. We need the usual syntax, axioms, and rules of inference to show that φ n has a proof with only n variables. To show that φ n has no proof with only n - 1 variables we use alternative semantics in place of the usual, standard, set-theoretical semantics of first-order logic. (shrink)

We present relational proof systems for the four groups of theories of spatial reasoning: contact relation algebras, Boolean algebras with a contact relation, lattice-based spatial theories, spatial theories based on a proximity relation.

This paper introduces Basic Intuitionistic Set Theory BIST, and investigates it as a first-order set theory extending the internal logic of elementary toposes. Given an elementary topos, together with the extra structure of a directed structural system of inclusions on the topos, a forcing-style interpretation of the language of first-order set theory in the topos is given, which conservatively extends the internal logic of the topos. This forcing interpretation applies to an arbitrary elementary topos, since any such is equivalent to (...) one carrying a dssi. We prove that the set theory BIST+Coll is sound and complete relative to forcing interpretations in toposes with natural numbers object . Furthermore, in the case that the structural system of inclusions is superdirected, the full Separation schema is modelled. We show that all cocomplete and realizability toposes can be endowed with such superdirected systems of inclusions.A large part of the paper is devoted to an alternative notion of category-theoretic model for BIST, which, following the general approach of Joyal and Moerdijkʼs Algebraic Set Theory, axiomatizes the structure possessed by categories of classes compatible with BIST. We prove soundness and completeness results for BIST relative to the class-category semantics. Furthermore, BIST+Coll is complete relative to the restricted collection of categories of classes given by categories of ideals over elementary toposes with nno and dssi. It is via this result that the completeness of the original forcing interpretation is obtained, since the internal logic of categories of ideals coincides with the forcing interpretation. (shrink)

We present a dual tableau system, RLK, which is itself a deterministic decision procedure verifying validity of K-formulas. The system is constructed in the framework of the original methodology of relational proof systems, determined only by axioms and inference rules, without any external techniques. Furthermore, we describe an implementation of the system in Prolog, and we show some of its advantages.

In 1941, Tarski published an abstract, finitely axiomatized version of the theory of binary relations, called the theory of relation algebras, He asked whether every model of his abstract theory could be represented as a concrete algebra of binary relations. He and Jonsson obtained some initial, positive results for special classes of abstract relation algebras. But Lyndon showed, in 1950, that in general the answer to Tarski's question is negative. Monk proved later that the answer remains negative even if one (...) adjoins finitely many new axioms to Tarski's system. In this paper we describe a far-reaching generalization of the positive results of Jonsson and Tarski, as well as of some later, related results of Maddux. We construct a class of concrete models of Tarski's axioms-called coset relation algebras-that are very close in spirit to algebras of binary relations, but are built using systems of groups and cosets instead of elements of a base set. The models include all algebras of binary relations, and many non-representable relation algebras as well, We prove that every atomic relation algebra satisfying a certain measurability condition-a condition generalizing the conditions imposed by Jonsson and Tarski-is essentially isomorphic to a coset relation algebra. The theorem raises the possibility of providing a positive solution to Tarski's problem by using coset relation algebras instead of the standard algebras of binary relations. (shrink)

A connection between Aristotle's syllogistic and the calculus of relations is investigated. Aristotle's and Gergonne's syllogistics are considered as some algebraic structures. It is proved that Gergonne's syllogistic is isomorphic to closed elements algebra of a proper approximation relation algebra. This isomorphism permits to evaluate Gergonne's syllogisms and also Aristotle's syllogisms, laws of conversion and relations in the "square of oppositions" by means of regular computations with Boolean matrices.

ABSTRACT In this paper it is shown that a broad class of propositional logics can be interpreted in an equational logic based on fork algebras. This interpetability enables us to develop a fork-algebraic formalization of these logics and, as a consequence, to simulate non-classical means of reasoning with equational theories algebras.

Unifiability of terms (and formulas) and structural completeness in the variety of relation algebras RA and in the products of modal logic S5 is investigated. Nonunifiable terms (formulas) which are satisfiable in varieties (in logics) are exhibited. Consequently, RA and products of S5 as well as representable diagonal-free n-dimensional cylindric algebras, RDfn, are almost structurally complete but not structurally complete. In case of S5n a basis for admissible rules and the form of all passive rules are provided.

Contact relations have been studied in the context of qualitative geometry and physics since the early 1920s, and have recently received attention in qualitative spatial reasoning. In this paper, we present a sound and complete proof system in the style of Rasiowa and Sikorski (1963) for relation algebras generated by a contact relation.