Formal systems, equivalence of
From Encyclopedia of Mathematics
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
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