symbolic logic

 

or mathematical logic, formalized system of deductive logic, employing abstract symbols for the various aspects of natural language. Symbolic logic draws on the concepts and techniques of mathematics, notably set theory, and in turn has contributed to the development of the foundations of mathematics. Symbolic logic dates from the work of Augustus De Morgan and George Boole in the mid-19th cent. and was further developed by W. S. Jevons, C. S. Peirce, Ernst Schröder, Gottlob Frege, Giuseppe Peano, Bertrand Russell, A. N. Whitehead, David Hilbert, and others.

Truth-functional Analysis

The first part of symbolic logic is known as truth-functional analysis, the propositional calculus, or the sentential calculus; it deals with statements that can be assigned truth values (true or false). Combinations of these statements are called truth functions, and their truth values can be determined from the truth values of their components.

The basic connectives in truth-functional analysis are usually negation, conjunction, and alternation. The negation of a statement is false if the original statement is true and true if the original statement is false; negation corresponds to “it is not the case that,” or simply “not” in ordinary language. The conjunction of two statements is true only if both are true; it is false in all other instances. Conjunction corresponds to “and” in ordinary language. The alternation, or disjunction, of two statements is false only if both are false and is true in all other instances; alternation corresponds to the nonexclusive sense of “or” in ordinary language (Lat. vel), as opposed to the exclusive “either...or...but not both” (Lat. aut).

Other connectives commonly used in truth-functional analysis are the conditional and the biconditional. The conditional, or implication, corresponds to “if...then” or “implies” in ordinary language, but only in a weak sense. The conditional is false only if the antecedent is true and the consequent is false; it is true in all other instances. This kind of implication, in which the connection between the antecedent and the consequent is merely formal, is known as material implication. The biconditional, or double implication, is the equivalence relation and is true only if the two statements have the same truth value, either true or false. In any truth function one may substitute an equivalent expression for all or any part of the function. The validity of arguments may be analyzed by assigning all possible combinations of truth values to the component statements; such an array of truth values is called a truth table.

The Predicate Calculus

There are many valid argument forms, however, that cannot be analyzed by truth-functional methods, e.g., the classic syllogism: “All men are mortal. Socrates is a man. Therefore Socrates is mortal.” The syllogism and many other more complicated arguments are the subject of the predicate calculus, or quantification theory, which is based on the calculus of classes. The predicate calculus of monadic (one-variable) predicates, also called uniform quantification theory, has been shown to be complete and has a decision procedure, analogous to truth tables for truth-functional analysis, whereby the validity or invalidity of any statement can be determined. The general predicate calculus, or quantification theory, was also shown to be complete by Kurt Gödel, but Alonso Church subsequently proved (1936) that it has no possible decision procedure.

Analysis of the Foundations of Mathematics

Symbolic logic has been extended to a description and analysis of the foundations of mathematics, particularly number theory. Gödel also made (1931) the surprising discovery that number theory cannot be complete, i.e., that no matter what axioms are chosen as a basis for number theory, there will always be some true statements that cannot be deducted from them, although they can be proved within the larger context of symbolic logic. Since many branches of mathematics are ultimately based on number theory, this result has been interpreted by some as affirming that mathematics is an open, creative discipline whose possibilities cannot be delineated. The work of Gödel, Church, and others has led to the development of proof theory, or metamathematics, which deals with the nature of mathematics itself.

Bibliography

See D. Hilbert and W. Ackermann, Principles of Mathematical Logic (tr. of 2d ed. 1950); W. V. Quine, Mathematical Logic (1968) and Methods of Logic (3d ed. 1972).

Mathematical logic is a branch 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.

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.

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.

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]}

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.

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.

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.

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.

Fields of mathematical logic

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

• Set theory is the study of sets, which are abstract collections of objects. The basic concepts of set theory such as subset and relative complement are often called naive set theory. Modern research is in the area of axiomatic set theory, which uses logical methods to study which propositions are provable in various formal theories such as ZFC or NF.

• 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.

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.

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.

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.

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.

Boolean algebra is used to design the hardware digital logic that determines what actions a computer will perform when it receives any particular combination of instructions from the program.

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.

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.

shree guru m mallapur

• The London Philosophy Study Guide offers many suggestions on what to read, depending on the student's familiarity with the subject:
  • Mathematical Logic
  • Set Theory & Further Logic
  • Philosophy of Mathematics

See also

• Theorem
• List of mathematical logic topics
• List of computability and complexity topics
• List of set theory topics
• List of first order theories
• Table of logic symbols

External links

• Mathematical Logic around the world
• Polyvalued logic
• forall x: an introduction to formal logic, by P.D. Magnus, is a free textbook.
• A Problem Course in Mathematical Logic by Stefan Bilaniuk, also a free textbook published under GNU FDL
• Detlovs, Vilnis, and Podnieks, Karlis (University of Latvia) Introduction to Mathematical Logic. A hyper-textbook.
• Stanford Encyclopedia of Philosophy: Classical Logic -- by Stewart Shapiro.
• Stanford Encyclopedia of Philosophy: First-order Model Theory -- by Wilfred Hodges.

Major fields of mathematics
Logic · Set theory · Algebra (Abstract algebra – Linear algebra) · Discrete mathematics · Number theory · Analysis · Geometry · Topology · Applied mathematics · Probability · Statistics · Mathematical physics

Logic
Navigation:	Portal · Category · WikiProject · Logic Stubs · Mathlogic Stubs · Cleanup · Noticeboard
Main Articles:	Reason · History of Logic · Philosophical Logic  · Philosophy of logic · Mathematical Logic · Metalogic · Logic in computer science
Key Concepts	Reasoning: Deduction · Induction · Abduction Informal Logic: Proposition · Inference · Argument · Validity · Cogency · Term logic · Critical Thinking · Fallacies · Syllogism Mathematical logic: Set · Syntax · Semantics · Wff · Axiom · Theorem · Consistency · Soundness · Completeness · Decidability · Formal system · Set theory · Proof theory · Model theory · Recursion theory Zeroth-Order Logic: Boolean functions · Monadic predicate calculus · Propositional calculus · Logical connectives · Truth Tables Predicate Logic: First-Order Logic · Quantifiers  · Second-order logic Modal Logic: Deontic logic · Epistemic logic · Temporal logic · Doxastic logic Other non-classical logics: Computability logic · Fuzzy logic · Linear logic · Relevance logic · Non-monotonic logic
Controversies	Paraconsistent Logic · Dialetheism · Intuitionistic logic · Paradoxes · Antinomies · Is logic empirical?
Key Figures	Aristotle · Boole · Cantor · Carnap · Church · Frege · Gentzen · Gödel · Hilbert · Kripke · Peano · Peirce · Putnam · Quine · Russell · Skolem · Tarski · Turing · Whitehead
Lists	Basic Topics in Logic · Topics in Logic · Logicians · Rules of Inference · Mathematical Logic Topics · Basic Discrete Mathematics Topics · Set theory topics · Paradoxes · Fallacies · Logical Symbols

be-x-old:Матэматычная логікаlij:Logica Matematica

Donate to Wikimedia