Nielsen-Schreierの定理 自由群の部分群は自由群である．

Nielsen-Schreierの定理は ZF で証明できない．(Nielsen-Schreierの定理から「有限集合の族についての選択公理」が導かれることが知られている．また，Nielsen-Schreierの定理が選択公理を導くかどうかは未解決問題のようだ．)一方，Nielsen-Schreierの定理に条件を付け加えると選択公理と同値になることが知られている．ここではそれを証明する．

G を集合 X で生成される自由群とする．部分集合 A⊂G に対して A^-1 := { a^-1 | a∈A } として A^±1 := A∪A^-1 とする．任意の g∈G は z₁, …, z_n∈X^±1 を使って

g=z₁…z_n　(z₁z₂≠e,…,z_n-1z_n≠e)

と一意に書ける．そこで，この表示に現れる非負整数 n を z の長さといい L(z) で表す．

定義 G を集合 X で生成される自由群とし， A⊂G を部分集合とする．

1. A で生成される G の部分群を <A> と書く．
2. 以下の条件を満たす A をレベル(level)という．
   • <A> は A で生成される自由群である．
   • 任意の b∈<A> に対し b∈< { a∈A | L(a)≦L(b) } > である．
3. 以下の条件を満たす A をNielsen集合という．
   • A∩A^-1= ∅ ．
   • a, b∈A^±1 が L(ab) < L(a) を満たせば ab=e である．
   • a, b, c∈A^±1 が L(abc)≦L(a)-L(b)+L(c) を満たせば ab=e または bc=e である．

補題 Nielsen集合はレベルである．

証明 略([3]を参照)．

定理 次の命題は( ZF 上)同値．

1. 選択公理
2. G を集合 X で生成される自由群とする．任意の部分群 H⊂G は，あるNielsen集合 A⊂G で生成される自由群になる．
3. G を集合 X で生成される自由群とする．任意の部分群 H⊂G は，あるレベル A⊂G で生成される自由群になる．

証明 (1 ⇒ 2)選択公理により X に整列順序を入れて， G に辞書式順序 ◁ を入れる( ^-1 は濁点のように扱って順序を決める)． G に整列順序 ≦ を以下のように定める．

g∈G とする． L(g)=2n とすると g=st^-1 ， s, t∈G ， L(s)=L(t)=n と書ける． s, t のうち( ◁ で)小さい方を g の前半，大きい方を g の後半と呼ぶ． L(g)=2n+1 の場合は g=sct^-1，s, t∈G，c∈X^±1，L(s)=L(t)=n と書ける． s, t のうち( ◁ で)小さい方を g の前半，大きい方を g の後半と呼び，c を g の中央と呼ぶ．g, h∈G，g≠h に対しての順序≦を

• まず長さを比較し， L(g) < L(h) ならば g < h とする．
• 長さが一致した場合は前半を比較し，( g の前半) ◁ ( h の前半)ならば g < h とする．
• 前半も一致した場合は後半を比較し，( g の後半) ◁ ( h の後半)ならば g < h とする．
• 後半も一致した場合，長さが奇数の場合は中央を比較し，( g の中央) ◁ ( h の中央)ならば g < h とする．
• 以上に当てはまらない場合は g=h^-1 である． g=st^-1 もしくは g=sct^-1 と書いたときに， s が前半ならば g < h ， t が前半ならば h < g とする．

により定める． ≦ により G は整列順序集合となる．

g, h∈G が s, t, u∈G により g=st^-1，h=su^-1，L(s)=L(t)=L(u)=L(g)/2=L(h)/2 と書けているとする．このとき st^-1 < su^-1 ならば t◁u である．

定義から明らかに， st^-1 < us^-1 などの場合も同様のことが成り立つ．

Γ(H) をHartogs数として， H に含まれない元 ∞ を一つ取る．写像 f: Γ(H)→H∪{∞} を

f(α) := min(H＼K_α)　(H＼K_α≠ ∅ のとき)
f(α) := ∞　(それ以外のとき)
(ただしK_α := < { f(ξ) | ξ < α } > とする．)

により定めて λ := min{ α∈Γ(H) | f(α)=∞ } として A := { f(α) | α < λ } ⊂H と置く．定義から明らかに H=<A> だから， A がNielsen集合であることを示せばよい．

まず明らかに A∩A^-1= ∅ である．

次に a, b∈A^±1 が L(ab) < L(a) を満たすとする．α, β < λ，ε, δ∈{±1} を使って a=f(α)^ε，b=f(β)^δ と書ける． α < β と仮定する． L(ab) < L(a) だから ab < a であり， a=min(H＼K_α) だから ab∈K_α となる．よって b=a^-1(ab)∈K_α+1 となって b=min(H＼K_β) に矛盾する．故に α≧β である．同様にして α≦β も分かり， α=β となる．よって L(ab) < L(a) となるには ab=e でなければならない．

最後に a, b, c∈A^±1 が L(abc)≦L(a)-L(b)+L(c) を満たすとする． ab≠e ， bc≠e と仮定する． α, β, γ < λ，ε, δ, η∈{±1} を使って a=f(α)^ε，b=f(β)^δ，c=f(γ)^η と書ける．

L(abc)≦L(a)-L(b)+L(c) となるには積 abc において b が全てキャンセルしなければならない．また ab≠e だから L(ab)≧L(a) であり，よって積 ab で b がキャンセルされるのは半分以下である．同様に積 bc で b がキャンセルされるのも半分以下である．従って a=st^-1，b=tu^-1，c=uv^-1，L(t)=L(u)=L(b)/2 と書けることが分かる．

α < β とすると t◁u である．

β < α としても t◁u である．

以上により t◁u であることが分かる．同様の議論を β, γ に対しても行う．まず γ < β とすると u◁t である．

β < γ としても u◁t である．

故に u◁t かつ t◁u となり矛盾し， ab=e または bc=e が分かった．

以上により A はNielsen集合である．

(2 ⇒ 3)補題により明らか．

(3 ⇒ 1) { X_λ }_λ∈Λ を互いに素な非空集合の族とする． Λ∩∪_λ∈ΛX_λ= ∅ としてよい． X := Λ∪∪_λ∈ΛX_λ で生成される自由群を G とする． H⊂G を { xλ³ | λ∈Λ, x∈X_λ } で生成される部分群とすると，仮定3により H はあるレベル A⊂G で生成される自由群である．

λ∈Λ とする．ある x∈X_λ が一意に存在して xλ³∈A^±1 となる．

そこで f(λ):=(xλ³∈A∪A^-1 となる唯一つの x∈X_λ )と定めれば f が選択関数である．