Automated Mathematician tried to explore mathematics and find interesting concepts the same way mathematicians do and using similar heuristics. And it got fairly far, discovering numbers and primes and Goldbach's conjecture. But eventually it just started discovering useless concepts which had no apparent relevance to anything and were pointlessly complex or specific.
But really the process is reversed: given arithmetic, what is the smallest axiom set to give us the power to prove our theorems.
It's like, given all code, what is the smallest language we can use to express it. Which is sequences of 0s and 1s.
This should be of interest: https://en.wikipedia.org/wiki/Binary_lambda_calculus
Also, there are easily understandable theorems about the natural numbers not provable from the Peano axioms.
I'm familiar with the distinction between formalism and Platonism, although I still haven't made my mind up yet :)
Gödel's first incompleteness theorem [1] states this fact, that no theory above a certain expressiveness (read as can express natural numbers with addition and multiplication) can be consistent and complete. Assuming Peano arithmetic is consistent, it can not be complete and complete means you can prove all true facts expressible in the system within the system itself.
The (standard) proof of Goodstein's theorem uses ordinal numbers [2] which are outside of Peano arithmetic and the Kirby–Paris theorem proves that there is no proof inside Peano arithmetic [3].
[1] http://en.wikipedia.org/wiki/G%C3%B6dels_incompleteness_theo...
[2] http://en.wikipedia.org/wiki/Ordinal_number
[3] http://en.wikipedia.org/wiki/Goodsteins_theorem#Proof_of_Goo...
[1] https://en.wikipedia.org/wiki/Peano_axioms