ファイル置き場 Sendai Logic Homepage 100730izawa

Mal’cev ^{条件の特徴付け}

東北大学理学研究科数学専攻 井澤 昇平

２０１０年７月３０日 東北大学ロジックセミナー

目次

1

一般代数系の基礎

2

_Mal’cev 条件とは

一般代数系とは

集合A と A 上の演算（の集合）S の対に関する一般的な性質を 研究する分野。「関係記号のない言語を固定して、その構造の全 体像を探る」という研究が主流の模様。

用語

以下では関数記号（と定数記号）のみからなる言語Lを固 定し、Lを作用域と呼ぶ。

L構造のことを代数系と呼ぶ。

一般代数系とは

集合A と A 上の演算（の集合）S の対に関する一般的な性質を 研究する分野。「関係記号のない言語を固定して、その構造の全 体像を探る」という研究が主流の模様。

用語

以下では関数記号（と定数記号）のみからなる言語Lを固 定し、Lを作用域と呼ぶ。

L構造のことを代数系と呼ぶ。

新しい代数系を作る操作１

定義

部分構造を部分（代数）系と呼ぶ。

{A_k}_k∈Kを代数系の族としたとき直積集合に成分毎の演算を 入れた代数系を_{Ak}の直積（代数系）という。

s((a_k)_k)_{i := (s(ai}))_k

新しい代数系を作る操作２

定義₍合同関係・剰余系₎ A を代数系、θ ⊂ A^{2とする。}

θ が^{合同関係であるとは}

(ai,bi) ∈ θ ⇒ (s(ai), s(bi)) ∈ θ

が任意の_{s ∈ L, ai,bi} ∈ A に対して成り立つことをいう。 A の合同関係全体を Con(A) と書く。

θ がA の合同関係のとき、次のように構造を入れた A/θ を A の_{θ による}剰余系と呼ぶ：

s(a_i/θ_{) := s(ai})/θ

定義₍準同型と核₎

A, B：代数系。写像 f : A → B が^{準同型であるとは} f (s_A(a_{i)) = sB}( f (a_i))

が任意の_{s ∈ L と ai} ∈ A に対して成り立つことをいう。 準同型 f : A → B に対し以下を f の核という。

Ker( f ) := {(a1,a₂) ∈ A²| f (a_{1) = f (a2})}

命題₍準同型定理₎

f : A → B を準同型とするとき Ker( f ) は A の合同関係であり、 A/Ker( f ) ≃ Im( f )

が成り立つ。

等式クラスの定義

定義

1 ∀ ¯x(t( ¯x) = t^′( ¯x)) の形の論理式からなる公理系を^{等式公理と} 呼ぶ。

2 等式公理Σ により V = {A|A |= Σ} と書けるクラス V を^等式 クラスと呼ぶ。

一般代数系の研究は等式クラスに関連するものがかなりの割合 を占めているように思われる。

理由は・・・何故か心惹かれるという身も蓋もないものが一番大 きい（？？）

また後述の_cloneという代数系と等式クラスが一対一に対応する という事実があり研究を行ないやすく、一般の代数系のクラスを 考えるときにもそれを含む最小の等式クラスを経由して考える 方が扱いやすいという理由も大きいかも知れない。

等式クラスの定義

定義

1 ∀ ¯x(t( ¯x) = t^′( ¯x)) の形の論理式からなる公理系を^{等式公理と} 呼ぶ。

2 等式公理Σ により V = {A|A |= Σ} と書けるクラス V を^等式 クラスと呼ぶ。

一般代数系の研究は等式クラスに関連するものがかなりの割合 を占めているように思われる。

理由は・・・何故か心惹かれるという身も蓋もないものが一番大 きい（？？）

また後述の_cloneという代数系と等式クラスが一対一に対応する という事実があり研究を行ないやすく、一般の代数系のクラスを 考えるときにもそれを含む最小の等式クラスを経由して考える 方が扱いやすいという理由も大きいかも知れない。

抽象化して初めて考えられる問題

以上は群、環、束など、特殊な代数系の場合に考えられる基本的 な概念のいくつかが、より広い場合においても考えることがで きるということだった。しかし

一般代数系が真に取り組むべき問題は「演算構造が入った集合」 というもの全てを見るという視点に立ったときに初めて意味を 持つ現象を発見することにあると思われる。

例：

V₁, V₂を代数系のクラスとする。V₁とV₂が圏として同型 となる条件を求めよ。

そこに属する有限生成の代数系は集合として有限であるよ うな等式クラスVに対して、ランクn の自由代数系の元の

数を_{FV(n) とおく。FV}が多項式オーダーとなるVの特徴付

けを与えよ。

抽象化して初めて考えられる問題

以上は群、環、束など、特殊な代数系の場合に考えられる基本的 な概念のいくつかが、より広い場合においても考えることがで きるということだった。しかし

一般代数系が真に取り組むべき問題は「演算構造が入った集合」 というもの全てを見るという視点に立ったときに初めて意味を 持つ現象を発見することにあると思われる。

例：

V₁, V₂を代数系のクラスとする。V₁とV₂が圏として同型 となる条件を求めよ。

そこに属する有限生成の代数系は集合として有限であるよ うな等式クラスVに対して、ランクn の自由代数系の元の

数を_{FV(n) とおく。FV}が多項式オーダーとなるVの特徴付

けを与えよ。

抽象化して初めて考えられる問題

以上は群、環、束など、特殊な代数系の場合に考えられる基本的 な概念のいくつかが、より広い場合においても考えることがで きるということだった。しかし

一般代数系が真に取り組むべき問題は「演算構造が入った集合」 というもの全てを見るという視点に立ったときに初めて意味を 持つ現象を発見することにあると思われる。

例：

V₁, V₂を代数系のクラスとする。V₁とV₂が圏として同型 となる条件を求めよ。

そこに属する有限生成の代数系は集合として有限であるよ うな等式クラスVに対して、ランクn の自由代数系の元の 数を_{FV(n) とおく。FV}が多項式オーダーとなるVの特徴付 けを与えよ。

抽象化して初めて考えられる問題（続き）

ある性質を持つ代数系／等式クラスの分類を与えよ。  等式クラスの性質の例：

  非自明な部分等式クラスがない   圏の構造がアーベル圏

 代数系の性質の例：   直積分解できない

  非自明な合同関係がない   部分系の集合が全順序

全く別種の複数の代数系（のクラス）から新しい代数系

（のクラス）を作る操作を考え、その性質を調べる。（例：直 積、Interpretation^）

“ 方程式 ” の解の性質、数の評価

代数論理について：

推論規則の集合K と論理式の集合 T が与えられたとき、論理式 の集合を

ϕ ∼ ψ:⇔ T ⊢_K (ϕ ↔ ψ)

という同値関係で割ったもの（に論理結合子を作用させるとい う演算を入れたもの）をリンデンバーム代数という。_{K のみ固定} し、言語とT を動かしたときに得られるリンデンバーム代数の 全体は

∀ ¯x









∧

i

(t_{i( ¯x) = si}( ¯x)) → t( ¯x) = t( ¯x)









の形の公理によって特徴付けられる。このような=, →, ∧ のみを 用いて書ける論理式はquasi-equation^とかHorn-formula^と呼ば れ、代数論理との関連において注目されている。

（有名な推論規則に対応するリンデンバーム代数のクラスは等 式公理で特徴付けられることが多く、等式クラスのみの考察でも いろいろわかる部分も多いようである。）

定義

K を代数系のクラスとする。F ∈ K が X ⊂ F を自由生成元とす るK の自由（代数）系であるとは、

任意のA ∈ K と写像 f : X → A に対し、g|_{X = f となる準同型} g : F → A がただ一つ存在することをいう。

X の濃度を F のランクという。

命題

等式クラスは任意ランクの自由系を持つ。

証明：_termの全体を公理からt = s が導けるものを同一視する同 値関係で割ったものに自然に演算を入れたものが自由系になる。



定義

K を代数系のクラスとする。F ∈ K が X ⊂ F を自由生成元とす るK の自由（代数）系であるとは、

任意のA ∈ K と写像 f : X → A に対し、g|_{X = f となる準同型} g : F → A がただ一つ存在することをいう。

X の濃度を F のランクという。

命題

等式クラスは任意ランクの自由系を持つ。

証明：_termの全体を公理からt = s が導けるものを同一視する同 値関係で割ったものに自然に演算を入れたものが自由系になる。



定理_(Birkhoff)

L代数系のクラスKが等式クラスである必要十分条件は同型、 部分系、剰余系、直積に閉じていることである。

証明の方針：_(⇒)は容易である。

（⇐）Kに属する全ての代数系がみたす等式公理を_{Σ，Σ が定め} る等式クラスをVとおく。V ⊂ K，すなわちA |= Σ ⇒ A ∈ K を 示せばよいが、K が剰余系に閉じているので任意ランクのVの 自由系がKに入ることを示せばよい。

基数κ に対し、κ 個の変数 {xi^}i∈κ^からなるterm^の対で

ε ≡”t = s” < Σ となるものに対し Aε ^{∈ Kとt( ¯a}ε^{) , s( ¯a}ε^{) となる}

¯

a_{ε = (ai,ε})_i∈κ^{をとる。∏}

ε

A_i^において((a_i,ε)_ε)_i∈κ^は_{Σ に属さない全}

ての関係式を成り立たせない。したがって_{(ai,ε)ε}_i∈κが生成する 部分系がランクκ の V の自由系となる。 _

定理_(Birkhoff)

L代数系のクラスKが等式クラスである必要十分条件は同型、 部分系、剰余系、直積に閉じていることである。

証明の方針：_(⇒)は容易である。

（⇐）Kに属する全ての代数系がみたす等式公理を_{Σ，Σ が定め} る等式クラスをVとおく。V ⊂ K，すなわちA |= Σ ⇒ A ∈ K を 示せばよいが、K が剰余系に閉じているので任意ランクのVの 自由系がKに入ることを示せばよい。

基数κ に対し、κ 個の変数 {xi^}i∈κ^からなるterm^の対で

ε ≡”t = s” < Σ となるものに対し Aε ^{∈ Kとt( ¯a}ε^{) , s( ¯a}ε^{) となる}

¯

a_{ε = (ai,ε})_i∈κ^{をとる。∏}

ε

A_i^において((a_i,ε)_ε)_i∈κ^は_{Σ に属さない全}

ての関係式を成り立たせない。したがって_{(ai,ε)ε}_i∈κが生成する 部分系がランクκ の V の自由系となる。 _

定理_(Birkhoff)

L代数系のクラスKが等式クラスである必要十分条件は同型、 部分系、剰余系、直積に閉じていることである。

証明の方針：_(⇒)は容易である。

（⇐）Kに属する全ての代数系がみたす等式公理を_{Σ，Σ が定め} る等式クラスをVとおく。V ⊂ K，すなわちA |= Σ ⇒ A ∈ K を 示せばよいが、K が剰余系に閉じているので任意ランクのVの 自由系がKに入ることを示せばよい。

基数κ に対し、κ 個の変数 {xi^}i∈κ^からなるterm^の対で

ε ≡”t = s” < Σ となるものに対し Aε ^{∈ Kとt( ¯a}ε^{) , s( ¯a}ε^{) となる}

¯

a_{ε = (ai,ε})_i∈κ^{をとる。∏}

ε

A_i^において((a_i,ε)_ε)_i∈κ^は_{Σ に属さない全} ての関係式を成り立たせない。したがって_{(ai,ε)ε}_i∈κが生成する 部分系がランクκ の V の自由系となる。 _

定義

1 _{代数系の族{Ai}}に対し以下の条件をみたす_{∏ Ai}の部分系_B を_{Ai}のsub-direct product^とよぶ：

全ての_{i に対して射影∏ Ai} →→ A_i^のB への制限は全射。

2 代数系B はどんな B が {A_i}のsub-direct product となるどん な_{Ai}をとっても、必ず_{B ≃ Ai}となる_{i があるとき}

sub-directly irreducible^{であるという。}

sub-direct product^{をとる操作は“ 関係式を消去 ” すること} に他ならない。

代数系のクラスKを固定したとき、K での_sub-direct prodctへの分解の仕方を系統的に調べ、さらにsub-directly

irreducibleな代数系の分類を与えることでKの構造を調べ

るという道筋が考えられる。

定義

1 _{代数系の族{Ai}}に対し以下の条件をみたす_{∏ Ai}の部分系_B を_{Ai}のsub-direct product^とよぶ：

全ての_{i に対して射影∏ Ai} →→ A_i^のB への制限は全射。

2 代数系B はどんな B が {A_i}のsub-direct product となるどん な_{Ai}をとっても、必ず_{B ≃ Ai}となる_{i があるとき}

sub-directly irreducible^{であるという。}

sub-direct product^{をとる操作は“ 関係式を消去 ” すること} に他ならない。

代数系のクラスKを固定したとき、K での_sub-direct prodctへの分解の仕方を系統的に調べ、さらにsub-directly

irreducibleな代数系の分類を与えることでKの構造を調べ

るという道筋が考えられる。

Mal’cev条件とは

２． _Mal’cev 条件とは

1 一般代数系の基礎

2 _Mal’cev条件とは

Mal’cev条件とは

定理(Mal’cev 1954)

Vを等式クラスとするとき、次は同値。

1 任意のA ∈ V, α, β ∈ Con(A) に対し α ∨ β = α ◦ β．^（Vは congruence permuratable.）

2 次の条件をみたす_Vの３項term p が存在する。 V |= ∀x, y[p(x, x, y) = y ∧ p(x, y, y) = x]. 定理(J´onson 1967)

等式クラスVに対し次は同値。

1 任意のA ∈ V に対し Con(A) は分配束。

2 次をみたすn ∈ N と３項 term d₀, ···,d_n^{が存在する：} d0(x, y, z) = x, dⁿ(x, y, z) = z

d_i(x, y, x) = x (i = 0, ···, n)

d_i(x, x, y) = di+1(x, x, y) (i : even) di(x, y, y) = di+1(x, y, y) (i : odd)

Mal’cev条件とは

定理(Mal’cev 1954)

Vを等式クラスとするとき、次は同値。

1 任意のA ∈ V, α, β ∈ Con(A) に対し α ∨ β = α ◦ β．^（Vは congruence permuratable.）

2 次の条件をみたす_Vの３項term p が存在する。 V |= ∀x, y[p(x, x, y) = y ∧ p(x, y, y) = x]. 定理(J´onson 1967)

等式クラスVに対し次は同値。

1 任意のA ∈ V に対し Con(A) は分配束。

2 次をみたすn ∈ N と３項 term d₀, ···,d_n^{が存在する：} d0(x, y, z) = x, dⁿ(x, y, z) = z

d_i(x, y, x) = x (i = 0, ···, n)

d_i(x, x, y) = di+1(x, x, y) (i : even) di(x, y, y) = di+1(x, y, y) (i : odd)

Mal’cev条件とは

定理_{(Day 1969)}

等式クラスVに対し次は同値。

1 任意のA ∈ V に対し Con(A) はモジュラー束。

2 次をみたすn ∈ N と４項 term m₀, ···,m_n^{が存在する：} m₀(x, y, z, u) = x, mn(x, y, z, u) = u

m_i(x, y, y, x) = x (i = 0, ···, n)

m_i(x, x, y, y) = mi+1(x, x, y, y) (i : even) m_i(x, y, y, z) = mi+1(x, y, y, z) (i : odd)

このような“ ある条件をみたす_termが存在する ” という形の等 式クラスに対する条件を_Mal’cev条件と呼ぶ。

Mal’cev条件とは

定義

Vを等式クラス、_TnをVのn 項 term の全体とし（V で常に同 一の演算を定めるものを同一視する）_{xn,i ∈ Tn}を変数記号、 c_n,m : T_n^m× T_m→ T_n^を

c_n,m((t₁, ···,t_m), s) := s(t1, ···,t_n) と定める。

({Tn^}n∈N, {cn,m^}n,m∈N, {xn,i^}n∈N,1≤i≤n) を V の clone といい C(V) と かく。

cloneはもとの等式クラスの本質的情報（_termを一義的なものと

考え、何が演算記号であるかを気にしない立場から見たときの 構造：definitionally equivalence）を完全に表現している。また、 等式クラスの_cloneとなりうる構造の特徴付けも容易に与えるこ とができる。

Mal’cev条件とは

定義

以下の条件をみたす対_({Cn}_{n∈N, {cn,m}}_{n,m∈N, {pn,i}}_{n∈N,1≤i≤n) を clone} という：

各_Cnは集合。 cn,m : C^m_n × C_m→ C_n.

p_n,i ∈ C_n

c_n,l((c_n,m((x_i)^m_i=1,y_j))^l_j=1,_{z) = cn,m}((x_i)^m_i=1,c_m,l((y_j)^l_j=1,z)). c_n,m((x_i)^m_i=1,p_{j) = xj}.

c_n,n((p_i)ⁿ_i=1,_{y) = y.} 定理

等式クラスのclone は clone である。また、任意の clone C に対し C(V) = C となる等式クラス V が存在し、V は定数記号の有無と definitionally equivalent を除いて一意に定まる。

Mal’cev条件とは

定義_(Mal’cev条件の現代的な定義₎ Cをclone のクラスとする。

1 _Cが狭義Mal’cev クラスであるとは有限表示 clone C₀^によっ て以下の形に書けることをいう：

C = {C| 準同型 C0 → C が存在する }．

2 _CがMal’cev クラスであるとは狭義 Mal’cev 条件の可算増加 列C₀ ⊂ C₁⊂ ···の和集合_{C =}

∪

i∈N

C_iとなることをいう。

例

等式クラスVがcongruence permutable である条件は

C_{P := ⟨x|c3,3}(p_3,1,p_3,1,p_3,2,_{x) = p3,2},c_3,3(p_3,1,p_3,2,p_3,2,_{x) = p3,1}⟩

からC(V) への準同型が存在することである。

Mal’cev条件とは

定義_(Mal’cev条件の現代的な定義₎ Cをclone のクラスとする。

1 _Cが狭義Mal’cev クラスであるとは有限表示 clone C₀^によっ て以下の形に書けることをいう：

C = {C| 準同型 C0 → C が存在する }．

2 _CがMal’cev クラスであるとは狭義 Mal’cev 条件の可算増加 列C₀ ⊂ C₁⊂ ···の和集合_{C =}

∪

i∈N

C_iとなることをいう。

例

等式クラスVがcongruence permutable である条件は

C_{P := ⟨x|c3,3}(p_3,1,p_3,1,p_3,2,_{x) = p3,2},c_3,3(p_3,1,p_3,2,p_3,2,_{x) = p3,1}⟩ からC(V) への準同型が存在することである。

Mal’cev条件とは

定理(Taylor 1973)

clone のクラス C が（狭義） Mal’cev クラスである必要十分条件 は以下が成り立つことである。

1 C ∈ C であり準同型 C → C^{′が存在するなら}C^{′ ∈ C．}

2 _Cは有限直積（任意個数の直積）に閉じている。

3 C ∈ C なら有限表示 clone C₀^で、C₀∈ C^{かつ準同型}C₀ → C が存在するようなものが存在する。

証明の概略：必要性は容易である。

S = {C ∈ C|^{Cは有限表示}} = {A1, ···} とおく。B1_{:= A}1^{とし、以下}

帰納的に_Bn+1を_An と _Bn のsubdirect product^{である有限表示} cloneとする。C_n = {C ∈ C| 準同型 Bn→ C が存在する } とおくと C =^{∪ C}n^となる。

Cが可算直積に閉じていて、狭義 _Mal’cevクラスでないとすると C_n ∈ C_n+1\ C_nをとると_{C = ∏ Cn}∈ C_mとなるm ∈ N がとれ、C

の剰余_cloneである_CmがC_mに入ることになり矛盾 _

Mal’cev条件とは

定理(Taylor 1973)

clone のクラス C が（狭義） Mal’cev クラスである必要十分条件 は以下が成り立つことである。

1 C ∈ C であり準同型 C → C^{′が存在するなら}C^{′ ∈ C．}

2 _Cは有限直積（任意個数の直積）に閉じている。

3 C ∈ C なら有限表示 clone C₀^で、C₀∈ C^{かつ準同型}C₀ → C が存在するようなものが存在する。

証明の概略：必要性は容易である。

S = {C ∈ C|^{Cは有限表示}} = {A1, ···} とおく。B1_{:= A}1^{とし、以下}

帰納的に_Bn+1を_An と _Bn のsubdirect product^{である有限表示} cloneとする。C_n = {C ∈ C| 準同型 Bn→ C が存在する } とおくと C =^{∪ C}n^となる。

Cが可算直積に閉じていて、狭義 _Mal’cevクラスでないとすると C_n ∈ C_n+1\ C_nをとると_{C = ∏ Cn}∈ C_mとなるm ∈ N がとれ、C

の剰余_cloneである_CmがC_mに入ることになり矛盾 _

Mal’cev条件とは

定理(Taylor 1973)

clone のクラス C が（狭義） Mal’cev クラスである必要十分条件 は以下が成り立つことである。

1 C ∈ C であり準同型 C → C^{′が存在するなら}C^{′ ∈ C．}

2 _Cは有限直積（任意個数の直積）に閉じている。

3 C ∈ C なら有限表示 clone C₀^で、C₀∈ C^{かつ準同型}C₀ → C が存在するようなものが存在する。

証明の概略：必要性は容易である。

S = {C ∈ C|^{Cは有限表示}} = {A1, ···} とおく。B1_{:= A}1^{とし、以下}

帰納的に_Bn+1を_An と _Bn のsubdirect product^{である有限表示} cloneとする。C_n = {C ∈ C| 準同型 Bn→ C が存在する } とおくと C =^{∪ C}n^となる。

Cが可算直積に閉じていて、狭義 _Mal’cevクラスでないとすると C_n ∈ C_n+1\ C_nをとると_{C = ∏ Cn}∈ C_mとなるm ∈ N がとれ、C

の剰余_cloneである_CmがC_mに入ることになり矛盾 _

Mal’cev条件とは

参考文献

1 W. Taylor, Characterizing Mal’cev conditions, Algebra Universalis 3 (1973), 351-397

2 Stanley N. Burris and H.P. Sankappanavar, A Course in Universal Algebra The Millennium Edition, Springer-Verlag

3 Ralph Freese and Ralph McKenzie, Commutator Theory for Congruence Modular Varieties Second Edition,^{ウェブ上で} 公開

4 David Hobby and Ralph McKenzie, The Structure of Finite Algebras, American Mathematical Society, 1988

5 George M.Bergman, An Invitation to General Algebra and Universal Constructions, 1998