위키득계정 ↗
과학

관계의 합성

관계의 합성과학
영문명
Composition of relations
순서
먼저 R, 다음 S
중간 조건
조건을 만족하는 b가 하나 이상 존재
결과
A×C의 부분집합
관계의 합성은 중간 원소를 통해 두 이항 관계를 이어 새 관계를 만드는 연산이다. R⊆A×B와 S⊆B×C에 대해 어떤 b∈B가 aRb와 bSc를 함께 만족하면 (a,c)를 S∘R에 넣는다.

중간 원소를 찾는다

R={(1,3),(2,4)}, S={(3,5),(4,5)}라면 S∘R={(1,5),(2,5)}이다. 1은 3을 거쳐 5로, 2는 4를 거쳐 5로 연결된다.

모든 중간 원소가 필요한가

합성에 쌍을 넣으려면 조건에 맞는 중간 원소가 적어도 하나 있으면 된다. B의 모든 원소를 거쳐 연결되어야 하는 것은 아니다. 여러 경로가 같은 끝점을 이어도 결과 관계에는 같은 쌍을 한 번만 포함한다.

순서에 주의한다

S∘R은 R을 먼저 적용하는 표기를 쓴다. 순서를 바꾸면 결과가 달라질 수 있고 집합의 종류가 맞지 않으면 반대 순서의 합성이 같은 방식으로 정의되지 않을 수도 있다.

추이성과 연결

같은 집합 위의 관계 R이 추이적이라는 것은 R∘R⊆R로 나타낼 수 있다. 두 단계로 이어지는 모든 연결이 이미 한 단계 관계 안에 있어야 한다는 뜻이다.

관련 문서

이항 관계 / 추이 관계 / 역관계 / 합성함수 / 부분집합 / 순서쌍 / 곱집합