집합 위의 이항관계

집합 위의 이항관계는 같은 두 집합 사이에서 정의한 이항관계를 말한다.

예

집합 위의 이항관계는 두 바탕 집합이 같은 특별한 이항관계이다. 즉 집합 위의 이항관계는 R ⊆ M × M인 관계 R이다.

‘보다 크다’라는 관계는 집합 위의 이항관계이다. 양쪽 모두에서 수를 다루기 때문이다. 즉 > ⊆ ℝ × ℝ이다. ‘아버지와 자녀 수’라는 관계는 집합 위의 이항관계가 아니다. 아버지는 모든 사람의 집합에서 고르고, 자녀 수는 어떤 수의 집합에서 고르기 때문이다.

성질

집합 M 위의 이항관계 R은 몇 가지 흥미로운 성질을 가질 수 있다. 관계 R이 다음과 같을 때 이렇게 부른다.

• 반사적이다: 모든 a ∈ M에 대해 (a, a) ∈ R이다.
• 대칭적이다: 모든 a, b ∈ M에 대해 (a, b) ∈ R이면 (b, a) ∈ R이다.
• 반대칭적이다: 모든 a, b ∈ M에 대해 (a, b) ∈ R이고 동시에 (b, a) ∈ R이면 a = b이다.
• 추이적이다: 모든 a, b, c ∈ M에 대해 (a, b) ∈ R이고 동시에 (b, c) ∈ R이면 (a, c)도 R에 있다.

반사성의 예

반사성은 원소가 자기 자신과 관계에 있다는 뜻이다. 대표적인 예가 같음 관계이다. 자연수에서 같음 관계를 정의하면 어떤 원소 a에 대해서도 a = a가 성립한다. 나누어떨어짐도 예가 될 수 있다. 이번에도 수 a는 자기 자신으로 나누어떨어지므로 순서쌍 (a, a)는 나누어떨어짐 관계에 있다(7은 7을 나눈다).

하지만 ‘보다 작다’라는 관계는 반사적이지 않다. a < a가 성립하지 않기 때문이다. 7이 7보다 작을 수는 없다. ‘자식의 아버지이다’라는 관계도 마찬가지이다. 나는 나 자신의 아버지일 수 없다. 이런 관계는 반사적이지 않다.

중요한 것은 반사성이 모든 원소에 대해 성립해야 한다는 점이다. 몇몇 원소만 찾아서는 안 된다. 예를 들어 ‘누군가를 좋아한다’라는 관계를 보자. 나는 다른 사람, 예를 들어 버스 검표원을 좋아할 수도 있지만 나 자신을 좋아할 수도 있다. 자기 자신을 좋아하는 사람은 분명히 있다. 하지만 자기 자신을 좋아하지 않는 사람도 분명히 있다. 그러니 이 관계는 반사적이지 않다. 반사적이려면 모든 사람이 자기 자신을 좋아해야 한다.

대칭성의 예

대칭적인 관계에서는 어떤 순서쌍이 관계에 있으면 뒤집은 순서쌍도 관계에 있다. 예를 들어 ‘형제자매이다’라는 관계가 그렇다. 지호가 지은의 형제자매이면 지은도 지호의 형제자매이다. 수의 관계로는 ‘서로 반수(부호를 바꾼 수)이다’라는 관계를 들 수 있다. 2와 −2, −7과 7 같은 쌍을 말한다. 더하면 0이 되는 두 수이다. 이 관계는 대칭적이다. 순서가 아예 상관없기 때문이다. (2, −2)와 (−2, 2) 모두 서로 반수이고 더하면 0이 된다.

대칭적이지 않은 관계로는 (실수에서의) ‘보다 작다’가 있다. 이 관계에는 대칭인 원소가 하나도 없다. a < b와 b < a가 동시에 성립할 수는 없기 때문이다. 5 < 15이면 15 < 5는 성립할 수 없다. ‘아들의 아버지이다’라는 관계도 대칭적이지 않다. 아들의 아버지일 수는 있지만, 그러면 아들이 아버지의 아버지일 수는 없다.

이 성질도 모든 경우에 성립해야 한다. ‘누군가를 좋아한다’라는 관계(모든 사람의 집합에서)가 대칭적이려면, 내가 어느 유명 배우를 좋아할 때 그 배우도 나를 좋아해야 한다. 그런데 그 배우는 나를 알지도 못하니 나를 좋아한다고 말할 수 없다. 아쉬운 일이고, 이 관계는 대칭적이지 않다. 그것도 아쉬운 일이다.

반대칭성의 예

반대칭적인 관계의 대표적인 예는 ‘작거나 같다’이다. 반대칭성은 원소 (a, b)와 (b, a)가 모두 관계에 있으면 둘이 같을 때, 즉 a = b일 때뿐이라는 뜻이다. ‘작거나 같다’라는 관계는 이것을 만족한다. a ≤ b와 b ≤ a가 동시에 성립하는 것은 언제일까? a = b일 때뿐이다. 수를 넣어 보자. 3 ≤ 5와 5 ≤ 3이 동시에 성립할까? 아니다. 하지만 4 ≤ 4와 4 ≤ 4는 동시에 성립한다.

반대칭적이지 않은 관계의 예로 글자 수가 같은 단어의 쌍, 예를 들어 (토요일, 손도끼)를 들 수 있다. 이 관계는 반대칭적이지 않다. 관계에 있는 단어 쌍 가운데, 뒤집은 쌍도 관계에 있으면서 두 단어가 서로 다른 것을 찾을 수 있기 때문이다. 앞에서 말한 원소 (토요일, 손도끼)와 그것을 뒤집은 (손도끼, 토요일)이 그렇다. 둘 다 분명히 이 관계에 있지만 토요일 ≠ 손도끼이므로 이 관계는 반대칭적이지 않다.

추이성의 예

‘보다 작다’라는 관계는 추이적이다. 추이성은 3 < 4이고 동시에 4 < 5이면 반드시 3 < 5도 성립해야 한다는 뜻이다. 많은 관계에서 꽤 자연스러운 성질이다. 글자 수가 같은 단어의 예도 마찬가지이다. (손도끼, 토요일)이 관계에 있고 (토요일, 장작불)이 관계에 있으면 (손도끼, 장작불)도 관계에 있다.

‘아들의 아버지이다’라는 관계는 추이적이지 않다. 성호가 민재의 아버지이고 민재가 도윤의 아버지이면, 성호는 도윤의 아버지가 아니라 할아버지이다. ‘누군가를 좋아한다’라는 관계도 추이적이지 않다. 내가 그 배우를 좋아하고 그 배우가 자기 배우자를 좋아한다고 해서 내가 그 배우의 배우자를 좋아한다는 뜻은 아니다.

추이성은 보통의 주사위에서도 문제가 된다. 주사위 A를 던졌을 때 더 큰 수가 주사위 B보다 자주(더 큰 확률로) 나오면 주사위 A가 주사위 B보다 좋다는 관계를 생각하자. 이 관계는 추이적일까? 그 답은 비추이적 주사위에서 다룬다.

동치관계와 순서관계

이항관계 가운데 특별한 몇 가지는 따로 이름이 있다.

• 동치관계는 반사적이고 대칭적이며 추이적인 관계이다.
• 순서관계는 반사적이고 반대칭적이며 추이적인 관계이다.