“Gödel's β function”的意思、由来-开放百科全书

词条

Gödel's β function

释义

Definition
Properties
The β lemma
See also
References

In mathematical logic, Gödel's β function is a function used to permit quantification over finite sequences of natural numbers in formal theories of arithmetic. The β function is used, in particular, in showing that the class of arithmetically definable functions is closed under primitive recursion, and therefore includes all primitive recursive functions.

Definition

The function takes three natural numbers as arguments. It is defined as

where denotes the remainder after integer division of by (Mendelson 1997:186).

Properties

The β function is arithmetically definable in an obvious way, because it uses only arithmetic operations and the remainder function which is arithmetically definable. It is therefore representable in Robinson arithmetic and stronger theories such as Peano arithmetic. By fixing the first two arguments appropriately, one can arrange that the values obtained by varying the final argument from 0 to n run through any specified n + 1-tuple of natural numbers (the β lemma described in detail below). This allows simulating the quantification over sequences of natural numbers of arbitrary length, which cannot be done directly in the language of arithmetic, by quantification over just two numbers, to be used as the first two arguments of the β function.

Concretely, if f is a function defined by primitive recursion on a parameter n, say by f(0) = c and f(n+1) = g(n,f(n)), then to express f(n)= y one would like to say: there exists a sequence a₀, a₁, …, a_n such that a₀= c, a_n = y and for all i < n one has g(i,a_i)=a_i+1. While that is not possible directly, one can say instead: there exist natural numbers a, b such that β(a,b,0) = c, β(a,b,n)=y and for all i < n one has g(i,β(a,b,i)) = β(a,b,i+1).

The β lemma

The utility of the β function comes from the following result (Mendelson 1997:186), which is also due to Gödel.

The β Lemma. For any sequence of natural numbers (k₀, k₁, …, k_n), there are natural numbers b and c such that, for every i ≤ n, β(b, c, i) = k_i.

This follows from the Chinese remainder theorem.

References

{{cite book

|author=Elliott Mendelson
|year=1997
|title=Introduction to Mathematical Logic
|edition=4th
|publisher=CRC Press
|isbn=0-412-80830-7
}}

{{cite book

|author=Wolfgang Rautenberg
|doi=10.1007/978-1-4419-1221-3
|title=A Concise Introduction to Mathematical Logic
|page=244
|url=http://www.springerlink.com/content/978-1-4419-1220-6/
|publisher=Springer Science+Business Media
|location=New York
|edition=3rd
|isbn=978-1-4419-1220-6
|year=2010
}}{{DEFAULTSORT:Godel's B Function}}

1 : Mathematical logic

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

Definition

Properties

The β lemma

See also

References