対角線論法と選択公理

某所で「対角線論法（のうち、実数全体が可算でないことを示すアレ）に選択公理は必要か？」という話題を見かけた。
この問い自体については、新しい十進小数を作るために各桁を既存の小数と異なるように選ぶ際、選び方を他の桁と無関係に具体的に指定できる（例えば、元々その桁が1だったら2、それ以外なら1を選ぶ）ので選択公理は不要ということでよいとして、そこからの連想で以下の問いを考えてみた。

問：「各正整数nごとに要素数2以上の集合X_nが与えられているとき、それらの直積集合と正整数全体との間に全単射は存在しない」ことは、（可算）選択公理を使えば対角線論法で証明できるけれども、では選択公理抜きのZF集合論ではどうだろうか？

なお、私自身も答えはわからないので、わかった方はご教示くださると嬉しいです。

（追記あり）

追記：

Aさんが一晩でやってくれました。いや、一晩もかかってないわけですが。さすがプロは違いますね。
ネタバレ回避のためにリンクを張るだけにしておきますので、答えを知りたい方はリンク先へどうぞ。

で、氏も言及されてましたが、正整数全体のかわりに任意の集合を考えたらどうなるんでしょうね。