Peano Arithmetic Represents All Computable Functions

-
This is a document I wrote some time back proving the classical result that any µ-recursive function is representable in Peano arithmetic (PA). You can think of this result as saying that anything that can be computed, can be computed using just PA. 
This fact is crucial for proving the diagonal lemma which itself is an essential part of the proof of Gödel's first incompleteness theorem.
I should note that there are some typos in the text.
 

Comments

Post a Comment

Popular posts from this blog

Stop proving uncountability by contradiction, please

-
Image
 If you've seen any amount of pop-math content, you've probably seen a theorem along the lines of the following: Theorem  (Cantor): There are just as many natural numbers as integers and as rational numbers, but there are more real numbers.   I don't have a problem with the above result, since it is true. However, I have a bone to pick with the way the proof is often represented in pop-math videos. For the first part (that the cardinalities of N , Z and Q are all equal), the way it is usually represented is good. For the integers there is the reasonably easy bijection: 0, 1, -1, 2, -2, 3, ... which can in fact be given by the explicit formula where ⌈ x ⌉ means "round x up to the nearest integer". For the rational numbers there are a few ways, the most common one using the zig-zag method. Sure, there are more elegant methods that give an immediate bijection and don't require skipping numbers that already appeared in the list. However, for the purpose of intro...
Read more