Hilbert’s $\epsilon$-operator

Abstract

Hilbert’s $\epsilon$-operator is a function introduced in the formal system of Hilbert and Bernays Grundlagen der Matematik, the purpose of which is a reformulation of classical predicate calculus.

In particular, it allows the elimination of Russell’s $\iota$-terms and of the usual symbols for quantification.

It is usually referred to as a "choice function" or a "choice operator" due to its kinship with the axiom of choice.

1 Background, definitions and notation

In a first order theory with equality, whose domain is for example the set of positive integers, an object of the domain can be represented by a name, like "2", or by a complex expression, like "the positive square root of 4", in which case the number 2 is not even explicitly used.

The interesting difference between the two representations consists in the fact that the complex expression makes it possible to refer to an object with a certain property, even in the absence of the object’s name.

The first systematic study of this fundamental logical process was done by Bertrand Russell in Principia Mathematica and in Introduction to mathematical philosophy, where Russell proposed to call descriptions all expressions of the general form

"the object $x$ such that $F(x)$".

In Introduction to mathematical philosophy Russell makes a distinction between definite and indefinite descriptions. These have the general form

"an object $x$ such that $F(x)$".

This distinction did not find much echo in his subsequent logical theory, where the main focus became rather the development of a theory of definite descriptions.

Thus where a name is an arbitrary symbol assigned to an object of the domain, and one then says that the object is the denotation of the name, in contrast a description is a condition which applies to any object of the domain that satisfies it. In a definite description the object is characterized by the fact that a certain predicate is uniquely satisfied by the object.

The condition that a certain predicate $F(a)$ is satisfied by a unique object $a$ is represented in the so called uniqueness formulas for $F(a)$ with the following configuration:

$$(\exists x)F(x)$$

$$(\forall x)(\forall y)[F(x)\wedge F(y)]\to (x=y).$$

The extension of the predicate $F(a)$ determines the object that uniquely satisfies $F$ and for that reason the argument of the predicate plays the role of a bound variable.

In Principia Mathematica the notation introduced for the definite description is a functional variable, known as the description operator. It is build by the small Greek letter $\iota$ with $x$ as an index, followed by the predicate to which the operator is applied:

${\iota }_{x}F(x).$

It is to such an expression that Russell calls a description.

2 Syntax

In relation to syntax it is to be noticed that a description may have an occurrence in an argument position. This then gives rise to a formula like

$$B[{\iota }_{x}F(x)]$$

the interpretation of which is the statement

"there is a unique object which satisfies $F(a)$ and also satisfies $B(a)$".

If the conditions stipulated by the uniqueness formulas are not satisfied, in propositions like for example "the smallest complex number is prime", the description "the smallest complex number" is said to be empty and the proposition in which it occurs is false.

Notice that the interpretation of the formula

$$B[{\iota }_{x}F(x)]$$

is not an explicit definition of the description

$${\iota }_{x}F(x),$$

since for this symbol we do not have a defining expression. What we have is a semantic characterization of the formulas in which the description occurs as one of its constituent parts, as a term.

If there is a derivation of the uniqueness formulas for $F(a)$ then the symbol

$${\iota }_{x}F(x)$$

is a term, in particular the term representing the unique object that satisfies $F(a)$.

The $\iota$-operator is subject to the so called $\iota$-Rule with the following content:

If the uniqueness formulas for $F\mathit{}\mathrm{(}a\mathrm{)}$ have been derived then the description ${\iota }_x\mathit{}F\mathit{}\mathrm{(}x\mathrm{)}$ is a term and the formula

$$F[{\iota }_{x}F(x)]$$

can now be derived by means of the following scheme:
                $(\exists x)F(x)$
                $(\forall x)(\forall y)[F(x)\wedge F(y)]\to (x=y)$
                
                $\therefore F[{\iota }_{x}F(x)]$

The rule of the redenomination of bound variables for quantifiers can be applied to the bound variable of the $\iota$-operator. Likewise the collision of bound variables, that one has to prevent when using quantifiers, has also to be prevented also with the use of the $\iota$-operator.

3 Hilbert’s epsilon-axiom

On the face of it it would seem that the introduction of $\iota$-terms and of the $\iota$-Rule would allow the derivation of new formulas. But one can prove that if a formula $A$ of the first order predicate calculus with equality, with 0-occurences of $\iota$-terms, is derivable by means of the $\iota$-operator and the $\iota$-Rule, then $A$ can also be derived without the use of the $\iota$-operator.

Other than the formal eliminability of the $\iota$-operator, Hilbert also adopted the introduction of a symbol which secures the eliminability of the $\iota$-operator.

The basic idea is the following:

the descriptive term

$${\iota }_{x}A(x)$$

formally represents the statement

"the object $x$ which has the property $A$".

As we have seen above this term can only be formally introduced after the derivation of the uniqueness formulas.

Hilbert proves that these formulas can be dispensed with and the $\iota$-operator be replaced by his $\epsilon$-operator.

The introduction of this operator is to be controlled by conditions that specify:

1. Which are the well formed formulas in which the operator is going to occur;

2. How the underlying logic is going to be adjusted;

3. They give an axiom that defines the use of $\epsilon$.

In particular, let us assume that $A(x)$ is a formula in which $x$ has a free occurrence. We can then build a term of the form

$${\epsilon }_{x}A(x)$$

where the occurrence of $x$ is now bound.

If a term built with the $\iota$-operator can be interpreted as a definite description, the term built with $\epsilon$ can be interpreted as an indefinite description.

So if there is at least a value $k$ such that $A(k)$ is satisfied, then the term

$${\epsilon }_{x}A(x)$$

denotes an object, without further specifications, which satisfies $A$. If there is no such $k$ such that

$${\epsilon }_{x}A(x)$$

then we let the term denote an arbitrary value. This already implies that the formula

$$(\exists x)A(x)\to A[{\epsilon }_{x}A(x)]$$

is true.

The fundamental axiom is the following:

Axiom $\epsilon$: If $F$ is a predicate with a free occurrence of $y$, then

($\star$)     $F(y)\to F[{\epsilon }_{x}F(x)]$.

4 The axiom of choice

It was already pointed out that the variable $x$ of the $\epsilon$-term is a bound variable and that the redenomination rule for bound variables can be applied.

The formula $A(x)$ to which the $\epsilon$-operator is attached as a prefix may contain variables, free or bound by $\forall$, $\exists$, $\iota$ or $\epsilon$. In that case the formal definition of the $\epsilon$-term can not give rise to the collision of bound variables.

For Hilbert’s new symbol the name "choice operator" has been suggested, due to the obvious analogy between the $\epsilon$-axiom and the axiom of choice.

To develop the analogy, let us suppose that

$$\{M_i\}$$

denotes a set of disjoint non-empty sets $M_i$ (with $i\in I$). Now the axiom of choice secures the existence of a function which chooses from each set $M_i$ an element $m_i\in M_i$, the representative element of $M_i$.

Hilbert’s $\epsilon$-operator works like such a function, since the term

$${\epsilon }_x(x\in M_i)$$

in the usual interpretation represents a chosen element $m_i$ from $M_i$.

Thus if we have the following:

1. $A(a,\mathrm{\dots },k,x)$

   is a formula in which $a,\mathrm{\dots },k,x$ are the only free variables, and

2. A relation which maps every set of elements $a,\mathrm{\dots },k$ to at least an element $m$ such that

   $$A(a,\mathrm{\dots },k,m),$$

   then

   $${\epsilon }_{x}A(a,\mathrm{\dots },k,x)$$

   is a function which maps every set of values of the arguments $a,\mathrm{\dots },k$ to a unique value $x$.

To sober up the analogy a little, it is to be noticed that Hilbert intended the choice function to have a finitistic meaning and accordingly to perform only a finite number of choices of one element at a time. In contrast the real choice function of the axiom of choice performs an infinite number of simultaneous choices.

5 The elimination of descriptions and quantifiers

We sketch now some of the best known properties of the $\epsilon$-operator.

1. Descriptions

   If for a formula $A(x)$ it is at all possible to introduce the

   $\iota$-operator

   then

   $${\iota }_{x}A(x)={\epsilon }_{x}A(x).$$

   The argument is the following:

   • i) If the $\iota$-operator can be introduced then one has the term

     $$A[{\iota }_{x}A(x)].$$

   • ii) In the formula ($\star$), Hilbert’s axiom, we insert $A$ for $F$ and the descriptive term ${\iota }_{x}A(x)$ for $y$ and we obtain the formula

     $$A[{\iota }_{x}A(x)]\to A[{\epsilon }_{x}A(x)].$$

   • iii) By i) and modus ponens one has then

     $$A[{\epsilon }_{x}A(x)].$$

   • iv) This shows that if the descriptive term can be introduced then the $\epsilon$-term satisfies the same predicate $A$ and therefore that

     $${\iota }_{x}A(x)={\epsilon }_{x}A(x).$$

2. Quantifiers

   • i) Existence

     If we start with the $\epsilon$-axiom

     $$F(y)\to F[{\epsilon }_{x}F(x)]$$

     then by $\exists$-introduction we obtain

     $$(\exists x)F(x)\to F[{\epsilon }_{x}F(x)].$$

     Existential Generalization gives the formula

     $$F(y)\to (\exists x)F(x)$$

     and by inserting the $\epsilon$-term for $y$ we get

     $$F[{\epsilon }_{x}F(x)]\to (\exists x)F(x).$$

     This shows that

     $$(\exists x)F(x)\leftrightarrow F[{\epsilon }_{x}F(x)].$$

   • ii) Generality

     We use as starting formula

     $$(\exists x)F(x)\leftrightarrow F[{\epsilon }_{x}F(x)].$$

     The rule of insertion allows the reformulation

     $$(\exists x)\sim F(x)\leftrightarrow \sim F[{\epsilon }_x\sim F(x)].$$

     The propositional tautology

     $$(X\leftrightarrow Y)\to (\sim X\leftrightarrow \sim Y)$$

     gives the formula

     $$\sim (\exists x)\sim F(x)\leftrightarrow \sim \sim F[{\epsilon }_x\sim F(x)].$$

     From predicate calculus we get

     $$(\forall x)F(x)\leftrightarrow \sim \sim F[{\epsilon }_x\sim F(x)].$$

   • iii) Dictum de Omni

     The same kind of argument allows the derivation of dictum de omni.

     To prove

     $$(\forall x)F(x)\to F(y)$$

     we start with the $\epsilon$-axiom

     $$F(y)\to F[{\epsilon }_{x}F(x)]$$

     and by the rule of insertion we get

     $$\sim F(y)\to \sim F[{\epsilon }_x\sim F(x)].$$

     The propositional tautology

     $$(X\to Y)\leftrightarrow (\sim Y\to \sim X)$$

     gives the formula

     $$\sim \sim F[{\epsilon }_x\sim F(x)]\to \sim \sim F(y).$$

     But by Part ii) above this is

     $$(\forall x)F(x)\to \sim \sim F(y).$$

     Double negation gives

     $$(\forall x)F(x)\to F(y)$$

     as desired.

Title	Hilbert’s $\epsilon$-operator
Canonical name	Hilbertsvarepsilonoperator
Date of creation	2013-03-22 18:39:18
Last modified on	2013-03-22 18:39:18
Owner	gribskoff (21395)
Last modified by	gribskoff (21395)
Numerical id	8
Author	gribskoff (21395)
Entry type	Definition
Classification	msc 03E30
Classification	msc 03E25
Classification	msc 03B10
Classification	msc 03-01
Synonym	choice function
Synonym	choice operator
Related topic	AnOutlineOfHilbertsProgramme
Related topic	FOUNDATIONSOFMATHEMATICSOVERVIEW
Related topic	AxiomOfChoice
Related topic	RussellsTheoryOfTypes
Defines	Hilbert’s epsilon-operator