Formal system

Last updated

A formal system is an abstract structure and formalization of an axiomatic system used for inferring theorems from axioms by a set of inference rules. [1]

Contents

In 1921, David Hilbert proposed to use the formal system as the foundation for the knowledge in mathematics. [2]

The term formalism is sometimes a rough synonym for formal system, but it also refers to a given style of notation, for example, Paul Dirac's bra–ket notation.

Concepts

This diagram shows the syntactic entities that may be constructed from formal languages. The symbols and strings of symbols may be broadly divided into nonsense and well-formed formulas. A formal language can be thought of as identical to the set of its well-formed formulas, which may be broadly divided into theorems and non-theorems. Formal languages.svg
This diagram shows the syntactic entities that may be constructed from formal languages. The symbols and strings of symbols may be broadly divided into nonsense and well-formed formulas. A formal language can be thought of as identical to the set of its well-formed formulas, which may be broadly divided into theorems and non-theorems.

A formal system has the following: [3] [4] [5]

A formal system is said to be recursive (i.e. effective) or recursively enumerable if the set of axioms and the set of inference rules are decidable sets or semidecidable sets, respectively.

Formal language

A formal language is a language that is defined by a formal system. Like languages in linguistics, formal languages generally have two aspects:

Usually only the syntax of a formal language is considered via the notion of a formal grammar. The two main categories of formal grammar are that of generative grammars, which are sets of rules for how strings in a language can be written, and that of analytic grammars (or reductive grammar [6] [7] ), which are sets of rules for how a string can be analyzed to determine whether it is a member of the language.

Deductive system

A deductive system, also called a deductive apparatus, [8] consists of the axioms (or axiom schemata) and rules of inference that can be used to derive theorems of the system. [9]

Such deductive systems preserve deductive qualities in the formulas that are expressed in the system. Usually the quality we are concerned with is truth as opposed to falsehood. However, other modalities, such as justification or belief may be preserved instead.

In order to sustain its deductive integrity, a deductive apparatus must be definable without reference to any intended interpretation of the language. The aim is to ensure that each line of a derivation is merely a logical consequence of the lines that precede it. There should be no element of any interpretation of the language that gets involved with the deductive nature of the system.

The logical consequence (or entailment) of the system by its logical foundation is what distinguishes a formal system from others which may have some basis in an abstract model. Often the formal system will be the basis for or even identified with a larger theory or field (e.g. Euclidean geometry) consistent with the usage in modern mathematics such as model theory.[ clarification needed ]

An example of a deductive system would be the rules of inference and axioms regarding equality used in first order logic.

The two main types of deductive systems are proof systems and formal semantics. [8]

Proof system

Formal proofs are sequences of well-formed formulas (or WFF for short) that might either be an axiom or be the product of applying an inference rule on previous WFFs in the proof sequence. The last WFF in the sequence is recognized as a theorem.

Once a formal system is given, one can define the set of theorems which can be proved inside the formal system. This set consists of all WFFs for which there is a proof. Thus all axioms are considered theorems. Unlike the grammar for WFFs, there is no guarantee that there will be a decision procedure for deciding whether a given WFF is a theorem or not.

The point of view that generating formal proofs is all there is to mathematics is often called formalism . David Hilbert founded metamathematics as a discipline for discussing formal systems. Any language that one uses to talk about a formal system is called a metalanguage . The metalanguage may be a natural language, or it may be partially formalized itself, but it is generally less completely formalized than the formal language component of the formal system under examination, which is then called the object language, that is, the object of the discussion in question. The notion of theorem just defined should not be confused with theorems about the formal system, which, in order to avoid confusion, are usually called metatheorems.

Formal semantics of logical system

A logical system is a deductive system (most commonly first order logic) together with additional non-logical axioms. According to model theory, a logical system may be given interpretations which describe whether a given structure - the mapping of formulas to a particular meaning - satisfies a well-formed formula. A structure that satisfies all the axioms of the formal system is known as a model of the logical system.

A logical system is:

  • Sound, if each well-formed formula that can be inferred from the axioms is satisfied by every model of the logical system.
  • Semantically complete, if each well-formed formula that is satisfied by every model of the logical system can be inferred from the axioms.

An example of a logical system is Peano arithmetic. The standard model of arithmetic sets the domain of discourse to be the nonnegative integers and gives the symbols their usual meaning. [10] There are also non-standard models of arithmetic.

History

Early logic systems includes Indian logic of Pāṇini, syllogistic logic of Aristotle, propositional logic of Stoicism, and Chinese logic of Gongsun Long (c. 325–250 BCE) . In more recent times, contributors include George Boole, Augustus De Morgan, and Gottlob Frege. Mathematical logic was developed in 19th century Europe.

David Hilbert instigated a formalist movement called Hilbert’s program as a proposed solution to the foundational crisis of mathematics, that was eventually tempered by Gödel's incompleteness theorems. [2] The QED manifesto represented a subsequent, as yet unsuccessful, effort at formalization of known mathematics.

See also

Related Research Articles

An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word ἀξίωμα (axíōma), meaning 'that which is thought worthy or fit' or 'that which commends itself as evident'.

<span class="mw-page-title-main">Formal language</span> Sequence of words formed by specific rules

In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules called a formal grammar.

First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over non-logical objects, and allows the use of sentences that contain variables, so that rather than propositions such as "Socrates is a man", one can have expressions in the form "there exists x such that x is Socrates and x is a man", where "there exists" is a quantifier, while x is a variable. This distinguishes it from propositional logic, which does not use quantifiers or relations; in this sense, propositional logic is the foundation of first-order logic.

<span class="mw-page-title-main">Gödel's completeness theorem</span> Fundamental theorem in mathematical logic

Gödel's completeness theorem is a fundamental theorem in mathematical logic that establishes a correspondence between semantic truth and syntactic provability in first-order logic.

The propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions and relations between propositions, including the construction of arguments based on them. Compound propositions are formed by connecting propositions by logical connectives representing the truth functions of conjunction, disjunction, implication, equivalence, and negation. Some sources include other connectives, as in the table below.

Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal systems of logic such as their expressive or deductive power. However, it can also include uses of logic to characterize correct mathematical reasoning or to establish foundations of mathematics.

In logic and deductive reasoning, an argument is sound if it is both valid in form and its premises are true. Soundness has a related meaning in mathematical logic, wherein a formal system of logic is sound if and only if every well-formed formula that can be proven in the system is logically valid with respect to the logical semantics of the system.

<span class="mw-page-title-main">Theorem</span> In mathematics, a statement that has been proved

In mathematics, a theorem is a statement that has been proved, or can be proved. The proof of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of the axioms and previously proved theorems.

Proof theory is a major branch of mathematical logic and theoretical computer science within which proofs are treated as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures such as lists, boxed lists, or trees, which are constructed according to the axioms and rules of inference of a given logical system. Consequently, proof theory is syntactic in nature, in contrast to model theory, which is semantic in nature.

In logic and mathematics, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory.

Metalogic is the study of the metatheory of logic. Whereas logic studies how logical systems can be used to construct valid and sound arguments, metalogic studies the properties of logical systems. Logic concerns the truths that may be derived using a logical system; metalogic concerns the truths that may be derived about the languages and systems that are used to express truths.

<span class="mw-page-title-main">Syntax (logic)</span> Rules used for constructing, or transforming the symbols and words of a language

In logic, syntax is anything having to do with formal languages or formal systems without regard to any interpretation or meaning given to them. Syntax is concerned with the rules used for constructing, or transforming the symbols and words of a language, as contrasted with the semantics of a language which is concerned with its meaning.

In logic and mathematics, a formal proof or derivation is a finite sequence of sentences, each of which is an axiom, an assumption, or follows from the preceding sentences in the sequence by a rule of inference. It differs from a natural language argument in that it is rigorous, unambiguous and mechanically verifiable. If the set of assumptions is empty, then the last sentence in a formal proof is called a theorem of the formal system. The notion of theorem is not in general effective, therefore there may be no method by which we can always find a proof of a given sentence or determine that none exists. The concepts of Fitch-style proof, sequent calculus and natural deduction are generalizations of the concept of proof.

In mathematical logic, a theory is a set of sentences in a formal language. In most scenarios a deductive system is first understood from context, after which an element of a deductively closed theory is then called a theorem of the theory. In many deductive systems there is usually a subset that is called "the set of axioms" of the theory , in which case the deductive system is also called an "axiomatic system". By definition, every axiom is automatically a theorem. A first-order theory is a set of first-order sentences (theorems) recursively obtained by the inference rules of the system applied to the set of axioms.

Metamath is a formal language and an associated computer program for archiving and verifying mathematical proofs. Several databases of proved theorems have been developed using Metamath covering standard results in logic, set theory, number theory, algebra, topology and analysis, among others.

Logic is the formal science of using reason and is considered a branch of both philosophy and mathematics and to a lesser extent computer science. Logic investigates and classifies the structure of statements and arguments, both through the study of formal systems of inference and the study of arguments in natural language. The scope of logic can therefore be very large, ranging from core topics such as the study of fallacies and paradoxes, to specialized analyses of reasoning such as probability, correct reasoning, and arguments involving causality. One of the aims of logic is to identify the correct and incorrect inferences. Logicians study the criteria for the evaluation of arguments.

In mathematical logic, formation rules are rules for describing which strings of symbols formed from the alphabet of a formal language are syntactically valid within the language. These rules only address the location and manipulation of the strings of the language. It does not describe anything else about a language, such as its semantics. .

In the philosophy of mathematics, formalism is the view that holds that statements of mathematics and logic can be considered to be statements about the consequences of the manipulation of strings using established manipulation rules. A central idea of formalism "is that mathematics is not a body of propositions representing an abstract sector of reality, but is much more akin to a game, bringing with it no more commitment to an ontology of objects or properties than ludo or chess." According to formalism, the truths expressed in logic and mathematics are not about numbers, sets, or triangles or any other coextensive subject matter — in fact, they aren't "about" anything at all. Rather, mathematical statements are syntactic forms whose shapes and locations have no meaning unless they are given an interpretation. In contrast to mathematical realism, logicism, or intuitionism, formalism's contours are less defined due to broad approaches that can be categorized as formalist.

<span class="mw-page-title-main">Brouwer–Hilbert controversy</span>

The Brouwer–Hilbert controversy was a debate in twentieth-century mathematics over fundamental questions about the consistency of axioms and the role of semantics and syntax in mathematics. L. E. J. Brouwer, a proponent of the constructivist school of intuitionism, opposed David Hilbert, a proponent of formalism. Much of the controversy took place while both were involved with Mathematische Annalen, the leading mathematical journal of the time, with Hilbert as editor-in-chief and Brouwer as a member of its editorial board. In 1920, Hilbert succeeded in having Brouwer, whom he considered a threat to mathematics, removed from the editorial board of Mathematische Annalen.

References

  1. ↑ "Formal system | Logic, Symbols & Axioms | Britannica". www.britannica.com. Retrieved 2023-10-10.
  2. 1 2 Zach, Richard (31 July 2003). "Hilbert's Program". Hilbert's Program, Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University.
  3. ↑ "formal system". planetmath.org. Retrieved 2023-10-10.
  4. ↑ Rapaport, William J. (25 March 2010). "Syntax & Semantics of Formal Systems". University of Buffalo.
  5. ↑ "Definition:Formal System - ProofWiki". proofwiki.org. Retrieved 2023-10-16.
  6. ↑ Reductive grammar: (computer science) A set of syntactic rules for the analysis of strings to determine whether the strings exist in a language. "Sci-Tech Dictionary McGraw-Hill Dictionary of Scientific and Technical Terms" (6th ed.). McGraw-Hill.[ unreliable source? ] About the Author Compiled by The Editors of the McGraw-Hill Encyclopedia of Science & Technology (New York, NY) an in-house staff who represents the cutting-edge of skill, knowledge, and innovation in science publishing.
  7. ↑ "There are two classes of formal-language definition compiler-writing schemes. The productive grammar approach is the most common. A productive grammar consists primarrly of a set of rules that describe a method of generating all possible strings of the language. The reductive or analytical grammar technique states a set of rules that describe a method of analyzing any string of characters and deciding whether that string is in the language." "The TREE-META Compiler-Compiler System: A Meta Compiler System for the Univac 1108 and General Electric 645, University of Utah Technical Report RADC-TR-69-83. C. Stephen Carr, David A. Luther, Sherian Erdmann" (PDF). Retrieved 5 January 2015.
  8. 1 2 "Definition:Deductive Apparatus - ProofWiki". proofwiki.org. Retrieved 2023-10-10.
  9. ↑ Hunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Press, 1971
  10. ↑ Kaye, Richard (1991). "1. The Standard Model". Models of Peano arithmetic. Oxford: Clarendon Press. p. 10. ISBN   9780198532132.

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.