Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-22T22:42:04.192Z Has data issue: false hasContentIssue false
  • English
  • Français

ON TARSKI’S AXIOMATIC FOUNDATIONS OF THE CALCULUS OF RELATIONS

Published online by Cambridge University Press:  08 May 2017

HAJNAL ANDRÉKA ,
STEVEN GIVANT ,
PETER JIPSEN  and
ISTVÁN NÉMETI
HAJNAL ANDRÉKA
Affiliation:
ALFRÉD RÉNYI INSTITUTE OF MATHEMATICS HUNGARIAN ACADEMY OF SCIENCES H-1364BUDAPEST, PF. 127 HUNGARYE-mail: [email protected]
STEVEN GIVANT
Affiliation:
MILLS COLLEGE DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE 5000 MACARTHUR BOULEVARD OAKLAND, CA 94613, USAE-mail:[email protected]
PETER JIPSEN
Affiliation:
CHAPMAN UNIVERSITY, FACULTY OF MATHEMATICS SCHOOL OF COMPUTATIONAL SCIENCES 545 WEST PALM AVENUE ORANGE, CA 92866, USAE-mail:[email protected]
ISTVÁN NÉMETI
Affiliation:
ALFRÉD RÉNYI INSTITUTE OF MATHEMATICS HUNGARIAN ACADEMY OF SCIENCESH-1364BUDAPEST, PF. 127 HUNGARYE-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

It is shown that Tarski’s set of ten axioms for the calculus of relations is independent in the sense that no axiom can be derived from the remaining axioms. It is also shown that by modifying one of Tarski’s axioms slightly, and in fact by replacing the right-hand distributive law for relative multiplication with its left-hand version, we arrive at an equivalent set of axioms which is redundant in the sense that one of the axioms, namely the second involution law, is derivable from the other axioms. The set of remaining axioms is independent. Finally, it is shown that if both the left-hand and right-hand distributive laws for relative multiplication are included in the set of axioms, then two of Tarski’s other axioms become redundant, namely the second involution law and the distributive law for converse. The set of remaining axioms is independent and equivalent to Tarski’s axiom system.

Keywords

03G1503B3003C0503C13axiom systemcalculus of relationsindependence modelindependent axiom systemrelation algebra
Type
Articles
Information
The Journal of Symbolic Logic , Volume 82 , Issue 3 , September 2017 , pp. 966 - 994
Copyright
Copyright © The Association for Symbolic Logic 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Chin, L. H., and Tarski, A., Distributive and modular laws in the arithmetic of relation algebras . University of California Publications in Mathematics, New Series, vol. 1 (1951), pp. 341–384.Google Scholar
De Morgan, A., On the syllogism, no. IV, and on the logic of relations . Transactions of the Cambridge Philosophical Society, vol. 10 (1864), pp. 331–358.Google Scholar
Henkin, L., Monk, J. D., and Tarski, A., Cylindric Algebras, Part I. Studies in Logic and the Foundations of Mathematics, vol. 64, North-Holland, Amsterdam, 1971.Google Scholar
Hirsch, R. and Hodkinson, I., Relation Algebras by Games. Studies in Logic and the Foundations of Mathematics, vol. 147, Elsevier Science, North-Holland, Amsterdam, 2002.Google Scholar
Jónsson, B., Varieties of relation algebras . Algebra Universalis, vol. 15 (1982), pp. 273–298.CrossRefGoogle Scholar
Jónsson, B., The theory of binary relations. Algebraic Logic (Andréka, H., Monk, J. D., and Németi, I., editors), Colloquia Mathematica Societatis János Bolyai, vol. 54, North-Holland Publishing Company, Amsterdam, 1991, pp. 245–292.Google Scholar
Jónsson, B., and Tarski, A., Representation problems for relation algebras . Bulletin of the American Mathematical Society, vol. 54 (1948), pp. 80, 1192.Google Scholar
Jónsson, B., and Tarski, A., Boolean algebras with operators, Part II . American Journal of Mathematics, vol. 74 (1952), pp., 127–162.CrossRefGoogle Scholar
Kamel, H., Relational Algebra. Doctoral dissertation, University of Pennsylvania, Philadelphia PA, 1952.Google Scholar
Kamel, H., Relational algebra and uniform spaces . Journal of the London Mathematical Society, vol. 29 (1954), pp. 342–344.CrossRefGoogle Scholar
Löwenheim, L., Über Möglichkeiten im Relativkalkül . Mathematische Annalen , vol. 76 (1915), pp. 447–470.CrossRefGoogle Scholar
Lyndon, R. C., The representation of relational algebras, II . Annals of Mathematics, series 2, vol. 63 (1956), pp. 294–307.CrossRefGoogle Scholar
Maddux, R. D., Topics in Relation Algebras. Doctoral dissertation, University of California at Berkeley, 1978.Google Scholar
Maddux, R. D., Some varieties containing relation algebras . Transactions of the American Mathematical Society, vol. 272 (1982), pp. 501–526.CrossRefGoogle Scholar
Maddux, R. D., A sequent calculus for relation algebras . Annals of Pure and Applied Logic, vol. 25 (1983), pp. 73–101.CrossRefGoogle Scholar
Maddux, R. D., Necessary subalgebras of simple nonintegral semiassociative relation algebras . Algebra Universalis, vol. 27 (1990), pp. 544–558.CrossRefGoogle Scholar
Maddux, R. D., Pair-dense relation algebras . Transactions of the American Mathematical Society, vol. 328 (1991), pp. 83–131.CrossRefGoogle Scholar
Maddux, R. D., Relation Algebras. Studies in Logic and the Foundations of Mathematics, vol. 150, Elsevier Science, North-Holland, Amsterdam, 2006.Google Scholar
McCune, W., Prover9 and Mace4, http://www.cs.unm.edu/∼mccune/mace4, 2005–2010.Google Scholar
McKenzie, R. N., Representations of integral relation algebras . Michigan Mathematical Journal, vol. 17 (1970), pp. 279–287.CrossRefGoogle Scholar
Monk, J. D., On representable relation algebras . Michigan Mathematical Journal, vol. 11 (1964), pp. 207–210.CrossRefGoogle Scholar
Peirce, C. S., Note B. The logic of relatives . Studies in Logic by Members of the Johns Hopkins University (Peirce, C. S., editor), Little, Brown, and Company, Boston, 1883, pp. 187–203. [Reprinted by John Benjamins Publishing Company, Amsterdam, 1983.]CrossRefGoogle Scholar
Russell, B., The Principles of Mathematics. Cambridge University Press, 1903. [Reprinted by Allen & Unwin, London, 1948.]Google Scholar
Schröder, E., Vorlesungen über die Algebra der Logik (exakte Logik), vol. III, Algebra und Logik der Relative, part 1. B. G. Teubner, Leipzig, 1895. [Reprinted by Chelsea Publishing Company, New York, 1966.]Google Scholar
Tarski, A., On the calculus of relations , this Journal, vol. 6 (1941), pp. 73–89.Google Scholar
Tarski, A., Book manuscript containing some of Tarski’s early contributions to the theory of relation algebras, written during the period 1943 to 1945. The book was never published, but most of the results in the book were later included in [27].Google Scholar
Tarski, A. and Givant, S., A Formalization of Set Theory without Variables. Colloquium Publications, vol. 41, American Mathematical Society, Providence RI, 1987.Google Scholar