동치관계 (equivalence relation)
쉽게 풀면
학급 학생들을 "같은 요일에 태어난 사람들"끼리 묶는다고 해봅시다. 이 묶는 규칙이 제대로 작동하려면 세 가지가 필요합니다. 첫째, 나는 당연히 나와 같은 요일에 태어났습니다(반사성). 둘째, 내가 철수와 같은 요일에 태어났다면 철수도 나와 같은 요일에 태어난 것입니다(대칭성). 셋째, 내가 철수와 같은 요일이고 철수가 영희와 같은 요일이면, 나와 영희도 같은 요일입니다(추이성). 이 세 조건을 모두 만족하는 관계를 동치관계라고 부르며, 이런 관계가 있으면 전체 집합을 겹치지 않는 여러 그룹(동치류)으로 깔끔하게 나눌 수 있습니다.
왜 중요한가
동치관계는 겉보기에 다른 대상들을 "본질적으로 같다"고 묶어 분류함으로써 복잡한 문제를 단순화하는 도구이기 때문에 수학과 컴퓨터과학 전반에서 폭넓게 쓰입니다. 데이터나 상태 공간을 동치류 단위로 묶으면 분석해야 할 경우의 수가 크게 줄어들어, 알고리즘의 효율을 높이거나 증명을 단순화하는 데 직접적으로 기여합니다. 또한 새로운 수학적 대상(정수를 나머지로 묶은 모듈러 체계, 분수를 비율로 묶은 유리수 등)을 엄밀하게 정의할 때도 동치관계와 동치류라는 개념이 기초를 이룹니다.
논문에서는 이렇게 쓰입니다
이 문장은 겉보기에 다른 데이터라도 결과적으로 같은 취급을 받아야 하는 것들을 하나의 그룹으로 묶는 방식으로, 분석해야 할 경우의 수를 크게 줄였다는 뜻입니다. 알고리즘 이론이나 형식 검증, 조합론 논문에서 복잡한 대상을 단순화할 때 자주 사용되는 개념입니다.
이론전산학 분야에서는 동치관계를 이용해 겉보기에 다른 상태들이 실제로는 같은 동작을 하는지를 판별하고, 이를 바탕으로 시스템을 최소화한다는 것을 보여줍니다.
화학정보학 분야에서는 서로 다른 방식으로 표현되었지만 본질적으로 같은 분자 구조를 동치관계로 묶어 중복을 제거하는 데 활용한다는 것을 보여줍니다.
조금 더 깊게 보면
동치관계가 정의되면 전체 집합은 서로 겹치지 않는 동치류들로 완전히 나뉘게 되는데, 이를 그 관계에 대한 분할(partition)이라 부르며, 임의의 동치관계와 임의의 분할은 항상 서로 대응됩니다. 실제 연구에서는 어떤 대상들 사이의 관계가 동치관계인지 확인하기 위해 반사성, 대칭성, 추이성 세 조건을 하나씩 점검하는 절차를 거치며, 이 중 하나라도 성립하지 않으면 동치류로 깔끔하게 나눌 수 없다는 점이 논증의 핵심이 되는 경우가 많습니다. 동치관계와 유사하지만 대칭성 대신 반대칭성을 요구하는 관계는 순서관계로 분류되어, 원소들을 그룹으로 묶는 대신 순서를 매기는 데 쓰인다는 점에서 구분됩니다.
주의할 점
세 조건 중 하나라도 빠지면 동치관계가 아닙니다. 예를 들어 "~보다 크다"는 관계는 추이성은 만족하지만 반사성(자기 자신보다 크지 않음)과 대칭성을 만족하지 않으므로 동치관계가 아니라 명제와 논리에서 다루는 순서관계에 가깝습니다. 모듈러 연산에서 "나머지가 같다"는 관계가 동치관계의 대표적인 예입니다.