Namespaces
Variants
Actions

Formal systems, equivalence of

From Encyclopedia of Mathematics
Revision as of 20:14, 13 May 2017 by Richard Pinch (talk | contribs) (TeX done)
Jump to: navigation, search

Two formal systems are called equivalent if the sets of expressions that are deducible in these systems are identical. More precisely, two formal systems $S_1$ and $S_2$ are equivalent if and only if the following conditions are satisfied: 1) every axiom of $S_1$ is deducible in $S_2$; 2) every axiom of $S_2$ is deducible in $S_1$; 3) if an expression $B$ follows immediately from expressions $A_1,\ldots,A_n$ by virtue of a derivation rule of $S_1$, and $A_1,\ldots,A_n$ are deducible in $S_2$, then $B$ is also deducible in $S_2$; and 4) the same as 3) with $S_1$ and $S_2$ interchanged.

How to Cite This Entry:
Formal systems, equivalence of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Formal_systems,_equivalence_of&oldid=14205
This article was adapted from an original article by V.E. Plisko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article