FACTOID # 28: Austin, Texas has more people than Alaska.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Mathematical logic

Mathematical logic is a major area of mathematics, which grew out of symbolic logic. Subfields include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic has contributed to, and been motivated by, the study of foundations of mathematics, but mathematical logic also contains areas of pure mathematics not directly related to foundational questions. Image File history File links This is a lossless scalable vector image. ... Mathematical logic is a discipline within mathematics, studying formal systems in relation to the way they encode intuitive concepts of proof and computation as part of the foundations of mathematics. ... In mathematics, model theory is the study of the representation of mathematical concepts in terms of set theory, or the study of the structures that underlie mathematical systems. ... Proof theory is a branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. ... Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... Recursion theory, or computability theory, is a branch of mathematical logic dealing with generalizations of the notion of computable function, and with related notions such as Turing degrees and effective descriptive set theory. ... Foundations of mathematics is a term sometimes used for certain fields of mathematics itself, namely for mathematical logic, axiomatic set theory, proof theory, model theory, and recursion theory. ...


Mathematical logic is closely related to the much older study of formal logic in philosophy, which began with Aristotle. It provides an easier and more complete method of checking the validity of arguments than the classical Aristotlian forms. Mathematical logic is also closely related to metamathematics. Logic (from ancient Greek λόγος (logos), meaning reason) is the study of arguments. ... The philosopher Socrates about to take poison hemlock as ordered by the court. ... Aristotle (Greek: AristotélÄ“s) (384 BC – 322 BC) was a Greek philosopher, a student of Plato and teacher of Alexander the Great. ... In general, metamathematics or meta-mathematics is reflection about mathematics seen as an entity/object in human consciousness and culture. ...


One unifying theme in mathematical logic is the study of the expressive power of formal logics and formal proof systems. This power is measured by what mathematical concepts can be defined and what theorems can be proven within these formal systems. Logic (from ancient Greek λόγος (logos), meaning reason) is the study of arguments. ... In mathematics, a proof is a demonstration that, given certain axioms, some statement of interest is necessarily true. ...


Mario Bunge, Frothingham Professor of Logic and Metaphysics at McGill University has also claimed that mathematical logic is what Leibniz called characteristica universalis. [citation needed] Mario Augusto Bunge (born September 21, 1919, Buenos Aires) is an Argentinian philosopher and physicist mainly active in Canada. ... McGill University is a publicly funded, co-educational research university located in the city of Montreal, Quebec, Canada. ... Characteristica Universalis from Latin is commonly interpreted as Universal Character in English. ...

Contents

History

Mathematical logic was the name given by Giuseppe Peano to what was later called symbolic logic. In its classical version, the basic aspects resemble the logic of Aristotle, but written using symbolic notation rather than natural language. Attempts to treat the operations of formal logic in a symbolic or algebraic way were made by some of the more philosophical mathematicians, such as Leibniz and Lambert; but their labors remained little known and isolated. It was George Boole and then Augustus De Morgan, in the middle of the nineteenth century, who presented a systematic mathematical way of studying logic. The traditional, Aristotelian doctrine of logic was reformed and completed; and out of this development came an adequate instrument for investigating the fundamental concepts of mathematics. It would be misleading to say that the foundational controversies that were alive in the period 1900–1925 have all been settled; but philosophy of mathematics was greatly clarified by the "new" logic. Giuseppe Peano Giuseppe Peano (August 27, 1858 – April 20, 1932) was an Italian mathematician and philosopher best known for his contributions to set theory. ... Aristotle (Greek: AristotélÄ“s) (384 BC – 322 BC) was a Greek philosopher, a student of Plato and teacher of Alexander the Great. ... Gottfried Leibniz Gottfried Wilhelm von Leibniz (July 1, 1646 in Leipzig - November 14, 1716 in Hannover) was a German philosopher, scientist, mathematician, diplomat, librarian, and lawyer of Sorb descent. ... Johann Heinrich Lambert Johann Heinrich Lambert (August 26, 1728 – September 25, 1777), was a mathematician, physicist and astronomer. ... George Boole [], (November 2, 1815 – December 8, 1864) was a British mathematician and philosopher. ... The tone or style of this article or section may not be appropriate for Wikipedia. ... Foundations of mathematics is a term sometimes used for certain fields of mathematics itself, namely for mathematical logic, axiomatic set theory, proof theory, model theory, and recursion theory. ... // Philosophy of mathematics is the branch of philosophy that studies the philosophical assumptions, foundations, and implications of mathematics. ...


While the Greek development of logic put heavy emphasis on forms of arguments, the attitude of current mathematical logic might be summed up as the combinatorial study of content. This covers both the syntactic and the semantic, that is, both the forms of expressions and the meanings of those expressions. In computer science, purely syntactic considerations allow a string from some formal language to be transformed by a compiler program into a sequence of machine instructions. Semantic considerations allow a computer programmer to choose which strings to use to accomplish a particular purpose. In mathematics, logic, and computer science, a formal language is a language that is defined by precise mathematical or machine processable formulas. ... A diagram of the operation of a typical multi-language, multi-target compiler. ...


Some landmark publications in mathematical logic include the Begriffsschrift by Gottlob Frege, Studies in Logic by Charles Peirce, Principia Mathematica by Bertrand Russell and Alfred North Whitehead, and On Formally Undecidable Propositions of Principia Mathematica and Related Systems by Kurt Gödel. Begriffsschrift is the title of a short book on logic by Gottlob Frege, published in 1879, and is also the name of the formal system set out in that book. ... Friedrich Ludwig Gottlob Frege (8 November 1848, Wismar – 26 July 1925, IPA: ) was a German mathematician who became a logician and philosopher. ... Charles Sanders Peirce (IPA: /pɝs/), (September 10, 1839 – April 19, 1914) was an American polymath, physicist, and philosopher, born in Cambridge, Massachusetts. ... The Principia Mathematica is a three-volume work on the foundations of mathematics, written by Alfred North Whitehead and Bertrand Russell and published in 1910-1913. ... Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS, (18 May 1872 – 2 February 1970), was a British philosopher, logician, mathematician, advocate for social reform, and pacifist. ... Alfred North Whitehead, OM (February 15, 1861 Ramsgate, Kent, England – December 30, 1947 Cambridge, Massachusetts, USA) was an English-born mathematician who became a philosopher. ... In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proved by Kurt Gödel in 1931. ... Kurt Gödel (IPA: ) (April 28, 1906 Brünn, Austria-Hungary (now Brno, Czech Republic) – January 14, 1978 Princeton, New Jersey) was an Austrian American mathematician and philosopher. ...


Formal logic

At its core, mathematical logic deals with mathematical concepts expressed using formal logical systems. The system of first-order logic is the most widely studied because of its applicability to foundations of mathematics and because of its desirable properties. Stronger classical logics such as second-order logic or infinitary logic are also studied, along with nonclassical logics such as intuitionistic logic. First-order logic (FOL) is a universal language in symbolic science, and is in use everyday by mathematicians, philosophers, linguists, computer scientists and practitioners of artificial intelligence. ... Foundations of mathematics is a term sometimes used for certain fields of mathematics itself, namely for mathematical logic, axiomatic set theory, proof theory, model theory, and recursion theory. ... In mathematical logic, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. ... Those unfamiliar with mathematical logic or the concept of ordinals should read these articles first. ... Intuitionistic logic, or constructivist logic, is the logic used in mathematical intuitionism and other forms of mathematical constructivism. ...


Fields of mathematical logic

The "Handbook of Mathematical Logic" (1977) divides mathematical logic into four parts:

  • Proof theory is the study of formal proofs in various logical deduction systems. These proofs are represented as formal mathematical objects, facilitating their analysis by mathematical techniques. Frege worked on mathematical proofs and formalized the notion of a proof.
  • Model theory studies the models of various formal theories. The set of all models of a particular theory is called an elementary class; classical model theory seeks to determine the properties of models in a particular elementary class, or determine whether certain classes of structures form elementary classes. The method of quantifier elimination is used to show that models of particular theories cannot be too complicated.
  • Recursion theory, also called computability theory, studies the properties of computable functions and the Turing degrees, which divide the uncomputable functions into sets which have the same level of uncomputability. Recursion theory also includes the study of generalized computability and definability.

The border lines between these fields, and also between mathematical logic and other fields of mathematics, are not always sharp; for example, Gödel's incompleteness theorem marks not only a milestone in recursion theory and proof theory, but has also led to Loeb's theorem, which is important in modal logic. The mathematical field of category theory uses many formal axiomatic methods resembling those used in mathematical logic, but category theory is not ordinarily considered a subfield of mathematical logic. Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... In mathematics, a set can be thought of as any collection of distinct objects considered as a whole. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, the terms, subset, superset and proper (or strict) subset or superset are used to describe the relation, called inclusion, of one set being contained inside another set. ... In mathematics, a relatively complemented lattice is a lattice L in which for all a, b, c in L with a ≤ b ≤ c there is some x in L such that x ∨ b = c and x ∧ b = a. ... In abstract mathematics, naive set theory[1] was the first development of set theory, which was later to be framed more carefully as axiomatic set theory. ... This article or section is in need of attention from an expert on the subject. ... The Zermelo-Fraenkel axioms of set theory (ZF) are the standard axioms of axiomatic set theory on which, together with the axiom of choice, all of ordinary mathematics is based in modern formulations. ... In mathematical logic, New Foundations (NF) is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. ... Proof theory is a branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. ... In mathematics, model theory is the study of the representation of mathematical concepts in terms of set theory, or the study of the structures that underlie mathematical systems. ... In mathematics, specifically model theory, a class K of models for a first-order language L is an elementary class if there is some sentence in the language such that for all models A, iff A satisfies . ... Quantifier elimination is a technique in logic, model theory, and theoretical computer science. ... Recursion theory, or computability theory, is a branch of mathematical logic dealing with generalizations of the notion of computable function, and with related notions such as Turing degrees and effective descriptive set theory. ... Computable functions (or Turing-computable functions) are the basic objects of study in computability theory. ... In computer science and mathematical logic, the Turing degree or degree of unsolvability of a set X of natural numbers is the equivalence class of all sets that are Turing equivalent to X. The concept of Turing degree is fundamental in computability theory. ... In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proven by Kurt Gödel in 1931. ... In mathematical logic, Löbs theorem states that in a theory with Peano arithmetic, for any formula P, if it is provable that if P is provable then P, then P is provable. ... In formal logic, a modal logic is any logic for handling modalities: concepts like possibility, existence, and necessity. ... In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them. ...


Connections with computer science

There are many connections between mathematical logic and computer science. Early pioneers in computer science, such as Alan Turing, were also mathematicians and logicians. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... Alan Mathison Turing, FRS,OBE (23 June 1912 – 7 June 1954) was an English mathematician, logician, and cryptographer. ...


The study of computability theory in computer science is closely related to the study of computability in mathematical logic. There is a difference of emphasis, however. Computer scientists often focus on concrete programming languages and feasible computability, while researchers in mathematical logic often focus on computability as a theoretical concept and on noncomputability. In computer science, computability theory is the branch of the theory of computation that studies which problems are computationally solvable using different models of computation. ...


The study of programming language semantics is related to model theory, as is program verification (in particular, model checking). The Curry-Howard isomorphism between proofs and programs relates to proof theory; intuitionistic logic and linear logic are significant here. Calculi such as the lambda calculus and combinatory logic are nowadays studied mainly as idealized programming languages. A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ... In theoretical computer science, formal semantics is the field concerned with the rigorous mathematical study of the meaning of programming languages and models of computation. ... In mathematics, model theory is the study of the representation of mathematical concepts in terms of set theory, or the study of the structures that underlie mathematical systems. ... Program verification is the process of formally proving that a computer program does exactly what is stated in the program specification it was written to realize. ... Model checking is the process of checking whether a given model satisfies a given logical formula. ... The Curry-Howard correspondence is the close relationship between computer programs and mathematical proofs; the correspondence is also known as the Curry-Howard isomorphism, or the formulae-as-types correspondence. ... Proof theory is a branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. ... Intuitionistic logic, or constructivist logic, is the logic used in mathematical intuitionism and other forms of mathematical constructivism. ... In mathematical logic, linear logic is a type of substructural logic that denies the structural rules of weakening and contraction. ... The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ... Combinatory logic is a notation introduced by Moses Schönfinkel and Haskell Curry to eliminate the need for variables in mathematical logic. ... Other listings of programming languages are: Categorical list of programming languages Generational list of programming languages Chronological list of programming languages Note: Esoteric programming languages have been moved to the separate List of esoteric programming languages. ...


Computer science also contributes to mathematics by developing techniques for the automatic checking or even finding of proofs, such as automated theorem proving and logic programming. Automated theorem proving (ATP) or automated deduction, currently the most well-developed subfield of automated reasoning (AR), is the proving of mathematical theorems by a computer program. ... Logic programming (which might better be called logical programming by analogy with mathematical programming and linear programming) is, in its broadest sense, the use of mathematical logic for computer programming. ...


Groundbreaking results

  • The Löwenheim–Skolem theorem (1919) showed that if a set of sentences in a countable first-order language has an infinite model then it has at least one model of each infinite cardinality.
  • Gödel's completeness theorem (1929) established the equivalence between semantic and syntactic definitions of logical consequence in first-order logic.
  • Gödel's incompleteness theorems (1931) showed that no sufficiently strong formal system can prove its own consistency.
  • The algorithmic unsolvability of the Entscheidungsproblem, established independently by Alan Turing and Alonzo Church in 1936, showed that no computer program can be used to correctly decide whether arbitrary mathematical statements are true.
  • The independence of the continuum hypothesis from ZFC showed that an elementary proof or disproof of this hypothesis is impossible. The fact that the continuum hypothesis is consistent with ZFC (if ZFC itself is consistent) was proved by Gödel in 1940. The fact that the negation of the continuum hypothesis is consistent with ZFC (if ZFC is consistent) was proved by Paul Cohen in 1963.
  • The algorithmic unsolvability of Hilbert's tenth problem, established by Yuri Matiyasevich in 1970, showed that it is not possible for any computer program to correctly decide whether multivariate polynomials with integer coefficients have any integer roots.

In mathematical logic, the classic Löwenheim–Skolem theorem states that for any countable first-order language L with signature and L-structure M, there exists a countably infinite elementary substructure N M. A natural and useful corollary of this theorem is that every consistent L-theory has a countable... Gödels completeness theorem is an important theorem in mathematical logic which was first proved by Kurt Gödel in 1929. ... In mathematical logic, Gödels incompleteness theorems, proved by Kurt Gödel in 1931, are two theorems stating inherent limitations of all but the most trivial formal systems for arithmetic of mathematical interest. ... The Entscheidungsproblem (German for decision problem) is the challenge in symbolic logic to find a general algorithm which decides for given first-order statements whether they are universally valid or not. ... Alan Mathison Turing, FRS,OBE (23 June 1912 – 7 June 1954) was an English mathematician, logician, and cryptographer. ... ‹ The template below (Expand) is being considered for deletion. ... In mathematics, the continuum hypothesis is a hypothesis about the possible sizes of infinite sets. ... The Zermelo-Fraenkel axioms of set theory (ZF) are the standard axioms of axiomatic set theory on which, together with the axiom of choice, all of ordinary mathematics is based in modern formulations. ... Kurt Gödel (IPA: ) (April 28, 1906 Brünn, Austria-Hungary (now Brno, Czech Republic) – January 14, 1978 Princeton, New Jersey) was an Austrian American mathematician and philosopher. ... Paul Joseph Cohen (April 2, 1934 – March 23, 2007[1]) was an American mathematician. ... Hilberts tenth problem is the tenth on the list of Hilberts problems of 1900. ... Yuri Matiyasevich born March 2, 1947 in Leningrad, is a Russian mathematician. ...

References

  • Andrews, Peter B., 2002. An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof, 2nd ed. Kluwer Academic Publishers.
  • Barwise, Jon, ed. (1977) Handbook of Mathematical Logic, Amsterdam: North-Holland. ISBN 0-444-86388-5
  • George Boolos, John Burgess, and Richard Jeffrey (2002) Computability and Logic, 4th ed. Cambridge University Press. ISBN 0-521-00758-5.
  • Enderton, Herbert (2002) A mathematical introduction to logic, 2nd ed. Academic Press.
  • Hamilton, A. G. (1988) Logic for Mathematicians Cambridge University Press.
  • Wilfrid Hodges, 1997. A Shorter Model Theory. Cambridge University Press.
  • Mendelson, Elliott (1997) Introduction to Mathematical Logic, 4th ed. Chapman & Hall. ISBN 0412808307
  • A. S. Troelstra & H. Schwichtenberg (2000) Basic Proof Theory, 2nd. ed. (Cambridge Tracts in Theoretical Computer Science). Cambridge University Press. ISBN 0-521-77911-1.
  • John L. Bell & Alan B. Slomson (1969) Models and Ultraproducts: An Introduction, North-Holland (re-printed in 2006 by Dover publications). ISBN 0-486-44979-3.

Kenneth Jon Barwise (June 29, 1942 - March 5, 2000) was a US mathematician, philosopher and logician who proposed some fundamental revisions to the way that logic is understood and used. ... George Stephen Boolos (September 4, 1940, New York City - May 27, 1996) was a philosopher and a mathematical logician. ... Richard C. Jeffrey (5 August 1926 – 9 November 2002) was an American philosopher, logician, and probability theorist. ... Wilfrid Hodges (born 1941) is a British mathematician, known for his work in model theory. ... Anne Sjerp Troelstra (born August 10, 1939 at Maartensdijk (Utrecht), The Netherlands) is Emeritus professor of pure mathematics and foundations of mathematics at the Institute of Logic, Language and Information (ILLC) of the University of Amsterdam. ... JOHN L. BELL is an ordained minister of the Church of Scotland and a Member of the Iona Community. ...

Further reading

See also

Look up theorem in Wiktionary, the free dictionary. ... This is a list of mathematical logic topics, by Wikipedia page. ... This is a list of computability and complexity topics, by Wikipedia page. ... Set theory Axiomatic set theory Naive set theory Zermelo set theory Zermelo-Fraenkel set theory Kripke-Platek set theory with urelements Simple theorems in the algebra of sets Axiom of choice Zorns lemma Empty set Cardinality Cardinal number Aleph number Aleph null Aleph one Beth number Ordinal number Well... In mathematical logic, a first-order theory is given by a set of axioms in some language. ... In logic, a set of symbols is frequently used to express logical constructs. ...

External links

Logic Portal

  Results from FactBites:
 
Logic - Wikipedia, the free encyclopedia (3824 words)
Mathematical logic really refers to two distinct areas of research: the first is the application of the techniques of formal logic to mathematics and mathematical reasoning, and the second, in the other direction, the application of mathematical techniques to the representation and analysis of formal logic.
The boldest attempt to apply logic to mathematics was undoubtedly the logicism pioneered by philosopher-logicians such as Gottlob Frege and Bertrand Russell: the idea was that mathematical theories were logical tautologies, and the programme was to show this by means to a reduction of mathematics to logic.
Logic cut to the heart of computer science as it emerged as a discipline: Alan Turing's work on the Entscheidungsproblem followed from Kurt Gödel's work on the incompleteness theorems, and the notion of general purpose computer that came from this work was of fundamental importance to the designers of the computer machinery in the 1940s.
Mathematical logic - Wikipedia, the free encyclopedia (969 words)
In essentials, it is still the logic of Aristotle, but from the point of view of notation it is written as a branch of abstract algebra.
Attempts to treat the operations of formal logic in a symbolic or algebraic way were made by some of the more philosophical mathematicians, such as Leibniz and Lambert; but their labors remained little known and isolated.
While the traditional development of logic (see list of topics in logic) put heavy emphasis on forms of arguments, the attitude of current mathematical logic might be summed up as the combinatorial study of content.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m