Difference between revisions of "Formal systems, equivalence of"
From Encyclopedia of Mathematics
(TeX done) |
m (category) |
||
| Line 1: | Line 1: | ||
Two [[formal system]]s 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. | Two [[formal system]]s 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. | ||
| + | |||
| + | {{TEX|done}} | ||
Latest revision as of 20:17, 13 May 2017
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=41452
Formal systems, equivalence of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Formal_systems,_equivalence_of&oldid=41452
This article was adapted from an original article by V.E. Plisko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article