Expressiveness of Peano Arithmetic

• Unproven claim: Peano arithmetic is powerful enough to do primitive recursion.
• I.e., algorithms that have simple “for loops”
• PA can be used to “code” numeric operations on
• formulas-as-numbers