圏論/代数系/関係, 同値関係のソースを表示

<div id="関係">
<div id="関係\rhoにある">
<div id="関係\rhoをみたす>
<div id="内部関係">
<div id="2.1">
<strong>2.1</strong>
<math>A, B</math> を集合とする．
集合論的直積 <math>A\times B=\{(a, b)|a\in A, b\in B\}</math> の（任意に定められた）部分集合 <math>\rho</math> を
<math>A</math> の元と <math>B</math> の元の間の'''関係'''という．

<math>(a, b)\in \rho</math> のとき <math>a</math> と <math>b</math> は'''関係 <math>\rho</math> にある'''，
または'''関係 <math>\rho</math> をみたす'''といい，
このとき <math>\rho(a, b)</math> あるいは <math>a\rho b</math> と書く．特に <math>A=B</math> のとき <math>\rho</math> は
'''<math>A</math> の内部関係'''，または単に '''<math>A</math> 上の関係''' という．

<div id="弱い関係">
<div id="強い関係">
<div id="交">
<math>A</math> の元と <math>B</math> の元との間に他の[[圏論/代数系/関係, 同値関係#関係|関係]] <math>\sigma</math> があり，<math>A\times B</math> の部分集合として
<math>\sigma \subset \rho</math> であるとき，<math>\sigma</math> は <math>\rho</math> より'''弱い'''関係，
<math>\rho</math> は <math>\sigma</math> より'''強い'''関係という．これは <math>a\sigma b</math> ならば <math>a\rho b</math>
でることと同等である．また <math>\Sigma</math> が <math>A</math> の元と <math>B</math> の元の間の[[圏論/代数系/関係, 同値関係#関係|関係]]の族であるとき，
<math>A\times B</math> の中でのその集合論的共通部分を <math>\bigwedge\Sigma</math> であらわす．
<math>\sigma=\bigwedge\Sigma</math> であるとき <math>a\sigma b</math> であることとすべての <math>\rho\in\Sigma</math> について
<math>a\rho b</math> であることとは同等である．
<ref>
<math>a\in A, b\in B</math> を先に決めて、それに対して <math>\Sigma</math> に属する一つ一つの関係 <math>\rho \in \Sigma</math> を順次あてはめていく。
大抵の場合は、特定の関係 <math>\rho</math> にて <math>(a, b) \notin \rho</math>，すなわち関係 <math>\rho</math> はなりたたない、ということになるが、
<math>(a, b)</math> の組によっては、すべての関係 <math>\rho \in \Sigma</math> について <math>(a, b) \in \rho</math>，いいかえると <math>a\rho b</math> となる組 <math>(a, b)</math> が存在するかもしれない．そういう <math>(a, b)</math> が存在するのなら、<math>(a, b)</math> は <math>\Sigma</math> の[[圏論/代数系/関係, 同値関係#交|交]] <math>\bigwedge\Sigma</math> に含まれている。
</ref>
この <math>\sigma</math> を <math>\Sigma</math> の'''交'''という．


<div id="同値条件">
<div id="同値関係">
<div id="同値である">
<div id="2.2">
<strong>2.2</strong>
<math>A</math> は集合，<math>\rho</math> はその上の[[圏論/代数系/関係, 同値関係#関係|関係]]とする．<math>\rho</math> が <math>A</math> の中で条件
<div id="反射律">
;'''反射律'''
: すべての元 <math>a</math> に対して <math>a\rho a</math>
</div>

<div id="対象律">
;'''対称律'''
: 各元 <math>a</math>, <math>b</math> に対して <math>a\rho b</math> ならば <math>b\rho a</math>
</div>

<div id="推移律">
;'''推移律'''
: 各元 <math>a</math>, <math>b</math>, <math>c</math> に対して <math>a\rho b</math> かつ <math>b\rho c</math> ならば <math>a\rho c</math>
</div>

を同時にみたすとき，<math>\rho</math> は <math>A</math> の上で'''同値条件'''をみたす，または'''同値関係'''であるといい，
<math>\rho</math> が[[圏論/代数系/関係, 同値関係#同値関係|同値関係]]であるとき <math>a \rho b</math> である <math>a</math> と <math>b</math> は <math>\rho</math> について互いに'''同値である''' という．



<div id="2.3">
<strong>2.3</strong>
<math>\rho</math> が <math>A</math> の上の[[圏論/代数系/関係, 同値関係#同値関係|同値関係]]のとき，各 <math>a\in A</math> に対して

<math>U_{\rho}(a)=\{x\in A|x\rho a\}</math>

とおく．<math>\rho</math> の[[圏論/代数系/関係, 同値関係#反射律|反射律]]から各 <math>a\in A</math> について <math>a\in U_{\rho}(a)</math> で特に <math>U_{\rho}(a)\ne\phi</math>．
また <math>c\in U_{\rho}(a)\cap U_{\rho}(b)</math> のとき，<ref>
そのような <math>c</math> が仮に存在した場合の論議が続き，結論は <math>U_{\rho}(a)\subset U_{\rho}(b), U_{\rho}(b)\subset U_{\rho}(a)</math> を経て <math>U_{\rho}(a)=U_{\rho}(b)</math>．
</ref>
[[圏論/代数系/関係, 同値関係#対称律|対称律]]から <math>a\in U_{\rho}(c)</math> で<ref>
<math>c \in U_{\rho}(a) \cap U_{\rho}(b)</math> より <math>c \in U_{\rho}(a)</math>．<math>\therefore c \in \{ x \in A | x \rho a \}</math>．
これに[[圏論/代数系/関係, 同値関係#対称律|対称律]]を適用して <math>c \in \{ x \in A | a \rho x \}</math>．
<math>\therefore a \rho c</math>．
<math>\therefore a \in \{ x \in A | x \rho c \}</math>．
<math>\therefore a \in U_{\rho}(c)</math>．
</ref>，
よって <math>x\in U_{\rho}(a)</math> なら[[圏論/代数系/関係, 同値関係#推移律|推移律]]から <math>x\in U_{\rho}(c)</math> で，さらに <math>x\in U_{\rho}(b)</math>
<ref>
<math>\forall x \in A</math>について<math>x \in U_{\rho}(a)</math> のとき
<math>\forall x (\in A) x \rho a</math>，…① <br />
<math>c \in U_{\rho}(a)</math> より <math>a \rho c</math>，…②<br />
①②より[[関係, 同値関係#推移律|推移律]]から <math>\forall x(\in A) x \rho c </math>．…③<br />
<math>c \in U_{\rho}(a) \cap U_{\rho}(b)</math> より <math>c \in U_{\rho}(b)</math>．<math>\therefore c \rho b</math>．…④<br />
③④より[[関係, 同値関係#推移律|推移律]]から <math>\forall x(\in A) x \rho b</math>．<math>\therefore x \in A</math> について <math>x \in U_{\rho}(b)</math>
</ref>
すなわち <math>U_{\rho}(a)\subset U{\rho}(b)</math>．
同様にして <math>U_{\rho}(b)\subset U{\rho}(a)</math>
<ref>
<math>c\in U_{\rho}(a)\cap U_{\rho}(b)</math> より 
<math>c\in U_{\rho}(b)</math>．これと[[圏論/代数系/関係, 同値関係#対称律|対称律]]より <math>\therefore b \rho c</math>…①，<br />
また <math>c\in U_{\rho}(a)</math>．<math>\therefore c \rho a</math>…②，<br />
今 <math>\forall x \in A</math> で <math>x \in U_{\rho}(b)</math> のとき…③、<br />
③より <math>\forall x(\in A) x \rho b</math>…④<br />
④①より[[関係, 同値関係#推移律|推移律]]から <math>\forall x (\in A) x \rho c</math>．<br />
これと②より[[関係, 同値関係#推移律|推移律]]から <math>\forall x (\in A) x \rho a</math>．<br />
すなわち <math>\forall x (\in A) \in U_{\rho}(a)</math>．…⑤ <br />
③⑤はすなわち <math>\forall x (\in A) \in U_{\rho}(b)</math> ならば <math> \forall x (\in A) \in U_{\rho}(a)</math>．<math>\therefore U_{\rho}(b) \subset U_{\rho}(a)</math>．
</ref>
で，従って <math>U_{\rho}(a)=U{\rho}(b)</math> となる．よって
<div id="類別">
<div id="同値類">
<div id="関係\rhoから導かれた類別">
<math>\mathfrak{U}=\{X|</math> ある <math>a\in A</math> について <math>X=U_{\rho}(a)\}</math>

とおけば <math>\mathfrak{U}</math> は <math>\mathfrak{P}(A)</math> の部分集合<ref>
各々の <math>X</math> に重なりがある可能性を含んでベキ集合として把握する． 
</ref>
で三つの条件<br />
<math>1^\circ\quad\  </math> どの <math>X \in \mathfrak{U}</math> も空ではない <br />
<math>2^\circ\quad\  </math> <math>X, Y \in \mathfrak{U}</math> ならば <math>X \cap Y = \phi</math> であるかまたは <math>X = Y</math> である　<br />
<math>3^\circ\quad\  </math> <math>\bigcup\mathfrak{U} = A</math><ref>
<math>\blacktriangle</math> <math>\bigcup</math> の下に添え字がないときは <math>\bigcup\mathfrak{U}</math> は <math>\bigcup_{X \in \mathfrak{U}}X</math> を表す．<math>\bigcap\mathfrak{U}</math> についても同様
</ref>

をみたす．<math>\mathfrak{P}(A)</math> の部分集合 <math>\mathfrak{U}</math> がこの三条件をみたすとき <math>\mathfrak{U}</math> は <math>A</math> の'''類別'''といい，
各 <math>X \in \mathfrak{U} </math> はこの類別の'''同値類'''という．また <math>\rho</math> から上のように定められた <math>\mathfrak{U}</math> を
<math>\rho</math> から '''導かれた類別'''という．

逆に <math>\mathfrak{U}</math> が <math>A</math> の任意の[[圏論/代数系/関係, 同値関係#類別|類別]]のとき，<math>a, b</math> が同一の <math>X \in \mathfrak{U}</math> に属するとき
<math>a\rho b</math> とすれば，<math>\rho</math> は <math>A</math> 上の[[圏論/代数系/関係, 同値関係#同値関係|同値関係]]となり，もとの <math>\mathfrak{U}</math> は[[圏論/代数系/関係, 同値関係#関係\rhoから導かれた類別|これから導かれた類別]]となる<ref>.
</ref>．



<div id="含意型">
<div id="終結式">
<div id="仮設式">
<div id="2.4">
<strong>2.4</strong>
[[圏論/代数系/関係, 同値関係#2.2|2.2]] の中で考察された <math>\rho</math> についての三つの条件，
[[圏論/代数系/関係, 同値関係#反射律|反射律]]，
[[圏論/代数系/関係, 同値関係#対称律|対称律]]，
[[圏論/代数系/関係, 同値関係#推移律|推移律]]
はすべて次の形をしているのに気がづく．

”すべての元 <math>a, b, c, d, \cdots, x, y</math> について（これらの変数のいくつかは同一のものであってもよい），
もし <math>a \rho b</math>，<math>c \rho d</math>，<math>\cdots</math>（これらを'''仮設式'''という）であるならば
<math>x \rho y</math> (これを'''終結式'''という）である．”

[[圏論/代数系/関係, 同値関係#関係|関係]]に関する条件がこの形をしているとき，この条件は '''含意型'''であるという．

[注] 特別な場合として[[関係, 同値関係#反射律|反射律]]のように[[圏論/代数系/関係, 同値関係#仮設式|仮設式]]の集合が空であってもかまわない．
この場合[[圏論/代数系/関係, 同値関係#終結式|終結式]]が無条件に成立つことを意味する．

<strong>補題　</strong>

<math>\alpha</math> が集合 <math>A</math> の上の関係に関する[[圏論/代数系/関係, 同値関係#含意型|含意型]]の条件，<math>\Sigma</math> は <math>A</math> の上の関係のある族とする．
もしすべての <math>\rho \in \Sigma</math> が <math>\alpha</math> をみたすなら <math>\sigma \in \bigwedge \Sigma</math> も <math>\alpha</math> をみたす．

<strong>証明　</strong>
<math>A</math> の元<math>a, b, c, d, \cdots</math> に対して <math>\sigma</math> が <math>\alpha</math> の各[[圏論/代数系/関係, 同値関係#仮設式|仮設式]] <math>a \sigma b</math> 等を成立させたとする．
このときすべての <math>\rho \in \Sigma</math> について <math>a\rho b</math> 等が成立ち，
よってすべての <math>\rho\in\Sigma</math> に対して[[圏論/代数系/関係, 同値関係#終結式|終結式]] <math>x\rho y</math> が成立つ．
従って <math>x\sigma y</math> で <math>\sigma</math> は <math>\alpha</math> をみたす．（証明終）

<strong>系　</strong>
<math>\Sigma</math> が集合 <math>A</math> 上の[[圏論/代数系/関係, 同値関係#同値関係|同値関係]]の集合ならば <math>\bigwedge\Sigma</math> も[[圏論/代数系/関係, 同値関係#同値関係|同値関係]]である．



<div id="粗い">
<div id="細かい">
<div id="2.5">
<strong>2.5</strong>
<math>\rho</math> と <math>\sigma</math> が共に集合 <math>A</math> 上の[[圏論/代数系/関係, 同値関係#同値関係|同値関係]]で，
<math>\rho</math> が <math>\sigma</math> より[[圏論/代数系/関係, 同値関係#強い関係|強]]ければ
<math>a, x\in A</math> について <math>x\sigma a</math> ならば <math>x \rho a </math> となり，よって <math>U_\sigma (a) \subset U_\rho (a)</math>．
従って <math>\sigma</math> による[[圏論/代数系/関係, 同値関係#同値類|同値類]]はすべて <math>\rho</math> による一つの[[圏論/代数系/関係, 同値関係#同値類|同値類]]の部分集合となる．<ref>
例えば <math>\sigma</math> は '<math>=</math>'，<math>\rho</math> は合同（剰余系）の'<math>\equiv</math>'．
</ref>
一般に <math>A</math> の二つの[[圏論/代数系/関係, 同値関係#類別|類別]] <math>\mathfrak{U}, \mathfrak{B}</math> があり，<math>\mathfrak{U}</math> の各[[圏論/代数系/関係, 同値関係#同値類|同値類]]が <math>\mathfrak{B}</math>
の一つの[[圏論/代数系/関係, 同値関係#同値類|同値類]]に含まれるとき，<math>\mathfrak{U}</math> は <math>\mathfrak{B}</math> より '''細かい'''，
<math>\mathfrak{B}</math> は <math>\mathfrak{U}</math> より '''粗い'''という．
[[圏論/代数系/関係, 同値関係#同値関係|同値関係]]は[[圏論/代数系/関係, 同値関係#強い関係|強]]いほど対応する[[圏論/代数系/関係, 同値関係#類別|類別]]は[[圏論/代数系/関係, 同値関係#粗い|粗]]くなり，
特に [[圏論/代数系/関係, 同値関係#2.4|2.4]] の系に現れる <math>\bigwedge \Sigma</math> を <math>\sigma</math> とすれば，
<math>U_{\sigma}(a)=\bigcap\{ U_\rho(a)|\rho \in \Sigma \}</math> が成り立つ．



<div id="同一関係">
<div id="全称関係">
<strong>2.6</strong>
'''同一関係''' <math>=</math> はすべての[[圏論/代数系/関係, 同値関係#同値関係|同値関係]]の中で最も[[圏論/代数系/関係, 同値関係#弱い関係|弱い]]ものであり，
またすべての元 <math>a, b</math> に対して <math>a\upsilon b</math> とした'''全称関係''' <math>\upsilon</math> 
はどのような[[圏論/代数系/関係, 同値関係#関係|関係]]よりも[[圏論/代数系/関係, 同値関係#強い関係|強い]][[圏論/代数系/関係, 同値関係#同値関係|同値関係]]である．さらに一般に

<strong>定理　</strong>
<math>\tau</math> を集合 <math>A</math> の上の任意に与えられた[[圏論/代数系/関係, 同値関係#関係|関係]]とするとき，
<math>\tau</math> より[[圏論/代数系/関係, 同値関係#強い関係|強い]][[圏論/代数系/関係, 同値関係#同値関係|同値関係]]の中で最も[[圏論/代数系/関係, 同値関係#弱い関係|弱い]]もの <math>\sigma</math> が
存在する．

<strong>証明 </strong>
<math>\Sigma</math> を <math>\tau</math> より[[圏論/代数系/関係, 同値関係#強い関係|強い]][[圏論/代数系/関係, 同値関係#同値関係|同値関係]]全体の集合とすれば、
[[圏論/代数系/関係, 同値関係#全称関係|全称関係]]は <math>\Sigma</math> に入るから <math>\Sigma</math> は空ではない．
<math>\sigma = \wedge \Sigma</math> とすればよい。（証明終）

また同じことであるが，<math>a\sigma b</math> の条件として <math>a=b</math> であるかまたは


<div id="\tau鎖">
<div id="\tau鎖条件">
<div id="\tauから生成された同値関係>
<strong><math>\tau</math> 鎖条件：</strong> 元 <math>x_1, x_2, \cdots , x_{n - 1}</math> が存在し，
さらに <math>x_0 = a, x_n = b</math> として、

各 <math>k = 1, 2, \cdots, n</math> に対して <math>x_{k - 1}\tau x_{k}</math> であるかまたは
<math>x_k \tau x_{k - 1}</math> である

がみたされることにすればよい．<ref>
これは必要条件である．
</ref>
このような <math>x_1, x_2, \cdots , x_{n - 1}</math> を
<math>a</math> と <math>b</math> とを結ぶ '''<math>\tau</math> 鎖''' という．
上のように定めた <math>\sigma</math> が[[圏論/代数系/関係, 同値関係#同値関係|同値関係]]であること、また <math>\sigma</math> が
<math>\tau</math> より[[圏論/代数系/関係, 同値関係#強い関係|強い]][[圏論/代数系/関係, 同値関係#同値関係|同値関係]]であれば，[[圏論/代数系/関係, 同値関係#\tau鎖|<math>\tau</math>鎖]]で結ばれる二元 <math>a, b</math> に対して
<math>a\sigma b</math> に対して <math>a\sigma b</math> でなければならないことは明らかである．
上の <math>\sigma</math> を <math>\tau</math> から'''生成された'''同値関係という．



<strong>2.7　</strong>
<math>n</math> を正の整数とするとき、<math>a, b \in Z</math> に対して
<math>a - b</math> が <math>n</math> の倍数であるという[[圏論/代数系/関係, 同値関係#関係|関係]]
<math>a \equiv b \pmod n</math> は[[圏論/代数系/関係, 同値関係#同値条件|同値条件]]である．
<math>m</math> も正の整数のとき，[[圏論/代数系/関係, 同値関係#関係|関係]] <math>a \equiv b \pmod m</math> が
<math>a \equiv b \pmod n</math> より[[圏論/代数系/関係, 同値関係#強い関係|強くなる]]のは <math>m</math> が <math>n</math> の約数のときに限る．

同様に実数 <math>a, b</math> に対して
<math>a - b</math> が整数であるという[[圏論/代数系/関係, 同値関係#関係|関係]] <math>a \equiv b \pmod 1</math>，
<math>a - b</math> が有理数であるという[[圏論/代数系/関係, 同値関係#関係|関係]] <math>a \equiv b \pmod Q</math>，
<math>a - b</math> が代数的数であるという[[圏論/代数系/関係, 同値関係#関係|関係]] <math>q \equiv b \pmod{Alg. no.}</math>
等は <math>R</math> 上の[[圏論/代数系/関係, 同値関係#同値関係|同値関係]]で、この順に[[圏論/代数系/関係, 同値関係#強い関係|強く]]なっている．

<div id="対称差">
集合 <math>X, Y</math> に対して <math>X \triangle Y = (X \cup Y) - (X \cap Y)</math> を
<math>X</math> と <math>Y</math> の'''対称差''' という。
<math>X \triangle Y</math> が有限であるという[[圏論/代数系/関係, 同値関係#関係|関係]] <math>X \equiv Y \pmod{\mathfrak{a}}</math>，
<math>X \triangle Y</math> がある無限濃度 <math>\mathfrak{m}</math> より小さいという[[圏論/代数系/関係, 同値関係#関係|関係]]
<math>X \equiv Y \pmod{\mathfrak{m}}</math> は[[圏論/代数系/関係, 同値関係#同値関係|同値関係]]で，特に後者は <math>\mathfrak{m}</math>
が大きいほど[[圏論/代数系/関係, 同値関係#強い関係|強く]]なる．


<references/>
{{DEFAULTSORT:かんけいとうちかんけい}}
[[category:数学]]
[[category:圏論]]