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.

The book provides a historical and systematic exposition of the semantic theory of truth formulated by Alfred Tarski in the 1930s. This theory became famous very soon and inspired logicians and philosophers. It has two different, but interconnected aspects: formal-logical and philosophical. The book deals with both, but it is intended mostly as a philosophical monograph. It explains Tarski’s motivation and presents discussions about his ideas as well as points out various applications of the semantic theory of truth to philosophical (...) problems. (shrink)

This paper provides several examples of how modal logic can be used in studying the XML document navigation language XPath. More specifically, we derive complete axiomatizations, computational complexity and expressive power results for XPath fragments from known results for corresponding logics. A secondary aim of the paper is to introduce XPath in a way that makes it accessible to an audience of modal logicians.

In this manuscript, published here for the first time, Tarski explores the concept of logical notion. He draws on Klein's Erlanger Programm to locate the logical notions of ordinary geometry as those invariant under all transformations of space. Generalizing, he explicates the concept of logical notion of an arbitrary discipline.

We prove an Omitting Types Theorem for certain algebraizable extensions of first order logic without equality studied in [SAI 00] and [SAY 04]. This is done by proving a representation theorem preserving given countable sets of infinite meets for certain reducts of ?- dimensional polyadic algebras, the so-called G polyadic algebras (Theorem 5). Here G is a special subsemigroup of (?, ? o) that specifies the signature of the algebras in question. We state and prove an independence result connecting our (...) representation theorem to Martin's axiom (Theorem 6). Also we show that the countable atomic G polyadic algebras are completely representable (Corollary 16) contrasting results on cylindric algebras. Several related results are surveyed. (shrink)

Tarski characterized logical notions as invariant under permutations of the domain. The outcome, according to Tarski, is that our logic, which is commonly said to be a logic of extension rather than intension, is not even a logic of extension—it is a logic of cardinality. In this paper, I make this idea precise. We look at a scale inspired by Ruth Barcan Marcus of various levels of meaning: extensions, intensions and hyperintensions. On this scale, the lower the level of meaning, (...) the more coarse-grained and less “intensional” it is. I propose to extend this scale to accommodate a level of meaning appropriate for logic. Thus, below the level of extension, we will have a more coarse-grained level of form. I employ a semantic conception of form, adopted from Sher, where forms are features of things “in the world”. Each expression in the language embodies a form, and by the definition we give, forms will be invariant under permutations and thus Tarskian logical notions. I then define the logical terms of a language as those terms whose extension can be determined by their form. Logicality will be shown to be a lower level analogue of rigidity. Using Barcan Marcus’s principles of explicit and implicit extensionality, we are able to characterize purely logical languages as “sub-extensional”, namely, as concerned only with form, and we thus obtain a wider perspective on both logicality and extensionality. (shrink)

This paper starts by investigating Ackermann's interpretation of finite set theory in the natural numbers. We give a formal version of this interpretation from Peano arithmetic (PA) to Zermelo-Fraenkel set theory with the infinity axiom negated (ZF−inf) and provide an inverse interpretation going the other way. In particular, we emphasize the precise axiomatization of our set theory that is required and point out the necessity of the axiom of transitive containment or (equivalently) the axiom scheme of ∈-induction. This clarifies the (...) nature of the equivalence of PA and ZF−inf and corrects some errors in the literature. We also survey the restrictions of the Ackermann interpretation and its inverse to subsystems of PA and ZF−inf, where full induction, replacement, or separation is not assumed. The paper concludes with a discussion on the problems one faces when the totality of exponentiation fails, or when the existence of unordered pairs or power sets is not guaranteed. (shrink)

We show that the variety of n -dimensional weakly higher order cylindric algebras, introduced in Németi [9], [8], is finitely axiomatizable when n > 2. Our result implies that in certain non-well-founded set theories the finitization problem of algebraic logic admits a positive solution; and it shows that this variety is a good candidate for being the cylindric algebra theoretic counterpart of Tarski’s quasi-projective relation algebras.

The class \ of t rue p airing a lgebras is defined to be the class of relation algebras expanded with concrete set theoretical projection functions. The main results of the present paper is that neither the equational theory of \ nor the first order theory of \ are decidable. Moreover, we show that the set of all equations valid in \ is exactly on the \ level. We consider the class \ of the relation algebra reducts of \ ’s, (...) as well. We prove that the equational theory of \ is much simpler, namely, it is recursively enumerable. We also give motivation for our results and some connections to related work. (shrink)

In this paper, we introduce a general technology, calledtaming, for finding well-behaved versions of well-investigated logics. Further, we state completeness, decidability, definability and interpolation results for a multimodal logic, calledarrow logic, with additional operators such as thedifference operator, andgraded modalities. Finally, we give a completeness proof for a strong version of arrow logic.

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.

A system of finite mathematics is proposed that has all of the power of classical mathematics. I believe that finite mathematics is not committed to any form of infinity, actual or potential, either within its theories or in the metalanguage employed to specify them. I show in detail that its commitments to the infinite are no stronger than those of primitive recursive arithmetic. The finite mathematics of sets is comprehensible and usable on its own terms, without appeal to any form (...) of the infinite. That makes it possible to, without circularity, obtain the axioms of full Zermelo-Fraenkel Set Theory with the Axiom of Choice (ZFC) by extrapolating (in a precisely defined technical sense) from natural principles concerning finite sets, including indefinitely large ones. The existence of such a method of extrapolation makes it possible to give a comparatively direct account of how we obtain knowledge of the mathematical infinite. The starting point for finite mathematics is Mycielski's work on locally finite theories. (shrink)

Modal logic is concerned with the analysis of sentential operators in the widest sense. Originally invented to analyse the notion of necessity applications have been found in many areas of philosophy, logic, linguistics and computer science. This in turn has led to an increased interest in the technical development of modal logic.

Ordinal addition and multiplication can be extended in a natural way to all sets. I survey the structure of the sets under these operations. In particular, the natural partial ordering associated with addition of sets is shown to be a tree. This allows us to prove that any set has a unique representation as a sum of additively irreducible sets, and that the non-empty elements of any model of set theory can be partitioned into infinitely many submodels, each isomorphic to (...) the original model. Also any model of set theory has an isomorphic extension in which the empty set of the original model is non-empty. Among other results, the relations between the arithmetical operations and the transitive closure and the adductive hierarchy are elucidated. (shrink)

It is known that for all finite n ≥ 5, there are relation algebras with n-dimensional relational bases but no weak representations. We prove that conversely, there are finite weakly representable relation algebras with no n-dimensional relational bases. In symbols: neither of the classes RA n and wRRA contains the other.

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)

There have been several different and even opposed conceptions of the problem of logical constants, i.e. of the requirements that a good theory of logical constants ought to satisfy. This paper is in the first place a survey of these conceptions and a critique of the theories they have given rise to. A second aim of the paper is to sketch some ideas about what a good theory would look like. A third aim is to draw from these ideas and (...) from the preceding survey the conclusion that most conceptions of the problem of logical constants involve requirements of a philosophically demanding nature which are probably not satisfiable by any minimally adequate theory. (shrink)

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.

The standard model for mereotopological structures are Boolean subalgebras of the complete Boolean algebra of regular closed subsets of a nonempty connected regular T 0 topological space with an additional "contact relation" C defined by xCy x ØA (possibly) more general class of models is provided by the Region Connection Calculus (RCC) of Randell et al. We show that the basic operations of the relational calculus on a "contact relation" generate at least 25 relations in any model of the RCC, (...) and hence, in any standard model of mereotopology. It follows that the expressiveness of the RCC in relational logic is much greater than the original 8 RCC base relations might suggest. We also interpret these 25 relations in the the standard model of the collection of regular open sets in the two-dimensional Euclidean plane. (shrink)

In this paper we show that the class of fork squares has a complete orthodox axiomatization in fork arrow logic (FAL). This result may be seen as an orthodox counterpart of Venema's non-orthodox axiomatization for the class of squares in arrow logic. FAL is the modal logic of fork algebras (FAs) just as arrow logic is the modal logic of relation algebras (RAs). FAs extend RAs by a binary fork operator and are axiomatized by adding three equations to RAs equational (...) axiomatization. A proper FA is an algebra of relations where the fork is induced by an injective operation coding pair formation. In contrast to RAs, FAs are representable by proper ones and their equational theory has the expressive power of full first-order logic. A square semantics (the set of arrows is U×U for some set U) for arrow logic was defined by Y. Venema. Due to the negative results about the finite axiomatizability of representable RAs, Venema provided a non-orthodox finite axiomatization for arrow logic by adding a new rule governing the applications of a difference operator. We address here the question of extending the type of relational structures to define orthodox axiomatizations for the class of squares. Given the connections between this problem and the finitization problem addressed by I. Németi, we suspect that this cannot be done by using only logical operations. The modal version of the FA equations provides an orthodox axiomatization for FAL which is complete in view of the representability of FAs. Here we review this result and carry it further to prove that this orthodox axiomatization for FAL also axiomatizes the class of fork squares. (shrink)

This paper discusses the history of the confusion and controversies over whether the definition of consequence presented in the 11-page 1936 Tarski consequence-definition paper is based on a monistic fixed-universe framework?like Begriffsschrift and Principia Mathematica. Monistic fixed-universe frameworks, common in pre-WWII logic, keep the range of the individual variables fixed as the class of all individuals. The contrary alternative is that the definition is predicated on a pluralistic multiple-universe framework?like the 1931 Gödel incompleteness paper. A pluralistic multiple-universe framework recognizes multiple (...) universes of discourse serving as different ranges of the individual variables in different interpretations?as in post-WWII model theory. In the early 1960s, many logicians?mistakenly, as we show?held the ?contrary alternative? that Tarski 1936 had already adopted a Gödel-type, pluralistic, multiple-universe framework. We explain that Tarski had not yet shifted out of the monistic, Frege?Russell, fixed-universe paradigm. We further argue that between his Principia-influenced pre-WWII Warsaw period and his model-theoretic post-WWII Berkeley period, Tarski's philosophy underwent many other radical changes. (shrink)

Contrary to common misconceptions, today's logic is not devoid of existential import: the universalized conditional ∀ x [S→ P] implies its corresponding existentialized conjunction ∃ x [S & P], not in all cases, but in some. We characterize the proexamples by proving the Existential-Import Equivalence: The antecedent S of the universalized conditional alone determines whether the universalized conditional has existential import, i.e. whether it implies its corresponding existentialized conjunction.A predicate is an open formula having only x free. An existential-import predicate (...) Q is one whose existentialization, ∃ x Q, is logically true; otherwise, Q is existential-import-free or simply import-free.How abundant or widespread is existential import? How abundant or widespread are existential-import predicates in themselves or in comparison to import-free predicates? We show that existential-import predicates are quite abundant, and no less so than import-free predicates. Existential.. (shrink)

We consider fragments of the relational logic RL(1) obtained by posing various constraints on the relational terms involving the operator of composition of relations. These fragments allow to express several non classical logics including modal and description logics. We show how relational dual tableaux can be employed to provide decision procedures for each of them.

(2013). On the meaning of statements in psychophysics characterizing conditional indeterminacy of percepts. Philosophical Psychology: Vol. 26, No. 2, pp. 234-262. doi: 10.1080/09515089.2012.663715.

Relevance logics are known to be sound and complete for relational semantics with a ternary accessibility relation. This paper investigates the problem of adequacy with respect to special kinds of dynamic semantics (i.e., proper relation algebras and relevant families of relations). We prove several soundness results here. We also prove the completeness of a certain positive fragment of R as well as of the first-degree fragment of relevance logics. These results show that some core ideas are shared between relevance logics (...) and relation algebras. Some details of certain incompleteness results, however, pinpoint where relevance logics and relation algebras diverge. To carry out these semantic investigations, we define a new tableaux formalization and new sequent calculi (with the single cut rule admissible) for various relevance logics. (shrink)

What precisely are fragments of classical first-order logic showing “modal” behaviour? Perhaps the most influential answer is that of Gabbay 1981, which identifies them with so-called “finite-variable fragments”, using only some fixed finite number of variables (free or bound). This view-point has been endorsed by many authors (cf. van Benthem 1991). We will investigate these fragments, and find that, illuminating and interesting though they are, they lack the required nice behaviour in our sense. (Several new negative results support this claim.) (...) As a counterproposal, then, we define a large fragment of predicate logic characterized by its use of only bounded quantification. This so-called guarded fragment enjoys the above nice properties, including decidability, through an effectively bounded finite model property. (These are new results, obtained by generalizing notions and techniques from modal logic.) Moreover, its own internal finite variable hierarchy turns out to work well. Finally, we shall make another move. The above analogy works both ways. Modal operators are like quantifiers, but quantifiers are also like modal operators. This observation inspires a generalized semantics for first-order predicate logic with accessibility constraints on available assignments (cf. N´emeti 1986, 1992) which moves the earlier quantifier restrictions into the semantics. This provides a fresh look at the landscape of possible predicate logics, including candidates sharing various desirable features with basic modal logic – in particular, its decidability. (shrink)

We study algebras whose elements are relations, and the operations are natural “manipulations” of relations. This area goes back to 140 years ago to works of De Morgan, Peirce, Schröder . Well known examples of algebras of relations are the varieties RCAn of cylindric algebras of n-ary relations, RPEAn of polyadic equality algebras of n-ary relations, and RRA of binary relations with composition. We prove that any axiomatization, say E, of RCAn has to be very complex in the following sense: (...) for every natural number k there is an equation in E containing more than k distinct variables and all the operation symbols, if 2 < n < ω. Completely analogous statement holds for the case n ω. This improves Monk's famous non-finitizability theorem for which we give here a simple proof. We prove analogous nonfinitizability properties of the larger varieties SNrnCAn + k. We prove that the complementation-free subreducts of RCAn do not form a variety. We also investigate the reason for the above “non-finite axiomatizability” behaviour of RCAn. We look at all the possible reducts of RCAn and investigate which are finitely axiomatizable. We obtain several positive results in this direction. Finally, we summarize the results and remaining questions in a figure. We carry through the same programme for RPEAn and for RRA. By looking into the reducts we also investigate what other kinds of natural algebras of relations are possible with more positive behaviour than that of the well known ones. Our investigations have direct consequences for the logical properties of the n-variable fragment Ln of first order logic. The reason for this is that RCAn and RPEAn are the natural algebraic counterparts of Ln while the varieties SNrnCAn + k are in connection with the proof theory of Ln. This paper appears in two parts. The first part contains the non-finite axiomatizability results. The present second part contains finite axiomatizations of some fragments together with a figure summarizing the finite and non-finite axiomatizability results in this area and the problems left open. (shrink)

An early, very preliminary edition of this book was circulated in 1962 under the title Set-theoretical Structures in Science. There are many reasons for maintaining that such structures play a role in the philosophy of science. Perhaps the best is that they provide the right setting for investigating problems of representation and invariance in any systematic part of science, past or present. Examples are easy to cite. Sophisticated analysis of the nature of representation in perception is to be found already (...) in Plato and Aristotle. One of the great intellectual triumphs of the nineteenth century was the mechanical explanation of such familiar concepts as temperature and pressure by their representation in terms of the motion of particles. A more disturbing change of viewpoint was the realization at the beginning of the twentieth century that the separate invariant properties of space and time must be replaced by the space-time invariants of Einstein's special relativity. Another example, the focus of the longest chapter in this book, is controversy extending over several centuries on the proper representation of probability. The six major positions on this question are critically examined. Topics covered in other chapters include an unusually detailed treatment of theoretical and experimental work on visual space, the two senses of invariance represented by weak and strong reversibility of causal processes, and the representation of hidden variables in quantum mechanics. The final chapter concentrates on different kinds of representations of language, concluding with some empirical results on brain-wave representations of words and sentences. (shrink)

I argue that we can and should extend Tarski's model-theoretic criterion of logicality to cover indefinite expressions like Hilbert's ɛ operator, Russell's indefinite description operator η, and abstraction operators like 'the number of'. I draw on this extension to discuss the logical status of both abstraction operators and abstraction principles.

We are much better equipped to let the facts reveal themselves to us instead of blinding ourselves to them or stubbornly trying to force them into preconceived molds. We no longer embarrass ourselves in front of our students, for example, by insisting that “Some Xs are Y” means the same as “Some X is Y”, and lamely adding “for purposes of logic” whenever there is pushback. Logic teaching in this century can exploit the new spirit of objectivity, humility, clarity, observationalism, (...) contextualism, and pluralism. Besides the new spirit there have been quiet developments in logic and its history and philosophy that could radically improve logic teaching. This lecture expands points which apply equally well in first, second, and third courses, i.e. in “critical thinking”, “deductive logic”, and “symbolic logic”. (shrink)

We are much better equipped to let the facts reveal themselves to us instead of blinding ourselves to them or stubbornly trying to force them into preconceived molds. We no longer embarrass ourselves in front of our students, for example, by insisting that “Some Xs are Y” means the same as “Some X is Y”, and lamely adding “for purposes of logic” whenever there is pushback. Logic teaching in this century can exploit the new spirit of objectivity, humility, clarity, observationalism, (...) contextualism, and pluralism. Besides the new spirit there have been quiet developments in logic and its history and philosophy that could radically improve logic teaching. One rather conspicuous example is that the process of refining logical terminology has been productive. Future logic students will no longer be burdened by obscure terminology and they will be able to read, think, talk, and write about logic in a more careful and more rewarding manner. Closely related is increased use and study of variable-enhanced natural language as in “Every proposition x that implies some proposition y that is false also implies some proposition z that is true”. Another welcome development is the culmination of the slow demise of logicism. No longer is the teacher blocked from using examples from arithmetic and algebra fearing that the students had been indoctrinated into thinking that every mathematical truth was a tautology and that every mathematical falsehood was a contradiction. A fifth welcome development is the separation of laws of logic from so-called logical truths, i.e., tautologies. Now we can teach the logical independence of the laws of excluded middle and non-contradiction without fear that students had been indoctrinated into thinking that every logical law was a tautology and that every falsehood of logic was a contradiction. This separation permits the logic teacher to apply logic in the clarification of laws of logic. This lecture expands the above points, which apply equally well in first, second, and third courses, i.e. in “critical thinking”, “deductive logic”, and “symbolic logic”. (shrink)

Paraconsistent logics are logics that can be used to base inconsistent but non-trivial systems. In paraconsistent set theories, we can quan- tify over sets that in standard set theories, if consistent, would lead to contradictions, such as the Russell set, R = fx : x =2 xg. Quasi-set theories are mathematical systems built for dealing with collections of indiscernible elements. The basic motivation for the development of quasi-set theories came from quantum physics, where indiscernible entities need to be considered. Usually, (...) the way of dealing with indiscernible objects within clas- sical logic and mathematics is by restricting them to certain structures, in a way so that the relations and functions of the structure are not sufficient to individuate the objects; in other words, such structures are not rigid. In quantum physics, this idea appears when symmetry conditions are introduced, say by choosing symmetric and anti-symmetric functions in the relevant Hilbert spaces. But in standard mathematics, such as that built in Zermelo-Fraenkel set theory, any structure can be extended to a rigid structure. That means that, although we can deal with certain objects as they were indiscernible, we realize that from out- side of these structures these objects are no more indiscernible, for they can be individualized in the extended rigid structures: ZF is a theory of individuals, distinguishable objects. In quasi-set theory, it seems that there are structures that cannot be extended to rigid ones, so it seems that they provide a natural mathematical framework for expressing quantum facts without certain symmetry suppositions. There may be situations, however, in which we may need to deal with inconsistent bits of infor- mation in a quantum context, even if these informations are concerned with ways of speech. Furthermore, some authors think that superposi- tions may be understood in terms of paraconsistent logics, and even the notion of complementarity was already treated by such a means. This is, apparently, a nice motivation to try to merge these two frameworks. In this work, we develop the technical details, by basing our quasi-set theory in the paraconsistent system C1. We also elaborate a new hierarchy of paraconsistent calculi, the paraconsistent calculi with indiscernibility. For the finalities of this work, some philosophical questions are outlined, but this topic is left to a future work. (shrink)

I briefly discuss the epistemological role of quasi-set theory in mathematics and theoretical physics. Quasi-set theory is a first order theory, based on Zermelo-Fraenkel set theory with Urelemente. Nevertheless, quasi-set theory allows us to cope with certain collections of objects where the usual notion of identity is not applicable, in the sense that $x = x$ is not a formula, if $x$ is an arbitrary term. Basically, quasi-set theory offers us some sort of logical apparatus for questioning the need for (...) identity in some branches of mathematics and theoretical physics. I also use this opportunity to discuss a misunderstanding about quasi-sets due mainly to Nicholas J. J. Smith, who argues, in a general way, that sense cannot be made of vague identity. (shrink)

The algebra of all binary relations on a given set is the most important example of a relation algebra . In this note we will examine the possible isomorphisms within some subclasses of a closely related class ; A is a relation set algebra with base U if its Boolean reduct is a field of sets with unit element 2 U, its universe A contains the identity relation on U and it is closed under the operations −1 and |, where (...) R |S = { : ∈ R, ∈ S for some z} and R−1 = { : ∈ R} for any R, S ⊆ 2 U. The class of all relation set algebras is denoted by Rs. (shrink)