Gracias por aclararlo. 
A mandar.
Que n + 0 = n lo pruebo por inducción, pero no por "intuición".
No, creo que aquí te has liado un poco. Quiero decir que no es ésa la respuesta que correspondería a tu punto de vista (o eso creo, salvo que me sorprendas). Si hablamos de ZF, entonces \( n+0=n \) forma parte de la definición de suma, es decir, demuestras el teorema de recursión y defines la suma como la única aplicación que cumple eso y \( n+m'=(n+m)' \), y entonces no puedes demostrar por inducción la definición de suma.
En AP es parecido pero no igual. No tienes teorema de recursión, sino que directamente tienes un signo + no definido y tomas como axioma las dos afirmaciones que definen la suma, luego ni en AP ni en ZF tiene sentido demostrar n+0=n por inducción.
Pero es que aquí la cuestión no es definir la suma, sino demostrar que \( n+0=n \) es verdadero cuando \( + \) se interpreta como la suma usual. Al final, lo que queremos es demostrar que unos axiomas (entre ellos los que definen la suma) son consistentes, y el argumento que lo prueba es que esos axiomas pueden interpretarse en términos de algo que sabemos hacer, de modo que si esos axiomas fueran contradictorios podríamos razonar que lo que hacermos cuando sumanos 2+2 debería darnos 5, cuando podemos comprobar que nos da 4. Si te quedas en el terreno de los axiomas, no llegas a ningún sitio. Tal y como lo pretendes enfocar, el argumento se queda en que AP es consistente si y sólo si AP es consistente, pero es que estás "olvidando" que AP no son sólo unas fórmulas (unos axiomas), sino unas fórmulas que sabemos interpretar, y al interpretarlas resultan ser todas verdaderas.
La intuición "me inspira" el teorema que luego sale por inducción.
No. Ahí estás usando la palabra "intuición" en el sentido coloquial, que no tiene nada que ver con el sentido técnico. No digo más con la esperanza de que me aceptes que la inducción no viene al caso justo en este contexto.
Pero sin un axioma de inducción escrito formalmente y explícitamente estipulado, me cuesta creer en la validez de los números "intuitivos". 
Pero la cuestión es que si quieres demostrar que AP es consistente, no puedes limitarte a decir "acepto un axioma de inducción", sino que tienes que darte cuenta de que ese axioma de inducción significa algo, y además es verdadero. Y no puedes demostrar por inducción que el principio de inducción es verdadero.

En cuanto al lenguaje C... creo que tengo una "intuición" de programador antes que una de matemático.
Vuelves a usar intuición en el sentido coloquial. No me refería a cómo se te ocurre que la mejor forma de programar algo es así o asá (ahí podrías decir que lo sabes por "intuición" de programador). Yo me refería a cómo te convences de que un algoritmo programado hace lo que pretendes que haga y no otra cosa (al margen de que al final siempre hay "bugs" y nunca está uno seguro hasta que no se prueba varias veces y todo parece ir bien). Creo que caes en un círculo vicioso (o, mejor, en un "descenso infinito") si me dices que cuando te dan un trozo de código (relativamente simple) y lo analizas hasta deducir, por ejemplo, que lo que hace es probar si un número dado es par o impar, estás demostrando algo formalmente, porque, al fin y al cabo, cuando tomas una demostración formal y analizas si es correcta o tiene algún fallo, estás aplicando un proceso similar al que aplicas cuando revisas un algoritmo, y si ese proceso fuera un argumento formal, necesitarías también un proceso para comprobar que la comprobación es correcta, y así hasta el infinito, pero no. Cuando compruebas si un algoritmo va a hacer esto o lo otro, no estás escribiendo una demostración matemática que a su vez debas comprobar. Estás razonando a partir de conceptos intuitivos como "variable", "for", "if", que tienen un significado intuitivo, un significado en términos de acciones que hará el ordenador, y las acciones no son teoremas.
La matemática se escribe con caracteres, una string. Las operaciones aritméticas pueden definirse en forma explícita y mecánica con manipulaciones de caracteres, o de bits.
Sí, pero las manipulaciones no son strings, y esto no es una observación puñetera, sino algo esencial que desarbola tu intento de reducirlo todo a strings. Si usas strings para especificar las manipulaciones válidas de strings, caes en otro descenso infinito.
No hace falta "intuir" nada, del mismo modo que uno no es capaz de "intuir" las reglas del ajedrez, sino que las especifica explícitamente.
El ajedrez (como los números naturales) se puede formalizar, por supuesto, pero no necesitas un formalismo para jugar al ajedrez. Puedes entender que "mover ficha" significa "mover" en el sentido intuitivo de la palabra, de "cambiar la posición en el espacio de la ficha" (desde una casilla hasta otra del tablero, o sacándola del tablero).
En realidad pareciera que los números "intuitivos" no pueden abarcarse por ningún sistema axiomático.
Con lo cual, muchos teoremas quedan "indecidibles".
Según entiendo el teorema de incompletitud de Godel, dice que ninguna teoría formal puede demostrar todos los teoremas de los números naturales "intuitivos".
Cierto. El conjunto de las afirmaciones aritméticas verdaderas no es recursivo, ni recursivamente numerable (es decir, no puedes programar a un ordenador para que vaya enumerando fórmulas aritméticas de modo que todas las que produzca sean verdaderas y toda fórmula verdadera termine saliendo, tarde o temprano, en la lista.
¿Pero todo es verdadero o falso en el N intuitivo? ¿O hay afirmaciones indecidibles?
Je, je. La forma en que lo preguntas parece sugerir que planteas dos alternativas opuestas, pero no. La respuesta es afirmativa a las dos preguntas. Hay afirmaciones indecidibles. Por ejemplo, la consistencia de ZFC es equivalente a una afirmación sobre números naturales (si quieres, a una afirmación de la forma existen números \( x_1,\ldots, x_{13} \) tales que \( P(x_1,\ldots, x_{13}) = Q(x_1,\ldots, x_{13}) \), donde P y Q son polinomios con coeficientes naturales (si admites coeficientes enteros puedes despejar y quedarte con sólo un polinomio). Pues esa afirmación es indecidible, pero seguro que es verdadera o es falsa. O existen esos trece números, o alguien puede escribir trece números en un papel (quepa o no en nuestro universo), evaluar los dos polinomios en esos trece números y obtener el mismo resultado, o eso es imposible. La afirmación es verdadera o falsa con absoluta independencia de que exista un argumento que lo demuestre (que no lo hay).
Esto que estoy diciendo no tendría sentido alguno si AP fuera sólo "strings". Esto que estoy diciendo no tiene sentido alguno si cambio AP por ZFC y la ecuación diofántica por la hipótesis del continuo. Ahora no hay ningún sentido que yo conozca en el cual se pueda decir que "en verdad" HC es verdadera o falsa. Lo que distingue AP de ZFC en este sentido es precisamente que AP tiene un contenido intuitivo concreto y objetivo, y ZFC no.
¿O ciertas afirmaciones del N intuitivo se vuelven verdaderas sólo porque sí, desde que a alguien les parecieron intuitivamente ciertas?
No. La consistencia de ZFC (vista como afirmación del N intuitivo) no se sabe si es verdadera o falsa. Nadie ha dicho "me parece intuitivamente cierta". Pero lo que podemos decir es que, como tiene un significado intuitivo preciso (o alguien puede escribir los trece dichosos números adecuados o es inútil buscarlos porque no los hay) podemos decir que es verdadera o falsa.
En teoría puedes programar en C un ordenador para que vaya enumerando todos los teoremas de ZFC y se pare si encuentra como teorema \( 2+2=5 \). Por mucho que examines tu algoritmo, no podrás razonar si el programa se va a parar o no (haciendo abstracción de limitaciones de memoria), porque eso sería tanto como razonar si ZFC es consistente o no, pero muy radical tendrías que ser para sostener que la afirmación "este programa que tengo aquí explícitamente escrito en C (y que no depende de ningún input) se para en un tiempo finito" no es ni verdadera ni falsa.