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)

The set of equations which use only one variable and hold in all representable relation algebras cannot be derived from any finite set of equations true in all representable relation algebras. Similar results hold for cylindric algebras and for logic with finitely many variables. The main tools are a construction of nonrepresentable one-generated relation algebras, a method for obtaining cylindric algebras from relation algebras, and the use of relation algebras in defining algebraic semantics for first-order logic.

Conjecture (1) of [Ma83] is confirmed here by the following result: if $3 \leq \alpha < \omega$, then there is a finite relation algebra of dimension α, which is not a relation algebra of dimension α + 1. A logical consequence of this theorem is that for every finite α ≥ 3 there is a formula of the form $S \subseteq T$ (asserting that one binary relation is included in another), which is provable with α + 1 variables, but not (...) provable with only α variables (using a special sequent calculus designed for deducing properties of binary relations). (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.

This is a supplement to the paper “Finitary Algebraic Logic” [1]. It includes corrections for several errors and some additional results. MSC: 03G15, 03G25.

If K is a class of semiassociative relation algebras and K contains the relation algebra of all binary relations on a denumerable set, then the word problem for the free algebra over K on one generator is unsolvable. This result implies that the set of sentences which are provable in the formalism Lwx is an undecidable theory. A stronger algebraic result shows that the set of logically valid sentences in Lwx forms a hereditarily undecidable theory in Lwx. These results generalize (...) similar theorems, due to Tarski, concerning relation algebras and the formalism Lx. (shrink)

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.

We confirm a conjecture, about neat embeddings of cylindric algebras, made in 1969 by J. D. Monk, and a later conjecture by Maddux about relation algebras obtained from cylindric algebras. These results in algebraic logic have the following consequence for predicate logic: for every finite cardinal α ≥ 3 there is a logically valid sentence X, in a first-order language L with equality and exactly one nonlogical binary relation symbol E, such that X contains only 3 variables (each of (...) which may occur arbitrarily many times), X has a proof containing exactly α + 1 variables, but X has no proof containing only α variables. This solves a problem posed by Tarski and Givant in 1987. (shrink)

There are eighteen isomorphism types of finite relation algebras with eight or fewer elements, and all of them are representable. We determine all the cardinalities of sets on which these algebras have representations.

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)

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.

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)

I argue that its appearing to you that P does not provide justification for believing that P unless you have independent justification for the denial of skeptical alternatives – hypotheses incompatible with P but such that if they were true, it would still appear to you that P. Thus I challenge the popular view of ‘dogmatism,’ according to which for some contents P, you need only lack reason to suspect that skeptical alternatives are true, in order for an experience as (...) of P to justify belief that P. I pursue three lines of objection to dogmatism, having to do with probabilistic reasoning, considerations of future or hypothetically available justification, and epistemic circularity. I briefly sketch a fall-back position which avoids the problems raised. (shrink)

Michael Bergmann claims that all versions of epistemic internalism face an irresolvable dilemma. We show that there are many plausible versions of internalism that falsify this claim. First, we demonstrate that there are versions of ‘‘weak awareness internalism’’ that, contra Bergmann, do not succumb to the ‘‘Subject’s Perspective Objection’’ horn of the dilemma. Second, we show that there are versions of ‘‘strong awareness internalism’’ that do not fall prey to the dilemma’s ‘‘vicious regress’’ horn. We note along the way that (...) these versions of internalism do not, in avoiding one horn of the dilemma, succumb to the dilemma’s other horn. The upshot is that internalists have many available strategies for avoiding dilemmatic defeat. (shrink)

I believe that Tom is the proud father of a baby boy. Why do I think his child is a boy? A natural answer might be that I remember that his name is ‘Owen’ which is usually a boy’s name. Here I’ve given information that might be part of a causal explanation of my believing that Tom’s baby is a boy. I do have such a memory and it is largely what sustains my conviction. But I haven’t given you just (...) any causally relevant information, I’ve given my grounds for my belief. I’ve given reasons that might justify me in supposing that Tom’s baby is a boy. Less naturally, the question might be taken as a request for a broader causal explanation of my holding this belief. Appropriate answers might cite all manner of facts concerning the evolution of the human race, why I chose to pursue philosophy and hence came to know Tom, the mechanisms of email transmission, the firing of various neurons, the circumstances of concept formation as a result of which I’m able to grasp the thought that Tom’s baby is a boy, and so on. It is an interesting question what distinguishes the narrower set of answers that I first suggested. I won’t pursue that here. I assume you have a good enough sense of the distinction I’m drawing. We might call the narrower set of answers justifying reasons, the kind of reasons I might cite in justifying my belief. Answers of the first sort are clearly relevant to epistemological evaluation. In assessing whether you know p or are rational in believing it to the degree you do, I will naturally want to consider what reasons you have for your belief. In deliberating myself about whether to believe p, in seeking an answer to the question of whether p, I will naturally consider what reasons or grounds I have to suppose that p. But what I want to focus on here is how explanations of the broader sort bear on such questions as whether to believe p. From a third-person perspective we can ask, ‘In assessing the epistemic status of S’s belief that p, what is the relevance of causal information that lies outside of the realm of justifying reasons?’ From the first-person standpoint we can ask ‘In seeking to answer whether p, how should such causal information affect my deliberations?’ At first it might seem that such broader causal information could have little relevance if any. Like any belief my belief that p can be traced back to innumerable causes from far and wide.. (shrink)