정의
${ n }$-ary relation
주어진 집합 ${ A }$와 음이 아닌 정수 ${n}$ 대해, ${ n }$-ary relation은 ${ R }$ 다음과 같이 정의된다.
\[R \subseteq A^{n}\]여기서 ${ A^{n} }$은 A의 ${ n }$-tuple들의 집합이다.
binary relation
\[R \subseteq A \times A\]일 때 relation ${ R }$을 binary relation이라고 하고,
${ (x,y) \in R }$ 이면, ${ xRy }$라고 적자.1
${ A }$ 위의 모든 binary relation을 모은 class를 다음과 같이 표기한다.
domain과 range
${ R }$이 ${ A }$ 위의 binary relation이라고 하자. ${ R }$의 domain과 range는 각각 다음과 같이 정의된다.
\[\begin{gather} \mbox{(domain)} & \mathrm{dom}(R):= \{ x \in A : xRy \mbox{ for some } y \in R\} \\ \mbox{(range)} & \mathrm{ran}(R):= \{y \in A: xRy \mbox{ for some } x\in R \} \end{gather}\]따라서 임의의 binary relation은 다음 성질을 만족한다.
\[R \subseteq \mathrm{dom}(R) \times \mathrm{ran}(R)\]마지막으로 field는 다음과 같이 정의된다.
\[\begin{gather} \mathrm{field} (R):= \mathrm{dom}(R)\cup \mathrm{ran}(R) \end{gather}\]inverse relation
${ R }$이 ${ A }$ 위의 binary relation 일때 그것의 inverse relation ${ R^{-1} }$은 다음과 같이 정의된다.
\[xR^{-1}y \mbox{ iff } yRx\]inverse operator ${ ^{-1} }$는 다음 성질을 만족한다.
\[(R^{-1})^{-1}=R\]image와 preimage
${ R }$이 ${ A }$ 위의 binary relation이고 ${ B \subseteq A}$일 때
\[\begin{gather} \mbox{(image)} & R[B]=\{ y \in A: xRy \mbox{ for some } x \in B \} \\ \mbox{(preimage)} & R^{-1}[B] = \{ x \in A : xRy \mbox{ for some } y\in B \} \end{gather}\]Remark ${ R }$의 image는 ${ R^{-1} }$의 preimage와 같다.
composition
${ R }$과 ${ S }$가 각각 ${ A }$와 ${ B }$ 위의 binary relation이라고 하자, composition ${ R \circ S }$는 다음과 같이 정의된다.
\[R \circ S =\{ (x,y) : xRz \mbox{ and } zSy \mbox{ for some } z \in A \}\]Exercise ${ (R \circ S)^{-1}=S^{-1} \circ R^{-1} }$ 임을 보여라.
Exercise ${ (R \circ S) \circ T = R \circ (T \circ S) }$임을 보여라. 이런 성질을 associativity라고 한다.
binary relation의 속성들
${ R }$이 ${ A }$ 위의 binary operation이라고 하자.
Reflexivity (Refl)
\[\forall x \in A, \quad xRx\]Strictness (Stric)
\[\nexists x \in A, \quad xRx\]Symmetry (Sym)
\[\forall x,y \in A, \quad xRy \Rightarrow yRx\]Antisymmetry (ASym)2
\[\forall x,y \in A, \quad xRy \Rightarrow yRx\]Transitivity (Trans)
\[\forall x,y,z \in A, \quad xRy \mbox{ and } yRz \Rightarrow xRz\]Linearlity (Lin)
\[\forall x,y \in A, \quad xRy \mbox{ or } yRx\]Univalence (Unival)
\[\forall x_{1},x_{2} \in \mathrm{dom}(R), \exists y \in \mathrm{ran}(R), \quad x_{1}Ry \mbox{ and } x_{2}Ry \Rightarrow x_{1}=x_{2}\]이 속성을 만족시키는 binary relation을 함수(function)이라고 한다.
Injectivity (Inj)
\[\forall y_{1},y_{2} \in \mathrm{ran}(R), \exists x \in \mathrm{dom}(R), \quad xRy_{1} \mbox{ and } xRy_{2} \Rightarrow y_{1}=y_{2}\]Exercise ${ R }$이 Unival를 만족하는 것과 ${ R^{-1} }$이 Inj을 만족하는 것이 동치임을 보여라.
함께보기
참고문헌
- Jech, Hrbacek (1999). Introduction to Set Theory, 3rd edition revised and expanded, CRC Press.
- Endorton (2001). A Mahtematical Introduction to Logic, 2nd ed, Academic Press.
- Grätzer (2011). Lattice Theory: Foundation, 1st ed., Birkhäuser.