대칭 관계

(대칭관계에서 넘어옴)

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

정의

편집

집합   위의 이항 관계  가 다음 조건을 만족시키면, 대칭 관계라고 한다.

  • 임의의  에 대하여, 만약  라면,  

성질

편집

크기  유한 집합 위에는 총  개의 대칭 관계가 존재한다. 작은  에 대하여, 이는 다음과 같다 ( ).

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

반사 대칭 관계

편집

집합   위의 반사 대칭 관계  에 대하여,   극대 클릭들의 집합이라고 하자. 즉,  는 다음 조건을 만족시키는 극대 부분 집합  들로 구성된다.

  • 임의의  에 대하여,  

그렇다면,   덮개이며, 다음 두 성질을 만족시킨다.

  • (A) 임의의   에 대하여, 만약  라면,  이다.
  • (B) 임의의  에 대하여, 만약   의 원소의 부분 집합이 아니라면,  의 원소의 부분 집합이 아닌 두 원소 집합  가 존재한다.

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

 

그렇다면,  반사 대칭 관계이다.    위의 반사 대칭 관계들의 집합과 조건 (A)와 (B)를 만족시키는  덮개들의 집합 사이의 일대일 대응이며, 그 역함수 이다. 즉, 반사 대칭 관계의 개념은 위 두 조건을 만족시키는 덮개의 개념과 동치이다.[1]:304, Theorem 1

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

순서체   위에서 다음과 같은 이항 관계  를 생각하자. (예를 들어,  유리수체  실수체  로 취할 수 있다.)

 

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

 

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

같이 보기

편집

각주

편집
  1. Chajda, Ivan; Niederle, Josef; Zelinka, Bohdan (1976). “On existence conditions for compatible tolerances”. 《Czechoslovak Mathematical Journal》 (영어) 26 (101): 304–311. doi:10.21136/CMJ.1976.101403. ISSN 0011-4642. MR 0401561. Zbl 0333.08006.