Equivalence Relation and Partition

UCPC 2022 예선

글 읽기 - UCPC 2022 예선이 종료되었습니다!

25323번: 수 정렬하기, 근데 이제 제곱수를 곁들인

25323번: 수 정렬하기, 근데 이제 제곱수를 곁들인

 

이번 UCPC 해설 덕분에 명확하게 알게 된 성질을 정리해보았다.

TL;DR: An equivalence relation on a nonempty set \(X\) gives rise to a partition of \(X\).

 

다음은 Set Theroy: An Intuitive Approach의 Chapter 3 일부를 인용하여 정리한 것이다.

 

A relation \(R\) from \(A\) to \(B\) is a subset of the Cartesian product \(A \times B\).

It is customary to write \(aRb\) for \((a, b) \in R \).

 

Let \(R\) be a relation in a set \(X\). Then we say that

(1) \(R\) is reflexive iff \(\forall x \in X, xRx \).

(2) \(R\) is symmetric iff \(x R y \Rightarrow y R x\).

(3) \(R\) is transitive iff \(x R y \wedge y R z \Rightarrow x \wedge z \).

(4) \(R\) is an equivalence relation iff \(R\) is reflexive, symmetric, and transitive.

 

Let \(\mathcal{E}\) be an equivalence relation on a nonempty set \(X\). For each \(x \in X\), we define \(x / \mathcal{E}\) = \(\{y \in X | y \mathcal{E} x\}\) which is called the equivalence class determined by the element \(x\).

The set of all such equivalence classes in \(X\) is denoted by \(X / \mathcal{E}\); that is, \(X / \mathcal{E} = \{x/\mathcal{E} | x \in X\}\).

 

Let \(X\) be a nonempty set. By a partition \(P\) of \(X\) we mean a set of nonempty subsets of \(X\) s.t

(1) If \(A, B \in P\) and \(A \neq B\), then \(A \cap B = \emptyset\).

(2) \( \bigcup_{C \in P} C = X \)

 

Let \(\mathcal{E}\) be an equivalence relation on a nonempty set \(X\). The \(X/\mathcal{E}\) is a partition of \(X\).

i) \(X / \mathcal{E} = \{x / \mathcal{E} | x \in X\}\) is a family of nonempty subsets of \(X\).

ii) \(x / \mathcal{E} \neq y / \mathcal{E} \Rightarrow (x / \mathcal{E}) \cap (y / \mathcal{E}) = \emptyset\)

iii) \(\bigcup_{x \in X} x / \mathcal{E} = X\)