대칭 관계

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

대칭 관계는 집합 X 위의 이항 관계 R⊆X²에서 임의의 x, y∈X에 대해 (x, y)∈R이면 (y, x)∈R을 만족하는 관계를 의미한다. 크기 n의 유한 집합 위에는 총 2^n(n+1)/2개의 대칭 관계가 존재한다. 동치 관계는 추이적이며 반사적인 대칭 관계의 예시이며, "같다"는 등식, "…와 결혼했다" 등의 관계 또한 대칭 관계에 해당한다. 비대칭 관계와 반대칭 관계와는 독립적인 관계이다.

대칭 관계

관계 속성

정의	어떤 집합의 원소 간의 관계에서, 한 원소가 다른 원소와 관계를 맺을 때, 그 역도 성립하는 관계이다.
수학적 정의	집합 X에 대한 이항 관계 R에 대해, 만약 모든 a, b ∈ X에 대해 (a, b) ∈ R이면 (b, a) ∈ R인 경우, R은 대칭적이라고 한다.

예시

예시 1	수학에서, '같음' 관계는 대칭적이다. 왜냐하면 만약 a = b이면 b = a이기 때문이다.
예시 2	'...와 결혼했다' 관계는 (사람들의 집합에서) 대칭적이다. 왜냐하면 만약 A가 B와 결혼했다면, B는 A와 결혼했기 때문이다.
예시 3	'...와 같은 생일이다' 관계는 대칭적이다. 왜냐하면 만약 A가 B와 같은 생일이라면, B는 A와 같은 생일이기 때문이다.

속성

필요충분 조건	관계 R이 대칭적일 필요충분 조건은 R이 자신의 역관계와 같다는 것이다. 즉, R = R^T이다. 여기서 R^T는 R의 역관계를 나타낸다.

관계 종류

관련 관계	반사 관계 비대칭 관계 추이 관계

📚 더 읽어볼만한 페이지

집합론 - 퍼지 집합
퍼지 집합은 각 원소가 0과 1 사이의 소속도를 가지며, 소속 함수를 통해 정의되고, 여집합, 합집합, 교집합 등의 연산을 수행하며, 퍼지 논리, 퍼지 수, 엔트로피 등의 개념과 L-퍼지 집합, 직관적 퍼지 집합 등으로 확장된다.
집합론 - 무한 집합
무한 집합은 유한 집합이 아니며, 자연수보다 큰 크기를 가지고 자신의 진부분집합과 일대일 대응을 가지며, 가산 무한 집합과 비가산 무한 집합으로 나뉜다.

1. 개요
2. 정의
3. 성질
- 3.1. 반사 대칭 관계
4. 예
- 4.1. 수학에서의 예
- 4.2. 수학 외의 예
5. 비대칭 관계 및 반대칭 관계와의 관계
6. 성질

2. 정의

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

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

3. 성질

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

대칭적이고 추이 관계는 항상 준반사 관계이다.

n개의 원소에 대한 대칭 관계의 수는 이진 행렬 표현에서 오른쪽 위 삼각형이 관계를 완전히 결정하고 임의로 주어질 수 있다는 점을 통해 구할 수 있다. 따라서 이진 위 삼각형 행렬의 수, 즉 2^n(n+1)/2만큼의 대칭 관계가 존재한다.

{|class=wikitable style="text-align:right;"
|+ 다양한 유형의 n-원소 이진 관계 수
|-
! 원소
! 이진 관계
! 추이 관계
! 반사 관계
! 대칭 관계
! 전순서
! 부분 순서 집합
! 강한 약한 순서
! 전순서
! 동치 관계
|-
| 0 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1
|-
| 1 || 2 || 2 || 1 || 2 || 1 || 1 || 1 || 1 || 1
|-
| 2 || 16 || 13 || 4 || 8 || 4 || 3 || 3 || 2 || 2
|-
| 3 || 512 || 171 || 64 || 64 || 29 || 19 || 13 || 6 || 5
|-
| 4 || || || || || 355 || 219 || 75 || 24 || 15
|-
| n
| 2^n²
|
| 2ⁿ⁽ⁿ⁻¹⁾
| 2^n(n+1)/2
|
|
|
| n!
|
|-
!}

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

3.1. 반사 대칭 관계

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

* 임의의 c, c'∈C에 대하여, (c, c')∈R

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

* (A) 임의의 C∈C_R 및 F⊆C_R에 대하여, 만약 C⊆∪F라면, ∩F⊆C이다.
* (B) 임의의 S⊆X에 대하여, 만약 S가 C_R의 원소의 부분 집합이 아니라면, C_R의 원소의 부분 집합이 아닌 두 원소 집합 {s, t}⊆S가 존재한다.

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

:(x, y)∈R_C ⇔ ∃C∈C: x, y∈C

그렇다면, R_C는 반사 대칭 관계이다. R↦C_R은 X 위의 반사 대칭 관계들의 집합과 조건 (A)와 (B)를 만족시키는 X의 덮개들의 집합 사이의 일대일 대응이며, 그 역함수는 C↦R_C이다. 즉, 반사 대칭 관계의 개념은 위 두 조건을 만족시키는 덮개의 개념과 동치이다.

4. 예

모든 동치 관계는 대칭 관계이다. 예를 들어 "같다"(등식)는 대칭 관계이지만, "보다 작다"는 대칭 관계가 아니다.

순서체 K 위에서 |x-y|≤1과 같이 정의된 이항 관계는 반사 대칭 관계이다. 반면 0<|x-y|≤1과 같이 정의된 이항 관계는 대칭 관계이지만, 반사 관계는 아니다.

"…와 (대부분의 법적 체계에서) 결혼했다", "…의 완전한 생물학적 형제/자매이다" 등은 대칭 관계의 예시이다.

4.1. 수학에서의 예

* "같다" (등식) (반면 "보다 작다"는 대칭적이지 않다)
* 부분 순서 집합의 원소에 대해 "…와 …는 비교 가능하다"
* "...와 ...는 홀수이다":

* 「(A는 B와) 결혼했다」는 대칭 관계이지만, 「(A는 B보다) 작다」는 대칭 관계가 아니다.
* 「(A는 B와) 같다」(등식).
* 「A는 홀수이고, B도 홀수이다」

4.2. 수학 외의 예

* "…와 (대부분의 법적 체계에서) 결혼했다"
* "…의 완전한 생물학적 형제/자매이다"
* "…의 동음이의어이다"
* "…의 동료이다"
* "…의 팀 동료이다"

5. 비대칭 관계 및 반대칭 관계와의 관계

정의에 따르면, 공집합이 아닌 관계는 대칭 관계이면서 동시에 비대칭 관계일 수 없다. (여기서 'a'가 'b'와 관련이 있다면, 'b'는 ('a'와) 같은 방식으로 관련될 수 없다.) 그러나 관계는 대칭적이지도 비대칭적이지도 않을 수 있는데, 이는 "이하" 및 "포식"의 경우에 해당한다.

대칭 관계와 반대칭 관계 (여기서 'a'가 'b'와 관련되고 'b'가 'a'와 관련될 수 있는 유일한 방법은 a = b인 경우)는 실제로 서로 독립적이다. 다음 예시들이 이를 보여준다.

👆

좌우로 밀어서 보기

수학적 예시
	대칭	대칭 아님
반대칭	등호	나누어떨어짐, 이하
반대칭 아님	합동 (모듈러 산술에서)	// (정수 나눗셈), 대부분의 비자명 순열

👆

좌우로 밀어서 보기

비수학적 예시
	대칭	대칭 아님
반대칭	동일 인물임, 결혼함	~의 복수형임
반대칭 아님	~의 완전한 생물학적 형제임	~를 포식함

; 동치 관계: 추이적이며 반사적인 대칭 관계

6. 성질

* 대칭적이고 추이 관계는 항상 준반사 관계이다.
* n개의 원소에 대한 대칭 관계의 수는 2^n(n+1)/2이다.

👆

좌우로 밀어서 보기

다양한 유형의 n-원소 이진 관계 수
원소	이진 관계	추이 관계	반사 관계	대칭 관계	전순서	부분 순서 집합	강한 약한 순서	전순서	동치 관계
0	1	1	1	1	1	1	1	1	1
1	2	2	1	2	1	1	1	1	1
2	16	13	4	8	4	3	3	2	2
3	512	171	64	64	29	19	13	6	5
4	65536	3994	4096	1024	355	219	75	24	15
n	2^n²		2ⁿ⁽ⁿ⁻¹⁾	2^n(n+1)/2			∑^영어 k!S(n, k)	n!	∑^영어 S(n, k)

* 제2종 스털링 수 S(n, k)는 크기가 n인 집합을 k개의 서로소 부분집합으로 나누는 경우의 수를 의미한다.
* 동치 관계: 추이적이며 반사적인 대칭 관계