離散数学及び演習 講義13

代数系の間の関係


離散数学及び演習
講義13 2014. 7.10（木）2限代数系


商系（教科書 pp.165-168 ）組（X，f1，…，fn）
 X は集合2
 f ： X → X
i

代数系（X，f1，…，fn），（Y，g1，…，gn）の間の関係
部分系（前回講義）
準同型，同型 （前回講義）

商系



教科書･･･野崎昭弘：離散系の数学、近代科学社
2

合同関係（congruent relation）

合同関係（続き）

集合 X 上の2項演算 f と同値関係～ に対して，～ は f と両立する（compatible）（～ は f に関して合同（congruent）である）

例： p∈ZZ 上の同値関係≡p，演算＋，・



任意の x，x’，y，y’∈X に対して，x～ x’かつ y～y’ならば，f （ x，y ）～ f （ x’，y’）X［ f （ x，y ）］f （ x，y ）f （ x’，y’）

ffx［x］≡p は＋，・ と両立する （≡p は＋，・ に関して合同である）
 任意の m，m’，n，n’∈Z に対して，m ≡p m’かつ n ≡p n’ならば，
m＋n ≡p m’＋n’， m・n ≡p m’・n’

y’
yx’

［y］
34商系（quotient system）


商系（quotient system）

代数系（X，f ）と f に関する X 上の合同関係～ に対する商系（X／～，f ～ ）

X／～ … 同値関係～による X の同値分割（商集合）f ～ ： （X／～）2 → X／～
任意の ［x］，［y］∈X／～ に対して，
f ～（［x］，［y］）＝［ f （x，y）］
X代数系（X，f ）と f に関する X 上の合同関係～ に対する商系（X／～，f ～ ）［ f （ x，y ）］f （ x，y ）≡p ＝{（m，n）｜ m ≡ n （mod p）} ⊆ Z2

X／～ … 同値関係～による X の同値分割（商集合）f ～ ： （X／～）2 → X／～
任意の ［x］，［y］∈X／～ に対して，
f ～（［x］，［y］）＝［ f （x，y）］
X ／～［ f （ x，y ）］f （ x’，y’）

ff［x］xx’

f～y’
y［y］

［x］
5［y］
61

離散数学及び演習 講義13

商系（続き）
商系（続き）Z 上の合同関係≡3

同値分割 Z／≡3＝{［3k＋r］｜k∈Z，r＝0，1，2 } ≡3 は演算＋，・ に関して両立している
 商系（ Z／≡3 ，＋，・ ） を定義できる
ただし，任意の ［m］，［n］∈Z／≡3 に対して，
 ［m］＋［n］＝［m＋n］，
 ［m］・［n］＝［m・n］.
例： 4，5∈Z［0］＝［3］［4］＝［1］ ， ［5］＝［2］［4］＋［5］＝［4＋5］＝［9］＝［0］ ［1］＝［4］［1］＋［2］＝［1＋2］＝［3］＝［0］［4］・［5］＝［4・5］＝［20］＝［2］ ［2］＝［5］［1］・［2］＝［1・2］＝［2］Z 上の合同関係≡3
同値分割 Z／≡3＝{［3k＋r］｜k∈Z，r＝0，1，2 }≡3 は演算＋，・ に関して両立している
 商系（ Z／≡3 ，＋，・ ） を定義できる
 ただし，任意の ［m］，［n］∈Z／≡3 に対して， ［m］＋［n］＝［m＋n］，
 ［m］・［n］＝［m・n］.



Z… 0 3 6 9 …
… 1 4 7 10 …

例： 4，5∈Z

… 2 5 8 11 …

7

商系（続き３）
［0］（＝［3］＝［6］＝…）［1］（＝［4］＝［7］＝…）［2］（＝［5］＝［8］＝…）
8定理

商系（ Z／≡3 ，＋，・ ） 上の演算
［4］＝［1］ ， ［5］＝［2］［4］＋［5］＝［4＋5］＝［9］＝［0］［1］＋［2］＝［1＋2］＝［3］＝［0］［4］・［5］＝［4・5］＝［20］＝［2］［1］・［2］＝［1・2］＝［2］Z ／≡3

任意の ［m］，［n］∈Z／≡3 に対して，
 ［m］＋［n］＝［m＋n］，
 ［m］・［n］＝［m・n］.

p∈Z に対して，商系（Z／≡p ，＋，・） は可換環である．
ただし，任意の ［m］，［n］∈Z／≡p に対して，
 ［m］＋［n］＝［m＋n］，
 ［m］・［n］＝［m・n］.

加算表＋ ［0］ ［1］ ［2］［0］ ［0］ ［1］ ［2］

［0］ ［0］ ［0］ ［0］［1］ ［1］ ［2］ ［0］［1］ ［0］ ［1］ ［2］［2］ ［2］ ［0］ ［1］［2］ ［0］ ［2］ ［1］・乗算表［0］ ［1］ ［2］（ Z／≡p ，＋，・ ）… p∈Z を法とする剰余環（residue class ring）

910

証明

証明（続き）p∈Z に対して，商系（ Z／≡p ，＋，・ ） は可換環である．
 a） 「演算＋，・ は Z／≡p 上で閉じている」を示す．
 b） 「（ Z／≡p ，＋，・ ）は可換環の公理を満たす」を示す．

p∈Z に対して，商系（ Z／≡p ，＋，・ ） は可換環である．
b） 「（ Z／≡p ，＋，・ ）は可換環の公理を満たす」を示す．

b-2） ［0］∈ Z／≡p を考えると，任意の ［m］∈Z／≡p に対して，［m］＋［0］＝［m＋0］＝［m］，［0］＋［m］＝［0＋m］＝［m］だから，［m］＋［0］＝［0］＋［m］＝［m］．
すなわち，［0］は加法の単位元である．
b-3） 任意の ［m］∈Z／≡p に対して， ［－m］∈Z／≡pを考えると，［m］＋［－m］＝［m＋（－m）］＝［0］，［－m］＋［m］＝［（－m）＋m］＝［0］だから，［m］＋［－m］＝［－m］＋［m］＝［0］．
すなわち，［m］に対して ［－m］は加法の逆元である．

a）定義から明らかに，演算＋，・ は Z／≡p 上で閉じている．
b-1） 任意の ［m］，［n］，［k］∈Z／≡p に対して，（［m］＋［n］）＋［k］＝ ［m＋n］＋［k］＝ ［（m＋n）＋k］＝ ［m＋（n＋k）］＝ ［m］＋［n＋k］＝ ［m］＋（［n］＋［k］）．
ゆえに，加法の結合則は成り立つ．
11122

離散数学及び演習 講義13

証明（続き２）定理

p∈Z に対して，商系（ Z／≡p ，＋，・ ） は可換環である．
次の（1），（2）が成り立つ．
（1） p∈Z に対して，剰余環（Z／≡p，＋，・）は整数環（Z，＋，・）に準同型である．
（2） p∈N に対して，剰余環（Z／≡p，＋，・）と環（Zp，＋p，・p）は同型である．
ただし，Zp＝{ 0，1，…，p－1 }（完全代表系）．

b） 「（ Z／≡p ，＋，・ ）は可換環の公理を満たす」を示す．

b-4） 加法の交換則は成り立つ．
b-5） 乗法の結合則は成り立つ．
b-6） ［1］∈ Z／≡p を考えると，任意の ［m］∈Z／≡p に対して，［m］・［1］＝［m・1］＝［m］，［1］・［m］＝［1・m］＝［m］
だから，［m］・［1］＝［1］・［m］＝［m］．
すなわち，［1］は乗法の単位元である．
b-7） 分配則は成り立つ．
b-8） 乗法の交換則は成り立つ．
以上から， （ Z／≡p ，＋，・ ） は可換環である．

［m］∈ Z／≡p と m∈ Zp を同一視すれば，（Z／≡p ，＋，・） と（Zp ，＋p ，・p ）は「同じもの」．

1314整数環・完全代表系と剰余環［0］…

… 2 5 8 11 …

|… …

Z… 0 3 6 9 …
… 1 4 7 10 …

準同型［2］［1］証明Z ／≡3（1） p∈Z に対して， （Z／≡p ，＋，・） は（Z，＋，・）に準同型．
 「準同型 |： Z→ Z／≡p が存在する」を示す．

|| ： Z→ Z／≡p を次のように定義する．
任意の n∈Z に対して，| （n）＝［n］．

任意の n∈Z に対して，|（n）＝［n］．
同型（準同型・全単射）

Z3|

0［0］

1［1］

2［2］

このとき，任意の m，n∈Z に対して，|（m＋n）＝［m＋n］ ＝ ［m］＋［n］ ＝ |（m）＋| （n），|（m・n）＝［m・n］ ＝ ［m］・［n］ ＝ |（m）・|（n）．
ゆえに，| は準同型である．

Z ／≡3|

任意の n∈Z3 に対して，|（n）＝［n］．
1516

証明（続き）

商系における合同関係（2） p∈N に対して，（Z／≡p，＋，・）と（Zp，＋p，・p）は同型．
 a） 「準同型 |： Zp → Z／≡p が存在する」を示す．
 b） 「| は全単射である」を示す．

代数系（X／～，f ～ ）

X 上の同値関係～は f に関して両立していないとする
a） | ： Zp → Z／≡p を次のように定義する．
任意の n∈Zp に対して，|（n）＝［n］．
（1）と同様に，| は準同型である．
b-1） 任意の m，n∈Zp に対して， |（m）＝ |（n）とする．
このとき， ［m］＝［n］．すなわち， m≡p n．
0 m，n＜p だから， m＝ n ．ゆえに，| は単射である．
b-2） 任意の n∈Z に対して， q，r∈Z が存在して， n＝qp＋r （0 r＜|p|）．
このとき，n≡p r．
ゆえに，任意の ［n］∈Z／≡p に対して， r∈Zp が存在して，| （r）＝ ［r］＝［n］．
ゆえに，| は全射である．
以上から， （Z／≡p，＋，・）と（Zp，＋p，・p）は同型である．

X 上の同値関係～は f に関する合同関係ではないとする

任意の ［x］，［y］∈X／～ に対して，f ～ （ ［x］，［y］ ）＝［ f （x，y）］とする．
 このとき，矛盾が生じる．


商系の定義の際には，同値関係～が f と両立していることが必要．

同値関係～は f に関して両立していないので，ある x，x’，y，y’∈Z に対して，x～x’かつ y～y’であるが， f （x，y）～ f （x’，y’）でない．
ところで， f ～ （ ［x］，［y］ ）＝［ f （x，y）］．
また， x～x’かつ y～y’ だから， ［x］＝［x’］かつ ［y］＝［y’］．
ゆえに， f ～ （ ［x］，［y］ ）＝ f ～ （ ［x’］，［y’］ ）＝［ f （x’，y’）］．
すなわち， ［ f （x，y）］＝［ f （x’，y’）］だから， f （x，y）～ f （x’，y’）．
18
これは矛盾．

173離散数学及び演習 講義13

ベクトル空間集合 V はベクトル空間（線形空間）である．
V は次の I，II を満たす．
I （ベクトル加法の公理）
任意の a，b∈V に対して，a＋b∈V が定義され，次の（1）～（4）を満たす．
（1） （a＋b）＋c ＝ a＋（b＋c）（結合則）（2） 任意のa∈V に対して，0∈V が存在して，a＋0 ＝ 0＋a ＝a（単位元の存在）（3） 任意のa∈V に対して，－a∈V が存在して，a＋（－a）＝（－a）＋a ＝0（逆元の存在）（4） a＋b ＝b＋a（交換則）［参考］ベクトル空間（全学共通科目・線形代数学Ⅱ １年後期）

20ベクトル空間（続き）

ベクトル空間の例

集合 V はベクトル空間（線形空間）である．
V は次の I，II を満たす．
II （スカラー乗法の公理）
任意の a∈V と任意の k∈R に対して，ka∈V が定義され，次の (1)～(4) を満たす．
(1) h（ka） ＝ （hk ）a（結合則）(2) （h＋k ）a ＝ ha＋ka（分配則）(3) k（a＋b） ＝ ka＋kb（分配則）(4) 1a＝aすべての n 次元数ベクトルからなる集合
Rn＝｛ t（a0，a1，…，an）｜ai∈R （i＝1，2，…，n） ｝
 すべての m×n 行列からなる集合M（m，n）
 すべての 1 変数実係数多項式からなる集合
R［x］＝｛ anxn＋…＋a1 x＋a0 ｜ai∈R （i＝0，1，…，n） ｝


すべての実数列からなる集合
閉区間［a，b］上のすべての連続関数からなる集合 同次連立1次方程式 Ax=0 のすべての解からなる集合
 微分方程式 f  x   pf  x   qf  x   0 （p，q∈R） のすべての解からなる集合



2122

ベクトル空間（続き２）線形写像

集合 V はベクトル空間（線形空間）である．
V は次の I，II を満たす．
I （ベクトル加法の公理）
任意の a，b∈V に対して，a＋b∈V が定義され，次の（1）～（4）を満たす．
（1） （a＋b）＋c ＝ a＋（b＋c）（結合則）（2） 任意のa∈V に対して，0∈V が存在して，a＋0 ＝ 0＋a ＝a（単位元の存在）（3） 任意のa∈V に対して，－a∈V が存在して，a＋（－a）＝（－a）＋a ＝0（逆元の存在）（4） a＋b ＝b＋a（交換則）

ベクトル空間 V ，W に対して，写像 f ：V→W は線形写像である
 任意の a，b∈V と任意の k∈R に対して，次の（1），（2）を満たす．
（1） f（a＋b） ＝ f（a）＋f（b）（2） f（ka） ＝ k f（a）

V

fa＋b＋f（a＋b ）＝ f（a）＋f（b）＋fab

ベクトル空間（V，＋，0）は可換群である

W

ff（a）
f（b）

f は群準同型である

23

424

離散数学及び演習 講義13

まとめ

今日の講義

商系





試験範囲： 講義1～13（全体）
持込み不可
教室： 演習時と同じ
演習問題解答例（pdf 版）



評価区分



（1限）部分系，準同型（2限）商系
解答用紙は提出不要





なし

集合論
 整数論
 代数系


概念を客観的かつ論理的に表現，論証するための手法・技術の習得約30％

2011年度以降入学者
Ｓ：100～90，Ａ： 89～ 80，Ｂ： 79～70，Ｃ：69～60，Ｆ：59～0
2010年度以前入学者
優：100～80，良：79～70，可：69～60，不可： 59～0
期末試験を欠席した場合は，「欠席」とする．

来年度も同じクラスで受講
26

離散的対象に関する知識の習得
様々な分野に対する基礎的知識の習得



約30％
約40％

不合格の場合

講義の目的（再掲）





25



演習板書

http://www.kl.i.is.nagoya-u.ac.jp/~toyama/lecture/risan14/

今日の演習



次回の演習（7／17）




中間試験
期末試験
小テスト
演習解答

期末試験（7／24 2 限）

成績評価（再掲）

数学的表現
論証技術

講義目的の達成度＝成績評価基準275