Modern Logic: From Frege to Gödel: Nineteenth-Century Mathematics

views updated

MODERN LOGIC: FROM FREGE TO GÖDEL: NINETEENTH-CENTURY MATHEMATICS

Mathematics in the nineteenth century was characterized by reorganization in every field, effected both by generalization, which led to the viewing of areas once considered discrete as special instances of the same general case, and by the examination of foundations, either in terms of basic concepts or by an axiomatic approach. Apart, therefore, from any specific contributions that mathematicians made to modern logic, the atmosphere was highly favorable to an explicitly logical investigation both of mathematics in general and of its various branches, including, by the end of the century, mathematical logic itself. At the same time, the growth of abstract algebra encouraged the persistence of Leibniz's ideal of mathematizing deductive logic; his ideas, although most were unpublished, maintained a steady, if at first tenuous, foothold. Thus, the early mathematical logicians, having caught the idea of a new kind of algebra, tended to work on it as a specialized branch of mathematics. By the end of the nineteenth century it had become an instrument sufficiently perfected to be able to discard its traditional algebraic appearance, even to forget momentarily its self-concern, and to apply itself to the articulation of the increasingly well-organized mathematical material. Only in the twentieth century did it catch up to its own axiomatic origins and fruitfully rejoin its algebraic ones.

Peacock

As early as 1821, A. L. Cauchy (1789–1857), in his influential Cours d'analyse (Paris, 1821, introduction, p. ii), attacked the current use of algebraic reasonings in geometry because "they tend to make one attribute an indefinite range to the algebraic formulas, while in reality most of these formulas hold uniquely under certain conditions, and for certain values of the quantities concerned." This thought was adopted, in a more positive version, by George Peacock (1791–1858) in A Treatise on Algebra (2 vols., London, 1842–1845), elaborating a work of 1830. Instead of merely rejecting such illegitimate, or at any rate unjustified, extensions of the ranges of algebraic formulas, he distinguished between two kinds of algebra, arithmetical and symbolic.

Arithmetical algebra is the science which results from the use of symbols and signs to denote numbers and the operations to which they may be subjected; those numbers or their representatives, and the operations upon them, being used in the same sense and with the same limitations as in common arithmetic. [In symbolical algebra] the symbols which are used are perfectly general in their representation, and perfectly unlimited in their values; and the operations upon them, in whatever manner they are denoted, or by whatever name they are called, are universal in their application. (Vol. I, Ch. 1)

The relationship of the two is more fully explained in the introduction:

The generalizations of arithmetical algebra are generalizations of reasoning not of form. … Symbolical algebra adopts the rules of arithmetical algebra, but removes altogether their restrictions. … It is this adoption of the rules of the operations of arithmetical algebra as the rules for performing the operations which bear the same names in symbolical algebra, which secures the absolute identity of the results in the two sciences so far as they exist in common. … This principle, in my former Treatise on Algebra, I denominated the "principle of the permanence of equivalent forms."

Peacock expressed his conviction that the convention by which such permanence had been commonly assumed had both delayed the emergence of his symbolical algebra as a science in its own right and resulted in consequent confusion and false reasoning such as Cauchy had complained of. By contrast to arithmetical algebra, "the results of symbolical algebra, which are not common to arithmetical algebra, are generalizations of form, and not necessary consequences of the definitions" which introduce special conditions according as the variables denote lines, forces, periods of time, and so on.

Boole

It is not hard to see the influence of Peacock's thoughts on George Boole. In the introduction to The Mathematical Analysis of Logic (1847), Boole wrote:

Those who are acquainted with the present state of the theory of symbolical algebra, are aware, that the validity of the process of analysis does not depend upon the interpretation of the symbols which are employed, but solely upon the laws of their combination. Every system of interpretation which does not affect the truth of the relation supposed, is equally admissible. … That to the existing forms of analysis a quantitative interpretation is assigned, is the result of the circumstances by which those forms were determined, and is not to be construed into a universal condition of analysis. It is upon the foundation of this general principle, that I purpose to establish the calculus of logic, and that I claim for it a place among the acknowledged forms of mathematical analysis, regardless that in its object and in its instruments it must at present stand alone.

In this passage we see mathematical logic struggling to be born, aware of its parentage, but still uncertain, as it continued to be for some time, of its status. Boole himself interpreted his calculus in relation to both classes and propositions. Thus, "The symbol 1 − x selects those cases in which the proposition X is false" (The Mathematical Analysis of Logic, "Of Hypotheticals"), and "Let us for simplicity of conception give to the symbol x the particular interpretation of men, then 1 − x will represent the class of 'not-men'" (An Investigation of the Laws of Thought, London, 1854, Ch. 3 in Prop. iv).

Peacock's work drew increased attention to the formal properties of operations, and Boole regarded his subject from this point of view.

The laws we have established … are sufficient for the base of a calculus. From the first of them it appears that the elective symbols are distributive, from the second that they are commutative ; properties which they possess in common with symbols of quantity, and in virtue of which, all the processes of common algebra are applicable to the present system." (The Mathematical Analysis of Logic, "First Principles")

These terms actually antedate Peacock; they may have been introduced by F. J. Servois (see Annales des mathématiques, 5 [1814]: 93). "Associativity" has been ascribed to Sir William Rowan Hamilton (see Hermann Hankel's Theorie der complexen Zahlensysteme, Leipzig, 1867).

Gergonne

The new trend in algebra was already evidenced by the "Essai de dialectique rationelle" (in Annales des mathématiques 7 [1816–1817]: 189–228) of J. D. Gergonne (1771–1859). In this he wrote:

In the same way that an algebraic calculation can be carried out without one having the least idea about the meaning of the symbols on which one is operating, it is possible to follow a course of reasoning without any knowledge of the meaning of the terms in which it is expressed, or without adverting to it if one knows it.

Such a formalistic approach would have been more in order when fields of application were better charted, and Karl Weierstrass was still fighting for this point of view many years later. Gergonne later did important work on duality in geometry, which shows again his ability to distinguish structure from interpretation. He offered a new analysis of the fundamental ideas of syllogistic and used an inverted C for inclusion, now standardized as the hook, ⊂.

De Morgan

Augustus De Morgan, a contemporary of Peacock and Boole, took a special interest in the organization of mathematics for didactic purposes. After Elements of Arithmetic (1830) he wrote On the Study and Difficulties of Mathematics (1831), First Notions of Logic (1839), which was designed to help beginning students of geometry, and Formal Logic (1847). In Trigonometry and Double Algebra he investigated symbolic calculuses. A remarkable text ("On the Syllogism, III") shows De Morgan striking out element after element in the material proposition "Every man is animal" till he is left with X——Y, showing the "pure form of the judgment"; thus, he made a start on the extension of the mathematical notion of function, to which Boole, Peirce, and most notably Frege also contributed. De Morgan's right parenthesis, as used in "X )" to mean "every X," yielding "X )Y "—that is, every X is Y —is reminiscent of Gergonne's inverted C, although Gergonne's symbol means "is contained in" and operates on two terms rather than one.

Grassmann

One of the creators of a new form of algebra was H. G. Grassmann (1809–1877). Grassmann's Ausdehnungslehre (Leipzig, 1844; rev. ed., 1862), fundamental to vector analysis, anticipated W. R. Hamilton's work through its greater generality and influenced Alfred North Whitehead's A Treatise on Universal Algebra with Applications (Cambridge, U.K., 1898). Giuseppe Peano's Calcolo geometrico (Turin, 1888) was written "according to the Ausdehnungslehre of H. Grassmann, preceded by the operations of deductive logic."

Non-Euclidean geometry

In geometry the great breakthrough was the effective creation of non-Euclidean systems. The chief figures were János Bolyai (1802–1860), Nikolai Ivanovich Lobachevski (1793–1856), and Bernhard Riemann (1826–1866). Bolyai's work on non-Euclidean geometry was titled Appendix Scientiam Spatii Absolute Veram Exhibens; A Veritate aut Falsitate Axiomatis XI Euclidei (A Priori Haud Unquam Decidenda) Independentem. Written in 1823, it was published in 1833 at Maros-Vásárhely in the second volume of the Tentamen of his father, F. Bolyai. Lobachevski wrote Geometrische Untersuchungen zur Theorie der Parallellinien (Berlin, 1840), an elaboration of ideas first presented in a lecture delivered at Kazan in 1826. Riemann's inaugural lecture Ueber die Hypothesen, welche der Geometrie zu Grunde liegen (1854) was published at Göttingen in 1867. Each seems to have done his work independently of the others, but behind all of them appears the great, although in this matter somewhat enigmatic, figure of Karl Friedrich Gauss (1777–1855), friend of Bolyai's father and of Lobachevski's teacher Bartels and teacher of Riemann. Gauss's correspondence shows him long to have had ideas on the subject, and to him we owe the word non-Euclidean (in a letter to Taurinus, 1824).

Bolyai, as the title of his work indicates, simply dropped Euclid's axiom of parallels; Lobachevski adopted its denial. Both required the infinity of the straight line. Riemann, approaching the matter from an analytic point of view, wished to determine the general conditions of spaces in which the measure of distance would remain everywhere constant and figures could move freely without deformation. He was thus led to consider spaces of constant curvature and more than three dimensions, with Euclidean space a special case. Riemann's work was immediately taken up by Hermann von Helmholtz (1821–1894), in Über die thatsachlichen Grundlagen der Geometrie (1868–1869) and Über die Thatsachen, die der Geometrie zu Grunde liegen (1868), and was further refined by Sophus Lie (1842–1899). Lie was one of the principal developers of the theory of groups, which Felix Klein (1849–1925) applied to geometry in his Erlanger Programm, Vergleichende Betrachtungen über neuere geometrische Forschungen (Erlangen, 1872; translated by M. W. Haskell as "A Comparative Review of Recent Researches in Geometry," in Bulletin of the New York Mathematical Society 2 [1892–1893]: 215–249).

Independence

Though Bertrand Russell (in 1897), Whitehead (in 1898), and David Hilbert (in 1899) all wrote on geometry, and Hilbert's later foundational work (Grundlagenforschung ) provided the basis for all subsequent investigations, these pioneers of mature mathematical logic failed to secure independence for their propositional axioms. This is remarkable after all the attention that had been devoted to the independence of Euclid's axiom of parallels. Frege, too, failed in this matter. Alessandro Padoa, in 1901, gave directives for establishing the independence of concepts within an axiom system—an idea that influenced Peano—but no general method for securing the independence of propositional axioms was attained until Jan Łukasiewicz (1925) and Paul Bernays (1926), independently, found the method of interpretation by matrices.

Many-valued logics and proof theory

Non-Euclidean geometries are often mentioned in discussions of the status of many-valued logics, but they appear to have had no direct influence. (Łukasiewicz was brought to the idea by Aristotle's Peri Hermeneias. ) It is likely that the theory of groups (closed systems of operations)—which was already finding widespread application by the end of the nineteenth century—and the rise of different algebras did much to create the climate of thought in which proof theory, and in general the metalogical investigation of the properties of entire deductive systems, could be developed. Such investigation seems to be one of the most notable characteristics differentiating mathematical logic from the logic of any other period. Proof theory stems mainly from Hilbert.

Schröder

The early, algebraic period of mathematical logic ended with Ernst Schröder (1841–1902). After a paper on algorithms for solving equations (1870) and a textbook on arithmetic and algebra, Schröder devoted himself more and more to the algebra of logic, his two chief works being Der Operationskreis des Logikkalküls (Leipzig, 1877) and Vorlesungen über die Algebra der Logik (3 vols., Leipzig, 1890–1905). Much of his work was a tidying up of the past. He discarded Boole's subtraction and division, which were subject to too many restrictions to be satisfactory inverse operations; used (as had W. S. Jevons) the sign of addition in the sense of inclusive rather than exclusive alternation; and introduced at the beginning a sign for inclusion. In this last matter he independently duplicated Frege's abandonment of the algebraic form in Begriffsschrift (Halle, 1879), which later became standard with Principia Mathematica (3 vols. Cambridge, U.K., 1910–1913). But Schröder remained interested in the solution of equations; his results for the Boolean system were taken over by Whitehead in A Treatise on Universal Algebra. Like Peirce, Schröder noticed a duality between logical multiplication and addition and similarly between the null and the universal classes. Duality in geometry had been brought to the fore by J. V. Poncelet (1822), enunciated with greater generality by Gergonne (1827), and skillfully exploited by Jakob Steiner (1830).

Schröder explicitly rejected those syllogisms that are invalid when the terms are null, Boole having merely passed them over. Besides using the method of 1 − 0 evaluation, which goes back to Boole, he developed a process of reduction to normal form. Schröder introduced two novelties. Unlike those of his contemporaries mentioned above, he was interested in independence, wishing particularly to have the distributive law independent of his other axioms, and he was thus brought to perhaps the first idea of a nondistributive lattice. He also had a clear view of the need for a theory of logical types:

By that process of arbitrary selection of classes of individuals of the manifold originally envisaged, there arises a new, much more extensive manifold, namely that of the domains or classes of the previous one. … [It] is necessary from the start that among the elements given as individuals there should be no classes comprising as elements individuals of the same manifold. (Vorlesungen, Vol. I, p. 247)

This foreshadows Russell's vicious-circle principle.

Schröder worked on Peirce's algebra of dyadic relatives as an extension of Boole's algebra, but the result was unsatisfactory, and, indeed, by the time Peirce reviewed it Schröder had already abandoned the algebraic form (though not the name) in favor of what is essentially first-order functional calculus. The Schröder-Bernstein theorem, to the effect that if each of two classes is similar to a part of the other, then they are similar to each other, was proved by Schröder in 1896 and independently by Felix Bernstein in 1898.

Peano

Schröder deplored the lack of use for the logical tool he had developed and experimented with the application of his theory of relation to Dedekind's chains. Giuseppe Peano, primarily interested in the rigor of mathematical proof, applied Schröder's instrument to comprehensive mathematical material in successive volumes of his Formulaire de mathématiques (5 vols., Turin, 1892–1908). He prefaced the work with a section on mathematical logic (a phrase that he originated), distinguished class membership from inclusion, which Schröder had not done, and expressed all theorems as implications rather than as equations. He still did not isolate propositional logic as a deductive preliminary, but he stated a generalized form of modus ponens, to the effect that a true proposition could be suppressed when it occurred as an antecedent or as part of a conjunction of antecedents in a theorem.

Peano had already obtained his five axioms of arithmetic, which contain the principle of mathematical induction, by 1889, when he published Arithmetices Principia Nova Methodo Exposita. The year before, J. W. R. Dedekind had reached substantially the same result in Was sind und was sollen die Zahlen? (Brunswick, Germany, 1888) with the induction principle provable, however, owing to his having started further back in logic, with sets and projections, rather than with sets, number, and successor. Frege, as Dedekind did not know at that time, had gone still further in the same direction. The fact that Peano, even in 1908, did not refer to either Frege or Dedekind but explicitly left the possibility of defining "number" an open question may indicate that he continued to be interested in logic more as a means of attaining brevity and rigor, and an occasional new insight, than as material from which the basic arithmetical notions might be constructed.

Cantor

Peano did draw on the theory of sets of Georg Cantor (1845–1918), including Cantor's proofs that the algebraic numbers can be put in one-to-one correspondence with the positive integers and that the real numbers cannot be so made to correspond (the "diagonal" proof). Cantor's work had grown out of a reorganization of analysis parallel to that of algebra and geometry. He was influenced, of course, by the work of Cauchy, Riemann, and Hankel on functions of complex variables, but his principal predecessor was Karl Weierstrass (1815–1897), who was greatly interested in foundational matters, especially in regard to irrational numbers and points of condensation of infinite sets. Cantor became convinced that without extending the concept of number to actually infinite sets it would hardly be possible to make the least step forward without constraint. The arithmetic that he thus created was welcomed by Frege; its influence is widely apparent and was acknowledged in Russell's Principles of Mathematics (Cambridge, U.K., 1903), which plotted the future progress of Principia Mathematica.

Bibliography

R. C. Archibald, "Outline of the History of Mathematics," in American Mathematical Monthly 56 (1949), cites standard histories of nineteenth-century mathematics. See also the general histories of logic listed above, as well as Roberto Bonola, Non-Euclidean Geometry (New York: Dover, 1955); Alonzo Church, "Schroder's Anticipation of the Simple Theory of Types," in Erkenntnis 9 (1939): 149–152; Georg Cantor, Contributions to the Founding of the Theory of Transfinite Numbers, translated, with an introduction, by P. E. B. Jourdain (Chicago: Open Court, 1915); Ettore Carruccio, Mathematics and Logic in History and in Contemporary Thought, translated by Isabel Quigly (Chicago: Aldine, 1965); H. B. Curry, Foundations of Mathematical Logic (New York: McGraw-Hill, 1963); and Giuseppe Peano, Formulario Mathematico (Turin, 1908; facsimile reprint, Rome: Edizioni Cremonese, 1960).