Tal como lo planteas es falso. Por ejemplo, el -2 es par, y no es natural; únicamente debes agregar un poco para que el enunciado sea cierto:
1)Probar que la unión de los pares e impares, tanto positivos como negativos, es el conjunto de los enteros.
2)Probar que la unión de los pares e impares positivos es el conjunto de los naturales.
Cualquiera de los dos enunciados es cierto. Supongo que te refieres al segundo.
El problema es equivalente a demostrar que todo número natural es par o impar.
Hay varias maneras de proceder. Con qué herramientas cuentas?
Saludos.