# Gödel Without Tears, slowly, 9

Today’s chapter is about ‘Expressing and capturing the primitive recursive functions’. We prove (in reasonable detail) that although the language of basic arithmetic \$latex L_A\$ only has the successor, addition and multiplication functions built in, we can in fact form a \$latex L_A\$ wff to express any primitive recursive function we pick. And then we prove (or rather, wave our arms at a proof) that even the weak Robinson Arithmetic can reprsent or ‘capture’ every primitive recursive function.

Even cutting lots of corners, this chapter is inevitably a bit fiddly. But one nice idea we meet is the use of a coding device for handling finite sequences of numbers. I try to make clear (a) how having such a device will enable us to express/capture primitive recursive functions, while (b) distinguishing the neat general coding idea from Gödel’s particular implementation of the device using his beta function.

[Link now removed]

### 1 thought on “Gödel Without Tears, slowly, 9”

1. p 73, last par of §9.5, “You’ll get a wff captures the function in Q” — missing “that” after “wff”.

Scroll to Top