Encyclosphere.org ENCYCLOREADER
  supported by EncyclosphereKSF

Formal systems, equivalence of

From Encyclopedia of Mathematics - Reading time: 1 min


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) | Licensed under CC BY-SA 3.0. Source: https://encyclopediaofmath.org/wiki/Formal_systems,_equivalence_of
12 views |
↧ Download this article as ZWI file
Encyclosphere.org EncycloReader is supported by the EncyclosphereKSF