同値類
Def
$ \sim を集合$ S で定義された同値関係とする。$ a \in S に対し、 $ C(a) = \{ x | x \in S, a \sim x \}
Prop 1
$ x \sim y \Leftrightarrow C(x) = C(y)
Proof 1
必要性
$ x \sim y のとき、$ a \in C(x) \Rightarrow a \sim x と推移律から$ a \sim y \Rightarrow a \in C(y) 、よって$ C(x) \subset C(y)
この議論の$ x, y を入れ替えて$ C(y) \in C(x) 、よって$ C(x) = C(y)
十分性
逆に$ C(x) = C(y) のとき$ x \in C(x) \Rightarrow x \in C(y) \Rightarrow x \sim y
Prop 2
$ C(x) \ne C(y) \Leftrightarrow C(x) \cap C(y) = \emptyset
Proof 2
必要性
対偶を示す。$ C(x) \cap C(y) \ne \emptyset とすると$ a \in C(x) かつ$ a \in C(y) なる$ a が取れる。
よって$ a \sim x, a \sim y より$ x \sim y よってProp 1より$ C(x) = C(y)
十分性
対偶を示す。$ C(x) = C(y) とすると$ x \sim x より$ x \in C(x) 、よって$ x \in C(y) だから$ x \in C(x) \cap C(y)
よって$ C(x) \cap C(y) \ne \emptyset
NOTE
$ a の同値類を$ [a] とか$ \overline a などと書くこともある