이항관계
이항관계는 항수가 2인 특별한 관계이다. 대표적인 이항관계로는 ‘보다 작다’, ‘같다’, ‘나누어떨어진다’, ‘보다 크다’ 등이 있다.
예
이항관계는 흔히 볼 수 있는 대표적인 관계이다. 또 몇 가지 흥미로운 성질이 있는데, 여기서 살펴보자.
이항관계의 예로는 ‘아버지와 아들’이라는 관계, ‘교통수단과 바퀴의 수’라는 쌍, 더 일반적으로 ‘대상과 대상의 성질’을 들 수 있다. 대상이 동물이라면 성질은 다리의 수, 평균 수명, 머리카락의 수 등이 될 수 있다.
집합 M1과 M2 사이의 이항관계 R은 R ⊆ M1 × M2로 정의할 수 있다. 즉 이항관계는 순서쌍의 집합이고, 이 집합은 관계를 정하는 두 집합의 곱집합의 부분집합이다. 그래서 ‘아버지와 아들’이라는 관계는 모든 사람의 집합 사이의 관계일 수도 있고, 유럽이나 서울에 사는 모든 사람의 집합 사이의 관계일 수도 있다. 집합을 다른 방향으로 좁힐 수도 있다. 이 관계를 사람 전체가 아니라 모든 남자의 집합 사이에서 정의한다고 말할 수도 있다.
이항관계에는 보통 특별한 표기를 쓴다. (a, b) ∈ R이라고 쓰는 대신 aRb라고 쓸 수 있다. 예를 들어 (3, 1) ∈ > 대신 3 > 1이라고 쓸 수 있다. 다른 관계도 마찬가지이다. 그러니 aSb는 (a, b) ∈ S와 같은 뜻이다.
역관계
역관계는 주어진 관계를 거꾸로 뒤집은 관계이다. (여관계와 헷갈리지 말자.) ‘보다 작다’의 역관계는 무엇일까? ‘보다 크다’이다. ‘보다 작다’라는 관계에 원소 (4, 7), 즉 4 < 7이 있으면 이를 뒤집은 원소는 7 > 4이고, 역관계에는 뒤집힌 순서쌍 (7, 4)가 들어 있다.
관계 R ⊆ M1 × M2가 있을 때 역관계 R−1는 R의 원소 (a, b) ∈ R을 모두 가져와 그 순서를 뒤집은 것을 R−1에 넣어 만든다. 즉 관계 R에 원소 (a, b)가 있으면 관계 R−1에는 원소 (b, a)가 있어야 한다. 거꾸로도 성립한다. R−1에 원소 (b, a)가 있으면 관계 R에는 원소 (a, b)가 있어야 한다.
정의로 쓰면, 관계 R−1가 R의 역관계일 필요충분조건은 다음과 같다.
그래서 6 < 8이면 8 > 6이고, 그 역도 성립한다. 다른 순서쌍도 마찬가지이다.
관계의 합성
이항관계끼리는 합성할 수 있다. 두 관계가 있다고 하자. 첫 번째 관계 R은 ‘아들의 아버지이다’이고 두 번째 관계 S는 ‘여자 형제의 남자 형제이다’이다. 관계 R에는 순서쌍 (아버지, 아들)이, 두 번째 관계에는 순서쌍 (남자 형제, 여자 형제)가 들어 있다.
이제 두 관계를 합성해 보자. 새 관계가 생기는데, 이것을 R ∘ S로 나타내자. 이 관계에 원소 (a, c)가 있을 필요충분조건은 (a, b) ∈ R이고 동시에 (b, c) ∈ S인 것이다. 두 원소 모두에 b가 있다는 점에 주목하자. 한 번은 순서쌍의 두 번째 자리에, 또 한 번은 첫 번째 자리에 있다. 이것이 합성을 이어 주는 연결 원소이다.
예: R = {(성호, 민재), (재현, 태윤)}이고 S = {(민재, 지은), (민재, 수아), (태윤, 예린)}이다. 성호는 민재의 아버지이고 재현은 태윤의 아버지이다. 민재에게는 여자 형제 지은과 수아가 있고 태윤에게는 여자 형제 예린이 있다.
이제 관계 R ∘ S를 합성한다. R에서 아들 자리에 있는 사람이 관계 S에서 남자 형제로 올라 있는 순서쌍을 찾는다. 예를 들어 순서쌍 (성호, 민재)와 (민재, 지은)이다. 민재는 연결 원소이므로 더는 필요 없고, 남은 이름으로 새 순서쌍 (성호, 지은)을 만든다. 그래서 관계 R ∘ S에는 순서쌍 (성호, 지은)이 들어 있다. 민재에게는 여자 형제 수아가 한 명 더 있으므로 합성한 관계에 (성호, 수아)도 넣는다. 마지막으로 아들 태윤이 남았다. 태윤에게는 여자 형제 예린이 있다. 그러니 순서쌍 (재현, 태윤)과 (태윤, 예린)이 있다. 이것으로 원소 (재현, 예린)을 하나 더 만든다.
결과는 관계 R ∘ S = {(성호, 지은), (성호, 수아), (재현, 예린)}이다. 이 관계에 어떤 이름을 붙일 수 있을까? ‘딸의 아버지이다’가 가장 알맞을 것이다.
정의를 다시 한 번 쓰면 다음과 같다.
참고: 반대로 쓰는 경우도 있다. 즉 같은 정의에 대해 R ∘ S 대신 S ∘ R이라고 쓰기도 한다.