Gödel's β function: Difference between revisions
Luckas-bot (talk | contribs) m r2.7.1) (robot Adding: es:Función beta de Gödel |
Use the more natural dividend and divisor positions in rem |
||
Line 5: | Line 5: | ||
The β function takes three natural numbers as arguments. It is defined as follows (Mendelson 1997:186): |
The β function takes three natural numbers as arguments. It is defined as follows (Mendelson 1997:186): |
||
:{{nowrap|β(''x''<sub>1</sub>, ''x''<sub>2</sub>, ''x''<sub>3</sub>) {{=}} rem |
:{{nowrap|β(''x''<sub>1</sub>, ''x''<sub>2</sub>, ''x''<sub>3</sub>) {{=}} rem(''x''<sub>1</sub>, 1 + (''x''<sub>3</sub> + 1) · ''x''<sub>2</sub>)}}. |
||
Where rem(''x'', ''y'') denotes the remainder after integer division of ''x'' by ''y''. |
|||
== Properties == |
== Properties == |
Revision as of 23:45, 28 January 2011
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, as a step in the extension of the language of Peano arithmetic to include all primitive recursive functions.
Definition
The β function takes three natural numbers as arguments. It is defined as follows (Mendelson 1997:186):
- β(x1, x2, x3) = rem(x1, 1 + (x3 + 1) · x2).
Where rem(x, y) denotes the remainder after integer division of x by y.
Properties
The β function is a primitive recursive function. It is representable in Robinson arithmetic and stronger theories such as Peano arithmetic.
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 (k0, k1, ..., kn), there are natural numbers b and c such that, for every i ≤ n, β(b, c, i) = ki.
This follows from the Chinese remainder theorem.
See also
References
- Elliott Mendelson (1997). Introduction to Mathematical Logic (4th ed.). CRC Press. ISBN 0-412-80830-7.
External links
- Stephen Simpson, Foundations of Mathematics lecture notes, section 2.2.