2016年5月29日更新

Lindenbaumの定理

PDF版

定義 S を集合とする.写像 Cn: P(S)→P(S) が S 上のconsequence operationとは以下の条件を満たすことを言う:

  1. X∈P(S) に対して X⊂Cn(X) である.
  2. Cn2 = Cn である.
  3. X, Y∈P(S) について,X⊂Y ならば Cn(X)⊂Cn(Y) である.
  4. X∈P(S) とする.任意の x∈Cn(X) に対してある有限部分集合 Y⊂X が存在して x∈Cn(Y) となる.

集合 S と S 上のconsequence operation Cn の組 <S, Cn> をsystemと呼ぶ.

定義 <S, Cn> をsystemで X∈P(S),x∈S とする.

  1. X が矛盾する ⇔ Cn(X)=S.
  2. X が無矛盾 ⇔ X が矛盾しない.
  3. X が理論 ⇔ Cn(X)=X.
  4. X が極大理論 ⇔ X が無矛盾な理論で,任意の Y⊋X が矛盾する.
  5. X が x-飽和 ⇔ x∉Cn(X) で,任意の y∉X に対して x∈Cn(X∪{y}).
  6. Cn がコンパクト ⇔ 矛盾する任意の X に対して,矛盾する有限部分集合 Y⊂X が存在する.

定理 選択公理 ⇔ <S, Cn> をsystemとして X∈P(S),x∈S とする.x∉Cn(X) ならば x-飽和な理論 Y⊃X が存在する.

証明 (⇒) 選択公理により,ある極限順序数 λ を使って S = { xα | α<λ } と書ける.α≦λに対して Xα

Xα := X (α=0 のとき)
Xα := Xβ∪{xβ} (α=β+1, x∉Cn(Xβ∪{xβ}) のとき)
Xα := Xβ (α=β+1, x∈Cn(Xβ∪{xβ}) のとき)
Xα := ∪β<αXβ (αが極限順序数のとき)

で定義する.Y := Xλ が x-飽和な理論であることを示せばよい.

まず Y が理論であることを示すため,Y⊊Cn(Y) と仮定する.xα∈Cn(Y)\Y となる α<λ が存在する.xα∈Cn(Y) だからある有限部分集合 Z⊂Y が存在して xα∈Cn(Z) となる.Z = { xβ1, …, xβn },β1 < … < βn と書く.このとき βn<α である.

α≦βn と仮定すると

Xα ⊂ Xβn ⊂ Xβn∪{xβn} ⊂ Cn(Xβn∪{xβn})

となる.また Z⊂Xβn∪{xβn} だから xα∈Cn(Z)⊂Cn(Xβn∪{xβn}) であるので,Xα∪{xα} ⊂ Cn(Xβn∪{xβn}) が分かる.故に

x ∈ Cn(Xα∪{xα}) ⊂ Cn(Cn(Xβn∪{xβn})) = Cn(Xβn∪{xβn})

となるが,一方 xβn∈Y = Xλ より x ∉ Cn(Xβn∪{xβn}) となり矛盾する.

よって Z⊂Xα が分かり xα∈Cn(Z)⊂Cn(Xα) である.従って Xα∪{xα} ⊂ Cn(Xα) だから

x ∈ Cn(Xα∪{xα}) ⊂ Cn(Cn(Xα)) = Cn(Xα)

が分かる.よって有限部分集合 W⊂Xα が存在して x∈Cn(W) となる. W = { xγ1, …, xγm } , γ1 < … < γm と書く.W⊂Xα だから γ<α である.また xγm∈Xα となるので x∉Cn(Xγm∪{xγm}) でなければならない.しかし W⊂Xγm∪{xγm} だから x∈Cn(W)⊂Cn(Xγm∪{xγm}) となり矛盾する.以上により Y が理論であることが分かった.

Y が x-飽和であることを示す.まず x∉Cn(Y) を示すため x∈Cn(Y) と仮定する.ある有限部分集合 Z⊂Y が存在して x∈Cn(Z) となる. Z = { xβ1, …, xβn }, β1 < … < βn と書く.xβn∈Y となる為には x ∉ Cn(Xβn∪{xβn}) でなければならない.一方 Z⊂Xβn∪{xβn} だから x∈Cn(Z)⊂Cn(Xβn∪{xβn}) となり矛盾する.故に x ∉ Cn(Y) である.

後は任意の y ∉ Y に対して x∈Cn(Y∪{y}) を示せばよい. y ∉ Y とする. y = xα と書けば, xα ∉ Y = Xλ だから x∈Cn(Xα∪{xα}) である. Xα∪{xα} ⊂ Y∪{xα} より x∈Cn(X∪{xα}) となる.

( ⇐ ) {X_λ}_{λ∈Λ} を互いに素な非空集合の族とする. S := ∪_{λ∈Λ}X_λ として Cn: P(S)→P(S) を, X∈P(S) に対して

Cn(X) := X (ある Σ⊂Λ が存在して X が { Xλ }λ∈Σ の選択集合となるとき)
Cn(X) := S (そうでないとき)

と定める.Cn は明らかにconsequence operationである.

ある μ∈λ に対して |Xμ| > 1 としてよい. a∈Xμ を一つ取る. Cn(∅) = ∅ だから a ∉ Cn(∅) となる.故に仮定により a-飽和な理論 Y⊃∅ が存在する.Y が理論だから Cn(Y) = Y であり,a-飽和だから Cn(Y)⊊S である.故にある Σ⊂Λ が存在して Y は { Xλ }λ∈Σ の選択集合となる.

Σ=Λ を示せばよい.その為に Σ⊊Λ と仮定すると λ∈Λ\Σ が取れる.x∈Xλ を任意にとる(但しλ=μの場合は x≠a としておく).明らかに Y∪{x} は { Xλ }λ∈Σ∪{λ} の選択集合である.x ∉ Y だから, Y が a-飽和であることより a∈Cn(Y∪{x}) かつ a ∉ Cn(Y) = Y である.従って a ∉ Y∪{x} だから Cn(Y∪{x})≠Y∪{x} が分かる.故に Y∪{x} が { Xλ }λ∈Σ∪{λ} の選択集合であることに矛盾する.

定理 選択公理 ⇔ <S, Cn> をsystemとして Cn がコンパクトなとき,任意の無矛盾な理論 X∈P(S) に対して極大理論 Y⊃X が存在する.

証明 ( ⇒ )省略

( ⇐ ) {X_λ}_{λ∈Λ} を互いに素な非空集合の族とする. S := ∪_{λ∈Λ}X_λ として Cn: P(S)→P(S) を, X∈P(S) に対して

Cn(X) := X (ある Σ⊂Λ が存在して X が { Xλ }λ∈Σ の選択集合となるとき)
Cn(X) := S (そうでないとき)

と定める. Cn は明らかにconsequence operationである.

ある μ∈λ に対して |Xμ| > 1 としてよい.すると Cn は明らかにコンパクトである. Cn(∅) = ∅ だから ∅ は無矛盾な理論であり,よって極大理論 Y⊃∅ が存在する.Y が理論だから Cn(Y) = Y であり,無矛盾だから Cn(Y)⊊S である.故にある Σ⊂Λ が存在して Y は { Xλ }λ∈Σ の選択集合となる.

Σ=Λ を示せばよい.その為にΣ⊊Λと仮定するとλ∈Λ\Σが取れる.x∈Xλ を任意にとる.明らかに Y∪{x} は { Xλ }λ∈Σ∪{λ} の選択集合である.x ∉ Y だから,Y が極大理論であることより Cn(Y∪{x}) = S となる.故に Y∪{x} が { Xλ }λ∈Σ∪{λ} の選択集合であることに矛盾する.

参考文献

コメント

コメントはまだありません。

コメントする

感想、意見、質問など何でもどうぞ。
※書き込んだのに表示されない場合は、ページをリロードしてみてください。