圏論/代数系/関係, 同値関係
2.1 を集合とする. 集合論的直積 の(任意に定められた)部分集合 を の元と の元の間の関係という.
のとき と は関係 にある, または関係 をみたすといい, このとき あるいは と書く.特に のとき は の内部関係,または単に 上の関係 という.
の元と の元との間に他の関係 があり, の部分集合として であるとき, は より弱い関係, は より強い関係という.これは ならば でることと同等である.また が の元と の元の間の関係の族であるとき, の中でのその集合論的共通部分を であらわす. であるとき であることとすべての について であることとは同等である. [1] この を の交という.
2.2 は集合, はその上の関係とする. が の中で条件
- 反射律
- すべての元 に対して
- 対称律
- 各元 , に対して ならば
- 推移律
- 各元 , , に対して かつ ならば
を同時にみたすとき, は の上で同値条件をみたす,または同値関係であるといい, が同値関係であるとき である と は について互いに同値である という.
2.3 が の上の同値関係のとき,各 に対して
とおく. の反射律から各 について で特に . また のとき,[2]対称律から で[3], よって なら推移律から で,さらに [4] すなわち . 同様にして [5] で,従って となる.よって
ある について
とおけば は の部分集合[6]
で三つの条件
どの も空ではない
ならば であるかまたは である
[7]
をみたす. の部分集合 がこの三条件をみたすとき は の類別といい, 各 はこの類別の同値類という.また から上のように定められた を から 導かれた類別という.
逆に が の任意の類別のとき, が同一の に属するとき とすれば, は 上の同値関係となり,もとの はこれから導かれた類別となる[8].
2.4 2.2 の中で考察された についての三つの条件, 反射律, 対称律, 推移律 はすべて次の形をしているのに気がづく.
”すべての元 について(これらの変数のいくつかは同一のものであってもよい), もし ,,(これらを仮設式という)であるならば (これを終結式という)である.”
関係に関する条件がこの形をしているとき,この条件は 含意型であるという.
[注] 特別な場合として反射律のように仮設式の集合が空であってもかまわない. この場合終結式が無条件に成立つことを意味する.
補題
が集合 の上の関係に関する含意型の条件, は の上の関係のある族とする. もしすべての が をみたすなら も をみたす.
証明 の元 に対して が の各仮設式 等を成立させたとする. このときすべての について 等が成立ち, よってすべての に対して終結式 が成立つ. 従って で は をみたす.(証明終)
2.5 と が共に集合 上の同値関係で, が より強ければ について ならば となり,よって . 従って による同値類はすべて による一つの同値類の部分集合となる.[9] 一般に の二つの類別 があり, の各同値類が の一つの同値類に含まれるとき, は より 細かい, は より 粗いという. 同値関係は強いほど対応する類別は粗くなり, 特に 2.4 の系に現れる を とすれば, が成り立つ.
2.6 同一関係 はすべての同値関係の中で最も弱いものであり, またすべての元 に対して とした全称関係 はどのような関係よりも強い同値関係である.さらに一般に
定理 を集合 の上の任意に与えられた関係とするとき, より強い同値関係の中で最も弱いもの が 存在する.
証明 を より強い同値関係全体の集合とすれば、 全称関係は に入るから は空ではない. とすればよい。(証明終)
また同じことであるが, の条件として であるかまたは
鎖条件: 元 が存在し, さらに として、
各 に対して であるかまたは である
がみたされることにすればよい.[10] このような を と とを結ぶ 鎖 という. 上のように定めた が同値関係であること、また が より強い同値関係であれば,鎖で結ばれる二元 に対して に対して でなければならないことは明らかである. 上の を から生成された同値関係という.
2.7 を正の整数とするとき、 に対して が の倍数であるという関係 は同値条件である. も正の整数のとき,関係 が より強くなるのは が の約数のときに限る.
同様に実数 に対して が整数であるという関係 , が有理数であるという関係 , が代数的数であるという関係 等は 上の同値関係で、この順に強くなっている.
集合 に対して を と の対称差 という。 が有限であるという関係 , がある無限濃度 より小さいという関係 は同値関係で,特に後者は が大きいほど強くなる.
- ^ を先に決めて、それに対して に属する一つ一つの関係 を順次あてはめていく。 大抵の場合は、特定の関係 にて ,すなわち関係 はなりたたない、ということになるが、 の組によっては、すべての関係 について ,いいかえると となる組 が存在するかもしれない.そういう が存在するのなら、 は の交 に含まれている。
- ^ そのような が仮に存在した場合の論議が続き,結論は を経て .
- ^ より .. これに対称律を適用して . . . .
- ^
について のとき
,…①
より ,…②
①②より推移律から .…③
より ..…④
③④より推移律から . について - ^
より
.これと対称律より …①,
また .…②,
今 で のとき…③、
③より …④
④①より推移律から .
これと②より推移律から .
すなわち .…⑤
③⑤はすなわち ならば .. - ^ 各々の に重なりがある可能性を含んでベキ集合として把握する.
- ^ の下に添え字がないときは は を表す. についても同様
- ^ .
- ^ 例えば は '', は合同(剰余系)の''.
- ^ これは必要条件である.