In mathematical logic, a formal system is a “set-up” to study the syntactic structures of statements that we see in everyday mathematics. Thus, instead of looking at the meaning of the statement , one looks at the expression made up of symbols , and .
Formally, a formal system consists of the following:
the language of , which is formed by
a set of symbols; finite sequences of these symbols are called words or expressions over ;
a set of rules that specify how these words are generated; the set is called the syntax of the language; typically, the rules are
certain expressions are singled out, which are called atoms, or atomic formulas
a set of rules (inductive in nature) showing how formulas can be formed from other formulas that have already been formed
a deductive system (or proof system) associated with , which consists of
a set of axioms; each axiom is usually (but not always) a formula;
Thus, in a formal system , one starts with a set of symbol. Three sets are associated:
where is the set of all expressions over , is the set of all (well-formed) formulas obtained by a set of formula formation rules, and is the set of all theorems obtained from the formulas by a set of rules of inference.
Here’s an example of a formal system: the (classical) propositional logic . The symbols of consists of
propositional variables are formulas; and
if are formulas, so are
A deduction system for may consist the following:
all formulas of the forms
for all formulas , and
, and the (only) rule of inference is modus ponens: from and , we may infer (or deduce) .
The (classical) first-order logic is another example of a formal system. Group theory, number theory (a la Peano arithmetic), theory of partially ordered sets, and set theory (a la ZFC) are other examples of formal systems that are extensively studied.
Remark. A formal system is sometimes called a logical system, although the latter term usually either refers to a formal system where the deducibility relation arising out of the associated deductive system satisfies certain properties (for example, for all wffs, etc…), or a formal system together with a semantical structure.
- 1 R. M. Smullyan, Theory of Formal Systems, Princeton University Press, 1961
- 2 J. R. Shoenfield, Mathematical Logic, AK Peters, 2001
|Date of creation||2013-03-22 19:12:25|
|Last modified on||2013-03-22 19:12:25|
|Last modified by||CWoo (3771)|