2の自然数乗は自然数か?

ref:わたしが知らないスゴ本は、きっとあなたが読んでいる: 数学ぎらいは幸せになれないか? 「生き抜くための数学入門」のコメント欄.

簡便のため, Nは0を含むとする.
数学的な記法で表すと以下になる. $\forall n \in N, 2^n \in N$

証明

任意の自然数 $k \in N$ について, $2 \cdot k \in N$ であることは明らか.
以下, 数学的帰納法を用いる.

n=0のとき, $2^0 = 1 \in N$
n-1で成立すると仮定すると, $2^{n-1} \in N$ . 自然数は2倍について閉じているので, $2^n = 2 \cdot 2^{n-1} \in N$ .

数学的帰納法より証明終わり.

補足1

正しいステートメントは

「2のn乗はいつも自然数になるとは限らない」は正しくない

である.
様相論理の言葉が入っているとするのは深読みかも知れないが, ありうる話だ.
こちらも書き直すと, $\neg \neg \box (\forall n \in N, 2^n \in N)$ は証明出来るか? という話になる. $\neg \box p$ という場合, 「pが必然的であるということはない」と読む. 排中律さえあれば大丈夫かな. 括弧の中身が真という仮定から示せる筈.

補足2あるいは詭弁

以下, 二進数で考えよう.

事実1: 全ての自然数は0,1で表現出来る.
事実2: [0,1)区間の二進数の小数での表記は, 例えば0.010101...で与えられる.

小数表現の方の, 最初の0.という記法は冗長なので無くすことにする. 例えば, 01という表現は, $0 \cdot \frac{1}{2} + 1 \cdot \frac{1}{2^2}$ という数を表すものとする.
事実1と事実2を組み合わせるとこんなことが言える気がしてくる.

ステートメント: $[0,1) \sim N$
証明: 任意の小数 $a \in [0,1)$ についてその表記を考える. これを左右反転させたものを自然数の二進表記と見る. これで一対一対応が付くので, [0,1)とNは同型.

カントールの対角線論法から分かる通り, この証明には誤りがある. 無限小数に対応する (無限桁の) 自然数は存在しないという点を無視して議論を進めているのが誤り.

補足3: 対角線論法について

勿論対角線論法を使うというのは誤り. 簡単に一対一対応が付く.
対角線論法を使うつもりでnと2^nを並べてみる.

$n \in N$	$2^n$
0	2^0=1
1	2^1=01
2	2^2=001
...	...

表の右カラムに無い2^nを持ってきて欲しい. この場合000...になるが, 000...は2^nでは無いので対角線論法が使えない.

追記1:

2のn乗は自然数？ - 菊やんの雑記帳
該当箇所の情報アリ.
孫引きになるが引く.

ロジックに不慣れな(or 全く異なるロジックを持ってる)宇宙人に

2のn乗はつねに自然数である。

ということを証明しようとするが、

nが大きくなると自然数であることを示すのに、莫大な資源が必要だから正しいかどうかわからない。

と反駁される。

可能無限とかの話じゃないですかね? それを示せないのなら自然数全体の体系と数学的帰納法が使えないので, そもそも対角線論法が使えないと思った (本当かどうかは知らない. より詳しい人に任せる).

追記2:

ゲーデルの不完全性定理について考えていると, 何が言いたいのか分かった. ω無矛盾性のことか.

ω無矛盾（オメガむむじゅん、omega consistency）とは、P(0),P(1),P(2),...のすべてと、¬∀xP(x)が同時に証明されるような論理式Pが存在しないことを意味する。
通常の無矛盾性、Pと¬Pとが同時に証明されるような論理式Pが存在しないことよりも強い条件を与える。ゲーデルは当初数論のω無矛盾性を前提として不完全性定理を導いたが、それは後に通常の無矛盾性からも導かれることが明らかになった。

P(x)を「2のx乗は自然数である」としてやれば良いのね. ¬∀xP(x)は「「すべての自然数について2のx乗は自然数である」は正しくない」と読むので, 本に出てきた例になっている.
ということで, ω矛盾の例として出したかったらしい. すっきり.
すっきりしたが, これが適当な例かどうかという判断はまた別である.

追記3:

もっと前か. 算術を扱う論理式の明確な定義とはという話だったらしいorz

著者である新井紀子さんに伺ったところ、わたしの解釈が誤っていたことが分かりました。超お忙しい中レクチャーしていただき、大変感謝しています。
まず、「任意の自然数nに対して、2^nは自然数である」は、正しい命題です。
わたしが誤っていた点は、（限定された数理体系の）宇宙人との問答であることを理解していなかったことに尽きます。宇宙人は地球にきたばかりで、足し算掛け算の小学生レベルの数理体系しか身につけていません。従って数学的帰納法は知らない、という前提です。
以下、新井さんの許諾を得て、メールの一部を転用します。

さて、本文の266ページをもう一度よくお読みください。
「じつは、中学1年の2のn乗が出てくるところまで（の知識と方法論）では、宇宙人の言っていることを否定することはできません」とあります。つまり、「小学校までの自然数に関する「ナイーブな理解では」」宇宙人が十分に納得できるような反駁はできない、ということです。
小学校までの算数・数学では、数学的帰納法を学んでいません。数学的帰納法というのは、

A(n)という数学的命題がn=1のとき正しい。

任意のnについて、A(n)が正しいと仮定するなら、A(n+1)も正しい。

以上の2点が証明できたなら、任意の自然数にnについてA(n)が正しい。
というもので、自然数の公理のひとつです。
これは高校で習いますが、実はこのときにも問題があります。「数学的命題」とはなんであるかが、曖昧なままだからです。「数学的帰納法を使えば簡単に宇宙人に反駁できる」と主張されている方たちは、実は、かなり広範な数学的命題に対して数学的帰納法を適用しています。
さて、宇宙人がなぜ、2^nが常に自然数になるとは限らない、といったか。想像するに、この宇宙人は、この数学的帰納法が適用される「数学的命題」の範囲を、「足し算、かけ算と＝と大小で書くことができる数式」あるいは、それに毛の生えた範囲に限定して考えていたのでしょう。これだと、2^nが常に自然数になることを証明できません。