How is first-order logic derived from the natural numbers? I've heard that first-order logic comes from Peano Arithmetic, yet I can't see how.
We don't need numbers to formulate quantifiers, variables, functions, constants, relations or even sets.
Insted, it is possible to formulate all Peano's axioms using first-order logic and sets, as one can see here http://de.wikipedia.org/wiki/Peano-Axiome, below the header "Ursprüngliche Formalisierung".
So, how is first-order logic generated from the natural numbers? Does it have anything to do with Primitive Recursive Arithmetic?

To add to HTFB's excellent answer above, I'd only add a few small points:


*

*Though Frege was first with the invention of quantifiers, he appears to have been overlooked at the time; it was Peirce's subsequent independent reinvention that spread. Consequently the notation we use is more similar to Peirce's than to Frege's two-dimensional notation (though we owe the "turnstile" notation for entailment to Frege). This random web page claims the $\in$ notation was introduced by Peano in 1889, as an abbreviation of "est".

*In retrospect, it's perhaps unsurprising that Frege ran into set-comprehension problems; his 1884 (non-rigorous) book The Foundations of Arithmetic is breathtakingly cavalier about such issues. He defines the number 3 as the collection of all collections with three elements - every triple of boots, telephones, planets, emotions, numbers...

*The formalization of arithmetic induction had been going on for a while before Peano; according to his Wikipedia page De Morgan made great strides here.
