[이산수학] 관계 -2

관계의 성질

관계는 특정한 성질에 따라 여러 가지로 나눌 수 있으며 관계가 가지고 있는 성질은 기본적으로 반사, 대칭, 반대칭, 추이 관계 등이 있다.

반사 관계

👉집합 A에 있는 모든 원소 x에 대하여 xRx((x,x) ∈ R)이면, 관계 R을 반사 관계라고 한다. 

반사 관계의 관계 R를 방향 그래프로 그렸을 때, 그래프의 모든 정점에서 자기 자신을 가리키는 화살표가 있어야 반사 관계가 성립한다. 

반사 관계를 가진 방향 그래프

즉, 집합 A = {1,2,3,4} 일 때, 반사 관계를 가지는 관계 R은 (1,1), (2,2), (3,3), (4,4)를 모두 포함하고 있어야 한다.

 

만약 집합 A의 모든 원소에 대하여 a ∈ A, (a,a)∉R 이면 R을 비반사 관계라고 한다. 비반사 관계에서 R은 R의 원소 중에서 (a,a), a ∈ A인 원소가 하나도 존재하지 않는다.

대칭 관계

👉 집합 A에 있는 원소 x, y에 대해 (x, y)∈R일 때 (y, x)∈R이면 관계 R을 대칭 관계라고 한다.

관계 R이 대칭 관계일 때 R의 원소 중 (a, b)가 존재하면 (b, a)는 반드시 존재해야 한다. 

• 방향 그래프 : 만약 a 정점에서 b 정점으로 화살표가 나가면, 반대로 b 정점에서 a 정점으로의 화살표도 존재해야 한다.
• 관계 행렬 : 대각선을 중심으로 행렬이 서로 대칭되어야 한다.

대칭 관계의 두 가지 예

 

반대칭 관계

👉 집합 A에 있는 모든 원소 x, y에 대하여 (x, y)∈R이고 (y, x)∈R일 때 x=y인 관계를 만족하면 관계 R을 반대칭 관계라고 한다.

반대칭 관계일 때, x≠y이고 (x, y)∈R이면, (y, x)∉R이 되어야 한다. 

추이 관계

👉 집합 A에 있는 원소 x, y, z에 대하여 관계 R이 (x, y)∈R이고, (y, z)∈R이면 (x, z)∈R인 관계를 만족할 때 관계 R을 추이 관계라고 한다.

집합 A = {1, 2, 3}이고 R = {(1,2)}이면 관계 R의 순서쌍은 (1,2)뿐이고 그로 시작하는 순서쌍이 존재하지 않으므로 추이 관계라고 할 수 있다.

추이 클로우저

R+는 추이 클로우저를 뜻한다.

위의 식은 다음과 같이 정의된다.

해당 경우들을 제외하고는 어떤 것도 추이 클로우저(R^+)에 속하지 않는다.

반사 및 추이 클로우저

R*는 반사 및 추이 클로우저를 뜻한다.

💡R = {(1,2),(2,2),(2,3)}을 집합 {1,2,3}상에서의 관계라고 할 때 R+와 R*을 구하시오
👉R+ 구하기

1번 조건 (a,b)∈R이면 (a,b)∈R+에 따라 R+ ={(1,2),(2,2), (2,3)}
2번 조건 (a,b)∈R+ 이고 (b,c)∈R이면 (a, c)∈R+에 따라 (1,3)이 추가된다. 

즉, R+ = {(1,2),(1,3),(2,2), (2,3)} 이 된다.


👉R* 구하기
R* = R+ ⋃ {(a, a) | a ∈ S}이므로
R* = {(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)}이 된다.

동치 관계 및 분할

동치 관계

관계 R에서 반사, 대칭, 추이 관계가 모두 성립할 때 동치 관계라고 한다. 동치 관계 R은 서로 공통 부분이 없으면서 공집합이 아닌 클래스들로 S를 분할한다는 성질을 가진다.

집합 A에서의 관계 R⊆ AxA는 다음과 같은 성질을 가질 수 있다.
1. 반사 관계 : 모든 x∈A에 대해 xRx이다.
2. 대칭 관계 : 모든 x,y∈A에 대해 xRy이면 yRx이다.
3. 추이 관계 : 모든 x,y,z∈A에 대해 xRy이고 yRz이면 xRz이다.

위 세 가지 관계를 모두 만족시키는 관계를 동치 관계라고 한다.

동치 관계는 일상에서 어떠한 물건을 대체할 수 있는 물건, 컴퓨터 프로그래밍에서 같은 입력으로부터 같은 출력이 나오는 것을 말한다.

동치류와 몫집합

• 동치류(= 동치 클래스) : 집합 A에 대한 동치 관계를 R이라고 할 때, A의 각 원소 x에 대하여 [x]를 R에 대한 x의 동치류라고 한다.
  • [x] = { y|(x,y) ∈R }
• 몫집합 : 동치류의 모임

분할

공집합이 아닌 집합 A의 분할을 말하며 다음과 같은 조건을 만족시키는 부분 집합의 모임이다.

위 조건을 말로 풀어내면 다음과 같다.

• 모든 분할 집합 {Ai}는 공집합이 아니다.
• S 안에 있는 모든 원소느 임의의 Ai에 속한다.
• {Ai}의 집합은 서로 교차하지 않는다.

mod 합동

mod 합동이란 x와 y를 m으로 각각 나누었을 때 나머지가 같은 경우를 말한다. 

부분 순서 관계

부분 순서 관계

집합 A에서의 관계 R⊆ AxA는 다음과 같은 성질을 가질 수 있다.
1. 반사 관계 : 모든 x∈A에 대해 xRx이다.
2. 반대칭 관계 : 모든 x,y∈A에 대해 xRy이면 yRx이면 x=y이다.
3. 추이 관계 : 모든 x,y,z∈A에 대해 xRy이고 yRz이면 xRz이다.

위 세 가지 관계를 모두 만족시키는 관계를 부분 순서 관계라고 한다.

부분 순서 관계란 집합 A에 대한 관계 R이 반사 관계, 반대칭 관계, 추이 관계인 관계를 말한다. 이러한 관계 R이 A에 대한 부분 순서 관계이면 순서쌍 (A, R)을 부분 순서 집합이라고 한다.

 

부분이라는 용어를 사용하는 이유는 집합 A의 원소의 모든 쌍이 관계를 가지는 것이 아니기 때문이다.

 

만약 집합 A에 대한 관계 R이 부분 순서 관계이면, A의 두 원소 x,y에 대하여 (x,y) ∈R을 x≲y로 표기하고 'x가 y를 선행한다'라고 읽는다.

선형 순서

부분 순서 집합에서 집합 A의 두 원소 x,y가 x≲y 또는 y≲x이면 x와 y를 비교 가능하다고 하고, 집합 A의 모든 두 원소가 비교 가능 하면 A를 선형 순서 집합이라고 한다. 

 

이럴 경우 관계 ≲ 를 선형 순서 관계라고 한다.

선형 순서는 다음 조건을 만족한다.
1. R이 부분 순서를 만족한다.
2. 만약 a∈A, b∈A라면 aRb, bRa 또는 a=b 중 하나가 성립한다.