Hilbert’s ε-operator

Abstract

Hilbert’s ε-operator is a functionMathworldPlanetmath 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 ι-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 choiceMathworldPlanetmath.


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 differencePlanetmathPlanetmath 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 predicateMathworldPlanetmath 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 formulasMathworldPlanetmathPlanetmath for F(a) with the following configurationPlanetmathPlanetmath:

(x)F(x)
(x)(y)[F(x)F(y)](x=y).

The extensionPlanetmathPlanetmath 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 variableMathworldPlanetmath.

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

ιxF(x).

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

2 Syntax

In relationMathworldPlanetmath 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[ιxF(x)]

the interpretationMathworldPlanetmathPlanetmath 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 propositionsPlanetmathPlanetmathPlanetmath like for example "the smallest complex numberPlanetmathPlanetmath 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[ιxF(x)]

is not an explicit definition of the description

ιxF(x),

since for this symbol we do not have a defining expression. What we have is a semantic characterizationMathworldPlanetmath 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

ιxF(x)

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

The ι-operator is subject to the so called ι-Rule with the following content:

If the uniqueness formulas for F(a) have been derived then the description ιxF(x) is a term and the formula

F[ιxF(x)]

can now be derived by means of the following scheme:
                (x)F(x)
                (x)(y)[F(x)F(y)](x=y)
                
                F[ιxF(x)]

The rule of the redenomination of bound variables for quantifiersMathworldPlanetmath can be applied to the bound variable of the ι-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 ι-operator.

3 Hilbert’s epsilon-axiom

On the face of it it would seem that the introduction of ι-terms and of the ι-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 ι-terms, is derivable by means of the ι-operator and the ι-Rule, then A can also be derived without the use of the ι-operator.

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

The basic idea is the following:

the descriptive term

ιxA(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 ι-operator be replaced by his ε-operator.

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

  1. 1.

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

  2. 2.

    How the underlying logic is going to be adjusted;

  3. 3.

    They give an axiom that defines the use of ε.

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

εxA(x)

where the occurrence of x is now bound.

If a term built with the ι-operator can be interpreted as a definite description, the term built with ε 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

εxA(x)

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

εxA(x)

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

(x)A(x)A[εxA(x)]

is true.

The fundamental axiom is the following:

Axiom ε: If F is a predicate with a free occurrence of y, then

()     F(y)F[εxF(x)].

4 The axiom of choice

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

The formula A(x) to which the ε-operator is attached as a prefix may contain variables, free or bound by , , ι or ε. In that case the formal definition of the ε-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 analogyMathworldPlanetmath between the ε-axiom and the axiom of choice.

To develop the analogy, let us suppose that

{Mi}

denotes a set of disjoint non-empty sets Mi (with iI). Now the axiom of choice secures the existence of a function which chooses from each set Mi an element miMi, the representative element of Mi.

Hilbert’s ε-operator works like such a function, since the term

εx(xMi)

in the usual interpretation represents a chosen element mi from Mi.

Thus if we have the following:

  1. 1.

    A(a,,k,x)

    is a formula in which a,,k,x are the only free variablesMathworldPlanetmath, and

  2. 2.

    A relation which maps every set of elements a,,k to at least an element m such that

    A(a,,k,m),

    then

    εxA(a,,k,x)

    is a function which maps every set of values of the arguments a,,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 infiniteMathworldPlanetmath number of simultaneous choices.

5 The elimination of descriptions and quantifiers

We sketch now some of the best known properties of the ε-operator.

  1. 1.

    Descriptions

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

    ι-operator

    then

    ιxA(x)=εxA(x).

    The argument is the following:

    • i) If the ι-operator can be introduced then one has the term

      A[ιxA(x)].
    • ii) In the formula (), Hilbert’s axiom, we insert A for F and the descriptive term ιxA(x) for y and we obtain the formula

      A[ιxA(x)]A[εxA(x)].
    • iii) By i) and modus ponensMathworldPlanetmath one has then

      A[εxA(x)].
    • iv) This shows that if the descriptive term can be introduced then the ε-term satisfies the same predicate A and therefore that

      ιxA(x)=εxA(x).
  2. 2.

    Quantifiers

    • i) Existence

      If we start with the ε-axiom

      F(y)F[εxF(x)]

      then by -introduction we obtain

      (x)F(x)F[εxF(x)].

      Existential Generalization gives the formula

      F(y)(x)F(x)

      and by inserting the ε-term for y we get

      F[εxF(x)](x)F(x).

      This shows that

      (x)F(x)F[εxF(x)].
    • ii) Generality

      We use as starting formula

      (x)F(x)F[εxF(x)].

      The rule of insertion allows the reformulation

      (x)F(x)F[εxF(x)].

      The propositional tautologyMathworldPlanetmath

      (XY)(XY)

      gives the formula

      (x)F(x)F[εxF(x)].

      From predicate calculus we get

      (x)F(x)F[εxF(x)].
    • iii) Dictum de Omni

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

      To prove

      (x)F(x)F(y)

      we start with the ε-axiom

      F(y)F[εxF(x)]

      and by the rule of insertion we get

      F(y)F[εxF(x)].

      The propositional tautology

      (XY)(YX)

      gives the formula

      F[εxF(x)]F(y).

      But by Part ii) above this is

      (x)F(x)F(y).
      (x)F(x)F(y)

      as desired.

References

  • 1 Fraenkel, A., Foundations of set theoryMathworldPlanetmath, North-Holland, Amsterdam, 1958.
  • 2 Bernays, P., Hilbert, D., Grundlagen der Mathematik, 2. Auflage, Berlin, 1968.
  • 3 Kreisel, G., "Hilbert’s Programme", Dialectica 12, 1958.
  • 4 Russell, B., Whitehead, A., Principia Mathematica, Cambridge, 1910.
Title Hilbert’s ε-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