Veo que Martiniano ha dado esencialmente el mismo argumento que iba a darte yo, pero lo pongo igualmente:
Decir que "no es intuitivo" que haya el mismo número de números naturales que de números pares es como decir que "no es intuitivo" que si uno juega a la lotería con el número 32711 tiene las mismas probabilidades de ganar que otro que juegue con el número 12345, porque lo "intuitivo" es que 32711 es un número que, podrá ganar o no, pero no sería sorprendente que ganara, mientras que para que pudiera salir ganador el número 12345 tendría que darse una casualidad tan grande que es inimaginable que uno pueda vivir para ver algo así.
En efecto, las dos "verdades intuitivas" se pueden refutar con el mismo argumento (que es el de Martiniano).
En el caso de la lotería, imagina un bombo que contiene 100000 bolas idénticas. Está claro que, si sacamos una al azar, todas tienen la misma probabilidad de salir. Pero imagina ahora que le pintamos a cada bola un número del 0 al 99999. Si admitimos que el número pintado no afecta al proceso físico por el que se extrae la bola, ¿cómo se puede sostener que las bolas marcadas como 32711 y 12345 ya no tienen las mismas probabilidades de salir? ¿Si les borras las marcas tienen la misma probabilidad y si no se las borras tienen probabilidades muy distintas?
Y más aún: ¿Y si numeras las bolas en base 8? Entonces la bola 12345 tendría el número 30071 ("un número normal"), mientras que la bola 5349 (en base 10) pasaría a tener el número 12345. ¿Sucede entonces que una misma bola tiene probabilidades de salir si su número (en base 10) es 5349, pero pasa a ser prácticamente imposible que salga si la numeras en base 8, porque entonces es la 12345?
Esto mismo se aplica a los cardinales. Imagina que hubiera infinitas estrellas (no es el caso, pero podríamos vivir en un universo infinito con infinitas estrellas), y que los astrónomos hubieran convenido un criterio para numerarlas en función de su distancia al Sol, con algún criterio extra para deshacer empates. Entonces el Sol sería la estrella 0, luego Proxima Centauri sería la estrella 1, Alfa Centauri A sería la 2, Alfa Centauri B sería la 3, la estrella de Barnard sería la 4, etc.
Podríamos decir que hay tantas estrellas como números naturales.
Pero ahora imagina que los astrónomos rusos deciden seguir otro criterio, y asignan a las estrellas números pares y a los planetas números impares. Así 0 sería el Sol, 1 sería Mercurio, 2 sería Proxima Centauri, 3 sería Venus, etc.
Si aceptamos que es "intuitivamente cierto" que hay la mitad de números pares que de números naturales, tendríamos que concluir que los rusos han reducido a la mitad el número de estrellas, porque para ellos hay tantas como números pares. Las estrellas son las que son, ni más ni menos. ¿Es "intuitivo" que el número de estrellas se duplique o se reduzca a la mitad según cómo las etiquetes? La respuesta es que es igual de "intuitivo" que afirmar que la probabilidad de que salga una bola de un bombo es mayor o menor según cómo la etiquetes.
Por otra parte, pongo siempre "intuitivo" entre comillas porque nada de lo dicho aquí tiene nada que ver con la intuición en el sentido que hay que dar a esta palabra como fuente del conocimiento matemático. Que una recta no puede cortar a una circunferencia en más de dos puntos es intuitivamente cierto, pero que el cardinal de los números naturales sea igual al de los números pares no tiene nada de intuitivo o de antiintuitivo. Es intuitivamente cierto si damos la definición de cardinal usual, y no es ni intuitivo ni antiintuitivo si no adoptamos ninguna definición de cardinal. Los argumentos previos muestran que cualquier intento de definir el cardinal de un conjunto infinito que no implique que los números naturales y los números pares tienen el mismo cardinal llevaría a admitir que un mismo conjunto puede tener un cardinal u otro distinto según "el cristal con que se mire", por lo que tal cardinalidad no sería una propiedad intrínseca del conjunto, sino una propiedad "relativa al contador".