[이산수학] 6강 - 관계

✅ 1. 기본사항

(1) 곱집합

• 곱집합: 집합 A와 B의 곱집합은 A X B 로 표현이 되며, A의 원소와 B의 원소의 모든 순서쌍들의 집합을 곱집합이라함.

A = {1, 2}, B = {a, b}
곱집합 = A X B = {(1, a), (1, b), (2, a), (2, b)}

• 쉽게 말해, 두 집합 A와 B에서 공통된 원소를 찾는 것은 교집합이며, 곱집합은 두 집합의 원소들을 하나씩 뽑아 만들 수 있는 모든 가능한 '순서쌍'의 모임을 말합니다.

(2) 관계

예시: "x는 y보다 작다"라는 관계(R)
조건: x < y
곱집합 중 선택된 원소: (1, 2), (1, 3), (2, 3)
결과: R = {(1, 2), (1, 3), (2, 3)} ⊆ (A X B)

• 관계: 곱집합의 모든 원소 중 특정한 조건을 만족하는 순서쌍들만 골라낸 것을 관계라고 함.
• 즉, 관계는 곱집합 내의 부분집합으로 곱집합이라는 전체 틀 안에서만 존재하며, 곱집합과 종속적인 관계를 가짐.

• 학생집합 X, 과목집합 Y 를 통해서 수강관계 R을 얻을 수 있음.

---

✅ 2. 관계의 표현

(1) 화살표 도표

• 화살표 도표: 집합 X와 Y 사이의 곱집합의 부분 집합이라는 관계라는 개념을 화살표로 표현하는 방식을 의미함.

• 화살표 도표 예제1: 집합 A와 B의 곱집합 A X B 의 원소 (x, y) 는 관계 R을 가지기 위한 필요충분조건은 y > x 이기 때문에, A 집합의 1부터 비교를 하며, 집합 R에 원소로 만들 때 {1, 2} 의 원소만 들어가게됨. 

• 화살표 도표 예제2: 집합 A와 B의 곱집합(A X B) 필요충분조건 x = y 인 경우가 S 집합인 경우, S 집합의 원소는 S = {(1,1),(2,2)} 두 개의 순서쌍만이 집합 S의 원소가 됨.

• 화살표 도표 예제3: 명확한 조건식으로 관계를 정의하는 대신에 T = {} 는 식 대신 연결된 결과(순서쌍)를 직접 나열하여 관계를 정의한 케이스임.

(2) 방향 그래프

• 방향 그래프: 정점과 간선으로 이루어진 구조이며, 방향이 있는 그래프를 의미함.

• x,y ∈ X: 집합 X에 x, y 원소가 속해있다는 의미이다.
• (x,y) ∈ R: 집합 X를 기반으로 관계 R에서 x와 y 사이에 관계가 성립함을 뜻하는 순서쌍을 의미함.
• 이때 x는 시작점(정의역), y는 끝점(공역)이 됨. 즉,x -> y 로 가는 방향을 가지는 그래프 형태가 된다는 의미임.

• 예제1: 집합A = {1,2,3} 를 기반으로 관계 집합 T에는 관계를 가지는 순서쌍이 원소로 들어가 있으며, 이를 방향 그래프로 표현하면 위와같은 방향 그래프가 형성이 될 것임.

(3) 부울행렬

• 관계-부울행렬 표현이란: 집합 사이의 관계를 컴퓨터가 이해하기 쉬운 행렬 형태로 변환하는 방법임.
• 두 집합: 집합 X = 원소가 m개인 집합, 집합 Y = 원소가 n개인 집합이 존재함.
• 관계 R: 두 집합 사이의 관계 R = X에서 Y로의 어떤 관계가 정의 되어있음.
• 부울행렬 관계 표현: 두 집합의 원소인 x, y 사이에 관계가 존재할 때는 즉, 집합 R에 원소가 있다는 의미로 부울행렬 1로 표현 반대로 집합 R에 없을 때는 관계가 없다고 판단하므로 부울행렬 0으로 표현이 됨.

• 부울행렬 예제: 집합 A = {1,2,3} 는 관계 집합 T 의 원소들의 순서쌍에 맞게 1과 0으로 표현을 함.
• 집합 T = 관계 집합으로, 순서쌍을 가지는 원소가 있을 때 부울행렬에 값을 1로 올려주고 없을 때 0으로 씀
• 즉, Mr 이건, Mt이건 결국 둘 다 관계 집합이며, 행렬로 따로 표현을 하는 것임.

---

✅ 3. 관계의 성질

(1) 성질의 종류

• 관계의 성질: 반사적 성질, 대칭적 성질, 추이적 성질이 세 가지 종류가 있음.
• 집합 A에서의 관계 R: 집합 A에서 집합A로의 관계로 외부의 다른 집합과 연결하는 것이 아닌, 집합 A안에 있는 원소들끼리 서로 어떻게 연결되는지를 보는 관계 R을 의미함.
• 반사적: 모든 원소가 자기 자신과 연결되어 있는 구조를 의미하며, 모든 a ∈ A에 대하여 (a,a) ∈ R이어야 함.
• 대칭적: 관계에 방향성 없거나 있더라도 양방향 구조를 의미하며, (a,b) ∈ R이면 반드시 (b,a) ∈ R이어야 함.
• 추이적: 관계가 다리 건너 전달이 되어야 하는 구조를 의미하며, (a,b) ∈ R 이고 (b,c) ∈ R이면 반드시 (a,c) ∈ R 이어야 함.
• 즉, a에서 b로 가고 b에서 c로 가는 길이 있다면, a에서 c로 바로 가는 직통 화살표가 반드시 있어야 한다는 의미임.

• 예제1: R = {(1,1), (2,2), (3,3), ... } 반사적인 특징만 가지고 있기 때문에 (1)번이 답임.

• 예제2: R = {(1,1), (2,2), (3,3), (1,2), (2,1), (1,3), (3,1)...} 반사적인 성질을 가짐과 동시에 대칭적인 성질도 가짐. 답: (1)(2)
• 관계가 존재하는 모든 쌍에 대해 역방향이 존재하기 때문에 대칭적임.

• 예제3: T = {(3,2),(2,1),(3,1)...} 3 -> 2 -> 1 구조 말고도 3 -> 1로 바로가는 직선 코드가 있기 때문에 추이적임.
• 반사적x: 추가적으로 집합의 모든 원소 a에 대해 (1,1), (2,2), (3,3) 이 아니기 때문에 반사적이지 않음.
• 대칭적x: 또한, 관계를 가지는 (3,2), (3,1) 에 대한 역방향 관계가 없기 때문에 대칭적이지 않다고 볼 수 있음.

(2) 관계의 성질과 부울행렬

• 반사적: 집합 A 의 반사적인 특징인 (a,a)의 반사적 순서쌍을 가진다면, 부울 행렬에서 순서쌍을 가지는 원소의 값이 1이 될 때의 모습은 반사적 특징을 가진다면 대각선이 모두 1인 경우가 될 수 있음.

A={1,2,3}
R={(1,1),(2,2),(3,3, ...)}

• 위의 예시를 보면 집합 A = {1,2,3} 일 때, 집합 R 의 원소들이 반사적 순서쌍을 가진다면 대각선으로 모두 1이 되는 모습을 볼 수 있음.

• 대칭적: 집합 A = {a,b} 인 경우 집합 R = {(a,b), (b,a)} 대칭적 형태를 띄워야 함.

A={1,2,3}
R={(1,1),(1,2),(2,1),(2,3),(3,2),(3,3)}

• 예시를 보면, (1,2) 대칭 (2,1) 을 보면 대칭적인 위치에 부울 행렬이 1인 모습을 볼 수 있음. (부울행렬에서의 대칭적인 표현임)

• 추이적: a -> b -> c 로 갈 수 있다면 제일 첫 번째 a -> 마지막 c로 한 번에 갈 수 있어야 하는 성질임.

• 추이적 특성을 지니는 원소들의 부울행렬의 곱을 진행하면 추이적 위치의 부울 행렬을 얻을 수 있음.

(3) 관계의 성질과 부울행렬 - 예제 풀이

• 예제1: 모든 원소에 대해서 반사적이어야 하지만, 4는 반사적이지 않기 때문에 반사적이 아님 답은 (1)

• 예제2: 반사적이지 않으며, 대칭적이 아님. 1 -> 2 -> 3 -> 4 와 1 -> 4가 있으므로, 추이적임.

• 예제3: 추이적x, 대칭적x, 대각선이지만 같은 원소가 아니므로 반사적이지 않음.

---

✅ 4. 관계의 종류

(1) 역관계

• 역관계: 기존의 관계를 반대로 뒤집은 것을 의미하며, 집합 R이 X에서 Y로 가는 방향이었다면, 역관계는 집합 R-1 로 Y에서 X로 가는 방향임. 즉, (x,y) 의 순서쌍이 뒤집힌 (y,x) 순서쌍의 집합으로 볼 수 있음.

• 역관계 예제: 조건 y = x - 1이고, x는 집합 A = {1,2,3,4}, y는 집합 B = {0,1,2,3} 에 속해야하며, 원래 관계 R의 원소를 조건을 통해서 구하게 되고(조건에 부합한 경우 집합에 포함), 이후에 R-1 역관계로 모든 원소들을 뒤집어 역관계를 구하게 됨.
• S^-1 의 경우 단순히 원소들의 역관계를 구함.

(2) 합성관계

집합: A, B, C
R: A에서 B로의 관계
S: B에서 C로의 관계
R과 S의 합성관계: S ○ R ( 합성관계 하나의 집합으로 볼 수 있음. )
S ○ R 는 A X C (곱집합) 의 부분집합임을 알 수 있음.

• 합성관계: 한 관계를 거쳐 다른 관계까지 연속해서 연결 가능한 경우를 하나의 새로운 관계로 만든 것을 의미함.

• 연결 가능한 경우: 위의 그림처럼, 관계 R에 a 뿐만 아니라 b 원소도 반드시 포함해야하며(연결 가능한 b가 "하나라도 존재하느냐"를 따짐), 관계 S에 c 뿐만 아니라 b 원소도 반드시 포함되어 있어 관계 R과 S는 원소 b를 통해 합성 관계를 이룰 수 있는 원리인 것임.
• 집합 A, B, C -> R: A에서 B로의 관계, S: B에서 C로의 관계 -> S ○ R: R와 S의 합성관계를 의미함.
• 세부적으로는 각 관계 집합 R, S 에서 b원소를 통해서 연결을 지어 합성관계로 만드는 것!

• 예제1: 집합 A, B, C 가 있을 때, A와 B는 R의 관계 집합을 가지며, B와 C는 S의 관계 집합을 가진다. 이때, R 과 S 관계집합은 서로 집합 B의 b원소를 통해서 연결이 가능하기 때문에 합성관계 S ○ R 이 성립이 됨.
• 세부적으로 A -> C로 연결되는 집합간의 순서쌍을 이룸.

• 예제2: 집합 A, B, C 에서 각 관계 집합 R, S 를 이루는 원소들은 필요충분조건에 의해서 순서쌍을 이룰 것이며, 해당 순서쌍을 이룬 원소들 중에서 R과 S의 합성 관계의 또 다른 필요충분조건에 의해서 S ○ R 합성 관계를 이룰 수 있음.

(3) 합성관계 - 부울행렬 표현

• 집합 A, B, C 에서 A에서 B로의 관계 R, B에서 C로의 관계 S는 부울행렬로 M R = m x n 부울 행렬이 되며, M S = n x p 부울 행렬이 된다. 즉, 합성관계 M S○R = m x p 부울 행렬로 볼 수 있음.

• 합성관계 부울행렬 표현 예제1: 위와 같이 A에서 B로의 관계 R, B에서 C로의 관계 S가 존재할 때, 관계 집합 R의 집합 B의 원소와 관계 집합 S의 집합 B의 원소와 동일한 원소들의 집합이 합성 관계 S ○ R = {(a,x),(b,z),(c,x)} 가 됨.
• 이후, 부울행렬로 표현을 한다면, 위와 같이 합성관계 부울행렬이 만들어질 수 있음. 행렬의 위치와 대응된 값이 1로 표현됨.

(4) 동치관계

• 동치관계: 집합 A에서의 관계인 관계집합 R이 반사적, 대칭적, 추이적인 특징을 가진다면 R은 동치관계라고 부른다.

• 실수에서의 상등 관계: a = a, a = b 면 b = a 이다., a = b 고 b = c 이면 a = c 이다.

• 예제1: 부호 관계에서는 반사적이지만, 0 <= 1 true 1 <= 0 false 이므로, 해당 예제는 대칭적이지 않는 특징이 있음.

• 모듈로 합동: 8 mod 5 = 3, 13 mod 5 = 3 처럼 나머지를 구하는 연산을 의미함.
• 모듈로 합동은 8 mod 5 = 3, 13 mod 5 = 3 이기 때문에 8과 13은 mod 5를 진행함에 있어서 둘은 동치관계로 볼 수 있음.
• 자세히는 위와 같이 모듈로 합동은 반사적, 대칭적, 추이적 성질을 모두 만족하므로 동치 관계로 볼 수 있음.

(5) 동치류

• 동치류: 하나의 집합 내에서 특정한 기준에 따라 끼리끼리 묶어놓은 집합을 의미하며, 쉽게 말해 하나의 집합 내에서 공통적인 원소들을 묶어놓은 집합으로도 볼 수 있음.
• [a]: a의 동치류로 집합 A안의 원소들(x) 중에서, 기준이 되는 원소 a와 관계(R)가 있는 애들만 쏙쏙 골라 모아놓은 부분집합을 의미 할 수 있음.

• 핵심은 실제 값은 다르더라도, 특정 조건 기준 조건을 통해서 같은 것으로 취급하는 관계로 볼 수 있음.
• 즉, 예를들면 위와 같이 A = {0,1,2,3,4,5,6,7,8} 집합에서 a,b 를 3으로 나눈 나머지가 같다는 조건을 통해서 나눠지는 분할 된 부분집합들을 결국 동치류로 볼 수 있는 것임.
• 결론은 동치관계를 가지는 관계집합 내부에는 여러 동치류(동치관계에 의해 나눠지는 부분집합들)로 나눠지는 것임.
• 동치관계가 이루어져 있는 집합 R을 기반으로 동치류를 구하는 것임!!!!!!!!!!!

• [0] (0의 동치류) 찾기: 관계 R에서 앞자리가 0인 순서쌍을 찾는데 (0,0) 하나뿐이기 때문에 이 순서쌍의 뒷자리에 있는 원소들을 모음. 순서쌍의 됫자리에 있는 원소들이 동일하게 0이기 때문에 [0] = {0} 이 됨.
• [1] (1의 동치류) 찾기: 관계 R에서 앞자리 1인 순서쌍 모두 찾기 (1,1), (1,2) 가 존재하고, 해당 순서쌍들의 뒷자리에 있는 원소들을 모두 모으면 {1,2} 가 나오는데 이것이 [1] = {1,2} 이 됨 ( 1의 동치류 )
• [2] (2의 동치류) 찾기: 관계 R 앞자리 1인 순서쌍 (2,1), (2,2) => [2] = {1,2} 이며, [1] 과 동일한 동치류가 나옴.
• 예제에선 서로 다른 동치류를 모두 찾으라고 했으므로, 0, 1의 동치류만 가능 즉, {0}, {1,2} 가 나옴.

• 관계집합 R이 동치관계가 이루어져 있는지 보고, 그 다음에 위에 동치류를 구하는 것임.