[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이 Function이 되기 위한 제한조건

• domain(정의역)의 모든 원소가 반드시 Relation을 가짐.
  • Function 에서는 정의역(domain)에 속하는 모든 원소에 대해 반드시 관계가 정의되어 있어야 함.
  • 정의역의 모든 원소는 적어도 하나의 치역(codomain) 원소와 연결되어야 함.
• domain의 한 element는 단 하나의 codomain 원소에만 대응.
  • 함수에서는 정의역의 한 원소가 두 개 이상의 치역 원소와 관계를 가질 수 없음.
  • 즉, 하나의 입력에 대해 정확히 하나의 출력만 존재.

---

집합의 curly bracket 내의 comma는 "such that"을 의미함.

---

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 (함수) : 간략 정의

[Math] Function (함수): 간략 정의

---

https://dsaint31.github.io/math/math-week01/#class-set-and-relation

[Math] Week 01

 

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

---