He also relates these issues to Christian philosophy, which I find very interesting. In particular, he claims that the a priori belief in the objects defined by Peano Arithmetic, is equivalent to worshipping numbers, as the Pythagoreans did.
I think this is the best starting point if you're interested in reading about his ideas: https://web.math.princeton.edu/~nelson/papers/warn.pdf
http://en.wikipedia.org/wiki/G%C3%B6del's_incompleteness_the...
Most of us take some axioms and believe them, ultimately because they correspond to physical experience - if you take a pile of n pebbles and add another pebble to the pile, you get a pile of n+1 pebbles, and n+1 is always a new number that doesn't =0 (that is, our pile looks different from a pile of 0 pebbles). Maybe there's some (very large) special n where this wouldn't happen - where you'd add 1 and get a pile of 0 pebbles, or where you can have n pebbles but you can't have n sheep. But so far we haven't found that. So far the universe remains simple, and the axioms of arithmetic are simpler than conceivable alternatives.