Talk:Gödel's β function

Falsche rem-Funktion

Ich habe die Defintion von $rem(x,y)$ mal angepasst. Es muss Rest bei $y/x$ sein, anstatt $x/y$.

Im Beweis in Mendelson werden $u_{i}$ konstruiert, sodass $rem(u_{i},b)=k_{i}$ sein soll. Das $b$ soll es nach Chinesischem Restsatz geben. Dort sind die Moduln jedoch eben die $u_{i}$, sodass in $rem$ "durch sie geteilt" werden muss. —Preceding unsigned comment added by 88.74.91.131 (talk) 07:57, 6 August 2010 (UTC)

Danke. You're right that the variables were backwards. — Carl (CBM · talk) 13:23, 6 August 2010 (UTC)

Origin of the β function and lemma

Neither the β function nor the β lemma are mentioned in Gödel's incompleteness article:

Kurt Gödel: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, Monatsheft für Mathematik und Physik, volume 38, pages 173-198, 1931

An English transaltion is given in

Solomon Feferman, John W. Dawson, Jr., Stephen C. Kleene, Gregory H. Moore, Robert M. Solovay, and Jean van Heijenoort, editors: Kurt Gödel - Collected Works, Oxford, UK, and New York, USA, pages 144-194

I believed the following: We can therefore safely assume that the β function nor the β lemma have been devised by Elliott Mendelson for his treatment of Gödel's First Incompeteness Theorem. Indeed, that function and lemma are used in Mendelson's book for a complete proof of definability which is not given (but only sehr briefly sketched) in Gödel's incompleteness article.

This was not ccorrect: the β function has been introduiced wirthout its name in Gödel's incomleterness article of 1931. Gödel gaver the function its name in 1934 a talk.

I added the information corresponding references. In my opinion, the issue is resolved.

The remainder function definable in Q

The article currently claims "the remainder function ... is arithmetically definable", and then follows this up with mention of Robinson Arithmetic (usually denoted "Q"). It's not obvious that $rem$ is definable in Q! So at the very least, I think a citation would be in order, or an explanation why 220.244.237.15 (talk) 09:22, 8 May 2022 (UTC)

Since Robinson arithmetic admits multiplication, my first guess for a definition of rem would be $z=rem(x,y)\;\;{\stackrel {def}{\Longleftrightarrow }}\;\;(\exists d.z+d=y)\land (\exists q.q\cdot y+z=x)$. - Jochen Burghardt (talk) 18:02, 9 May 2022 (UTC)

New section Elimination of Parameters

I made a new section "All primitive recursive functions".

I move the section Elimination of Parameters from there:

https://en.wikipedia.org/wiki/Primitive_recursive_function

To this article here. Jan Burse (talk) 00:12, 29 February 2024 (UTC)