Search

The connections between Tarski's Q-relation algebras and Thompson's groups F, T, V, and monoid M are reviewed here, along with Jonsson-Tarski algebras, fork algebras, true pairing algebras, and tabular relation algebras. All of these are related to the finitization problem and Tarski's formalization of set theory without variables. Most of the technical details occur in the variety of J-algebras, which is obtained from relation algebras by omitting union and complementation and adopting a set of axioms created by Jonsson. Every relation algebra or J-algebra that contains a pair of conjugated quasiprojections satisfying the Domain and Unicity conditions, such as those that arise from J\'onsson-Tarski algebras or fork algebras, will also contain homomorphic images of F, T, V, and M. The representability of tabular relation algebras is extended here to J-algebras, using a notion of tabularity equivalent among relation algebras to the original definition., Comment: 64 pages, 4 figures, 1 table

The Theorems of Pappus and Desargues are generalized by two special formulas that hold in the three-dimensional vector space over a field.

The Tarskian classical relevant logic TR arises from Tarski's work on the foundations of the calculus of relations and on first-order logic restricted to finitely many variables, presented by Tarski and Givant their book, A Formalization of Set Theory without Variables, and summarized in first nine sections. TR is closely related to the well-known logic KR. Every formula of relevance logic has a corresponding sentence in Tarski's extended first-order logic of binary relations with operators on the relation symbols. A formula is in TR (by definition), or in KR (by a theorem), if and only if its corresponding sentence can be proved in first-order logic, using at most four variables, from the assumptions that all binary relations are dense and, for TR, commute under composition, or, for KR, are symmetric. The vocabulary of TR is the same as the classical relevant logic CR$^*$ proposed by Meyer and Routley but TR properly contains CR$^*$. The frames characteristic for TR are the ones that are characteristic for CR$^*$ and satisfy an extra frame condition. There are formulas in TR (but not in CR$^*$) that correspond to this frame condition and provide a counterexample to a theorem of T. Kowalski. The frames characteristic for TR, or KR, are the ones whose complex algebras are integral dense relation algebras that are commutative, or symmetric, respectively. For both classes, the number of isomorphism types grows like the number of isomorphism types of ternary relations. Asymptotic formulas are obtained for both classes. Similar results apply to a hierarchy of logics defined by the number of variables used in the first-order proofs of their corresponding sentences.

Canonical relativized cylindric set algebras are used to sharpen the relative representation theorem for weakly associative relation algebras, that every complete atomic weakly associative relation algebra is isomorphic with the relativization of a set relation algebra to a symmetric and reflexive binary relation, by insuring that the atoms of the set relation algebra and its relativization are orbits of single sequences under a group of permutations of the underlying set. This sharpening of the relative representation theorem was first proved for the Resek-Thompson Theorem in 1989., Comment: 34 pages, Chapter 13 in Outstanding Contributions to Logic, Vol. 19, Springer

Tarski's relevance logic is defined and shown to contain many formulas and derived rules of inference. The definition arises from Tarski's work on first-order logic restricted to finitely many variables. It is a relevance logic because it contains the Basic Logic of Routley-Plumwood-Meyer-Brady, has Belnap's variable-sharing property, and avoids the paradoxes of implication. It does not include several formulas used as axioms in the Anderson-Belnap system $R$. For example, the Axiom of Contraposition is not in Tarski's relevance logic. On the other hand, the Rules of Contraposition and Disjunctive Syllogism are derived rules of inference in Tarski's relevance logic. It also contains a formula (not previously known or considered as an axiom for any relevance logic) that provides a counterexample to a completeness theorem of T. Kowalski (that the system $R$ is complete with respect to the class of dense commutative relation algebras).

Algebras introduced by, or attributed to, Sugihara, Belnap, Meyer, and Church are representable as algebras of binary relations with set-theoretically defined operations. They are definitional reducts or subreducts of proper relation algebras. The representability of Sugihara matrices yields sound and complete set-theoretical semantics for R-mingle., Comment: 39 pages, 6 tables, 5 figures, submitted to Journal of Logical and Algebraic Methods in Programming, third version, math-LO

In this note, we give two different proofs that relation algebra $52_{65}$ is representable over a finite set. The first is probabilistic, and uses Johnson schemes. The second is an explicit group representation over $ (\mathbb{Z}/2\mathbb{Z})^{10}$. We also give a finite representation of $59_{65}$ over $\mathbb{Z}/113\mathbb{Z}$ using a technique due to Comer.

The title theorem is proved by example: an algebra of binary relations, closed under intersection and composition, that is not isomorphic to any such algebra on a finite set.

Many finite symmetric integral non-representable relation algebras, including almost all Monk algebras, can be embedded in the completion of an atomic symmetric integral representable relation algebra whose finitely-generated subalgebras are finite., Comment: 22 pages, presented as Subcompletions of atomic representable relational algebras, Invited Talk, at the Workshop on Lattices and Relations, 12 September 2012, Institute for Logic, Language and Computation, University of Amsterdam, The Netherlands

This paper presents a proof of Gallai's Theorem, adapted from A. Soifer's presentation in The Mathematical Coloring Book of E. Witt's 1952 proof of Gallai's Theorem., Comment: 8 pages, 1 figure

We prove that any equational basis that defines RRA over wRRA must contain infinitely many variables. The proof uses a construction of arbitrarily large finite weakly representable but not representable relation algebras whose "small" subalgebras are representable., Comment: To appear in Review of Symbolic Logic