＞h: N→N を用いた合成関数 g(h(n)) もまた正解であることが自明です．
そうですね
題意から、 N-F に対する全射ならばなんでもOKです。
ボムボムさんの
>>7の解答は単射でなく、全射であるものの一つでした。
後で公開予定ですが、なかなかの力技で見つけだしているもので、すごいです。
追記：
h:N→N(全射)として、g(h(n))もまた正解ですが、
答えが綺麗かどうかは置いておいて、
そういう発見の仕方ではないので、素晴らしいってことです
それと、ボムボムさんの
>>8は、普通の狭義単調増加の答えです。
ゲーデル
h: N→N を用いた合成関数 g(h(n)) もまた正解であることが自明です．
たとえば，h(n) = 3 n - 4 [n/2] - 1 とすれば，
h(n): 2, 1, 4, 3, 6, 5, ... (n = 1, 2, 3, 4, 5, 6, ...)
ですし，h(n) = i - 2 mod(i-1, 3) + 2 とすれば，
h(n): 3, 2, 1, 6, 5, 4, ... (n = 1, 2, 3, 4, 5, 6, ...)
です．
つまり，標準形として，単調増加の解が示されれば，それで十分と思います．
ボムボム さんの解答 (No.8) が全く違う形に書けているならば，興味津々です．