In
mathematical logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal sy ...
, more specifically in the
proof theory
Proof theory is a major branchAccording to Wang (1981), pp. 3–4, proof theory is one of four domains mathematical logic, together with model theory, axiomatic set theory, and recursion theory. Barwise (1978) consists of four corresponding parts, ...
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
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concer ...
to introduce a symbol
for the
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
which 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
An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that which is thought worthy or f ...
, 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 In mathematical logic, a conservative extension is a supertheory of a theory which is often convenient for proving theorems, but proves no new theorems about the language of the original theory. Similarly, a non-conservative extension is a superthe ...
of the old one.
Definition of relation symbols
''Let''
be a
first-order theory
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
and
a
formula
In science, a formula is a concise way of expressing information symbolically, as in a mathematical formula or a ''chemical formula''. The informal use of the term ''formula'' in science refers to the general construct of a relationship betwe ...
of
such that
, ...,
are distinct and include the variables
free
Free may refer to:
Concept
* Freedom, having the ability to do something, without having to obey anyone/anything
* Freethought, a position that beliefs should be formed only on the basis of logic, reason, and empiricism
* Emancipate, to procure ...
in
. Form a new first-order theory
from
by adding a new
-ary relation symbol
, the
logical axiom
An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that which is thought worthy or ...
s 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 variable
In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a free variable is a notation (symbol) that specifies places in an expression where substitution may take place and is not ...
s 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 In mathematical logic, a conservative extension is a supertheory of a theory which is often convenient for proving theorems, but proves no new theorems about the language of the original theory. Similarly, a non-conservative extension is a superthe ...
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.
Definition of function symbols
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
. Then since
occurs in
one less time than in
, the formula
has already been defined, and we let
be
:
(changing the bound variables in
if necessary so that the variables occurring in the
are not bound in
). For a general formula
, the formula
is formed by replacing every occurrence of an atomic subformula
by
. Then the following hold:
#
is provable in
, and
#
is a
conservative extension In mathematical logic, a conservative extension is a supertheory of a theory which is often convenient for proving theorems, but proves no new theorems about the language of the original theory. Similarly, a non-conservative extension is a superthe ...
of
.
The formula
is called a ''translation'' of
into
. As in the case of relation symbols, the formula
has the same meaning as
, but the new symbol
has been eliminated.
The construction of this paragraph also works for constants, which can be viewed as 0-ary function symbols.
Extensions by definitions
A first-order theory
obtained from
by successive introductions of relation symbols and function symbols as above is called an extension by definitions of
. Then
is a conservative extension of
, and for any formula
of
we can form a formula
of
, called a ''translation'' of
into
, such that
is provable in
. Such a formula is not unique, but any two of them can be proved to be equivalent in ''T''.
In practice, an extension by definitions
of ''T'' is not distinguished from the original theory ''T''. In fact, the formulas of
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 has
(equality) and
(membership) as its only primitive relation symbols, and no function symbols. In everyday mathematics, however, many other symbols are used such as the binary relation symbol
, the constant
, the unary function symbol ''P'' (the
power set
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is p ...
operation), etc. All of these symbols belong in fact to extensions by definitions of ZF.
* Let
be a first-order theory for
groups
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
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
::
,
:and what we obtain is an extension by definitions
of
. Then in
we can prove that for every ''x'', there exists a unique ''y'' such that ''x''×''y''=''y''×''x''=''e''. Consequently, the first-order theory
obtained from
by adding a unary function symbol
and the axiom
::
:is an extension by definitions of
. Usually,
is denoted
.
See also
*
Conservative extension In mathematical logic, a conservative extension is a supertheory of a theory which is often convenient for proving theorems, but proves no new theorems about the language of the original theory. Similarly, a non-conservative extension is a superthe ...
*
Extension by new constant and function names
In mathematical logic, a theory can be extended with
new constants or function names under certain conditions with assurance that the extension will introduce
no contradiction. Extension by definitions is perhaps the best-known approach, but it req ...
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)
{{Mathematical logic
Mathematical logic
Proof theory