Extension by definitions

In mathematical logic, more specifically in the proof theory of first-order theories, extensions by definitions formalize the introduction of new symbols by means of a definition. For example, it is common in naive set theory to introduce a symbol for the set that has no member. In the formal setting of first-order theories, this can be done by adding to the theory a new constant and the new axiom , meaning "for all x, x is not a member of ". It can then be proved that doing so adds essentially nothing to the old theory, as should be expected from a definition. More precisely, the new theory is a conservative extension of the old one. Let be a first-order theory and a formula of such that , ..., are distinct and include the variables free in . Form a new first-order theory from by adding a new -ary relation symbol , the logical axioms featuring the symbol and the new axiom called the defining axiom of . If is a formula of , let be the formula of obtained from by replacing any occurrence of by (changing the bound variables in if necessary so that the variables occurring in the are not bound in ). Then the following hold: is provable in , and is a conservative extension of . The fact that is a conservative extension of shows that the defining axiom of cannot be used to prove new theorems. The formula is called a translation of into . Semantically, the formula has the same meaning as , but the defined symbol has been eliminated. Let be a first-order theory (with equality) and a formula of such that , , ..., are distinct and include the variables free in . Assume that we can prove in , i.e. for all , ..., , there exists a unique y such that . Form a new first-order theory from by adding a new -ary function symbol , the logical axioms featuring the symbol and the new axiom called the defining axiom of . Let be any atomic formula of . We define formula of recursively as follows. If the new symbol does not occur in , let be . Otherwise, choose an occurrence of in such that does not occur in the terms , and let be obtained from by replacing that occurrence by a new variable .