|
The development of modern logic falls into roughly five periods:[87] The embryonic period from Leibniz to 1847, when the notion of a logical calculus was discussed and developed, particularly by Leibniz, but no schools were formed, and isolated periodic attempts were abandoned or went unnoticed. The algebraic period from Boole's Analysis to Schröder's Vorlesungen. In this period there were more practitioners, and a greater continuity of development. The logicist period from the Begriffsschrift of Frege to the Principia Mathematica of Russell and Whitehead. This was dominated by the "logicist school", whose aim was to incorporate the logic of all mathematical and scientific discourse in a single unified system, and which, taking as a fundamental principle that all mathematical truths are logical, did not accept any non-logical terminology. The major logicists were Frege, Russell, and the early Wittgenstein.[88] It culminates with the Principia, an important work which includes a thorough examination and attempted solution of the antinomies which had been an obstacle to earlier progress. The metamathematical period from 1910 to the 1930s, which saw the development of metalogic, in the finitist system of Hilbert, and the non-finitist system of Löwenheim and Skolem, the combination of logic and metalogic in the work of Gödel and Tarski. Gödel's incompleteness theorem of 1931 was one of the greatest achievements in the history of logic. Later in the 1930s Gödel developed the notion of set-theoretic constructibility. The period after World War II, when mathematical logic branched into four inter-related but separate areas of research: model theory, proof theory, computability theory, and set theory, and its ideas and methods began to influence philosophy. Embryonic period Triptych: left, crucifixion; middle, figure approaches the virgin and child; right, figure approaches a man Life of Raymond Lull. 14th-century manuscript. The idea that inference could be represented by a purely mechanical process is found as early as Raymond Llull, who proposed a (somewhat eccentric) method of drawing conclusions by a system of concentric rings. The work of logicians such as the Oxford Calculators[89] led to a method of using letters instead of writing out logical calculations (calculationes) in words, a method used, for instance, in the Logica magna of Paul of Venice. Three hundred years after Llull, the English philosopher and logician Thomas Hobbes suggested that all logic and reasoning could be reduced to the mathematical operations of addition and subtraction.[90] The same idea is found in the work of Leibniz, who had read both Llull and Hobbes, and who argued that logic can be represented through a combinatorial process or calculus. But, like Llull and Hobbes, he failed to develop a detailed or comprehensive system, and his work on this topic was not published until long after his death. Leibniz says that ordinary languages are subject to "countless ambiguities" and are unsuited for a calculus, whose task is to expose mistakes in inference arising from the forms and structures of words;[91] hence, he proposed to identify an alphabet of human thought comprising fundamental concepts which could be composed to express complex ideas,[92] and create a calculus ratiocinator which would make reasoning "as tangible as those of the Mathematicians, so that we can find our error at a glance, and when there are disputes among persons, we can simply say: Let us calculate."[93] Gergonne (1816) said that reasoning does not have to be about objects about which we have perfectly clear ideas, since algebraic operations can be carried out without our having any idea of the meaning of the symbols involved.[94] Bolzano anticipated a fundamental idea of modern proof theory when he defined logical consequence or "deducibility" in terms of variables: a set of propositions n, o, p ... are deducible from propositions a, b, c ... in respect of the variables i, j, ... if any substitution for i, j that have the effect of making a, b, c ... true, simultaneously make the propositions n, o, p ... also.[95] This is now known as semantic validity. Algebraic period Coloured diagram of 4 interlocking sets Boolean multiples Modern logic begins with the so-called "algebraic school", originating with Boole and including Peirce, Jevons, Schröder and Venn.[96] Their objective was to develop a calculus to formalise reasoning in the area of classes, propositions and probabilities. The school begins with Boole's seminal work Mathematical Analysis of Logic which appeared in 1847, although De Morgan (1847) is its immediate precursor.[97] The fundamental idea of Boole's system is that algebraic formulae can be used to express logical relations. This idea occurred to Boole in his teenage years, working as an usher in a private school in Lincoln, Lincolnshire.[98] For example, let x and y stand for classes let the symbol = signify that the classes have the same members, xy stand for the class containing all and only the members of x and y and so on. Boole calls these elective symbols, i.e. symbols which select certain objects for consideration.[99] An expression in which elective symbols are used is called an elective function, and an equation of which the members are elective functions, is an elective equation.[100] The theory of elective functions and their "development" is essentially the modern idea of truth-functions and their expression in disjunctive normal form.[99] Boole's system admits of two interpretations, in class logic, and propositional logic. Boole distinguished between "primary propositions" which are the subject of syllogistic theory, and "secondary propositions", which are the subject of propositional logic, and showed how under different "interpretations" the same algebraic system could represent both. An example of a primary proposition is "All inhabitants are either Europeans or Asiatics." An example of a secondary proposition is "Either all inhabitants are Europeans or they are all Asiatics."[101] These are easily distinguished in modern propositional calculus, where it is also possible to show that the first follows from the second, but it is a significant disadvantage that there is no way of representing this in the Boolean system.[102] In his Symbolic Logic (1881), John Venn used diagrams of overlapping areas to express Boolean relations between classes or truth-conditions of propositions. In 1869 Jevons realised that Boole's methods could be mechanised, and constructed a "logical machine" which he showed to the Royal Society the following year.[99] In 1885 Allan Marquand proposed an electrical version of the machine that is still extant (picture at the Firestone Library). The defects in Boole's system (such as the use of the letter v for existential propositions) were all remedied by his followers. Jevons published Pure Logic, or the Logic of Quality apart from Quantity in 1864, where he suggested a symbol to signify exclusive or, which allowed Boole's system to be greatly simplified.[103] This was usefully exploited by Schröder when he set out theorems in parallel columns in his Vorlesungen (1890–1905). Peirce (1880) showed how all the Boolean elective functions could be expressed by the use of a single primitive binary operation, "neither ... nor ..." and equally well "not both ... and ...",[104] however, like many of Peirce's innovations, this remained unknown or unnoticed until Sheffer rediscovered it in 1913.[105] Boole's early work also lacks the idea of the logical sum which originates in Peirce (1867), Schröder (1877) and Jevons (1890),[106] and the concept of inclusion, first suggested by Gergonne (1816) and clearly articulated by Peirce (1870). The success of Boole's algebraic system suggested that all logic must be capable of algebraic representation, and there were attempts to express a logic of relations in such form, of which the most ambitious was Schröder's monumental Vorlesungen über die Algebra der Logik ("Lectures on the Algebra of Logic", vol iii 1895), although the original idea was again anticipated by Peirce.[107] Boole’s unwavering acceptance of Aristotle’s logic is emphasized by the historian of logic John Corcoran in an accessible introduction to Laws of Thought[108] Corcoran also wrote a point-by-point comparison of Prior Analytics and Laws of Thought.[109] According to Corcoran, Boole fully accepted and endorsed Aristotle’s logic. Boole’s goals were “to go under, over, and beyond” Aristotle’s logic by 1) providing it with mathematical foundations involving equations,2) extending the class of problems it could treat—from assessing validity to solving equations--,and 3) expanding the range of applications it could handle—e.g. from propositions having only two terms to those having arbitrarily many. More specifically, Boole agreed with what Aristotle said; Boole’s ‘disagreements’, if they might be called that, concern what Aristotle did not say. First, in the realm of foundations, Boole reduced the four propositional forms of Aristotle's logic to formulas in the form of equations—-by itself a revolutionary idea. Second, in the realm of logic’s problems, Boole’s addition of equation solving to logic—-another revolutionary idea—-involved Boole’s doctrine that Aristotle’s rules of inference (the “perfect syllogisms”) must be supplemented by rules for equation solving. Third, in the realm of applications, Boole’s system could handle multi-term propositions and arguments whereas Aristotle could handle only two-termed subject-predicate propositions and arguments. For example, Aristotle’s system could not deduce “No quadrangle that is a square is a rectangle that is a rhombus” from “No square that is a quadrangle is a rhombus that is a rectangle” or from “No rhombus that is a rectangle is a square that is a quadrangle”. Logicist period Straight line with bend; text "x" over bend; text "F(x)" to the right of the line. Frege's "Concept Script" After Boole, the next great advances were made by the German mathematician Gottlob Frege. Frege's objective was the program of Logicism, i.e. demonstrating that arithmetic is identical with logic.[110] Frege went much further than any of his predecessors in his rigorous and formal approach to logic, and his calculus or Begriffsschrift is important.[110] Frege also tried to show that the concept of number can be defined by purely logical means, so that (if he was right) logic includes arithmetic and all branches of mathematics that are reducible to arithmetic. He was not the first writer to suggest this. In his pioneering work Die Grundlagen der Arithmetik (The Foundations of Arithmetic), sections 15–17, he acknowledges the efforts of Leibniz, J.S. Mill as well as Jevons, citing the latter's claim that "algebra is a highly developed logic, and number but logical discrimination."[111] Frege's first work, the Begriffsschrift ("concept script") is a rigorously axiomatised system of propositional logic, relying on just two connectives (negational and conditional), two rules of inference (modus ponens and substitution), and six axioms. Frege referred to the "completeness" of this system, but was unable to prove this.[112] The most significant innovation, however, was his explanation of the quantifier in terms of mathematical functions. Traditional logic regards the sentence "Caesar is a man" as of fundamentally the same form as "all men are mortal." Sentences with a proper name subject were regarded as universal in character, interpretable as "every Caesar is a man".[113] Frege argued that the quantifier expression "all men" does not have the same logical or semantic form as "all men", and that the universal proposition "every A is B" is a complex proposition involving two functions, namely ' – is A' and ' – is B' such that whatever satisfies the first, also satisfies the second. In modern notation, this would be expressed as (x) Ax -> Bx In English, "for all x, if Ax then Bx". Thus only singular propositions are of subject-predicate form, and they are irreducibly singular, i.e. not reducible to a general proposition. Universal and particular propositions, by contrast, are not of simple subject-predicate form at all. If "all mammals" were the logical subject of the sentence "all mammals are land-dwellers", then to negate the whole sentence we would have to negate the predicate to give "all mammals are not land-dwellers". But this is not the case.[114] This functional analysis of ordinary-language sentences later had a great impact on philosophy and linguistics. This means that in Frege's calculus, Boole's "primary" propositions can be represented in a different way from "secondary" propositions. "All inhabitants are either Europeans or Asiatics" is (x) [ I(x) -> (E(x) v A(x)) ] whereas "All the inhabitants are Europeans or all the inhabitants are Asiatics" is (x) (I(x) -> E(x)) v (x) (I(x) -> A(x)) As Frege remarked in a critique of Boole's calculus: "The real difference is that I avoid [the Boolean] division into two parts ... and give a homogeneous presentation of the lot. In Boole the two parts run alongside one another, so that one is like the mirror image of the other, but for that very reason stands in no organic relation to it'[115] As well as providing a unified and comprehensive system of logic, Frege's calculus also resolved the ancient problem of multiple generality. The ambiguity of "every girl kissed a boy" is difficult to express in traditional logic, but Frege's logic captures this through the different scope of the quantifiers. Thus (x) [ girl(x) -> E(y) (boy(y) & kissed(x,y)) ] means that to every girl there corresponds some boy (any one will do) who the girl kissed. But E(x) [ boy(x) & (y) (girl(y) -> kissed(y,x)) ] means that there is some particular boy whom every girl kissed. Without this device, the project of logicism would have been doubtful or impossible. Using it, Frege provided a definition of the ancestral relation, of the many-to-one relation, and of mathematical induction.[116] This period overlaps with the work of the so-called "mathematical school", which included Dedekind, Pasch, Peano, Hilbert, Zermelo, Huntington, Veblen and Heyting. Their objective was the axiomatisation of branches of mathematics like geometry, arithmetic, analysis and set theory. The logicist project received a near-fatal setback with the discovery of a paradox in 1901 by Bertrand Russell. This proved that the Frege's naive set theory led to a contradiction. Frege's theory is that for any formal criterion, there is a set of all objects that meet the criterion. Russell showed that a set containing exactly the sets that are not members of themselves would contradict its own definition (if it is not a member of itself, it is a member of itself, and if it is a member of itself, it is not).[117] This contradiction is now known as Russell's paradox. One important method of resolving this paradox was proposed by Ernst Zermelo.[118] Zermelo set theory was the first axiomatic set theory. It was developed into the now-canonical Zermelo–Fraenkel set theory (ZF). The monumental Principia Mathematica, a three-volume work on the foundations of mathematics, written by Russell and Alfred North Whitehead and published 1910–13 also included an attempt to resolve the paradox, by means of an elaborate system of types: a set of elements is of a different type than is each of its elements (set is not the element; one element is not the set) and one cannot speak of the "set of all sets". The Principia was an attempt to derive all mathematical truths from a well-defined set of axioms and inference rules in symbolic logic. Metamathematical period Balding man, with bookshelf in background Alfred Tarski The names of Gödel and Tarski dominate the 1930s,[119] a crucial period in the development of metamathematics – the study of mathematics using mathematical methods to produce metatheories, or mathematical theories about other mathematical theories. Early investigations into metamathematics had been driven by Hilbert's program. which sought to resolve the ongoing crisis in the foundations of mathematics by grounding all of mathematics to a finite set of axioms, proving its consistency by "finitistic" means and providing a procedure which would decide the truth or falsity of any mathematical statement. Work on metamathematics culminated in the work of Gödel, who in 1929 showed that a given first-order sentence is deducible if and only if it is logically valid – i.e. it is true in every structure for its language. This is known as Gödel's completeness theorem. A year later, he proved two important theorems, which showed Hibert's program to be unattainable in its original form. The first is that no consistent system of axioms whose theorems can be listed by an effective procedure such as an algorithm or computer program is capable of proving all facts about the natural numbers. For any such system, there will always be statements about the natural numbers that are true, but that are unprovable within the system. The second is that if such a system is also capable of proving certain basic facts about the natural numbers, then the system cannot prove the consistency of the system itself. These two results are known as Gödel's incompleteness theorems, or simply Gödel's Theorem. Later in the decade, Gödel developed the concept of set-theoretic constructibility, as part of his proof that the axiom of choice and the continuum hypothesis are consistent with Zermelo–Fraenkel set theory. In proof theory, Gerhard Gentzen developed natural deduction and the sequent calculus. The former attempts to model logical reasoning as it 'naturally' occurs in practice and is most easily applied to intuitionistic logic, while the latter was devised to clarify the derivation of logical proofs in any formal system. Since Gentzen's work, natural deduction and sequent calculi have been widely applied in the fields of proof theory, mathematical logic and computer science. Gentzen also proved normalization and cut-elimination theorems for intuitionistic and classical logic which could be used to reduce logical proofs to a normal form.[120][121] Alfred Tarski, a pupil of Łukasiewicz, is best known for his definition of truth and logical consequence, and the semantic concept of logical satisfaction. In 1933, he published (in Polish) The concept of truth in formalized languages, in which he proposed his semantic theory of truth: a sentence such as "snow is white" is true if and only if snow is white. Tarski's theory separated the metalanguage, which makes the statement about truth, from the object language, which contains the sentence whose truth is being asserted, and gave a correspondence (the T-schema) between phrases in the object language and elements of an interpretation. Tarski's approach to the difficult idea of explaining truth has been enduringly influential in logic and philosophy, especially in the development of model theory.[122] Tarski also produced important work on the methodology of deductive systems, and on fundamental principles such as completeness, decidability, consistency and definability. According to Anita Feferman, Tarski "changed the face of logic in the twentieth century".[123] Alonzo Church and Alan Turing proposed formal models of computability, giving independent negative solutions to Hilbert's Entscheidungsproblem in 1936 and 1937, respectively. The Entscheidungsproblem asked for a procedure that, given any formal mathematical statement, would algorithmically determine whether the statement is true. Church and Turing proved there is no such procedure; Turing's paper introduced the halting problem as a key example of a mathematical problem without an algorithmic solution. Church's system for computation developed into the modern λ-calculus, while the Turing machine became a standard model for a general-purpose computing device. It was soon shown that many other proposed models of computation were equivalent in power to those proposed by Church and Turing. These results led to the Church–Turing thesis that any deterministic algorithm that can be carried out by a human can be carried out by a Turing machine. Church proved additional undecidability results, showing that both Peano arithmetic and first-order logic are undecidable. Later work by Emil Post and Stephen Cole Kleene in the 1940s extended the scope of computability theory and introduced the concept of degrees of unsolvability. The results of the first few decades of the twentieth century also had an impact upon analytic philosophy and philosophical logic, particularly from the 1950s onwards, in subjects such as modal logic, temporal logic, deontic logic, and relevance logic. Logic after WWII Man with a beard and straw hat on a beach After World War II, mathematical logic branched into four inter-related but separate areas of research: model theory, proof theory, computability theory, and set theory.[124] In set theory, the method of forcing revolutionized the field by providing a robust method for constructing models and obtaining independence results. Paul Cohen introduced this method in 1962 to prove the independence of the continuum hypothesis and the axiom of choice from Zermelo–Fraenkel set theory.[125] His technique, which was simplified and extended soon after its introduction, has since been applied to many other problems in all areas of mathematical logic. Computability theory had its roots in the work of Turing, Church, Kleene, and Post in the 1930s and 40s. It developed into a study of abstract computability, which became known as recursion theory.[126] The priority method, discovered independently by Albert Muchnik and Richard Friedberg in the 1950s, led to major advances in the understanding of the degrees of unsolvability and related structures. Research into higher-order computability theory demonstrated its connections to set theory. The fields of constructive analysis and computable analysis were developed to study the effective content of classical mathematical theorems; these in turn inspired the program of reverse mathematics. A separate branch of computability theory, computational complexity theory, was also characterized in logical terms as a result of investigations into descriptive complexity. Model theory applies the methods of mathematical logic to study models of particular mathematical theories. Alfred Tarski published much pioneering work in the field, which is named after a series of papers he published under the title Contributions to the theory of models. In the 1960s, Abraham Robinson used model-theoretic techniques to develop calculus and analysis based on infinitesimals, a problem that first had been proposed by Leibniz. In proof theory, the relationship between classical mathematics and intuitionistic mathematics was clarified via tools such as the realizability method invented by Georg Kreisel and Gödel's Dialectica interpretation. This work inspired the contemporary area of proof mining. The Curry-Howard correspondence emerged as a deep analogy between logic and computation, including a correspondence between systems of natural deduction and typed lambda calculi used in computer science. As a result, research into this class of formal systems began to address both logical and computational aspects; this area of research came to be known as modern type theory. Advances were also made in ordinal analysis and the study of independence results in arithmetic such as the Paris–Harrington theorem. This was also a period, particularly in the 1950s and afterwards, when the ideas of mathematical logic begin to influence philosophical thinking. For example, tense logic is a formalised system for representing, and reasoning about, propositions qualified in terms of time. The philosopher Arthur Prior played a significant role in its development in the 1960s. Modal logics extend the scope of formal logic to include the elements of modality (for example, possibility and necessity). The ideas of Saul Kripke, particularly about possible worlds, and the formal system now called Kripke semantics have had a profound impact on analytic philosophy.[127] His best known and most influential work is Naming and Necessity (1980).[128] Deontic logics are closely related to modal logics: they attempt to capture the logical features of obligation, permission and related concepts. Although some basic novelties syncretizing mathematical and philosophical logic were shown by Bolzano in the early 1800s, it was Ernst Mally, a pupil of Alexius Meinong, who was to propose the first formal deontic system in his Grundgesetze des Sollens, based on the syntax of Whitehead's and Russell's propositional calculus. Another logical system founded after World War II was fuzzy logic by Iranian mathematician Lotfi Asker Zadeh in 1965. |
About us|Jobs|Help|Disclaimer|Advertising services|Contact us|Sign in|Website map|Search|
GMT+8, 2015-9-11 22:08 , Processed in 0.650107 second(s), 16 queries .
