A formal system is an

abstract structure In mathematics and related fields, an abstract structure is a way of describing a set of mathematical objects and the relationships between them, focusing on the essential rules and properties rather than any specific meaning or example.{{Cite book ...

and formalization of an axiomatic system used for deducing, using

rules of inference Rules of inference are ways of deriving conclusions from premises. They are integral parts of formal logic, serving as norms of the logical structure of valid arguments. If an argument with true premises follows a rule of inference then the c ...

theorem In mathematics and formal logic, a theorem is a statement (logic), statement that has been Mathematical proof, proven, or can be proven. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to esta ...

s from axioms. In 1921,

David Hilbert David Hilbert (; ; 23 January 1862 – 14 February 1943) was a German mathematician and philosopher of mathematics and one of the most influential mathematicians of his time. Hilbert discovered and developed a broad range of fundamental idea ...

proposed to use formal systems as the foundation of knowledge in

mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

. The term ''formalism'' is sometimes a rough synonym for ''formal system'', but it also refers to a given style of

notation In linguistics and semiotics, a notation system is a system of graphics or symbols, Character_(symbol), characters and abbreviated Expression (language), expressions, used (for example) in Artistic disciplines, artistic and scientific disciplines ...

, for example,

Paul Dirac Paul Adrien Maurice Dirac ( ; 8 August 1902 – 20 October 1984) was an English mathematician and Theoretical physics, theoretical physicist who is considered to be one of the founders of quantum mechanics. Dirac laid the foundations for bot ...

bra–ket notation Bra–ket notation, also called Dirac notation, is a notation for linear algebra and linear operators on complex vector spaces together with their dual space both in the finite-dimensional and infinite-dimensional case. It is specifically de ...

Concepts

A formal system has the following: *

Formal language In logic, mathematics, computer science, and linguistics, a formal language is a set of strings whose symbols are taken from a set called "alphabet". The alphabet of a formal language consists of symbols that concatenate into strings (also c ...

, which is a set of well-formed formulas, which are strings of

symbols A symbol is a mark, sign, or word that indicates, signifies, or is understood as representing an idea, object, or relationship. Symbols allow people to go beyond what is known or seen by creating linkages between otherwise different concep ...

from an

alphabet An alphabet is a standard set of letter (alphabet), letters written to represent particular sounds in a spoken language. Specifically, letters largely correspond to phonemes as the smallest sound segments that can distinguish one word from a ...

, formed by a

formal grammar A formal grammar is a set of Terminal and nonterminal symbols, symbols and the Production (computer science), production rules for rewriting some of them into every possible string of a formal language over an Alphabet (formal languages), alphabe ...

(consisting of production rules or formation rules). *

Deductive system A formal system is an abstract structure and formalization of an axiomatic system used for deducing, using rules of inference, theorems from axioms. In 1921, David Hilbert proposed to use formal systems as the foundation of knowledge in math ...

, deductive apparatus, or proof system, which has

that take axioms and infers

s, both of which are part of the formal language. 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

formal language In logic, mathematics, computer science, and linguistics, a formal language is a set of strings whose symbols are taken from a set called "alphabet". The alphabet of a formal language consists of symbols that concatenate into strings (also c ...

is a language that is defined by a formal system. Like languages in

linguistics Linguistics is the scientific study of language. The areas of linguistic analysis are syntax (rules governing the structure of sentences), semantics (meaning), Morphology (linguistics), morphology (structure of words), phonetics (speech sounds ...

, formal languages generally have two aspects: * the

syntax In linguistics, syntax ( ) is the study of how words and morphemes combine to form larger units such as phrases and sentences. Central concerns of syntax include word order, grammatical relations, hierarchical sentence structure (constituenc ...

is what the language looks like (more formally: the set of possible expressions that are valid utterances in the language) * the

semantics Semantics is the study of linguistic Meaning (philosophy), meaning. It examines what meaning is, how words get their meaning, and how the meaning of a complex expression depends on its parts. Part of this process involves the distinction betwee ...

are what the utterances of the language mean (which is formalized in various ways, depending on the type of language in question) Usually only the

of a formal language is considered via the notion of a

. The two main categories of formal grammar are that of

generative grammar Generative grammar is a research tradition in linguistics that aims to explain the cognitive basis of language by formulating and testing explicit models of humans' subconscious grammatical knowledge. Generative linguists, or generativists (), ...

s, which are sets of rules for how strings in a language can be written, and that of analytic grammars (or reductive grammar), 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'', consists of the

axiom 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 (), meaning 'that which is thought worthy or ...

s (or

axiom schema In mathematical logic, an axiom schema (plural: axiom schemata or axiom schemas) generalizes the notion of axiom. Formal definition An axiom schema is a formula in the metalanguage of an axiomatic system, in which one or more schematic variabl ...

ta) and

that can be used to derive

s of the system. 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 Logical consequence (also entailment or logical implication) is a fundamental concept in logic which describes the relationship between statement (logic), statements that hold true when one statement logically ''follows from'' one or more stat ...

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

(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 A theory is a systematic and rational form of abstract thinking about a phenomenon, or the conclusions derived from such thinking. It involves contemplative and logical reasoning, often supported by processes such as observation, experimentation, ...

or field (e.g.

Euclidean geometry Euclidean geometry is a mathematical system attributed to ancient Greek mathematics, Greek mathematician Euclid, which he described in his textbook on geometry, ''Euclid's Elements, Elements''. Euclid's approach consists in assuming a small set ...

) consistent with the usage in modern mathematics such as

model theory In mathematical logic, model theory is the study of the relationship between theory (mathematical logic), formal theories (a collection of Sentence (mathematical logic), sentences in a formal language expressing statements about a Structure (mat ...

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

Proof system

Formal proofs are sequences of

well-formed formula In mathematical logic, propositional logic and predicate logic, a well-formed formula, abbreviated WFF or wff, often simply formula, is a finite sequence of symbols from a given alphabet that is part of a formal language. The abbreviation wf ...

s (or WFF for short) that might either be an

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

. 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 Decision may refer to: Law and politics *Judgment (law), as the outcome of a legal case * Landmark decision, the outcome of a case that sets a legal precedent * ''Per curiam'' decision, by a court with multiple judges Books * ''Decision'' (novel ...

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

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

metatheorem In logic, a metatheorem is a statement about a formal system proven in a metalanguage. Unlike theorems proved within a given formal system, a metatheorem is proved within a metatheory, and may reference concepts that are present in the metatheo ...

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

, a logical system may be given interpretations which describe whether a given

structure A structure is an arrangement and organization of interrelated elements in a material object or system, or the object or system so organized. Material structures include man-made objects such as buildings and machines and natural objects such as ...

- 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 A model is an informative representation of an object, person, or system. The term originally denoted the plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin , . Models can be divided in ...

of the logical system. A logical system is: *

Sound In physics, sound is a vibration that propagates as an acoustic wave through a transmission medium such as a gas, liquid or solid. In human physiology and psychology, sound is the ''reception'' of such waves and their ''perception'' by the br ...

, 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 In the formal sciences, the domain of discourse or universe of discourse (borrowing from the mathematical concept of ''universe'') is the set of entities over which certain variables of interest in some formal treatment may range. It is also ...

to be the

nonnegative integer In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positiv ...

s and gives the symbols their usual meaning. There are also non-standard models of arithmetic.

History

Early logic systems includes Indian logic of

Pāṇini (; , ) was a Sanskrit grammarian, logician, philologist, and revered scholar in ancient India during the mid-1st millennium BCE, dated variously by most scholars between the 6th–5th and 4th century BCE. The historical facts of his life ar ...

, 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 George Boole ( ; 2 November 1815 – 8 December 1864) was a largely self-taught English mathematician, philosopher and logician, most of whose short career was spent as the first professor of mathematics at Queen's College, Cork in Ireland. H ...

Augustus De Morgan Augustus De Morgan (27 June 1806 – 18 March 1871) was a British mathematician and logician. He is best known for De Morgan's laws, relating logical conjunction, disjunction, and negation, and for coining the term "mathematical induction", the ...

, and

Gottlob Frege Friedrich Ludwig Gottlob Frege (; ; 8 November 1848 – 26 July 1925) was a German philosopher, logician, and mathematician. He was a mathematics professor at the University of Jena, and is understood by many to be the father of analytic philos ...

Mathematical logic Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...

was developed in 19th century

Europe Europe is a continent located entirely in the Northern Hemisphere and mostly in the Eastern Hemisphere. It is bordered by the Arctic Ocean to the north, the Atlantic Ocean to the west, the Mediterranean Sea to the south, and Asia to the east ...

instigated a formalist movement called Hilbert’s program as a proposed solution to the

foundational crisis of mathematics Foundations of mathematics are the logical and mathematical framework that allows the development of mathematics without generating self-contradictory theories, and to have reliable concepts of theorems, proofs, algorithms, etc. in particul ...

, that was eventually tempered by

Gödel's incompleteness theorems Gödel's incompleteness theorems are two theorems of mathematical logic that are concerned with the limits of in formal axiomatic theories. These results, published by Kurt Gödel in 1931, are important both in mathematical logic and in the phi ...

. The QED manifesto represented a subsequent, as yet unsuccessful, effort at formalization of known mathematics.

References

Sources

System A system is a group of interacting or interrelated elements that act according to a set of rules to form a unified whole. A system, surrounded and influenced by its open system (systems theory), environment, is described by its boundaries, str ...

1st-millennium BC introductions