五分解説 集合論, および, 指数式と多項式の比較法について
前提知識 : 集合の濃度
$\ $
$\ $
$\ $
$\ $
$\ $
$\ $
冪集合の濃度について
自然数の集合$\mathbb{N}$を組みあわせて非交和あるいは直積を構成しても, $\mathbb{N}$より大きな集合を作ることはできない. 何故ならば,
\begin{align}
\mathbb{N}\mathbin{\sqcup}\mathbb{N}\cong\mathbb{N},\quad\mathbb{N}\times\mathbb{N}\cong\mathbb{N}
\end{align}
の同型が存在するからである. これらよりも上の濃度の集合を得るためには, 冪集合$2^\mathbb{N}$等を用いる必要が有る.
あらゆる集合$A$にたいして, $|A|<\left|2^A\right|$が成りたつ.
次の証明は, 素朴集合論における Russel のパラドックスの考え方を踏襲している: 自分自身を元として含まない集合の全体$P=\{x\mid x\not\in x\}$を考えるとき, $P\in P$と仮定しても, また$P\not\in P$と仮定しても, 集合$P$の定義との間に明らかなる矛盾が発生する. これは二十世紀初頭に指摘された集合論全体の綻びであって, 後に公理的集合論を企てた数学者たちは, このような種のパラドックスを悉く解消するのに際し多数の難を構えることになった.
扨て, 論題を$|A|<\left|2^A\right|$の証明に戻そう. $|A|\leqslant\left|2^A\right|$は明白であるので, 全単射$f\;\colon\; A\longrightarrow2^A$の存在しないことを示すべきである. そのために, 仮に全単射があるものとして,
\begin{align}
C=\{x\in A\mid x\not\in f(x)\}
\end{align}
なる$A$の部分集合を考察するとき, 全射性によって$f(c)=C$を充たす$c\in A$が存在する. 第一に$c\in C$と仮定すれば, $C$の定義によって$c\not\in f(c)=C$が成りたち矛盾である. 第二に$c\not\in C$と仮定しても, $C$の定義に基づき$c\in f(c)=C$が得られるから, 同じ矛盾が導かれる. 故に全単射$A\longrightarrow2^A$は存在しない. $\quad\Box$
$\ $
$\ $
$\ $
$\ $
$\ $
$\ $
指数式が多項式にたいして大きいこと
これからの解説には, 本質的な誤りが含まれます.
どこの推論が間違えているのか探してみてください.
若し証明の修復法をご存じの方が居ましたら, 私の Twitter アカウント (@Numerus_A) の DM 等を通じてご報告願います.
$2^n\leqslant n$を充たす自然数$n$は個数有限である.
今仮にそのような$n$が無数に存在するものとし, 適当に番号を付して$n_0,\ n_1,\ n_2,\ \ldots$と名付けるとき,
\begin{align}
\mathbb{N}\cong n_0\sqcup n_1\sqcup n_2\sqcup\cdots
\end{align}
および,
\begin{align}
2^\mathbb{N}\cong 2^{n_0}\sqcup2^{n_1}\sqcup2^{n_2}\sqcup\cdots
\end{align}
の同型によって, 単射$2^\mathbb{N}\longrightarrow\mathbb{N}$が作られるが, これは$|\mathbb{N}|<\left|2^\mathbb{N}\right|$の関係に矛盾している. 故に仮定は誤りである. $\quad\Box$
$2^n\leqslant n^2-n+2$を充たす自然数$n$は個数有限である.
代わりに$2^n\leqslant n^2+n+2$を充たす$n$が有限であることを証明する. そのような$n$が無数に存在したとして, これを$n_0,\ n_1,\ n_2,\ \ldots$と名付けるとき,
\begin{align}
\mathbb{N}\cong n_0\sqcup n_1\sqcup n_2\sqcup\cdots
\end{align}
から得られる,
\begin{align}
\mathbb{N}^2\sqcup\mathbb{N}\sqcup\mathbb{N}\cong(n_0^2\sqcup n_0\sqcup2)\sqcup(n_1^2\sqcup n_1\sqcup2)\sqcup(n_2^2\sqcup n_2\sqcup2)\sqcup\cdots,
\end{align}
および,
\begin{align}
2^\mathbb{N}\cong 2^{n_0}\sqcup2^{n_1}\sqcup2^{n_2}\sqcup\cdots
\end{align}
の同型によって, 単射$2^\mathbb{N}\longrightarrow\mathbb{N}^2\sqcup\mathbb{N}\sqcup\mathbb{N}$が作られるが, $\mathbb{N}^2\sqcup\mathbb{N}\sqcup\mathbb{N}\cong\mathbb{N}$であるから, 状況は全く上の例と同じい. 即ち仮定は誤りである. $\quad\Box$
$\ $
$\ $
$\ $
$\ast\ast\ast$
$\ $
$\ $
$\ $
余談のようになりますが, 正整数における素因子分解の存在性を仮定するなら, 素数が無数に存在することを, 集合論のみによって (加法・乗法の性質を用いることなく) 証明することができます: 素因子分解の存在性が成りたつということは, 正なる整数$N$にたいし, $2^N$以下の正の整数に素因子分解が一つずつ以上対応していなくてはなりませんが, $2$は最小の素数ですから, 各々の分解において同一の素数が$N$回よりも多く遣われることは有りません. 従って
\begin{align}
2^N\leqslant(N+1)^{\pi(2^N)}
\end{align}
の不等式が得られ, $\pi(2^N)$が収束するものと仮定すれば, $|\mathbb{N}|<\left|2^\mathbb{N}\right|$との間に矛盾が発生することになるのです.
$\ $
$\ $
$\ $
$\ $
$\ $
$\ $
コメントの方へ : メント頂きありがとうございます. こちらの不手際で上手く返信を送ることができませんでした. Twitter の DM にスクリーンショットを送信しましたので, ご確認をお願いします.