非専門的シンギュラリティー研究所

無限に動き続けるシステムを表す方法を AI なども使って考えていきます。

証明路開発支援システム(24)

証明路開発支援システム

対角線論法(1)

前回の証明では、集合の元の個数より順序数の方が多いということを示していないので証明ができていないと思われます。「集合でないと成り立たないこと」を何か使わないといけないのですが、前回の証明ではそれを使っているのか不明です。集合の元の個数に関する議論なので、対角線論法を使えば良いのではないかと思うのですが、使っているのか不明です。

いったん対角線論法について調べてみます。wikipedia:カントールの対角線論法を参考にします。

対角線論法(集合による表現)

X を集合、 2^X を X のべき集合とします。 \psi を X から 2^X への写像とします。 {\displaystyle X} の部分集合 Y を
Y = \{ x \in X \mid x \notin \psi(x) \}
と定義します。このとき \psi(x) = Y となる x \in X は存在しません。

[証明]

  • x \in X が \psi(x) = Y を満たすとすると
    • x \in Y \iff x \notin \psi(x) \iff x \notin Y となり矛盾。
  • よって \psi(x) = Y となる x \in X は存在しません。

対角線論法(関数による表現)

X を集合、 \varphi: X \times X \rightarrow \{0,1\} を写像とします。
\varphi(x, y) を \varphi_{x}(y) と書くと、各 x \in X に対し \varphi_{x} は X から \{0, 1\} への写像となります。 g: X \rightarrow \{0, 1\} を
g(x) = \neg \varphi_{x}(x)
と定義します。ここで、「 \neg」は 0 と 1 を反転する写像とします( \neg b = 1 - b)。このとき、 \varphi_{x} = g となる x \in X は存在しません。

[証明]

  • x \in X が \varphi_{x} = g を満たすとすると
    • g(x) = \varphi_{x}(x) = \neg g(x) となり矛盾。
  • よって \varphi_{x} = g となる x \in X は存在しません。

整列可能定理の証明

前回の証明では、集合 A の部分集合で整列集合であるものと順序数を対応させていました。集合 2^A の部分集合で整列集合であるものに対応する順序数の中には、対角線論法により、集合 A の部分集合で整列集合であるものに対応する順序数ではないものがあるので、それを見つければ証明ができると考えられます。しかしまだやり方は不明です。

公理的集合論への一歩　無限についてのおはなし (数学セミナーライブラリー)

公理的集合論への一歩　無限についてのおはなし (数学セミナーライブラリー)

Amazon
新装改版 集合への30講 数学30講シリーズ

新装改版 集合への30講 数学30講シリーズ

Amazon
集合論入門 (ちくま学芸文庫)

集合論入門 (ちくま学芸文庫)

Amazon
集合と位相(増補新装版)(数学シリーズ)

集合と位相(増補新装版)(数学シリーズ)

Amazon
手を動かしてまなぶ 集合と位相

手を動かしてまなぶ 集合と位相

Amazon
新装版 集合とはなにか―はじめて学ぶ人のために (ブルーバックス)

新装版 集合とはなにか―はじめて学ぶ人のために (ブルーバックス)

Amazon

グラフ理論入門(原書第4版)

グラフ理論入門(原書第4版)

Amazon

可換環論の勘どころ (数学のかんどころ 32)

可換環論の勘どころ (数学のかんどころ 32)

Amazon

代数学２　環と体とガロア理論　第２版

代数学２　環と体とガロア理論　第２版

Amazon

初等整数論入門 (ちくま学芸文庫)

初等整数論入門 (ちくま学芸文庫)

Amazon
発見・予想を積み重ねる ―それが整数論

発見・予想を積み重ねる ―それが整数論

Amazon
はじめての数論　原著第4版

はじめての数論　原著第4版

  • 丸善出版
Amazon
数論序説

数論序説

Amazon

群論 日評ベーシック・シリーズ

群論 日評ベーシック・シリーズ

Amazon
代数学１　群論入門　第２版

代数学１　群論入門　第２版

Amazon
代数学1群と環 (大学数学の入門 1)

代数学1群と環 (大学数学の入門 1)

Amazon
代数系入門 (松坂和夫 数学入門シリーズ 3)

代数系入門 (松坂和夫 数学入門シリーズ 3)

Amazon

数学セミナー2026年6月号　通巻776号【特集】高校生におすすめの整数論

数学セミナー2026年6月号　通巻776号【特集】高校生におすすめの整数論

  • 日本評論社
Amazon

ガウスの黄金定理　平方剰余の相互法則で語る数論の世界 (ブルーバックス)

ガウスの黄金定理　平方剰余の相互法則で語る数論の世界 (ブルーバックス)

Amazon

平方剰余の相互法則: ガウスの全証明

平方剰余の相互法則: ガウスの全証明

Amazon
数論への出発 増補版

数論への出発 増補版

Amazon
共立講座21世紀の数学 (20) 整数論

共立講座21世紀の数学 (20) 整数論

Amazon

証明路開発支援システム(23)

証明路開発支援システム

整列可能定理(3)

ChatGPT で調べてみました。

整列可能定理について教えてください

と入力すると以下のようになりました。

「整列可能定理（well-ordering theorem）」は、集合論における非常に重要な定理です。簡単にいうと、

任意の集合は、適切な順序を入れることによって「整列集合」にできる

という主張です。

1. 整列とは何か

まず、順序集合 (A,<) が整列集合であるとは、

\forall B\subseteq A,\quad B\neq\varnothing \Rightarrow \exists b\in B\quad \forall x\in B,\ b\leq x

が成り立つことです。

つまり、

任意の空でない部分集合が最小元を持つ

という性質です。

例えば自然数

\mathbb N=\{0,1,2,\ldots\}

は通常の大小関係で整列されています。

実際、自然数の空でない部分集合には必ず最小の元があります。

一方、整数

\mathbb Z

は通常の大小関係では整列されていません。

例えば

\mathbb Z

自身には最小元がありません。

しかし、整数にも**別の順序**を入れれば整列集合にできます。例えば

0,-1,1,-2,2,-3,3,\ldots

という順番で

0\prec -1\prec 1\prec -2\prec2\prec-3\prec3\prec\cdots

とすれば、これは整列になります。

したがって整列可能定理は、

\boxed{\text{「今ある順序で整列する」ではなく「何らかの順序を入れて整列する」}}

という定理です。


2. 整列可能定理

正確には、

\boxed{\text{任意の集合 }A\text{ に対して、}A\text{ を整列集合にする順序関係が存在する。}}

という定理です。

例えば実数集合

\mathbb R

についても、通常の大小関係

<

では整列されません。

例えば

(0,1)

には最小元がありません。

しかし整列可能定理によれば、

\mathbb R

には通常の大小関係とは全く別の順序を入れて整列集合にすることができます。

ただし、実際にその順序を具体的に書き下すことは一般にはできません。


3. なぜ重要なのか

整列可能定理は、選択公理（Axiom of Choice）と同値です。

つまり、通常のZF集合論において、

\boxed{ \text{選択公理} \iff \text{整列可能定理} }

が成り立ちます。

さらに、

\boxed{ \text{整列可能定理} \iff \text{ツォルンの補題} \iff \text{選択公理} }

です。

これは集合論で非常に重要な3つの原理です。


4. 選択公理との関係

選択公理は大まかにいうと、

  • 空でない集合をいくつか集めてきたとき、それぞれの集合から1個ずつ元を選ぶことができる。

という主張です。

例えば

\{A_i\}_{i\in I}

が空でない集合族なら、

\forall i\in I,\quad A_i\neq\varnothing

から、

f(i)\in A_i

となる関数

f:I\to\bigcup_{i\in I}A_i

が存在する、というものです。

この「無限個の集合から同時に1個ずつ選ぶ」という操作が、整列可能定理と深く結びついています。


5. 整列可能定理から選択公理を証明する

ここは整列可能定理の意味がよく分かるところです。

集合族

\{A_i\}_{i\in I}

があり、それぞれ

A_i\neq\varnothing

とします。

整列可能定理によって、各 A_i を整列する順序を選べます。

すると各 A_i には最小元

a_i=\min A_i

が存在します。

そこで

f(i)=a_i

と定義すれば、

f(i)\in A_i

ですから、f は選択関数になります。

したがって

\boxed{\text{整列可能定理}\Rightarrow\text{選択公理}}

となります。

ただし、この証明では「各 A_i に整列順序を選ぶ」という部分に注意が必要です。厳密なZFでの同値性証明では、この部分を適切に処理します。


6. 逆方向はもっと面白い

逆に、

\text{選択公理}\Rightarrow\text{整列可能定理}

を示すこともできます。

その代表的な証明がツォルンの補題を使うものです。

考え方としては、

1. A の部分集合をできるだけ大きく整列する
2. もしまだ A の元が残っていれば、それを追加する
3. そのような「最大の整列」を考える
4. 最大なのに元が残っていると矛盾する
5. よって A 全体が整列されている

というものです。

この「できるだけ大きなものを作る」という議論を厳密に保証するのがツォルンの補題です。


7. 整列可能定理と数学

整列可能定理を認めると、任意の集合 A に対して、その濃度をある基数で表すことができます。

例えば、

|\mathbb N|=\aleph_0

です。

そして整列可能定理によって、任意の集合 A に対して

|A|=\aleph

となる基数 \aleph が存在します。

つまり、

すべての集合の濃度を「基数」で比較できる

という非常に強力な結果が得られます。

例えば任意の2集合 A,B に対して、

|A|\leq |B|

または

|B|\leq |A|

のどちらかが成立します。

これは基数の比較可能性と呼ばれる性質です。


8. 直感的には

整列可能定理を一言で表すなら、

「どんなに巨大で複雑な集合でも、元を『1番目、2番目、3番目、……』という形で並べることができる」

ということです。

ただし、ここで「……」には自然数だけでなく、超限順序数が現れます。

例えば

0,1,2,\ldots,\omega,\omega+1,\omega+2,\ldots

のような順序です。

したがって、非可算集合を整列する場合には、

1番目,2番目,3番目,\ldots

だけでは足りません。

例えば実数全体 \mathbb R を整列すると、その順序型はある巨大な順序数になります。


9. 「実数を整列できる」という驚き

特に重要なのが、

\boxed{\mathbb R\text{ は整列可能}}

という結果です。

通常の順序では、

0<\frac12<\frac13<\cdots

のような集合は最小元を持たないので整列されません。

しかし、別の順序を使えば整列できます。

これは選択公理を受け入れた集合論では正しいのですが、

  • 「その整列順序を具体的に構成できる」

という意味ではありません。

ここが非常に重要です。

もし興味があれば次に、「整列可能定理 ⇔ 選択公理」を、ツォルンの補題を使わずにできるだけ初等的に証明する方法、あるいは「なぜ実数を実際に整列する具体的なアルゴリズムを作れないのか」を説明できます。

選択公理から整列可能定理を初等的な方法で証明してください

と入力すると以下のようになりました。

はい。ツォルンの補題を使わずに、選択公理から整列可能定理を導く標準的で比較的初等的な証明があります。

ポイントは、Hartogs（ハルトークス）の定理を使うことです。これは「選択公理を使わなくても、どんな集合 A よりも大きい順序数が存在する」という定理です。


1. 示したいこと

選択公理（AC）：

  • 任意の空でない集合族 \mathcal F に対して、各 X\in\mathcal F から1個ずつ元を選ぶ関数が存在する。

から、

  • 任意の集合 A は整列可能である。

を示します。

つまり、ある順序 < が存在して

(A,<)

が整列集合になることを証明します。


2. まず選択関数を1つ用意する

A\neq\varnothing とします。

選択公理を、 A の空でない部分集合全体に適用します。

\mathcal F=\mathcal P(A)\setminus{\varnothing}

とおきます。

選択公理によって関数

c:\mathcal F\to A

が存在し、

X\neq\varnothing \quad\Longrightarrow\quad c(X)\in X

となります。

つまり、

\boxed{\text{A の任意の空でない部分集合から、機械的に1個を選ぶ関数 }c}

を持っていることになります。

これを使って、 A の元を1個ずつ選んでいきます。


3. ただし「何個選べるか」が問題

自然数を使って

a_0=c(A)

a_1=c(A\setminus\{a_0\})

a_2=c(A\setminus\{a_0,a_1\})

\cdots

と選ぶことはできます。

しかし、これだけでは A 全体を取り尽くせるとは限りません。

例えば A=\mathbb R なら、可算回選んだだけでは全部の実数を選べません。

そこで、

0,1,2,\ldots

だけではなく、すべての順序数を使って選び続けることを考えます。


4. Hartogs の定理

ここで次の定理を使います。

Hartogs の定理

任意の集合 A に対して、ある順序数 h(A) が存在して、

\boxed{\text{$h(A)$ から $A$ への単射は存在しない}}

が成り立つ。

つまり、

h(A)\not\hookrightarrow A.

一方、

\alpha < h(A)

なら、

\alpha\hookrightarrow A

となります。

この h(A) を Hartogs 数と呼びます。

重要なのは、

\boxed{\text{Hartogs の定理には選択公理が必要ない}}

ということです。


5. Hartogs 数まで選び続けてみる

h(A) を \kappa と書きます。

\kappa=h(A).

そこで、超限再帰によって

a_\alpha\in A

を

\alpha<\kappa

について定義してみます。

すでに

a_\beta\qquad(\beta<\alpha)

が選ばれているとします。

そのとき、

R_\alpha={a_\beta\mid\beta<\alpha}

を、それまでに選んだ元の集合とします。

もし

A\setminus R_\alpha\neq\varnothing

なら、選択関数 c を使って

\boxed{ a_\alpha=c(A\setminus R_\alpha) }

と定義します。

つまり、

a_0,a_1,a_2,\ldots,a_\omega,a_{\omega+1},\ldots

という具合に、順序数を添字として A の元を選び続けるわけです。


6. 途中で A 全体を取り尽くしたら成功

ある

\alpha<\kappa

で

A\setminus R_\alpha=\varnothing

となったとします。

すると

R_\alpha=A.

つまり

A=\{a_\beta\mid\beta<\alpha\}.

しかも、各 a_\beta は以前選んだ元とは異なります。

したがって

\beta\longmapsto a_\beta

は

\alpha\to A

の全単射になります。

そこで A に

a_\beta < a_\gamma \quad\Longleftrightarrow\quad \beta<\gamma

と定義します。

すると A は \alpha と同じ順序型になります。

そして順序数 \alpha は整列集合なので、

\boxed{A\text{ は整列される}}

ことが分かります。


7. では、永遠に取り尽くせなかったら？

ここが証明の核心です。

仮に、どの

\alpha<\kappa

についても

A\setminus R_\alpha\neq\varnothing

だったとします。

すると、上の超限再帰によって

a_\alpha

をすべての

\alpha<\kappa

について選べます。

しかも、 a_\alpha はそれ以前に選んだ元とは異なります。

したがって、

f:\kappa\to A

を

f(\alpha)=a_\alpha

と定義すると、これは単射になります。

つまり、

\kappa\hookrightarrow A

が存在します。

しかし \kappa=h(A) の定義から、

h(A)\not\hookrightarrow A

でした。

これは矛盾です。

したがって、

\boxed{ \text{どこかの段階で必ず }A\text{ 全体を取り尽くす} }

ことが分かります。


8. したがって整列が得られる

ある \alpha<\kappa について

A=\{a_\beta\mid\beta < \alpha\}

となります。

各 a_\beta は相異なるので、

f:\alpha\to A,\qquad f(\beta)=a_\beta

は全単射です。

そこで

x < _{A}y

を

f^{-1}(x) < f^{-1}(y)

によって定義します。

すると A は \alpha と順序同型です。

したがって、

\boxed{(A, < _{A})\text{ は整列集合}}

です。

以上で、

\boxed{\mathrm{AC}\Longrightarrow\text{整列可能定理}}

が証明されました。


9. この証明の構造

証明全体を非常に簡潔にまとめると、

\boxed{ \begin{array}{c} \text{選択公理}\\ \Downarrow\\ \text{選択関数 }c\text{ を得る}\\ \Downarrow\\ \text{「まだ選んでいない元」を超限的に選ぶ}\\ \Downarrow\\ \text{どこまでも選べるなら }h(A)\hookrightarrow A\\ \Downarrow\\ \text{Hartogs 数の定義に矛盾}\\ \Downarrow\\ \text{途中で }A\text{ 全体を取り尽くす}\\ \Downarrow\\ A\text{ を整列できる} \end{array} }

というものです。


10. なぜこの証明が面白いのか

この証明では、実は「最大の整列部分集合」を作るという議論をしていません。

ツォルンの補題を使う証明では、

  • 「これ以上拡張できない整列部分集合」を取る

という発想になります。

それに対して今回の証明は、

「選択関数を使って、選べる限り超限的に選び続ける」

という非常に具体的な構成になっています。

そして、

\text{「いつまでも選べる」}

と仮定すると、

h(A)\hookrightarrow A

というHartogs 数の定義そのものに反する単射が作れてしまう、というのがポイントです。


さらに一歩進めると

この証明を理解すると、次の非常に興味深い事実も見えてきます。

\boxed{ \text{整列可能定理} \iff \text{選択公理} \iff \text{ツォルンの補題} }

のうち、

  • AC → 整列可能定理：今説明した「Hartogs 数＋超限再帰」
  • 整列可能定理 → AC：各集合を整列して最小元を選ぶ
  • AC → ツォルンの補題
  • ツォルンの補題 → 整列可能定理

という4本の関係を順に証明すると、3つがなぜ同値なのかがかなり明確になります。

公理的集合論への一歩　無限についてのおはなし (数学セミナーライブラリー)

公理的集合論への一歩　無限についてのおはなし (数学セミナーライブラリー)

Amazon
新装改版 集合への30講 数学30講シリーズ

新装改版 集合への30講 数学30講シリーズ

Amazon
集合論入門 (ちくま学芸文庫)

集合論入門 (ちくま学芸文庫)

Amazon
集合と位相(増補新装版)(数学シリーズ)

集合と位相(増補新装版)(数学シリーズ)

Amazon
手を動かしてまなぶ 集合と位相

手を動かしてまなぶ 集合と位相

Amazon
新装版 集合とはなにか―はじめて学ぶ人のために (ブルーバックス)

新装版 集合とはなにか―はじめて学ぶ人のために (ブルーバックス)

Amazon

グラフ理論入門(原書第4版)

グラフ理論入門(原書第4版)

Amazon

可換環論の勘どころ (数学のかんどころ 32)

可換環論の勘どころ (数学のかんどころ 32)

Amazon

代数学２　環と体とガロア理論　第２版

代数学２　環と体とガロア理論　第２版

Amazon

初等整数論入門 (ちくま学芸文庫)

初等整数論入門 (ちくま学芸文庫)

Amazon
発見・予想を積み重ねる ―それが整数論

発見・予想を積み重ねる ―それが整数論

Amazon
はじめての数論　原著第4版

はじめての数論　原著第4版

  • 丸善出版
Amazon
数論序説

数論序説

Amazon

群論 日評ベーシック・シリーズ

群論 日評ベーシック・シリーズ

Amazon
代数学１　群論入門　第２版

代数学１　群論入門　第２版

Amazon
代数学1群と環 (大学数学の入門 1)

代数学1群と環 (大学数学の入門 1)

Amazon
代数系入門 (松坂和夫 数学入門シリーズ 3)

代数系入門 (松坂和夫 数学入門シリーズ 3)

Amazon

数学セミナー2026年6月号　通巻776号【特集】高校生におすすめの整数論

数学セミナー2026年6月号　通巻776号【特集】高校生におすすめの整数論

  • 日本評論社
Amazon

ガウスの黄金定理　平方剰余の相互法則で語る数論の世界 (ブルーバックス)

ガウスの黄金定理　平方剰余の相互法則で語る数論の世界 (ブルーバックス)

Amazon

平方剰余の相互法則: ガウスの全証明

平方剰余の相互法則: ガウスの全証明

Amazon
数論への出発 増補版

数論への出発 増補版

Amazon
共立講座21世紀の数学 (20) 整数論

共立講座21世紀の数学 (20) 整数論

Amazon

証明路開発支援システム(22)

証明路開発支援システム

整列可能定理(2)

証明で使っている議論はだいたい以下のようになります。これを式の変形でできないかということを考えていきます。

  • 順序数全体を \mathbf{Ord} とします。 \mathbf{Ord} は集合ではありません。
  • 集合ではない場合も集合や関数の記法が使えるとします。
  • 部分集合が定義できます。
  • べき集合が定義できます。
  • 選択関数が定義できます。
  • 関数の帰納的定義ができます。
  • 式によって関数が定義できます。
  • 関数の制限が定義できます。
  • 関数の像が定義できます。
  • 集合の関数による像は集合になります。
  • 集合の部分集合は集合になります。
  • \restriction は関数の制限、 \mathrm{ran} は関数の値域を表します。

以下の証明の中で \gamma の定義を \gamma = \min \{ \alpha \mid X \subsetneq \alpha \} と変更します(証明がうまくできなかったため)。

集合 A \ne \varnothing に対して順序数 \gamma と全単射 f: \gamma \to A が存在する。

[証明]

  • a_0 \in A をとります。
  • 選択公理より選択関数 c: \mathfrak{P}(A) \setminus \{\varnothing\} \to A があります。
  • G: \mathbf{Ord} \to A を定義します。
    • 各順序数 \alpha に対して集合 G(\alpha) を
      G(\alpha) = \begin{cases} c(A \setminus \mathrm{ran}(G \restriction \alpha)) & (A \setminus \mathrm{ran}(G \restriction \alpha) \ne \varnothing のとき) \\ a_0 & (それ以外のとき) \end{cases}
      と定義できます。
  • G の像を B とします。
    • B = \{ G(\alpha) \mid \alpha \in \mathbf{Ord} \}
    • B は集合です。
  • g: B \to \mathbf{Ord} を定義します。
    • B の各元 b に対して順序数 g(b) を
      g(b) = \min \{ \alpha \mid G(\alpha) = b \}
      と定義します。
  • g の像を X とします。
    • X = \{ g(b) \mid b \in B \}
    • X は順序数からなる集合となります。
  • \gamma = \min \{ \alpha \mid X \subsetneq \alpha \} とおきます。
  • すると B と X の定義より B = \mathrm{ran}(G \restriction \gamma) が成り立ちます。
    • B \subseteq \mathrm{ran}(G \restriction \gamma) を示します。
      • b \in B をとります。 b \in \mathrm{ran}(G \restriction \gamma) を示します。
        • g(b) = \min \{ \alpha \mid G(\alpha) = b \} より b = G(g(b))
        • g(b) \in X より g(b) \in \gamma
        • G(g(b)) = b より b \in \mathrm{ran}(G \restriction \gamma)
    • \mathrm{ran}(G \restriction \gamma) \subseteq B を示します。
      • a \in \mathrm{ran}(G \restriction \gamma) として a \in B を示します。
        • a \in \mathrm{ran}(G \restriction \gamma) より順序数 \alpha が存在して a = G(\alpha)
        • よって a = G(\alpha) \in B
  • \gamma は B = \mathrm{ran}(G \restriction \delta) となる順序数 \delta で最小のものです。
    • B = \mathrm{ran}(G \restriction \delta) ならば X \subsetneq \delta であることを示します。
      • B = \mathrm{ran}(G \restriction \delta) とします。
      • \alpha \in X ならば \alpha \in \delta であることを示します。
        • \alpha \in X をとると b \in B が存在して \alpha = g(b)
        • B \subseteq \mathrm{ran}(G \restriction \delta) より \beta \in \delta が存在して b = G(\beta)
        • \alpha は b = G(\alpha) となる最小のものなので \alpha \in \beta
        • よって \alpha \in \delta
      • よって X \subsetneq \delta
    • \gamma は X \subsetneq \gamma となる最小のものなので \gamma \le \delta
  • B = A を示します。
    • B \subset A なので A \setminus B \ne \varnothing と仮定して矛盾を導きます。
      • B = \mathrm{ran}(G \restriction \gamma) なので A \setminus \mathrm{ran}(G \restriction \gamma) \ne \varnothing となります。
      • G の定義より
        G(\gamma) = c(A \setminus \mathrm{ran}(G \restriction \gamma))
      • c が \mathfrak{P}(A) \setminus \{\varnothing\} の選択関数であるから
        G(\gamma) \in A \setminus \mathrm{ran}(G \restriction \gamma) = A \setminus B
      • これは B の定義( G(\gamma) \in B)に反します。
    • したがって B = A となります。
  • 以上より \gamma が A = \mathrm{ran}(G \restriction \delta) となる順序数 \delta で最小のものであることがわかります。
  • f = G \restriction \gamma とすると f: \gamma \to A が全単射となることが G の定義と \gamma の最小性からわかります。
    • A = \mathrm{ran}(G \restriction \gamma) より f は全射です。
    • f が単射であることを証明します。
      • \delta = \min \{ \alpha \mid g(G(\alpha)) \ne \alpha \} とします。
      • \delta = \gamma を示します。
        • A = \mathrm{ran}(G \restriction \delta) を示します。
          • A \setminus \mathrm{ran}(G \restriction \delta) \ne \varnothing と仮定すると g(G(\delta)) = \delta となることを示します。
            • G の定義より G(\delta) \in A \setminus \mathrm{ran}(G \restriction \delta) となります。
            • \alpha < \delta ならば G(\alpha) \in \mathrm{ran}(G \restriction \alpha) なので G(\alpha) \ne G(\delta) です。
            • よって g(G(\delta)) = \min \{ \alpha \mid G(\alpha) = G(\delta) \} = \delta となります。
          • これは g(G(\delta)) \ne \delta に矛盾するので A = \mathrm{ran}(G \restriction \delta) となります。
        • \gamma は A = \mathrm{ran}(G \restriction \gamma) となる最小の順序数なので \gamma \le \delta
        • \gamma \notin X かつ g(G(\gamma)) \in X となるので g(G(\gamma)) \ne \gamma
        • \delta は g(G(\delta)) \ne \delta となる最小の順序数なので \delta \le \gamma
        • よって \delta = \gamma となります。
      • よって \gamma は G \restriction \gamma が単射ではない最小の順序数となります。
      • よって f は単射です。

公理的集合論への一歩　無限についてのおはなし (数学セミナーライブラリー)

公理的集合論への一歩　無限についてのおはなし (数学セミナーライブラリー)

Amazon
新装改版 集合への30講 数学30講シリーズ

新装改版 集合への30講 数学30講シリーズ

Amazon
集合論入門 (ちくま学芸文庫)

集合論入門 (ちくま学芸文庫)

Amazon
集合と位相(増補新装版)(数学シリーズ)

集合と位相(増補新装版)(数学シリーズ)

Amazon
手を動かしてまなぶ 集合と位相

手を動かしてまなぶ 集合と位相

Amazon
新装版 集合とはなにか―はじめて学ぶ人のために (ブルーバックス)

新装版 集合とはなにか―はじめて学ぶ人のために (ブルーバックス)

Amazon

グラフ理論入門(原書第4版)

グラフ理論入門(原書第4版)

Amazon

可換環論の勘どころ (数学のかんどころ 32)

可換環論の勘どころ (数学のかんどころ 32)

Amazon

代数学２　環と体とガロア理論　第２版

代数学２　環と体とガロア理論　第２版

Amazon

初等整数論入門 (ちくま学芸文庫)

初等整数論入門 (ちくま学芸文庫)

Amazon
発見・予想を積み重ねる ―それが整数論

発見・予想を積み重ねる ―それが整数論

Amazon
はじめての数論　原著第4版

はじめての数論　原著第4版

  • 丸善出版
Amazon
数論序説

数論序説

Amazon

群論 日評ベーシック・シリーズ

群論 日評ベーシック・シリーズ

Amazon
代数学１　群論入門　第２版

代数学１　群論入門　第２版

Amazon
代数学1群と環 (大学数学の入門 1)

代数学1群と環 (大学数学の入門 1)

Amazon
代数系入門 (松坂和夫 数学入門シリーズ 3)

代数系入門 (松坂和夫 数学入門シリーズ 3)

Amazon

数学セミナー2026年6月号　通巻776号【特集】高校生におすすめの整数論

数学セミナー2026年6月号　通巻776号【特集】高校生におすすめの整数論

  • 日本評論社
Amazon

ガウスの黄金定理　平方剰余の相互法則で語る数論の世界 (ブルーバックス)

ガウスの黄金定理　平方剰余の相互法則で語る数論の世界 (ブルーバックス)

Amazon

平方剰余の相互法則: ガウスの全証明

平方剰余の相互法則: ガウスの全証明

Amazon
数論への出発 増補版

数論への出発 増補版

Amazon
共立講座21世紀の数学 (20) 整数論

共立講座21世紀の数学 (20) 整数論

Amazon

証明路開発支援システム(21)

証明路開発支援システム

整列可能定理(1)

整列可能定理について調べてみます。以下の本を参考にします。

ここでは『 公理的集合論への一歩　無限についてのおはなし (数学セミナーライブラリー)』の定理2.11を見ていきます。本来は集合論の公理系から証明するのですが、ここでは計算でどれだけできるかを見ていきます。定理は以下のようになります。

集合 A \ne \varnothing に対して順序数 \gamma と全単射 f: \gamma \to A が存在する。

証明

  • a_0 \in A をとります。
  • 選択公理より選択関数 c: \mathfrak{P}(A) \setminus \{\varnothing\} \to A があります。
  • 各順序数 \alpha に対して集合 G(\alpha) を
    G(\alpha) = \begin{cases} c(A \setminus ran(G \restriction \alpha)) & (A \setminus ran(G \restriction \alpha) \ne \varnothing のとき) \\ a_0 & (それ以外のとき) \end{cases}
    と定義できます。
    • ここで \restriction は関数の制限、 ran は関数の値域
  • 集合 B を B = \{ G(\alpha) \in A \mid \alpha \in Ord \} とおきます。
    • ここで Ord は順序数全体
  • B の各元 b に対して順序数 \alpha_b を G(\alpha) = b となる順序数で最小のものとします。
  • X = \{ \alpha_b \mid b \in B \} とすると X は順序数からなる集合となります。
  • \gamma = \sup X とすると B と X の定義より B = ran(G \restriction \gamma) が成り立ちます。
    • ここで \displaystyle \sup X = \bigcup_{\alpha \in X} \alpha
  • \gamma は B = ran(G \restriction \delta) となる順序数 \delta で最小です。
  • B = A を示します。
    • そうでないとすると B \subsetneq A より A \setminus B \ne \varnothing です。
    • B = ran(G \restriction \gamma) なので A \setminus ran(G \restriction \gamma) \ne \varnothing となります。
    • しかし G の定義より
      G(\gamma) = c(A \setminus ran(G \restriction \gamma))
      であり c が \mathfrak{P}(A) \setminus \{\varnothing\} の選択関数であるから
      G(\gamma) \in A \setminus ran(G \restriction \gamma) = A \setminus B
      となりますが、これは B の定義に反します。
    • したがって B = A となります。
  • 以上より \gamma が A = ran(G \restriction \delta) となる順序数 \delta で最小のものであることがわかります。
  • f = G \restriction \gamma とすると f: \gamma \to A が全単射となることが G の定義と \gamma の最小性からわかります。

公理的集合論への一歩　無限についてのおはなし (数学セミナーライブラリー)

公理的集合論への一歩　無限についてのおはなし (数学セミナーライブラリー)

Amazon
新装改版 集合への30講 数学30講シリーズ

新装改版 集合への30講 数学30講シリーズ

Amazon
集合論入門 (ちくま学芸文庫)

集合論入門 (ちくま学芸文庫)

Amazon
集合と位相(増補新装版)(数学シリーズ)

集合と位相(増補新装版)(数学シリーズ)

Amazon
手を動かしてまなぶ 集合と位相

手を動かしてまなぶ 集合と位相

Amazon
新装版 集合とはなにか―はじめて学ぶ人のために (ブルーバックス)

新装版 集合とはなにか―はじめて学ぶ人のために (ブルーバックス)

Amazon

グラフ理論入門(原書第4版)

グラフ理論入門(原書第4版)

Amazon

可換環論の勘どころ (数学のかんどころ 32)

可換環論の勘どころ (数学のかんどころ 32)

Amazon

代数学２　環と体とガロア理論　第２版

代数学２　環と体とガロア理論　第２版

Amazon

初等整数論入門 (ちくま学芸文庫)

初等整数論入門 (ちくま学芸文庫)

Amazon
発見・予想を積み重ねる ―それが整数論

発見・予想を積み重ねる ―それが整数論

Amazon
はじめての数論　原著第4版

はじめての数論　原著第4版

  • 丸善出版
Amazon
数論序説

数論序説

Amazon

群論 日評ベーシック・シリーズ

群論 日評ベーシック・シリーズ

Amazon
代数学１　群論入門　第２版

代数学１　群論入門　第２版

Amazon
代数学1群と環 (大学数学の入門 1)

代数学1群と環 (大学数学の入門 1)

Amazon
代数系入門 (松坂和夫 数学入門シリーズ 3)

代数系入門 (松坂和夫 数学入門シリーズ 3)

Amazon

数学セミナー2026年6月号　通巻776号【特集】高校生におすすめの整数論

数学セミナー2026年6月号　通巻776号【特集】高校生におすすめの整数論

  • 日本評論社
Amazon

ガウスの黄金定理　平方剰余の相互法則で語る数論の世界 (ブルーバックス)

ガウスの黄金定理　平方剰余の相互法則で語る数論の世界 (ブルーバックス)

Amazon

平方剰余の相互法則: ガウスの全証明

平方剰余の相互法則: ガウスの全証明

Amazon
数論への出発 増補版

数論への出発 増補版

Amazon
共立講座21世紀の数学 (20) 整数論

共立講座21世紀の数学 (20) 整数論

Amazon

証明路開発支援システム(20)

証明路開発支援システム

シローの定理(2)

「シローの定理」は「証明路」にすることは難しそうですが、計算で証明できるようにすることはできるかもしれません。計算でどれだけできるか調べてみます。

(1) 写像による分類

  • f: X \to Y を写像とします。
  • \mathrm{Im}(f) = \{ f(x) \mid x \in X \} とおきます。
  • i \in \mathrm{Im}(f) のとき f^{-1}(i) = \{ x \in X \mid f(x) = i \} とおきます。
  • \displaystyle X = \bigsqcup_{i \in \mathrm{Im}(f)} f^{-1}(i) と共通部分のない部分集合に分割できます。
  • X が有限集合のとき \displaystyle |X| = \sum_{i \in \mathrm{Im}(f)} |f^{-1}(i)| が成り立ちます。
  • X が有限集合で、任意の i, \ j \in \mathrm{Im}(f) に対して |f^{-1}(i)| = |f^{-1}(j)| であれば i \in \mathrm{Im}(f) に対して \displaystyle |X| = |\mathrm{Im}(f)| \cdot |f^{-1}(i)| が成り立ちます。

(2) 左剰余類による分類

  • G を群、 H を G の部分群とします。
  • X を G の部分集合で任意の x \in X に対して xH \subseteq X とします。
  • f: X \to \mathfrak{P}(G) を x \mapsto xH とします。
  • \mathrm{Im}(f) = \{ f(x) \mid x \in X \} = \{ xH \mid x \in X \} とおきます。
  • X = G のとき \mathrm{Im}(f) を G/H と書きます。
  • i \in \mathrm{Im}(f) のとき f^{-1}(i) = \{ x \in X \mid f(x) = i \} とおきます。
  • y \in f^{-1}(f(x)) \iff f(y) = f(x) \iff yH = xH \iff y \in xH より
    f^{-1}(f(xH)) = xH
  • \displaystyle X = \bigsqcup_{i \in \mathrm{Im}(f)} f^{-1}(i) = \bigsqcup_{i \in \mathrm{Im}(f)} r(i)H
    ここで r(i) は \mathrm{Im}(f) の元から一つずつ元を取り出す写像とします。
  • X が有限集合のとき x, \ y \in X に対して
    z \in xH \iff yx^{-1}z \in yH より
    |xH| = |yH|
  • X が有限集合のとき
    \displaystyle |X| = \sum_{i \in \mathrm{Im}(f)} |r(i)H| = \sum_{i \in \mathrm{Im}(f)} |H| = |\mathrm{Im}(f)| \cdot |H|
    が成り立ちます。

(3) 右剰余類による分類

(2) と同様です。

(4) 群の作用

  • G を有限群、 X を有限集合とします。
  • \rho: G \to \mathfrak{S}(X) を群の準同型とします。
  • x \in X とします。
  • G_x = \{ g \in G \mid \rho(g)(x) = x \}
    は G の部分群になります。
  • O: X \to \mathfrak{P}(X) を
    O(x) = \{ \rho(g)(x) \mid g \in G \} とおきます。
  • _x: G \to \mathfrak{P}(G) を左剰余類に写す写像 g \mapsto gG_x とします。
  • f^{-1}(i) はある左剰余類 r(i)G_x に一致します。
  • \displaystyle G = \bigsqcup_{i \in G/G_x} r(i)G_x と左剰余類に分解できます。
  • |G| = |G/G_x| \cdot |G_x| が成り立ちます。
  • gG_x = hG_x \iff h^{-1}g \in G_x \iff \rho(h^{-1}g)(x) = x \iff \rho(g)(x) = \rho(h)(x)
    となります。よって |G/G_x| = |O(x)| が成り立ちます。
  • |G| = |O(x)| \cdot |G_x| が成り立ちます。
  • y \in O(x)
    \iff y \in \{ \rho(g)(x) \mid g \in G \}
    \iff g \in G が存在して y = \rho(g)(x)
    \iff g \in G が存在して \rho(g^{-1})y = x
    \iff g \in G が存在して x = \rho(g)(y)
    \iff x \in O(y)
  • y \in O(x) とします。
    z \in O(y)
    \iff g \in G が存在して z = \rho(g)(y)
    \implies g, \ h \in G が存在して z = \rho(g)(\rho(h)(x))
    \implies g, \ h \in G が存在して z = \rho(gh)(x)
    \implies z \in O(x)
    z \in O(x) ならば x \in O(y) なので上の議論から z \in O(y)
    よって O(y) = O(x)
  • y \in O(y) なので y \in O(x) \iff O(y) = O(x)
  • y \in O^{-1}(O(x)) \iff O(y) = O(x) より O^{-1}(O(x)) = O(x)
  • \displaystyle X = \bigsqcup_{i \in \mathrm{Im}(O)} O^{-1}(i) = \bigsqcup_{i \in \mathrm{Im}(O)} O(c(i)) と軌道に分解できます。
    ここで c(i) は \mathrm{Im}(O) の元から一つずつ元を取り出す写像とします。
  • \displaystyle |X| = \sum_{i \in \mathrm{Im}(O)} |O(c(i))| が成り立ちます。

(5)

n、 m を正の整数、 n > m とします。
元の個数が n の集合の、元の個数が m の部分集合の総数は
\displaystyle \binom{n}{m} = \prod_{k = 0}^{m-1} \frac{n-k}{m-k}
となります。

(6)

p を素数、 n を正の整数とするとき
\displaystyle d_p(n) = \max_{p^e | n} e とします。

  • d_p(m + n) \ge \min(d_p(m), d_p(n))
  • d_p(m) \ne d_p(n) のとき d_p(m + n) = \min(d_p(m), d_p(n))
  • d_p(mn) = d_p(m) + d_p(n)
  • n \mid m のとき d_p(m / n) = d_p(m) - d_p(n)

シローの定理

G を位数 n の有限群、 p を素数、 n = p^am、 p \not\mid m とします。このとき位数 p^a の G の部分群が存在します。

証明

  • X = \{ S \mid S \subseteq G, \ |S| = p^a \} とおきます。
  • d_p(|X|) = 0 を証明します。
    • \displaystyle |X| = \binom{n}{p^a} = \prod_{k = 0}^{p^a-1} \frac{n-k}{p^a-k}
    • \displaystyle d_p(|X|) = \sum_{k = 0}^{p^a-1} d_p(\frac{n-k}{p^a-k}) = \sum_{k = 0}^{p^a-1} (d_p(n-k) - d_p(p^a-k))
    • k = 0 のとき d_p(n-k) - d_p(p^a-k) = d_p(n) - d_p(p^a) = a - a = 0
    • k > 0 のとき d_p(k) < a
    • k > 0 のとき d_p(n-k) - d_p(p^a-k) = \min(d_p(n), d_p(k)) - \min(d_p(p^a), d_p(k)) = d_p(k) - d_p(k) = 0
    • \displaystyle d_p(|X|) = \sum_{k = 0}^{p^a-1} (d_p(n-k) - d_p(p^a-k)) \le 0
    • d_p(|X|) = 0
  • O: X \to \mathfrak{P}(X) を O(S) = \{ gS \mid g \in G \} とおきます。
  • d_p(|O(S)|) = 0 となる S \in X が存在することを証明します。
    • \displaystyle |X| = \sum_{i \in \mathrm{Im}(O)} |O^{-1}(i)|
    • \displaystyle 0 = d_p(|X|) \ge \min_{i \in \mathrm{Im}(O)} d_p(|O^{-1}(i)|)
    • i \in \mathrm{Im}(O) が存在して d_p(|O^{-1}(i)|) = 0
    • S \in X が存在して O^{-1}(i) = O(S)
    • よって d_p(|O(S)|) = 0
  • H = \mathrm{Stab}(S) = \{ g \in G \mid gS = S \} とおきます。
  • H は G の部分群になります。
  • d_p(|H|) = a を証明します。
    • f_H: G \to \mathfrak{P}(G) を g \mapsto gH とします。
    • f_{H}^{-1}(gH) = gH より f_{H}^{-1}(i) はある左剰余類 gH に一致します。
    • |O(S)| = |G/H| であることから
      \displaystyle |G| = \sum_{i \in \mathrm{Im}(f_H)} |f_H^{-1}(i)| = \sum_{i \in \mathrm{Im}(f_H)} |H| = |\mathrm{Im}(f_H)| \cdot |H| = |G/H| \cdot |H| = |O(S)| \cdot |H|
    • a = d_p(|G|) = d_p(|O(S)|) + d_p(|H|) = d_p(|H|)
  • |H| は p^a の約数であることを証明します。
    • f_{S,H}: S \to \mathfrak{P}(S) を s \mapsto Hs とします。
    • f_{S,H}^{-1}(Hs) = Hs より f_{S,H}^{-1}(i) はある右剰余類 Hs に一致します。
    • \displaystyle p^a = |S| = \sum_{i \in \mathrm{Im}(f_{S,H})} |f_{S,H}^{-1}(i)| = \sum_{i \in \mathrm{Im}(f_{S,H})} |H| = |\mathrm{Im}(f_{S,H})| \cdot |H|
    • |H| \mid |S| = p^a
  • よって |H| = p^a が成り立ちます。

グラフ理論入門(原書第4版)

グラフ理論入門(原書第4版)

Amazon

可換環論の勘どころ (数学のかんどころ 32)

可換環論の勘どころ (数学のかんどころ 32)

Amazon

代数学２　環と体とガロア理論　第２版

代数学２　環と体とガロア理論　第２版

Amazon

初等整数論入門 (ちくま学芸文庫)

初等整数論入門 (ちくま学芸文庫)

Amazon
発見・予想を積み重ねる ―それが整数論

発見・予想を積み重ねる ―それが整数論

Amazon
はじめての数論　原著第4版

はじめての数論　原著第4版

  • 丸善出版
Amazon
数論序説

数論序説

Amazon

群論 日評ベーシック・シリーズ

群論 日評ベーシック・シリーズ

Amazon
代数学１　群論入門　第２版

代数学１　群論入門　第２版

Amazon
代数学1群と環 (大学数学の入門 1)

代数学1群と環 (大学数学の入門 1)

Amazon
代数系入門 (松坂和夫 数学入門シリーズ 3)

代数系入門 (松坂和夫 数学入門シリーズ 3)

Amazon

数学セミナー2026年6月号　通巻776号【特集】高校生におすすめの整数論

数学セミナー2026年6月号　通巻776号【特集】高校生におすすめの整数論

  • 日本評論社
Amazon

ガウスの黄金定理　平方剰余の相互法則で語る数論の世界 (ブルーバックス)

ガウスの黄金定理　平方剰余の相互法則で語る数論の世界 (ブルーバックス)

Amazon

平方剰余の相互法則: ガウスの全証明

平方剰余の相互法則: ガウスの全証明

Amazon
数論への出発 増補版

数論への出発 増補版

Amazon
共立講座21世紀の数学 (20) 整数論

共立講座21世紀の数学 (20) 整数論

Amazon

証明路開発支援システム(19)

証明路開発支援システム

「シローの定理」について調べます。

を参照します。証明を見るとある程度計算でできる証明があるようです。

(1) 写像による分類

一般的な用語は不明ですが写像に対して成り立ちます。

  • f: X \to Y を写像とします。
  • \mathrm{Im}(f) = \{ f(x) \mid x \in X \} とおきます。
  • i \in \mathrm{Im}(f) のとき f^{-1}(i) = \{ x \in X \mid f(x) = i \} とおきます。
  • \displaystyle X = \bigsqcup_{i \in \mathrm{Im}(f)} f^{-1}(i) と共通部分のない部分集合に分割できます。
  • X が有限集合のとき \displaystyle |X| = \sum_{i \in \mathrm{Im}(f)} |f^{-1}(i)| が成り立ちます。

(2) 群の剰余類分解

  • G を有限群、 H を G の部分群とします。
  • f_H: G \to \mathfrak{P}(G) を左剰余類に写す写像 x \mapsto xH とします。
  • 左剰余類全体の集合を G/H とします。
    G/H = \{ xH \mid x \in G \}
  • G/H = \mathrm{Im}(f_H) となります。
  • f_H^{-1}(xH) = xH より f_H^{-1}(i) はある左剰余類 xH に一致します。
  • \displaystyle G = \bigsqcup_{i \in G/H} f_H^{-1}(i) と左剰余類に分解できます。
  • xH の元の個数は x によらずすべて等しいことを証明します。
    • z \in xH ならば yx^{-1}z \in yH
    • w \in yH ならば xy^{-1}w \in xH
    • よって任意の x, \ y \in G に対して xH と yH の元の個数は等しくなります。
  • H = eH なので G/H の元(左剰余類)の元の個数はすべて H の元の個数に等しくなり
    |G| = |G/H| \cdot |H|
    が成り立ちます。

(3) 対称群の固定部分群による分解

  • \mathfrak{S}(n) を n 次の対称群とします。
  • n を固定する置換の全体を \mathfrak{S}(n-1) とします。
    \mathfrak{S}(n-1) = \{ s \in \mathfrak{S}(n) \mid s(n) = n \}
  • \mathfrak{S}(n-1) は \mathfrak{S}(n) の部分群になります。
  • f_{\mathfrak{S}(n-1)}: \mathfrak{S}(n) \to \mathfrak{P}(\mathfrak{S}(n)) を s \mapsto s\mathfrak{S}(n-1) とおきます。
  • \mathrm{Im}(f_{\mathfrak{S}(n-1)}) = \{ s\mathfrak{S}(n-1) \mid s \in \mathfrak{S}(n) \} となります。
  • O(n) = \{ s(n) \mid s \in \mathfrak{S}(n) \} とおきます(軌道)。
  • s\mathfrak{S}(n-1) = t\mathfrak{S}(n-1) \iff t^{-1}s \in \mathfrak{S}(n-1) \iff t^{-1}s(n) = n \iff s(n) = t(n)
    となります。よって |\mathrm{Im}(f_{\mathfrak{S}(n-1)})| = |O(n)| が成り立ちます。
  • |\mathfrak{S}(n)| = |O(n)| \cdot |\mathfrak{S}(n-1)| が成り立ちます。

(4) X の置換群の固定部分群による分解

  • X を有限集合、 \mathfrak{S}(X) を X の置換群とします。
  • x \in X を固定する置換の全体を \mathrm{Stab}(x) とします。
    \mathrm{Stab}(x) = \{ s \in \mathfrak{S}(X) \mid s(x) = x \}
  • \mathrm{Stab}(x) は \mathfrak{S}(X) の部分群になります。
  • f_{\mathrm{Stab}(x)}: \mathfrak{S}(X) \to \mathfrak{P}(\mathfrak{S}(X)) を s \mapsto s\mathrm{Stab}(x) とおきます。
  • \mathrm{Im}(f_{\mathrm{Stab}(x)}) = \{ s\mathrm{Stab}(x) \mid s \in \mathfrak{S}(X) \} となります。
  • O(x) = \{ s(x) \mid s \in \mathfrak{S}(X) \} とおきます(軌道)。
  • |\mathrm{Im}(f_{\mathrm{Stab}(x)})| = |O(x)| が成り立ちます。
  • |\mathfrak{S}(X)| = |O(x)| \cdot |\mathrm{Stab}(x)| が成り立ちます。

(5) 群の作用

  • G を有限群、 X を有限集合とします。
  • ( G の X への作用)
    \rho: G \to \mathfrak{S}(X) を群の準同型とします。
  • x \in X とします。
  • (固定部分群) x を固定する元全体の集合
    G_x = \{ g \in G \mid \rho(g)(x) = x \}
    は G の部分群になります。
  • (軌道) O: X \to \mathfrak{P}(X) を
    O(x) = \{ \rho(g)(x) \mid g \in G \} とおきます。
  • f_x: G \to \mathfrak{P}(G) を左剰余類に写す写像 g \mapsto gG_x とします。
  • f_x^{-1}(gG_x) = gG_x より f_x^{-1}(i) はある左剰余類 gG_x に一致します。
  • \displaystyle G = \bigsqcup_{i \in G/G_x} f_x^{-1}(i) と左剰余類に分解できます。
  • |G| = |G/G_x| \cdot |G_x| が成り立ちます。
  • gG_x = hG_x \iff h^{-1}g \in G_x \iff \rho(h^{-1}g)(x) = x \iff \rho(g)(x) = \rho(h)(x)
    となります。よって |G/G_x| = |O(x)| が成り立ちます。
  • |G| = |O(x)| \cdot |G_x| が成り立ちます。
  • O^{-1}(O(x)) = O(x) より O^{-1}(i) はある軌道 O(x) に一致します。
  • \displaystyle X = \bigsqcup_{i \in \mathrm{Im}(O)} O^{-1}(i) と軌道に分解できます。
  • \displaystyle |X| = \sum_{i \in \mathrm{Im}(O)} |O^{-1}(i)| が成り立ちます。

(6) シローの定理

G を位数 n の有限群、 p を素数、 n = p^am、 p \not\mid m とします。このとき位数 p^a の G の部分群が存在します。

  • X = \{ S \mid S \subseteq G, \ |S| = p^a \} とおきます。
  • X は p で割り切れないことを証明します。
    • \displaystyle |X| = \binom{n}{p^a} = \prod_{k = 0}^{p^a-1} \frac{n-k}{p^a-k}
    • 0 \le k < p^a、 k = p^bl、 p \not\mid l とします。
    • k は p^a で割り切れないので a > b
    • \displaystyle \frac{n - k}{p^a-k} = \frac{p^am - p^bl}{p^a-p^bl} = \frac{p^{a-b}m - l}{p^{a-b}-l}
      は p で割り切れません。なぜなら p^{a-b}m は p で割り切れ、 l は p で割り切れないので p^{a-b}m - l は p で割り切れないためです。
    • よって X は p で割り切れません。
  • |O(S)| は p で割り切れないことを証明します。
    • \displaystyle |X| = \sum_{i \in \mathrm{Im}(O)} |O^{-1}(i)|
    • i \in \mathrm{Im}(O) が存在して p \not\mid |O^{-1}(i)|
    • S \in X が存在して O^{-1}(i) = O(S)
    • よって p \not\mid |O(S)|
  • H = \mathrm{Stab}(S) = \{ g \in G \mid gS = S \} とおきます。
  • H は G の部分群になります。
  • |H| は p^a の約数であることを証明します。
    • f: S \to \mathfrak{P}(S) を s \mapsto Hs
    • f^{-1}(Hs) = Hs より f^{-1}(i) はある右剰余類 Hs に一致します。
    • \displaystyle |S| = \sum_{i \in \mathrm{Im}(f)} |f^{-1}(i)| = \sum_{i \in \mathrm{Im}(f)} |H| = |\mathrm{Im}(f)| \cdot |H|
    • |H| \mid |S| = p^a
  • |G| = |O(S)| \cdot |H| で |G| = p^am、 |O(S)| は p で割り切れないので |H| は p^a で割り切れます。
  • よって |H| = p^a が成り立ちます。

グラフ理論入門(原書第4版)

グラフ理論入門(原書第4版)

Amazon

可換環論の勘どころ (数学のかんどころ 32)

可換環論の勘どころ (数学のかんどころ 32)

Amazon

代数学２　環と体とガロア理論　第２版

代数学２　環と体とガロア理論　第２版

Amazon

初等整数論入門 (ちくま学芸文庫)

初等整数論入門 (ちくま学芸文庫)

Amazon
発見・予想を積み重ねる ―それが整数論

発見・予想を積み重ねる ―それが整数論

Amazon
はじめての数論　原著第4版

はじめての数論　原著第4版

  • 丸善出版
Amazon
数論序説

数論序説

Amazon

群論 日評ベーシック・シリーズ

群論 日評ベーシック・シリーズ

Amazon
代数学１　群論入門　第２版

代数学１　群論入門　第２版

Amazon
代数学1群と環 (大学数学の入門 1)

代数学1群と環 (大学数学の入門 1)

Amazon
代数系入門 (松坂和夫 数学入門シリーズ 3)

代数系入門 (松坂和夫 数学入門シリーズ 3)

Amazon

数学セミナー2026年6月号　通巻776号【特集】高校生におすすめの整数論

数学セミナー2026年6月号　通巻776号【特集】高校生におすすめの整数論

  • 日本評論社
Amazon

ガウスの黄金定理　平方剰余の相互法則で語る数論の世界 (ブルーバックス)

ガウスの黄金定理　平方剰余の相互法則で語る数論の世界 (ブルーバックス)

Amazon

平方剰余の相互法則: ガウスの全証明

平方剰余の相互法則: ガウスの全証明

Amazon
数論への出発 増補版

数論への出発 増補版

Amazon
共立講座21世紀の数学 (20) 整数論

共立講座21世紀の数学 (20) 整数論

Amazon

証明路開発支援システム(18)

証明路開発支援システム

ChatGPT で「ガウスの補題」を使った証明を調べてみました。『発見・予想を積み重ねる ―それが整数論』、『はじめての数論　原著第4版』の証明や『ガウスの黄金定理　平方剰余の相互法則で語る数論の世界 (ブルーバックス)』の「ガウスの補題」を使った証明と同様と思われます。ChatGPT によると「ガウスの補題と格子点計数」の証明のようですが「アイゼンシュタインの証明」との違いはよくわかりません。この証明は「証明路」にするのは難しそうですが、何かにはできそうです。

まず「ガウスの補題」のための補題を考えます。

整数 x を整数 y \ne 0 で割った余りを x \bmod y とします( 0 \le x \bmod y \le y - 1)。

補題 1

p を奇素数、 a を p と互いに素な整数とします。
S = \left\{1, 2, 3, … , \cfrac{p-1}{2}\right\}
とおきます。
g: \mathbb{Z}→S を

  • x \bmod p ∈ S のとき g(x) = x \bmod p、
  • x \bmod p \not ∈ S のとき g(x) = p - (x \bmod p)
とすると
\displaystyle \sum_{x \in S} g(ax) = \sum_{x \in S} x
\displaystyle \prod_{x \in S} g(ax) = \prod_{x \in S} x
が成り立ちます。

証明

  • f: \mathbb{Z}→\{0, 1\} を
    • x \bmod p ∈ S のとき f(x) = 0、
    • x \bmod p \not ∈ S のとき f(x) = 1
    とします。
  • すると
    • g(x) = (-1)^{f(x)}・(x \bmod p) + pf(x)
    • g(x) \equiv (-1)^{f(x)}・x \pmod p
    となります。
  • h: S→S を h(x) = g(ax) とおくと h は全単射となります。
    • なぜなら h(x) = h(y) とすると
      • g(ax) = g(ay)
      • (-1)^{f(ax)}・ax \equiv (-1)^{f(ay)}・ay \pmod p
      • (-1)^{f(ax)-f(ay)}・ax \equiv ay \pmod p
      • (-1)^{f(ax)-f(ay)}・x \equiv y \pmod p
      x, y \in S なので f(ax) = f(ay) かつ x = y となります。よって h は単射となります。
    • S は有限集合なので h は全単射となります。
  • よって
    \displaystyle \sum_{x \in S} g(ax) = \sum_{x \in S} x
    \displaystyle \prod_{x \in S} g(ax) = \prod_{x \in S} x
    が成り立ちます。

以下は ChatGPT の証明を書き直したものです。

定理 2 (ガウスの補題)

p を奇素数、 a を p と互いに素な整数とします。
\displaystyle a,2a,\ldots,\frac{p-1}{2}a
を法 p で最小絶対値の代表
\displaystyle -\frac{p-1}{2},\ldots,-1,1,\ldots,\frac{p-1}{2}
に直します。この中で負になるものの個数を n(a,p) とすると
\displaystyle \left(\frac ap\right)=(-1)^{n(a,p)}
となります。ここで
\displaystyle \left(\frac ap\right)
はルジャンドル記号です。

証明

  • 補題 1 の f、 g を使って
    \displaystyle \prod_{x \in S} ax \equiv \prod_{x \in S} \left( (-1)^{f(ax)}・g(ax) \right) \equiv \prod_{x \in S} \left( (-1)^{f(ax)} \right)・\prod_{x \in S} g(ax) \equiv \prod_{x \in S} \left( (-1)^{f(ax)} \right)・\prod_{x \in S} x \pmod p
    となります。
  • よって
    \displaystyle a^{\frac{p-1}{2}} \equiv \left(\prod_{x \in S} ax \right)/\left(\prod_{x \in S} x \right) \equiv \prod_{x \in S} \left( (-1)^{f(ax)} \right) \equiv (-1)^{\sum_{x \in S}f(ax)} \equiv (-1)^{n(a,p)} \pmod p
    となります。
  • 「オイラーの規準」より
    \displaystyle \left(\frac ap\right) \equiv a^{\frac{p-1}{2}} \equiv (-1)^{n(a,p)}\pmod p
    となります。
  • \displaystyle \left(\frac ap\right) = 1 または \displaystyle \left(\frac ap\right) = -1 なので
    \displaystyle \left(\frac ap\right) = (-1)^{n(a,p)}
    となります。

定理 3 (平方剰余の相互法則)

p、 q が 2ではない異なる素数のとき、
\displaystyle \left(\frac{q}{p}\right) \left(\frac{p}{q}\right) = (-1)^{ \frac{(p-1)(q-1)}{4} }
が成り立ちます。

証明

Step 1

ガウスの補題より
\displaystyle \left(\frac qp\right)=(-1)^{n(q,p)}
\displaystyle \left(\frac pq\right)=(-1)^{n(p,q)}
となります。したがって
\displaystyle \left(\frac pq\right) \left(\frac qp\right) = (-1)^{n(p,q)+n(q,p)}
となります。

残る仕事は
\displaystyle n(p,q)+n(q,p) \equiv \frac{(p-1)(q-1)}4 \pmod2
を示すことです。

Step 2 格子点を数える

長方形
\displaystyle 0 < x < \frac p2,\qquad 0 < y < \frac q2
の整数格子点を考えます。つまり
\displaystyle 1\le x\le\frac{p-1}2,\qquad 1\le y\le\frac{q-1}2
です。全部で
\displaystyle \frac{(p-1)(q-1)}4
個あります。

Step 3 直線で分ける

直線
\displaystyle qx=py
を引きます。 p,q は互いに素なので、この直線は格子点を通りません。したがって全ての格子点は

  • 上側
  • 下側

のどちらかに入ります。

Step 4 下側の点

下側 \displaystyle py>qx では \displaystyle y > \frac{qx}{p} となるので、各 x に対して
\displaystyle \left\lfloor \frac{qx}{p} \right\rfloor
が現れます。
\displaystyle n(q, p) \equiv \sum_{x=1}^{(p-1)/2} \left\lfloor \frac{qx}{p} \right\rfloor \pmod2
となることを証明します。

  • \displaystyle qx \bmod p \le \frac{p-1}{2} のとき( qx が法 p で「正」のとき)
    • r(x) = qx \bmod p とします。
    • \displaystyle qx = \left\lfloor \frac{qx}{p} \right\rfloor p + r(x)
  • \displaystyle qx \bmod p \ge \frac{p+1}{2} のとき( qx が法 p で「負」のとき)
    • r(x) = p - (qx \bmod p) とします。
    • \displaystyle qx = \left\lfloor \frac{qx}{p} \right\rfloor p + (p - r(x))
    • \displaystyle qx \equiv \left\lfloor \frac{qx}{p} \right\rfloor p + p + r(x) \pmod2
  • n(q, p) は qx が法 p で「負」になる x の個数なので
    \displaystyle \sum_{x=1}^{(p-1)/2}qx \equiv \sum_{x=1}^{(p-1)/2}\left\lfloor \frac{qx}{p} \right\rfloor p + n(q, p)p + \sum_{x=1}^{(p-1)/2}r(x) \pmod2
  • 補題 1 より \displaystyle \sum_{x=1}^{(p-1)/2}r(x) = \sum_{x=1}^{(p-1)/2}x となるので
    \displaystyle q\sum_{x=1}^{(p-1)/2}x \equiv \sum_{x=1}^{(p-1)/2}\left\lfloor \frac{qx}{p} \right\rfloor p + n(q, p)p + \sum_{x=1}^{(p-1)/2}x \pmod2
  • \displaystyle (q - 1)\sum_{x=1}^{(p-1)/2}x \equiv \sum_{x=1}^{(p-1)/2}\left\lfloor \frac{qx}{p} \right\rfloor p + n(q, p)p \pmod2
  • \displaystyle 0 \equiv \sum_{x=1}^{(p-1)/2}\left\lfloor \frac{qx}{p} \right\rfloor p + n(q, p)p \pmod2
  • \displaystyle 0 \equiv \sum_{x=1}^{(p-1)/2}\left\lfloor \frac{qx}{p} \right\rfloor + n(q, p) \pmod2
  • \displaystyle n(q, p) \equiv \sum_{x=1}^{(p-1)/2}\left\lfloor \frac{qx}{p} \right\rfloor \pmod2

Step 5 上側

同様に
\displaystyle n(p, q) \equiv \sum_{y=1}^{(q-1)/2} \left\lfloor \frac{py}{q} \right\rfloor \pmod2

Step 6 合計

長方形の格子点は

  • 上側
  • 下側

に完全に分かれるので
\displaystyle \sum_{x=1}^{(p-1)/2} \left\lfloor \frac{qx}{p} \right\rfloor + \sum_{y=1}^{(q-1)/2} \left\lfloor \frac{py}{q} \right\rfloor = \frac{(p-1)(q-1)}4
です。これと
\displaystyle n(p, q)+n(q, p) \equiv \sum_{x=1}^{(p-1)/2} \left\lfloor \frac{qx}{p} \right\rfloor + \sum_{y=1}^{(q-1)/2} \left\lfloor \frac{py}{q} \right\rfloor \pmod2
より
\displaystyle n(p, q)+n(q, p) \equiv \frac{(p-1)(q-1)}4 \pmod2
となります。したがって
\displaystyle (-1)^{n(p, q)+n(q, p)} = (-1)^{\frac{(p-1)(q-1)}4}
よって
\displaystyle \boxed{\left(\frac pq\right) \left(\frac qp\right) = (-1)^{\frac{(p-1)(q-1)}4}}
が従います。

他の証明

ChatGPT によると

この証明の核心

証明の本質は、

1. ガウスの補題によってルジャンドル記号を「負になる倍数の個数」に置き換える。
2. その個数を格子点の個数として解釈する。
3. 長方形を直線 qx=py で二分することで、二つの個数の和が長方形全体の格子点数になることを示す。

という、数論を幾何学的な格子点計数へ翻訳する点にあります。

以下のような証明があるようです。

他の代表的な証明

平方剰余の相互法則には、ガウス自身だけでも複数の証明を与えており、その後もさまざまな証明が見つかっています。代表的なものとしては次のような方法があります。

  • ガウスの補題と格子点計数（上で説明した古典的な証明）
  • アイゼンシュタインの証明（床関数の和を直接計算する方法）
  • ヤコビ和・ガウス和を用いる解析的な証明
  • 有限体の性質を利用する証明
  • 代数的整数論（円分体など）による証明
  • フーリエ解析や指標和を利用する現代的な証明

特に、ガウスの補題による証明とアイゼンシュタインの証明は非常に近い関係にあり、多くの教科書ではこの二つを並べて扱っています。

グラフ理論入門(原書第4版)

グラフ理論入門(原書第4版)

Amazon

可換環論の勘どころ (数学のかんどころ 32)

可換環論の勘どころ (数学のかんどころ 32)

Amazon

代数学２　環と体とガロア理論　第２版

代数学２　環と体とガロア理論　第２版

Amazon

初等整数論入門 (ちくま学芸文庫)

初等整数論入門 (ちくま学芸文庫)

Amazon
発見・予想を積み重ねる ―それが整数論

発見・予想を積み重ねる ―それが整数論

Amazon
はじめての数論　原著第4版

はじめての数論　原著第4版

  • 丸善出版
Amazon
数論序説

数論序説

Amazon

群論 日評ベーシック・シリーズ

群論 日評ベーシック・シリーズ

Amazon
代数学１　群論入門　第２版

代数学１　群論入門　第２版

Amazon
代数学1群と環 (大学数学の入門 1)

代数学1群と環 (大学数学の入門 1)

Amazon
代数系入門 (松坂和夫 数学入門シリーズ 3)

代数系入門 (松坂和夫 数学入門シリーズ 3)

Amazon

数学セミナー2026年6月号　通巻776号【特集】高校生におすすめの整数論

数学セミナー2026年6月号　通巻776号【特集】高校生におすすめの整数論

  • 日本評論社
Amazon

ガウスの黄金定理　平方剰余の相互法則で語る数論の世界 (ブルーバックス)

ガウスの黄金定理　平方剰余の相互法則で語る数論の世界 (ブルーバックス)

Amazon

平方剰余の相互法則: ガウスの全証明

平方剰余の相互法則: ガウスの全証明

Amazon
数論への出発 増補版

数論への出発 増補版

Amazon
共立講座21世紀の数学 (20) 整数論

共立講座21世紀の数学 (20) 整数論

Amazon