대칭 관계

수학에서 대칭 관계(對稱關係, 영어: symmetric relation)는 두 대상 사이의 관계의 성립 여부가 두 대상의 순서와 무관한 이항 관계이다. 예를 들어, 형제자매 관계는 대칭 관계이지만, 조상과 자손의 관계는 대칭적이지 않다. 반사 관계인 대칭 관계는 그래프 이론의 연구 대상이다.

정의

집합 $X$ 위의 이항 관계 $R\subseteq X^{2}$가 다음 조건을 만족시키면, 대칭 관계라고 한다.

• 임의의 $x,y\in X$에 대하여, 만약 $(x,y)\in R$라면, $(y,x)\in R$

성질

크기 $n$의 유한 집합 위에는 총 $2^{n(n+1)/2}$개의 대칭 관계가 존재한다. 작은 $n$에 대하여, 이는 다음과 같다 ($n=0,1,2,\dots$).

1, 2, 8, 64, 1024, … (OEIS의 수열 A006125)

반사 대칭 관계

집합 $X$ 위의 반사 대칭 관계 $R$에 대하여, ${\mathcal {C}}_{R}$가 $R$의 극대 클릭들의 집합이라고 하자. 즉, ${\mathcal {C}}_{R}$는 다음 조건을 만족시키는 극대 부분 집합 $C\subseteq X$들로 구성된다.

• 임의의 $c,c'\in C$에 대하여, $(c,c')\in R$

그렇다면, ${\mathcal {C}}_{R}$는 $X$의 덮개이며, 다음 두 성질을 만족시킨다.

• (A) 임의의 $C\in {\mathcal {C}}_{R}$ 및 ${\mathcal {F}}\subseteq {\mathcal {C}}_{R}$에 대하여, 만약 $\textstyle C\subseteq \bigcup {\mathcal {F}}$라면, $\textstyle \bigcap F\subseteq C$이다.
• (B) 임의의 $S\subseteq X$에 대하여, 만약 $S$가 ${\mathcal {C}}_{R}$의 원소의 부분 집합이 아니라면, ${\mathcal {C}}_{R}$의 원소의 부분 집합이 아닌 두 원소 집합 $\{s,t\}\subseteq S$가 존재한다.

반대로, 조건 (A)와 (B)를 만족시키는 구문 분석 실패 (SVG (브라우저 플러그인을 통해 MathML 활성화 가능): "http://localhost:6011/ko.wikipedia.org/v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle X} 의 덮개 ${\mathcal {C}}$가 주어졌을 때, $X$ 위에 다음과 같은 이항 관계 $R_{\mathcal {C}}$를 정의하자.

$(x,y)\in R_{\mathcal {C}}\iff \exists C\in {\mathcal {C}}\colon x,y\in C$

그렇다면, $R_{\mathcal {C}}$는 반사 대칭 관계이다. $R\mapsto {\mathcal {C}}_{R}$는 $X$ 위의 반사 대칭 관계들의 집합과 조건 (A)와 (B)를 만족시키는 $X$의 덮개들의 집합 사이의 일대일 대응이며, 그 역함수는 ${\mathcal {C}}\mapsto R_{\mathcal {C}}$이다. 즉, 반사 대칭 관계의 개념은 위 두 조건을 만족시키는 덮개의 개념과 동치이다.^{:304, Theorem 1}

예

모든 동치 관계는 대칭 관계이다.

순서체 $K$ 위에서 다음과 같은 이항 관계 $R$를 생각하자. (예를 들어, $K$는 유리수체 $\mathbb {Q}$나 실수체 $\mathbb {R}$로 취할 수 있다.)

$(x,y)\in R\iff |x-y|\leq 1$

그렇다면 $R$는 $K$ 위의 반사 대칭 관계이다. 반면, $K$ 위에 이항 관계

$(x,y)\in S\iff 0<|x-y|\leq 1$

를 정의하였을 때, $S$는 대칭 관계이지만, 반사 관계가 아니다.

같이 보기

• 추이적 관계
• 반대칭관계