あとは、上記のような g が存在することを言えばよい。

偶数全体の集合を Z_0 とする(集合としては H ＝ Z_0 である)。
奇数全体の集合を Z_1 とする。以下の4つの集合

Z_0, Z_1, ∪[s＝0〜∞] { n∈N｜3^{2s} ≦ n ＜ 3^{2s＋1} }, ∪[s＝0〜∞] { n∈N｜3^{2s＋1} ≦ n ＜ 3^{2s＋2} }

はどれも可算無限集合であるから、どの2つの間にも全単射が取れる。特に、
全単射 f_0：∪[s＝0〜∞] { n∈N｜3^{2s} ≦ n ＜ 3^{2s＋1} } → Z_0 と
全単射 f_1：∪[s＝0〜∞] { n∈N｜3^{2s＋1} ≦ n ＜ 3^{2s＋2} } → Z_1 を
何でもいいから取っておく。

g：N → Z を以下のように定義する。

g_n ＝ f_0(n) (3^{2s} ≦ n ＜ 3^{2s＋1}, s＝0,1,2…),
g_n ＝ f_1(n) (3^{2s＋1}≦ n ＜ 3^{2s＋2}, s＝0,1,2…)

明らかに g：N → Z は全単射である。また、この g は明らかに

・ g_n が偶数になるのは、3^{2s} ≦ n ＜ 3^{2s＋1} (s＝0,1,2,…) のとき、かつそのときのみ

という性質を満たす。