Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-29T02:25:24.173Z Has data issue: false hasContentIssue false

Matrix development of the calculus of relations

Published online by Cambridge University Press:  12 March 2014

Irving M. Copilowish*
Affiliation:
University of Illinois

Extract

In his very interesting address On the calculus of refations, Professor Tarski discussed alternative bases for that calculus. He was there interested in “…different methods of setting up the foundations of this elementary calculus in a rigorously deductive way…” and so did not discuss the method of developing the calculus of relations with which this paper is concerned. Our purpose here is to show how the use of matrix notation for relations permits an algorithmic rather than a postulational-deductive development of the calculus of relations. One limitation of the present approach is to be admitted at the very outset: to enjoy the full benefits of the matrix approach, we are obliged to confine our investigations to Universes of Discourse which are finite. The reason for this restriction will become apparent presently.

Type
Articles
Copyright
Copyright © Association for Symbolic Logic 1948

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

1 This Journal, vol. 6 (1941), pp. 73–89.

2 Ibid. pp. 74 ff., pp. 77 ff., and pp. 86–7.

3 Ibid. p. 74.

4 Whitehead, A. N. and Russell, B., Principia mathematica, Cambridge, England, 19101913. Second edition, 1925–7.Google Scholar

5 Collected papers of Charles Sanders Peirce, edited by Hartshorne, C. and Weiss, P.. Volume 3, Exact logic, Cambridge, Mass., 1933.Google Scholar All page references to Peirce will be to this volume.

6 Algebra und Logik der Relative, Leipzig, 1895. This work appeared as Volume III of Ernst Schröder's Vorlesungen über die Algebra der Logik.

7 Description of a notation for the logic of relatives, resulting from an amplification of the conceptions of Boole's calculus of logic [first published in the Memoirs of the American Academy of Arts and Sciences, n.s. vol. 9, part 2, (1873), pp. 317–378.] Peirce, op. cit. pp. 27–98. Of this work, Peirce remarked in his Lowell lectures (1903) that: “In 1870 I made a contribution to this subject which nobody who masters the subject can deny was the most important excepting Boole's original work that has ever been made.” op. cit. p. 27.

8 Thus Peirce added a Postscript to his Brief description of the algebra of relatives [privately printed, Baltimore 1882, reprinted op. cit. pp. 180–6] in which he wrote: “I have this, day had the delight of reading for the first time Professor Cayley's, Memoir on matrices in the Philosophical transactions for 1858 [Philosophical transactions of the Royal Society of London, vol. 148, part 1, pp. 1737.Google Scholar] The algebra he there describes seems to me substantially identical with my long subsequent algebra for dual relatives.” Again, in his Nomenclature and divisions of dyadic relations [privately printed, circa 1903, reprinted op. cit. pp. 367–387] Peirce wrote: “Imagine all the dyads (or ordered pairs) of individuals in the universe to be arrayed in a matrix (Cayley's term, though the application of the conception to the logic of relations was first made by the author)…”

9 Ibid. p. 86.

10 Ibid. p. 140 and pp. 180–181.

11 “Taking dual individual relatives, for instance, we may arrange them all in an infinite block …” ibid. p. 140; and “These letters may be conceived to be finite in number or in numerable.” ibid. p. 180.

12 Ibid. p. 141 and p. 184. That Peirce did not propose any further generalization was a consequence of his peculiar belief that all relations of higher degree could be reduced to combinations of triadic relations.

13 Ibid. pp. 34, 140, 144,195, 377. But cf. p. 180.

14 See Principia mathematica, p. 243.

15 The question naturally arises as to the sense in which this convention could be considered a restriction prior to the drawing of type distinctions. But Peirce's habitual preoccupation with ontology suggests that he must have attached some restrictedness to the notion of an individual. In the case of Schröder, who made the same distinction, the situation is clearer. See note 21.

16 Thus, in 1870 he wrote : “I think there can be no doubt that a calculus, or art of drawing inferences, based upon the notation I am to describe, would be perfectly possible, and even practically useful in some difficult cases, and particularly in the investigation of logic. I regret that I am not in a situation to be able to perform this labor, but the account here given of the notation itself will afford the ground of a judgment concerning its probable utility.” (Ibid. p. 28. The notation referred to is matrix notation.) Nevertheless, thirteen years later he came up against certain difficulties, and felt himself forced to conclude that: “The effect of these peculiarities is that this algebra cannot be subjected to hard and fast rules like those of the Boolian calculus; and all that can be done in this place is to give a general idea of the way of working with it.” (Ibid. p. 200. The difficulties were not algebraic, but had to do with certain complications in translating from English into the algebraic symbolism and back again, and were concerned more with the deviousness of English idiom than with any deficiencies in the algebra.)

17 See, for example, Schröder, op. cit. pp. 33–34.

18 Ibid. p. 11, p. 44, and pp. 64–66.

19 Ibid., p. 5. “Oder aber das System der Elemente ist ein “unendliches” (unbegrenztes), wo dann von ihrer “Anzahl” nicht gesprochen werden kann. Im letzteren Falle mögen die Elemente entweder “diskrete” sein, etwa ein sogenanntes “einfach unendliches” System bildend, oder auch nicht, d.h. sie dürfen ebensogut auch als “konkrete” gedacht werden, welche z.B. ein “Kontinuum” ausfüllen, wie die Punkte einer linie, einer Fläche, eines Körpers, insbesondre einer Geraden, einer Ebene oder des Raumes.” See also pp. 38–9, p. 41, p. 51, and p. 53.

20 “Als gegeben, irgendwie begrifflich bestimmt, denken wir uns die “Elemente” oder Individuen

1) A, B, C, D, E, …

einer “gewöhnlichen” Mannigfaltigkeit … Sie müssen unter sich verträglich (konsistent), sein, sodass nicht etwa die Setzung eines von ihnen der Denkbarkeit eines andern vorbeugt und sie müssen einander gegenseitig ausschliessen (unter sich disjunkt sein), sodass auch keines der Elemente als eine Klasse gedeutet werden dürfte, die ein andres von ihnen unter sich begreift.” ibid., pp. 4–5.

21 On this, see Schröder's, Vorlesungen, Vol. I, pp. 248f.Google Scholar and p. 342. That Schröder had anticipated the distinctions of the theory of types has been pointed out by Professor Church: Schröder's anticipation of the simple theory of types, preprinted for the members of the Fifth International Congress for the Unity of Science, Cambridge, Mass., 1939, as from The journal of unified science (Erkenntnis), vol. 9, 4 pp. In the present connection, I think we may understand Schröder to be restricting himself to any homogeneous Universe of Discourse (Denkbereich), not necessarily the lowest. This would allow the formulation of the algebra of (homogeneous) relations of any given type, rather than of the lowest type only. But the restriction to homogeneity still binds too tightly. See note 22.

22 Without these restrictions, we may consider relations over a non-homogeneous domain, allowing such expressions as ‘Κ ε κ’ to be true or false, rather than meaningless. That this does not lead to contradictions of the type of the Russell Paradox has been urged by Quine (New foundations for mathematical logic, American mathematical monthly, vol. 44 (1937), pp. 70–80), who there avoided the paradoxes by certain restrictions on abstraction, while admitting unstratified formulas such as the above.

23 Principia mathematica, p. 26.

24 This is due, of course, to the non-categoricity of Boolean algebra. Allowing r ij to range over the interval I would adapt these matrices for use in a probability-calculus. This interesting aspect will not be considered in the present paper, however.

25 Principia mathematica, p. 256.

26 Origin of this familiar riddle is unknown. As already old in 1860, it is quoted by De Morgan in the equivalent form, “His mother was my mother's only child.” (Transactions of the Cambridge Philosophical Society, vol. 10, p. 335.)

27 American journal of mathematics, vol. 68 (1946), pp. 345–384. See especially his Chapter II, Boolean tensor algebra.