0. Relations, Binary Operations

Set

집합은 굳이 할 말이 없다. 집합이 잘 정의되어 있는 것은 모두가 안다. 짚고 넘어가야 할 집합과 관련한 정의는 아래의 몇 개 뿐이다.

• $S$의 공집합이 아닌 부분집합들의 집합 $\mathcal{P}$에 대해서, $S$의 임의의 원소는 $\mathcal{P}$의 딱 하나의 원소에만 포함되면 $\mathcal{P}$를 $S$의 partition이라 하고, $\mathcal{P}$의 원소들을 각각 cell이라 한다.
• $\bar{x}$를 $S$의 partition에서 $x$를 포함하는 cell로 정의한다.

Relation

Relation은 우리가 아는 $=$나 $<$ 같은 이항 관계를 생각하면 된다. 정의하면 다음과 같다.

• Relation $\mathscr{R}$ between sets $A$ and $B$는 $A\times B$의 부분집합이다.
• $(a,b)\in\mathscr{R}$을 $a\ \mathscr{R}\ b$라 표기한다.

 

특별히, $A=B$일 때는 Relation $\mathscr{R}$ on $A$라 표기한다.

함수도 relation으로 정의한다.

• Funtion $\phi$ mapping $X$ into $Y$는 relation between $X$ and $Y$로, $X$의 임의의 원소가 $\phi$의 원소의 첫 번째 원소에 딱 한 번만 나타나는 relation이다.
• 이때 표기는 $\phi: X\to Y$이며, $(x, y)\in\phi$이면 $\phi(x)=y$로 나타낸다.

 

솔직히 이것들은 그냥 우리가 원래 알던 대로 생각해도 뒤의 내용에 크게 영향이 가지 않는다.

Equivalence Relation

Def. Equivalence relation $\sim$ on $S$는 모든 $x, y, z\in S$에 대해 다음 세 조건을 만족하는 relation on $S$이다.

• Reflexive(반사성): $x\sim x$
• Symmetric(대칭성): $x\sim y \Longrightarrow y\sim x$
• Transitive(추이성): $x\sim y \wedge y\sim z \Longrightarrow x\sim z$

 

통상 아는 $=$는 위의 정의에 따라 자명하게 동치 관계이다.

위의 다양한 쓸데없어 보이는 것들은 아래 정리를 위해서 나온 것이라 생각한다.

---

Thm. 공집합이 아닌 집합 $S$ 위에서 정의된 동치 관계 $\sim$은 $\bar{a}=\{x\in S\mid x\sim a\}$가 각각의 cell이 되는 분할을 만든다. 반대로, $S$의 분할은 $a\sim b$가 $\bar{a}=\bar{b}$일 때 만족하는 동치 관계 $\sim$를 생성한다.

 

Proof. 동치 관계의 반사성에 의해 $\forall a\in S$에서 $a\in\bar{a}$. 만일 $a\in\bar{b}$이면 $a\sim b$이므로 $b\sim a$, 따라서 $x\in\bar{b}\Longleftrightarrow x\sim b\Longleftrightarrow x\sim a \Longleftrightarrow x\in\bar{a}$, 즉 $\bar{a}=\bar{b}$이므로 $S$의 각 원소는 하나의 cell에만 속함. 반대로, $S$의 분할에서 정의되는 동치 관계 $\sim$는 동치 관계의 조건을 모두 만족하므로 성립.

---

동치 관계의 정의와 마지막 정리는 쓸데가 좀 있다. 그 위는 사족이다. Fraleigh 0장은 여기서 끝이지만, 사실 Binary Operation까지도 0장에 포함되어야 한다고 생각한다.

Binary Operation

Def. Binary Operation $\ast $ on $S$는 $\ast :S\times S\to S$인 함수이며, $\ast ((a, b))$를 $a\ast b$로 표기한다.

Def. (Commutativity) Binary Operation $\ast $ on $S$가 $\forall a,b\in S, a\ast b=b\ast a$를 만족할 때 $\ast $를 commutative(가환)이라고 한다.

Def. (Associativity) Binary Operation $\ast $ on $S$가 $\forall a,b,c\in S, (a\ast b)\ast c=a\ast (b\ast c)$를 만족할 때 $\ast $를 associative라고 한다.

Def. (Identity Element) Binary Operation $\ast $ on $S$에 대해서, $\exists e\in S:\forall a\in S, a\ast e=e\ast a=a$이면 $e$를 $\ast $의 Identity Element(항등원)이라고 한다.

---

Thm. 하나의 이항 연산은 항등원이 존재하면 유일하다.

 

Proof. $e, e'$을 $\ast $의 항등원이라 하면, $e=e\ast e'=e'$.

---

Def. (Inverse Element) Identity Element $e$를 가지는 Binary Operation $\ast $ on $S$와 $S$의 원소 $a$에 대해서, $\exists x\in S: x\ast a=a\ast x=e$이면 이때 $x$를 $a$의 Inverse Element(역원)이라 한다.

---

Thm. 한 원소의 역원이 존재하면 유일하다.

 

Proof. $x, y$를 $a$의 역원이라 하면 $x=x\ast (a\ast y)=(x\ast a)\ast y=y$.

---