↑ arvau

Wikipedia / Extension by definition

In mathematical logic, more specifically in the proof theory of first-order theories, an extension by definition formalizes the introduction of a new symbol by means of a definition. For example, it is common in naive set theory for the set and the new axiom, meaning "for all x, x". 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.

Definition of relation symbols

Let be a first-order theory a formula are distinct and include the variables free, the logical axioms and the new axiom

  1. ,

called the defining axiom.

(changing the bound variables). Then the following hold:

  1. , and

  2. is a conservative extension.

is called a translation has been eliminated.

Definition of function symbols

be a first-order theory (with equality. Assume that we can prove

, there exists a unique y-ary function symbol and the new axiom

  1. ,

called the defining axiom.

be

. Then the following hold:

  1. , and

  2. is a conservative extension.

is called a translation has been eliminated.

The construction of this paragraph also works for constants, which can be viewed as 0-ary function symbols.

Extensions by definitions

by successive introductions of relation symbols and function symbols as above is called an extension by definitions, called a translation. Such a formula is not unique, but any two of them can be proved to be equivalent in T.

of T is not distinguished from the original theory T can be thought of as abbreviating their translations into T. The manipulation of these abbreviations as actual formulas is then justified by the fact that extensions by definitions are conservative.

Examples

  • Traditionally, the first-order set theory ZF, the unary function symbol P (the power set operation), etc. All of these symbols belong in fact to extensions by definitions of ZF.

  • be a first-order theory for groups in which the only primitive symbol is the binary product ×. In T, we can prove that there exists a unique element y such that x×y= y×x= x for every x. Therefore, we can add to T a new constant e and the axiom

    1. ,

    we can prove that for every x, there exists a unique y such that x×y= y×x= e and the axiom

  • .

See also

Bibliography

  • S. C. Kleene (1952), Introduction to Metamathematics, D. Van Nostrand

  • E. Mendelson (1997). Introduction to Mathematical Logic (4th ed.), Chapman & Hall.

  • J. R. Shoenfield (1967). Mathematical Logic, Addison-Wesley Publishing Company (reprinted in 2001 by AK Peters)