대칭 관계

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

정의

집합 $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

반사 대칭 관계

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

• 임의의 $c,c^{\prime }\in C$에 대하여, $(c,c^{\prime })\in R$

그렇다면, ${𝒞}_R$는 $X$의 덮개이며, 다음 두 성질을 만족시킨다.

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

반대로, 조건 (A)와 (B)를 만족시키는 $X$의 덮개 $𝒞$가 주어졌을 때, $X$ 위에 다음과 같은 이항 관계 $R_{𝒞}$를 정의하자.

$(x,y)\in R_{𝒞}⟺\mathrm{\exists }C\in 𝒞:x,y\in C$

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

예

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

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

$(x,y)\in R⟺|x-y|\le 1$

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

$(x,y)\in S⟺0<|x-y|\le 1$

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

직교

초등 기하학에서, 두 직선이 수직으로 만나는 관계는 대칭 관계를 이룬다. 보다 일반적으로, 임의의 체 $K$ 및 $K$-벡터 공간 $V$ 및 쌍선형 형식 $B:V\times V\to K$에 대하여, 다음 두 조건이 서로 동치이다.틀:Rp

• (직교의 대칭성) 만약 $B(u,v)=0$라면, $B(v,u)=0$이다.
• $B$는 대칭 쌍선형 형식이거나, 교대 쌍선형 형식이다.
• $B$는 대칭 쌍선형 형식이거나, 반대칭 쌍선형 형식이다.

같이 보기

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