Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
History of logic
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
==Modern logic== {{See also|History of mathematical logic}} The development of modern logic falls into roughly five periods:<ref>See Bochenski p. 269</ref> * The ''embryonic period'' from [[Gottfried Wilhelm Leibniz|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 [[Ernst Schröder (mathematician)|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 [[Bertrand Russell|Russell]] and [[A. N. Whitehead|Whitehead]]. The aim of the "logicist school" was to incorporate the logic of all mathematical and scientific discourse in a single unified system which, taking as a fundamental principle that all mathematical truths are logical, did not accept any non-logical terminology. The major logicists were [[Gottlob Frege|Frege]], [[Bertrand Russell|Russell]], and the early [[Ludwig Wittgenstein|Wittgenstein]].<ref>''Oxford Companion'' p. 499</ref> It culminates with the ''Principia'', an important work which includes a thorough examination and attempted solution of the [[antinomy|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 [[David Hilbert|Hilbert]], and the non-finitist system of [[Leopold Löwenheim|Löwenheim]] and [[Skolem]], the combination of logic and metalogic in the work of [[Gödel]] and [[Alfred Tarski|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=== [[File:Gottfried Wilhelm Leibniz, Bernhard Christoph Francke.jpg|thumb|upright|Leibniz]] The idea that inference could be represented by a purely mechanical process is found as early as [[Ramon Llull|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]]<ref>Edith Sylla (1999), "Oxford Calculators", in ''The Cambridge Dictionary of Philosophy'', Cambridge, Cambridgeshire: Cambridge.</ref> 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'' by [[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.<ref>El. philos. sect. I de corp 1.1.2.</ref> The same idea is found in the work of [[Gottfried Wilhelm Leibniz|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;<ref>Bochenski p. 274</ref> hence, he proposed to identify an [[alphabet of human thought]] comprising fundamental concepts which could be composed to express complex ideas,<ref>Rutherford, Donald, 1995, "Philosophy and language" in Jolley, N., ed., ''The Cambridge Companion to Leibniz''. Cambridge Univ. Press.</ref> and create a ''[[calculus ratiocinator]]'' that would make all arguments "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."<ref>Wiener, Philip, 1951. ''Leibniz: Selections''. Scribner.</ref> [[Joseph Diaz Gergonne|Gergonne]] (1816) said that reasoning does not have to be about objects about which one has perfectly clear ideas, because algebraic operations can be carried out without having any idea of the meaning of the symbols involved.<ref>''Essai de dialectique rationelle'', 211n, quoted in Bochenski p. 277.</ref> [[Bernard Bolzano|Bolzano]] anticipated a fundamental idea of modern proof theory when he defined logical consequence or "deducibility" in terms of variables:<ref>{{cite book |author-last=Bolzano |author-first=Bernard |url=https://books.google.com/books?id=oA1NDDirneQC&q=%22deducible%20from%20propositions%22&pg=PA209 |title=The Theory of Science: Die Wissenschaftslehre oder Versuch einer Neuen Darstellung der Logik |date=1972 |publisher=[[University of California Press]] |isbn=978-0-52001787-0 |editor-last=George |editor-first=Rolf |page=209 |translator-last=Rolf |translator-first=George}}</ref><blockquote>Hence I say that propositions <math>M</math>, <math>N</math>, <math>O</math>,... are ''deducible'' from propositions <math>A</math>, <math>B</math>, <math>C</math>, <math>D</math>,... with respect to variable parts <math>i</math>, <math>j</math>,..., if every class of ideas whose substitution for <math>i</math>, <math>j</math>,... makes all of <math>A</math>, <math>B</math>, <math>C</math>, <math>D</math>,... true, also makes all of <math>M</math>, <math>N</math>, <math>O</math>,... true. Occasionally, since it is customary, I shall say that propositions <math>M</math>, <math>N</math>, <math>O</math>,... ''follow'', or can be ''inferred'' or ''derived'', from <math>A</math>, <math>B</math>, <math>C</math>, <math>D</math>,.... Propositions <math>A</math>, <math>B</math>, <math>C</math>, <math>D</math>,... I shall call the ''premises'', <math>M</math>, <math>N</math>, <math>O</math>,... the ''conclusions.''</blockquote>This is now known as [[semantic validity]]. ===Algebraic period=== [[File:George Boole color.jpg|thumb|140px|George Boole]] Modern logic begins with what is known as the "algebraic school", originating with Boole and including [[Charles Sanders Peirce|Peirce]], [[William Stanley Jevons|Jevons]], [[Ernst Schröder (mathematician)|Schröder]], and [[John Venn|Venn]].<ref>See e.g. Bochenski p. 296 and ''passim''</ref> 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 [[Augustus De Morgan|De Morgan]] (1847) is its immediate precursor.<ref>Before publishing, he wrote to [[Augustus De Morgan|De Morgan]], who was just finishing his work ''Formal Logic''. De Morgan suggested they should publish first, and thus the two books appeared at the same time, possibly even reaching the bookshops on the same day. cf. Kneale p. 404</ref> 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]].<ref>Kneale p. 404</ref> 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.<ref name="Kneale p. 407">Kneale p. 407</ref> 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''.<ref>Boole (1847) p. 16</ref> The theory of elective functions and their "development" is essentially the modern idea of [[truth-function]]s and their expression in [[disjunctive normal form]].<ref name="Kneale p. 407"/> 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."<ref>Boole 1847 pp. 58–59</ref> These are easily distinguished in modern predicate logic, 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.<ref>Beaney p. 11</ref> 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.<ref name="Kneale p. 407"/> In 1885 [[Allan Marquand]] proposed an electrical version of the machine that is still extant ([https://web.archive.org/web/20080908073359/http://finelib.princeton.edu/instruction/wri172_demonstration.php picture at the Firestone Library]). [[File:Charles Sanders Peirce.jpg|left|thumb|160px|Charles Sanders Peirce]] 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.<ref>Kneale p. 422</ref> 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, "[[Logical NOR|neither ... nor ...]]" and equally well "[[Sheffer stroke|not both ... and ...]]",<ref>Peirce, "A Booli<!-- sic! -->an Algebra with One Constant", 1880 MS, ''Collected Papers'' v. 4, paragraphs 12–20, reprinted ''Writings'' v. 4, pp. 218–221. Google [https://archive.org/details/writingsofcharle0002peir <!-- quote=378 Winter. --> Preview].</ref> however, like many of Peirce's innovations, this remained unknown or unnoticed until [[Henry M. Sheffer|Sheffer]] rediscovered it in 1913.<ref>''Trans. Amer. Math. Soc., xiv (1913)'', pp. 481–488. This is now known as the [[Sheffer stroke]]</ref> Boole's early work also lacks the idea of the [[logical sum]] which originates in Peirce (1867), [[Ernst Schröder (mathematician)|Schröder]] (1877) and Jevons (1890),<ref>Bochenski 296</ref> and the concept of [[Inclusion (logic)|inclusion]], first suggested by Gergonne (1816) and clearly articulated by Peirce (1870). [[File:Boolean multiples of 2 3 5.svg|alt=Coloured diagram of 4 interlocking sets|right|thumb|250px|Boolean multiples]] 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.<ref>See CP III</ref> Boole's unwavering acceptance of Aristotle's logic is emphasized by the historian of logic [[John Corcoran (logician)|John Corcoran]] in an accessible introduction to ''[[The Laws of Thought|Laws of Thought]].''<ref>[[George Boole]]. 1854/2003. The Laws of Thought, facsimile of 1854 edition, with an introduction by J. Corcoran. Buffalo: Prometheus Books (2003). Reviewed by James van Evra in Philosophy in Review. 24 (2004) 167–169.</ref> Corcoran also wrote a point-by-point comparison of ''Prior Analytics'' and ''Laws of Thought''.<ref>JOHN CORCORAN, Aristotle's Prior Analytics and Boole's Laws of Thought, History and Philosophy of Logic, vol. 24 (2003), pp. 261–288.</ref> 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 Aristotelian 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=== [[File:Young frege.jpg|thumb|160px|Gottlob Frege.]] 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.<ref name="k435">Kneale p. 435</ref> Frege went much further than any of his predecessors in his rigorous and formal approach to logic, and his calculus or [[Begriffsschrift]] is important.<ref name="k435"/> 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 {{Lang|de|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."<ref>Jevons, ''The Principles of Science'', London 1879, p. 156, quoted in ''Grundlagen'' 15</ref> 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.<ref>Beaney p. 10 – the completeness of Frege's system was eventually proved by [[Jan Łukasiewicz]] in 1934</ref> The most significant innovation, however, was his explanation of the [[Quantifier (logic)|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".<ref>See for example the argument by the medieval logician [[William of Ockham]] that singular propositions are universal, in [[Summa Logicae]] III. 8 (??)</ref> At the outset Frege abandons the traditional "concepts ''subject'' and ''predicate''", replacing them with ''argument'' and ''function'' respectively, which he believes "will stand the test of time. It is easy to see how regarding a content as a function of an argument leads to the formation of concepts. Furthermore, the demonstration of the connection between the meanings of the words ''if, and, not, or, there is, some, all,'' and so forth, deserves attention".<ref>{{harvnb |Frege |1879}} in {{harvnb |van Heijenoort |1967 |p=7}}</ref> 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 : <math>\forall \; x \big( A(x) \rightarrow B (x) \big)</math> 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.<ref>"On concept and object" p. 198; Geach p. 48</ref> 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 men or women" is [[File:BS-13-Begriffsschrift Quantifier2-svg.svg|130px|alt=Straight line with bend; text "x" over bend; text "F(x)" to the right of the line.|thumb|[[Frege]]'s "Concept Script"]] : <math>\forall \; x \Big( I(x) \rightarrow \big( M(x) \lor W(x) \big) \Big) </math> whereas "All the inhabitants are men or all the inhabitants are women" is : <math>\forall \; x \big( I(x) \rightarrow M(x) \big) \lor \forall \;x \big( I(x) \rightarrow W(x) \big)</math> 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."<ref>BLC p. 14, quoted in Beaney p. 12</ref> 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 resolves this through the different scope of the quantifiers. Thus :<math>\forall \; x \Big( G(x) \rightarrow \exists \; y \big( B(y) \land K(x,y) \big) \Big)</math> [[File:Giuseppe_Peano.jpg|thumb|120px|Peano]] means that to every girl there corresponds some boy (any one will do) who the girl kissed. But :<math>\exists \;x \Big( B(x) \land \forall \;y \big( G(y) \rightarrow K(y, x) \big) \Big)</math> 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 [[Injective function|many-to-one relation]], and of [[mathematical induction]].<ref>See e.g. [http://www.utm.edu/research/iep/f/frege.htm The Internet Encyclopedia of Philosophy], article "Frege"</ref> [[File:Ernst Zermelo 1900s.jpg|thumb|left|130px|Ernst Zermelo]] This period overlaps with the work of what is known as the "mathematical school", which included [[Richard Dedekind|Dedekind]], [[Moritz Pasch|Pasch]], [[Giuseppe Peano|Peano]], [[David Hilbert|Hilbert]], [[Ernst Zermelo|Zermelo]], [[Edward Vermilye Huntington|Huntington]], [[Oswald Veblen|Veblen]] and [[Arend Heyting|Heyting]]. Their objective was the axiomatisation of branches of mathematics like geometry, arithmetic, analysis and set theory. Most notable was [[Hilbert's Program]], which sought to ground 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. The standard [[axiomatization]] of the [[natural number]]s is named the [[Peano axioms]] eponymously. Peano maintained a clear distinction between mathematical and logical symbols. While unaware of Frege's work, he independently recreated his logical apparatus based on the work of Boole and Schröder.<ref>Van Heijenoort 1967, p. 83</ref> The logicist project received a near-fatal setback with the discovery of a paradox in 1901 by [[Bertrand Russell]]. This proved Frege's [[naive set theory]] led to a contradiction. Frege's theory contained the axiom 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).<ref>See e.g. Potter 2004</ref> This contradiction is now known as [[Russell's paradox]]. One important method of resolving this paradox was proposed by [[Ernst Zermelo]].<ref>Zermelo 1908</ref> [[Zermelo set theory]] was the first [[axiomatic set theory]]. It was developed into the now-canonical [[Zermelo–Fraenkel set theory]] (ZF). Russell's paradox symbolically is as follows: :<math>\text{Let } R = \{ x \mid x \not \in x \} \text{, then } R \in R \iff R \not \in R</math> The monumental [[Principia Mathematica]], a three-volume work on the [[foundations of mathematics]], written by Russell and [[Alfred North Whitehead]] and published 1910–1913 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 [[axiom]]s and [[inference rule]]s in [[Mathematical logic|symbolic logic]]. ===Metamathematical period=== [[File:Kurt gödel.jpg|thumb|130px|right|Kurt Gödel]] The names of [[Kurt Gödel|Gödel]] and [[Alfred Tarski|Tarski]] dominate the 1930s,<ref>Feferman 1999 p. 1</ref> a crucial period in the development of [[metamathematics]]—the study of mathematics using mathematical methods to produce [[metatheory|metatheories]], or mathematical theories about other mathematical theories. Early investigations into metamathematics had been driven by Hilbert's program. Work on metamathematics culminated in the work of Gödel, who in 1929 showed that a given [[first-order logic|first-order sentence]] is [[Provability logic|deducible]] if and only if it is logically valid—i.e. it is true in every [[structure (mathematical logic)|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 method|effective procedure]] such as an [[algorithm]] or computer program is capable of proving all facts about the [[natural number]]s. 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]]. <!-- Commented out: [[File:Alonzo Church.jpg|thumb|left|130px|Alonzo Church]] --> 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.<ref>{{cite book |author-last1=Girard |author-first1=Jean-Yves |url=https://archive.org/details/proofstypes0000gira |title=Proofs and Types |author-last2=Taylor |first2=Paul |author-last3=Lafont |author-first3=Yves |date=1990 |publisher=Cambridge University Press (Cambridge Tracts in Theoretical Computer Science, 7) |isbn=0-521-37181-3 |author-link1=Jean-Yves Girard |orig-date=1989 |url-access=registration}}</ref> [[File:AlfredTarski1968.jpeg|right|200px|alt=Balding man, with bookshelf in background|thumb|Alfred Tarski]] [[Alfred Tarski]], a pupil of [[Jan Łukasiewicz|Łukasiewicz]], is best known for his definition of truth and [[logical consequence]], and the semantic concept of [[Open sentence|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 (logic)|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]].<ref>Feferman and Feferman 2004, p. 122, discussing "The Impact of Tarski's Theory of Truth".</ref> Tarski also produced important work on the methodology of deductive systems, and on fundamental principles such as [[completeness (logic)|completeness]], [[decidability (logic)|decidability]], [[consistency]] and [[Structure (mathematical logic)|definability]]. According to Anita Feferman, Tarski "changed the face of logic in the twentieth century".<ref>Feferman 1999, p. 1</ref> [[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 problem|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=== [[File:Kripke.JPG|alt=Man with a beard and straw hat on a beach|thumb|[[Saul Kripke]]]] 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]].<ref>See e.g. Barwise, ''Handbook of Mathematical Logic''</ref> In set theory, the method of [[Forcing (mathematics)|forcing]] revolutionized the field by providing a robust method for constructing models and obtaining independence results. <!-- Kunen p. 235ff, Kanamori p. 114ff --> [[Paul Cohen]] introduced this method in 1963 to prove the independence of the [[continuum hypothesis]] and the [[axiom of choice]] from [[Zermelo–Fraenkel set theory]].<ref>{{cite journal | jstor=72252 | last1=Cohen | first1=Paul J. | title=The Independence of the Continuum Hypothesis, II | journal=Proceedings of the National Academy of Sciences of the United States of America | date=1964 | volume=51 | issue=1 | pages=105–110 | doi=10.1073/pnas.51.1.105 | pmid=16591132 | pmc=300611 | bibcode=1964PNAS...51..105C | doi-access=free }}</ref> 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]].<ref>Many of the foundational papers are collected in ''The Undecidable'' (1965) edited by Martin Davis</ref> The [[Turing degree|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. <!-- cooper 246 --> Research into higher-order computability theory demonstrated its connections to set theory. <!-- sacks "higher recursion 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''. <!-- "alfred tarski's work in model theory", vaught, JSL, https://www.jstor.org/stable/2273900 --> In the 1960s, [[Abraham Robinson]] used model-theoretic techniques to develop calculus and analysis based on [[non-standard analysis|infinitesimals]], a problem that first had been proposed by Leibniz. <!-- Keisler, fundamentals of model theory, HML, p. 48 --> 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|''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 calculus|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 logic]]s extend the scope of formal logic to include the elements of [[Linguistic modality|modality]] (for example, [[Logical possibility|possibility]] and [[Necessary and sufficient conditions#Necessary conditions|necessity]]). The ideas of [[Saul Kripke]], particularly about [[possible world]]s, and the formal system now called [[Kripke semantics]] have had a profound impact on [[analytic philosophy]].<ref>Jerry Fodor, "[http://www.lrb.co.uk/v26/n20/jerry-fodor/waters-water-everywhere Water's water everywhere]", ''London Review of Books'', 21 October 2004</ref> His best known and most influential work is ''[[Naming and Necessity]]'' (1980).<ref>See ''Philosophical Analysis in the Twentieth Century: Volume 2: The Age of Meaning'', Scott Soames: "''Naming and Necessity'' is among the most important works ever, ranking with the classical work of Frege in the late nineteenth century, and of Russell, Tarski and Wittgenstein in the first half of the twentieth century". Cited in Byrne, Alex and Hall, Ned. 2004. 'Necessary Truths'. ''Boston Review'' October/November 2004</ref> [[Deontic logic]]s are closely related to modal logics: they attempt to capture the logical features of [[obligation]], [[Permission (philosophy)|permission]] and related concepts. Although some basic novelties [[syncretism|syncretizing]] mathematical and philosophical logic were shown by [[Bernard Bolzano#Metaphysics|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 Azerbaijani mathematician [[Lotfi Asker Zadeh]] in 1965.
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)