관계(Relations) / 관계의 특징(Relations and their properties)
이항관계(binary relations)
정의 1 : A와 B라는 집합이 있을 때, A로부터 B까지의 이항 관계는 AXB의 부분집합이다.
def 1 : Let A and B be sets. A binary relation from A to B is a subset of AXB
예시) A={0,1,2} B={a,b}
- A X B = {(0,a), (0,b), (1,a), (2,b)}
- set A 와 B의 관계를 graphically 하게 표현할 수 있다.
- 관계는 함수보다 더 general한 표현이다.
정의 2: A라는 집합에 대한 관계는 A X A 의 부분집합이다.
def 2 : a binary relation on a set A is a subset of A X A
예시) A={1,2,3,4} R={(a,b) | a divides b}
답)
문제) 만약 n개의 element가 있는 set은 몇개의 관계(relation)을 가질까?
답) A X A 가 n의 제곱개의 원소를 가지니까 2의 n제곱 승이 정답
relation의 종류
1. 반사 관계(reflective relation)
정의 :모든 a ∈ A 에 대해 (a,a) ∈R인 관계
def : R is reflective if (a,a)∈ R for every element a∈A
- A가 공집합일때도 reflective relation 이다.
반사 관계 / 반사 관계 아닌 것
주의해야할 점은 반산관계가 아니라고 해서 비반사관계거나, 비반사관계가 아니라고 해서 반사관계는 아니다.
2.대칭관계(Symmetric relation)
정의 : 어떤 a,b ∈ A에 대해 (a,b) ∈R이면 (b,a) ∈R인 관계
def : R is symmetric iff (b,a) ∈ R whenever (a,b) ∈ R for all, a,b ∈A
예시)
3.반대칭관계(Antisymmetric relation)
정의 : 어떤 a,b ∈ A 에 대해 (a,b) ∈ R 일 때, (b,a) ∈R이면 a=b인 관계
def : R is antisymmetric when (a,b) ∈ R, (b,a) ∈ R only if a= b for all a ∈ A, b ∈ A
예시)
4.추적관계(transitive relation)
정의 : (a,b) ∈ R , (b,c) ∈ R 일 때, 모든 a,b,c ∈ A에 대하여 (a,c) ∈ R이다.
def : R is transitive if whenever (a,b) ∈ R and (b,c) ∈ R then (a,c) ∈R, for all a,b,c ∈ A
예시)
5. 구성 관계(composition relation)
정의 : R 은 set A와 set B의 관계, S는 set B와 setC의 관계이다. R과 S의 구성관계는 set A 에서 setC의 관계이다.
Theorm 1 . The relation R on a set A is transitive iff R^n ⊆ R for n = 1,2,3...