[Math] Relation

다음은 Relation에 대한 간단한 정의임.

A relation (or, more precisely, a binary relation) on a set $A$ is
a collection of ordered pairs of elements from $A$.

 

이를 Cartesian Product를 통해 설명하면,

$A$로부터 $B$의 (binary) relation $R$은 $A \times B$의 subset 으로,

$$a\in A, b \in B \\ (a,b)\in R$$

이 성립하며, $_aR_b$ 로 표기한다.

 

이는 $a$와 $b$는 $R$의 관계가 있음을 나타내며 다음과 같이 표기하기도 한다.

$$R: A\rightarrow B$$

 

$\neg _a R_a$ 라고 기재하면 "$a$는 $a$와 $R$의 관계가 아님" 을 의미.: "$a$ is not related $a$."

 

일반적으로 set 에서 출발하여, relation을 거쳐, function으로 이어지는 형태로 개념이 확장된다.

 

domain, range, and inverse

참고로, relation은 function을 포함하는 개념으로, function은 특정 제약조건이 추가된 relation으로 볼 수 있다.

relation에서 domain(정의역), range(치역), inverse (역, 역관계)등이 다음과 같이 정의되며, 이는 function에서도 적용됨.

 

• domain: $\text{dom } R=\{ x\in A | \exists y \in B: (x,y)\in R\}$
• range: $\text{im } R=\{y \in B | \exists x \in A: (x,y) \in R\}$
• inverse: $R^{-1}=\{(y,x)\in B\times A| (x,y) \in R\}$

---

Relation 관련 정의

다음은 "set $A$에서의 relation $R$"과 관련된 정의임.

• Reflexive (반사적): $\forall a \in A, {}_aR_a$
  • 위의 조건을 만족하는 $R$을 reflexive하다고 한다: Reflexive Relation
  • 집합  $A$ 위의 관계 $R$이 반사적이라 함은, $A$의 모든 원소 $a$에 대해, $a$는 자기 자신과 $R$ 관계에 있다는 것을 의미 (작거나 같은 관계)
• Antireflexive (반반사적): $\forall a \in A, \neg _aR_a$
  • 위의 조건을 만족하는 $R$을 antireflexive하다고 한다: Antireflexive relation
  • 집합  $A$ 위의 관계 $R$이 반반사적(비반사적)이라 함은, $A$의 어떤 원소 $a$도 자기 자신과 $R$ 관계에 있지 않다는 것을 의미 (작다 $<$ 는 반반사적임)
• Symmetric (대칭적): ${}_aR_b \Leftrightarrow {}_aR_b$
  • 위의 조건을 만족하는 $R$을 symmetric하다고 한다: Symmetric relation
  • 집합  $A$ 위의 관계 $R$이 대칭적이라 함은, 어떤 원소 $a$와 $b$에 대해, 만약 ${}_aR_b$가 참이라면 ${}_bR_a$도 참이라는 것을 의미 (친구 관계는 symmetric, 부모관계는 not symmetric)
• Antisymmetric (반대칭): $\forall a, b \in A$, ${}_aR_b \wedge {}_bR_a \Rightarrow a=b$
  • 위의 조건을 만족하는 $R$을 antisymmetric하다고 한다.: Antisymmetric relation
  • 집합  $A$위의 관계 $R$이 반대칭적이라 함은, 모든 $A$에 대해, 만약 ${}_aR_b$와 ${}_bR_a$가 모두 참이라면, $a$와 $b$가 반드시 같아야 한다는 것을 의미 (작거나 같은 $\le$관계)
• Transitive (추이적): for $\forall a,b,c \in A$, ${}_aR_b \wedge {}_bR_c \Rightarrow {}_aR_c$
  •  위의 조건을 만족하는 $R$을 transitive하다고 한다.: Transitive relation
  • 집합 $A$ 위의 관계 $R$이 추이적이라 함은, 어떤 원소 $a$, $b$, $c$에 대해, 만약 ${}_aR_b$와 ${}_bR_c$가 모두 참이라면, $_aR_c$도 참이라는 것을 의미. (원소들 간의 논리적 체계적 관계)

---

Equivalence, Partial Ordering, and Strict Ordering Relations

위에서 배운 여러 relations을 통해 ordered set이 정의됨.

참고로 set 자체에서는 element간의 순서가 없고 단순히 set에 포함되는지 여부만 따짐.

relation을 통해 ordered set이라는 개념이 정의된다.

Equivalence Relation

Relation이 reflexive 하면서 symmetric, transitive 를 모두 만족하면 "Equivalence Relation"(동치관계, 동등관계)라고 한다.

---

Partial Ordering

Relation이 reflexive 하면서 antisymmetric, transitive 를 모두 만족하면 "Partial Ordering Relation"라고 한다.

Partial ordering relation을 가진 set을 partial ordered set이라고 부름.

 

예를 들어

• "less than or equal to"($\le$)라는 relation으로 ordering이 된 real number에 대한 set은 "partially ordered set"이다.

---

Strict Ordering

Relatoin이 antireflexive 하면서  transitive를 모두 만족하면 "Strict ordering relation".

Strict ordering을 가진 set을 strict ordered set이라고 부름.

 

예를 들어

• "가나다순 (preceding)" 이라는 relation으로 ordering이 되는 자음으로 구성된 set은 strict ordered set임.

---

References

Digital Image Processing: chapter 2.6 Introduction to The Basic Mathematical Tools Used in Digital Image Processing

https://product.kyobobook.co.kr/detail/S000003155767

Digital Image Processing | Rafael C . Gonzalez - 교보문고

 

https://m.blog.naver.com/pkeir/221613987941

집합론 핵심 내용 정리

2024.02.25 - [.../Math] - [Math] Class: set and proper class (클래스와 집합)

[Math] Class: set and proper class (클래스와 집합)

2021.09.14 - [.../Math] - Function (함수) : 간략 정의

Function (함수) : 간략 정의

 

https://www.notion.so/dsaint31/Set-and-Logical-Operations-aa25b000dc0f4484b97bb758536b24d4?pvs=4