//이 자료는 Discrete mathmatics and its application 7th edition에서 나오는 예제를 간추린 것입니다. 저는 코딩에 관심 있는 학생이며, 타인의 지적재산을 단지 학습을 위해 사용할 뿐 개인의 금리적 이윤을 위한 상업적인 용도로 쓰지 않습니다. 만약 저작권 관련 문제가 될 시 즉시 문서를 삭제하겠습니다.//
**여기서 relationships 과 relation 단어가 같이 사용됩니다. 두 단어는 같은 의미를 가지고 대체되서 사용되기도 하지만, 서로 다른 의미 또한 함축하고 있습니다. relation은 보다 큰 집단 간에 일반적으로 관계가 있다고 선언하는데 사용합니다. relationship 은 더욱 특정적인 인물들이나 작은 집단간의 특정한 관계를 표현할 때 사용됩니다. 여기서 relationship 은 연관성으로 relation은 관계로 해석했습니다.
9 관계 Relations
집합 내의 엘리먼트들간의 연관성은 많은 상황에서 발생합니다. 매일, 우리는 회사와 회사 전화번호, 근로자와 그/그녀의 월급, 한 사람과 그 사람의 친척과 같은 연관성들을 마주하게됩니다. 수학에서, 우리는 이런 연관성들에 대해서 연구합니다. 양의 정수와 그가 나눌 수 있는 수, 한 정수와 한 수를 5로 나누어 남는 나머지와 같은 수, 실수와 그 것 보다 또 큰 수, 실수 x와 f(x)의 값 여기서 f는 함수일 때 등등 정도입니다. 연관성이란 것은 프로그램과 프로그램이 사용하는 변수, 그리고 컴퓨터 언어와 그 언어에서 사용가능한 구문statement 같이 컴퓨터 과학에서도 자주 발생합니다.
집합 내의 엘리먼트들의 연관성은 관계relation이라고 불리는 구조체를 사용하여 표현됩니다. 관계는 집합 간의 데카르트 곱Cartesian product 의 부분집합입니다. 관계는 문제들을 풀기위해 사용되는데, 두 도시 간 비행 항공편으로 연결되어있는지, 복잡한 프로젝트의 단계를 위해 적절한 순서를 구하기위해, 또는 컴퓨터 데이터베이스에서 자료를 저장하는 유용한 방법을 만들기위해 사용됩니다.
어떤 컴퓨터 언어에서는, 변수의 이름의 앞 31글자만 중요합니다. 문자열의 순서쌍들로 이루어진 이런 변수들에서 앞 문자열이 앞 31글자가 뒷 문자열과 같다는 것은 특수한 관계relation의 한 예입니다. 이 것은 동치 관계Equivalence relation로 불립니다. 동치 관계는 수학과 컴퓨터 과학에서 발생합니다. 동치 관계에 대해서는 학습해 볼 것이고, 다른 관계에 대해서도 학습해 볼 것입니다.
1 관계들과 그 속성들 Relations and Their Properties
두 집합 내의 엘리먼트들간의 연관성을 표현하기 위한 가장 직접적인 방법은 순서쌍을 이용하는 것입니다. 이 순서쌍은 연관된 두 일리먼트들로 이루어져있습니다. 이런 이유로, 순서쌍의 집합은 이진 관계 또는 이항 관계binary relations이라고 불립니다. 이 섹션에서는 이진 관계를 설명하기위해 사용되는 기초적인 용어들에 대해 소개해보려합니다. 이 챕터 후반부에서는 특정 문제들을 풀기 위해 관계를 이용할 것입니다. 이는 통신 네트워크, 프로젝트 스케쥴링, 집합 내에서 같은 속성을 가진 엘리먼트들을 분간해내는 문제들입니다.
정의 1
A와 B를 집합이라하자. A에서 B로의 이진 관계binary relation는 AxB의 부분집합이다.
다른 표현으로는, A에서 B로의 이진 관계는 순서쌍들로 이루어진 집합 R입니다. 여기서 순서쌍 첫번째 원소는 A에서 왔고 두 번째 엘리먼트는 B에서 왔습니다. 우리는 a R b 표기를 (a, b) ∈ R 을 표현하는데 사용합니다. 그리고 표기 a R/ b 는 (a, b) ∉ R을 표현하는데 사용할 것입니다. 더, (a, b) 가 집합 R에 속하면, a는 R에 의해 b와 관계를 가진다고 말합니다.
이진 관계는 두 집합 내의 엘리먼트들 간의 연관성을 표현합니다. 나중에 이 챕터 후반부에서는 n - ary relation 에 대해서도 소개될 것입니다. 이는 두 집합 이상에서 엘리먼트들 간의 연관성을 표현합니다. 앞으로는 오해의 여지가 없을 때는 이진binary 단어를 생략하고 표현할 것입니다.
예제 1
A를 학교의 학생들의 집합이라하고, B를 강의들의 집합이라고 하자. R은 (a, b)와 같은 쌍들을 포함하는 관계라고 하자. 여기서 a는 b 강의를 수강하는 학생이다. 예로, 다솜과 예슬이 CS518을 수강한다면, 쌍(다솜, CS518) 과 (예슬, CS518)은 R에 속합니다. 만약 다솜이 CS510도 수강한다면, 쌍 (다솜, CS510) 또한 R에 속합니다. 그러나, 예슬이가 CS510 강의를 듣지 않는다면, (예슬, CS510)은 R에 속해있지 않습니다.
만약 어떤 강의도 수강하지 않는 학생이 존재한다면, R에서 그 학생을 첫 번째 원소로 갖는 순서쌍은 존재하지 않을것입니다. 비슷하게, 현재 진행되지 않는 강의가 존재한다면, R에서는 그 강의를 두번째 원소로 갖는 순서쌍은 없을 것입니다.
예제 3
A = { 0, 1, 2} 그리고 B = { a, b} 라 합시다. 그리고 {(0, a), (0,b), (1,a), (2,b)} 은 A에서 B로의 관계입니다. 이 뜻은, 예르 들어, 0 R a이고 1 R/ b 입니다. 관계는 그래프화 되어 표현될 수도 있고, 테이블을 통해 표현될 수도 있습니다. 예는 아래에 있습니다. 관계의 표현에 대해서는 9.3 섹션에서 자세히 논의될 것입니다.
관계와 같은 함수 Functions as Relations
집합 A에서 집합 B로의 함수 f는 B의 한 원소를 정확히 A의 각 원소에 할당하는 것입니다. f의 그래프는 순서쌍 (a, b)들의 집합입니다. 이 (a, b)는 b = f(a)를 만족합니다. f의 그래프는 A x B의 부분집합이기 때문에, A에서 B로의 관계라 할 수 있습니다. 게다가, 함수의 그래프는 A의 모든 엘리먼트들을 정확히 하나의 순서쌍에서 첫번째 원소로 가지는 특성을 가집니다.
반대로, 만약 관계 R이 집합 A에서 B로 있으며 A의 모든 엘리먼트들이 R의 정확히 하나의 순서쌍에서 첫 번째 원소로 존재할 때, 함수는 관계 R의 그래프로써 정의될 수 있습니다. 이는 (a, b) ∈ R를 만족하는 고유한 엘리먼트 b를 a에 할당하면서 수행됩니다. (즉, 어떠한 a도 다른 두개의 b와 순서쌍을 이룰 수 없습니다.)
관계relation은 집합 A와 B의 엘리먼트들간에 일-대-다 연관성을 표현하기 위해 사용될 수 도 있습니다. 여기서 A의 한 원소가 B의 여러 엘리먼트들과 연관있을 수 있습니다. 함수function는 B의 정확히 한 엘리먼트를 A의 한 엘리먼트와 연관 시키는 것입니다. 함수로는 일-대-다를 표현할 수 없습니다.
관계relation는 함수들의 그래프들의 일반화입니다. 집합들간의 더 넓은 연관류를 표현하기 위해 사용될 수도 있습니다. (A에서 B로의 함수 f의 그래프는 순서쌍 (a, f(a)) for a ∈ A 의 집합임을 기억해주세요)
한 집합에서의 관계 Relations on a Set
A에서 A로의, 자신으로의 관계는 흥미롭습니다.
정의 2
관계relation on a set은 A에서 A로의 관계입니다.
예제 4
A를 집합 { 1, 2, 3, 4} 라 하자. R= {(a,b) | b를 나눌수 있는 a}에 존재하는 순서쌍을 설명하세요.
*** (a,b)가 R에 속하려면 a와 b는 4를 넘지 않는 양의 정수이며 a가 b를 나눌수 있어야합니다. 따라서, R= {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)} 입니다.
예제 5
다음의 정수들로 이루어진 집합에서의 관계들을 고려해보세요.
R1 = {(a,b) | a<= b }
R2 = {(a,b) | a > b }
R3 = {(a,b) | a=b or a= -b }
R4 = {(a,b) | a=b }
R5 = {(a,b) | a=b+1 }
R6 = {(a,b) | a+b <= 3 }
이 관계들 중 각각 (1,1), (1,2), (2,1), (1,-1), (2,2)을 포함하는 관계들을 어느 골라주세요
*** 이는 모두 무한 집합에서의 관계들입니다. 순서쌍 (1,1) 은 R1, R3, R4에 있습니다. (2, 1)은 R2, R5, R6에 있습니다. (1, -1)은 R2, R3, R6에 있습니다. (2,2)는 R1, R3, R4에 있습니다.
유한집합에서의 관계들의 수를 알아내는 것은 어렵지 않습니다. 왜냐하면 집합 A 자신으로의 관계는 단지 A x A의 부분집합이기 때문입니다.
예제 6
n개의 엘리먼트들로 이루어진 집합에서 몇 개의 관계들이 있을 수 있습니까?
*** 집합 A 자신으로의 관계는 A x A의 부분집합입니다. 왜냐하면 A가 n 개의 엘리먼트를 가질 때 A x A 는 n^2의 엘리먼트들을 가집니다. 그리고 m 개의 엘리먼트인 집합은 2^m개의 부분집합을 가지므로, A x A는 2^(n^2) 개의 부분집합이 존재합니다. 그러므로, n개의 엘리먼트를 가진 집합에서 자신의 집합으로의 관계는 2^(n^2)개가 존재합니다. 예로, 집합 {a, b, c} 자신으로의 관계는 2^(3^2) = 2^9 = 512 개가 존재합니다.
관계의 속성 Properties of Relations
집합 자신으로의 관계들을 구별하기 위해 몇 가지 특성이 있습니다. 특성들 가운데 중요한 것을 우선적으로 소개해볼까 합니다. 관계에서 한 엘리먼트는 항상 자신과 연관을 가집니다. 예로, R을 집합 자신으로의 관계라고 합시다. 이 집합은 순서쌍 (x, y) 이루어진 사람들이며, 여기서 x와 y는 같은 엄마와 같은 아버지를 가지고 있습니다. 그렇다면 모든 사람 x에 대하여 x R x 를 만족합니다.
정의 3
만약 모든 엘리먼트 a ∈ A 에 대해 (a,a) ∈ R 를 만족한다면 집합 A 자신으로의 관계 R은 반사적reflexive 이라고 합니다.
집합 A 자신으로의 관계 R이 반사적인 것은 정량자를 이용하여 ∀a((a,a) ∈ R) 를 보이면 됩니다. 여기서 정의역은 A에 속한 모든 엘리먼트들입니다. 다시 한 번 더 말하면, A 자신으로의 관계가 반사적임을 보려면 A의 모든 엘리먼트가 자신 스스로와 연관을 가지는지 확인하면 됩니다.
예제 7
아래에 있는, {1, 2, 3, 4} 에서 자신으로의 관계를 고려해보세요.
R1 = {(1,1), (1,2), (2,1), (2,2), (3,4), (4,1), (4,4)}
R2 = {(1,1), (1,2), (2,1)}
R3 = {(1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4)}
R4 = {(2,1), (3,1), (3,2), (4,1), (4,2), (4,3)}
R5 = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3), (3,4), (4,4)}
R6 = {(3,4)}
어떤 관계가 반사적인가요?
*** 관계 R3 과 R5가 반사적입니다. 왜냐하면 두 관계는 (a,a) 형식의 모든 쌍을 포함하고 있기 떄문입니다. (1,1), (2,2), (3,3), (4,4) 입니다. 다른 관계들은 반사적이지 않습니다. 왜냐하면 순서쌍 (3,3)이 관계에 포함되어 있지 않기 때문입니다.
예제 8
예제 5에서 어떤것이 반사적인가요? a, b ∈ Z
R1 = {(a,b) | a<= b }
R2 = {(a,b) | a > b }
R3 = {(a,b) | a=b or a= -b }
R4 = {(a,b) | a=b }
R5 = {(a,b) | a=b+1 }
R6 = {(a,b) | a+b <= 3 }
*** R1, R3, R4가 반사적입니다. R1은 모든 정수 a에 대하여 a <=a 를 만족하므로 반사적입니다. R3 과 R4는 확실히 반사적이여 보입니다.
예제 9
양의 정수들의 집합 자신으로의 "나눌수 있다(divides)" 관계가 반사적인가요?
*** a가 양의 정수일 경우, a|a 를 만족하므로 나눗셈 관계는 반사적입니다. (a, a) ∈ Z+ 만약 Z인 경우는 0을 포함하므로, (0,0)은 존재할 수 없으므로 반사적이지 않습니다.
어떤 관계에서는, 한 엘리먼트가 두번째 엘리먼트와 연관이 있고 두번째 엘리먼트가 첫번째 엘리먼트와 연관있을 수 있습니다. 관계는 순서쌍 (x, y)로 이루어져있습니다. 여기서 x와 y는 적어도 한 강의를 공통적으로 수강하는 학교의 학생들이며 관계는 이럴때 이 특성을 가집니다. 즉, (x, y) (y, x) 같이 존재할 수 있습니다.
반대로 다른 관계는, 한 엘리먼트가 두번째 엘리먼트와 연관있다면, 두번째 엘리먼트는 첫번째와 연관이 있지않을 때 이 특성을 가집니다. 관계는 순서쌍 (x, y)로 이루어져있습니다. 여기서 x와 y는 학교 학생들이며, x는 y보다 평균 학점이 높을때 관계는 이 특성을 가질 수 있습니다. 즉 (x, y)는 존재하나 (y, x)는 존재할 수 없습니다.
정의 4
집합 A 자신으로의 관계 R에서 모든 a, b ∈ A에 대해 (a,b) ∈ R 일 때 (b, a) ∈ R 이면, 관계 R은 대칭적이라고 합니다.
집합 A 자신으로의 관계 R에서 모든 a, b ∈ A에 대해 (a,b) ∈ R 이고 (b, a) ∈ R 이면 a=b 일 때 반대칭적이라고 합니다.
정량자를 이용하여서, 집합 A 자신으로의 관계 R이 대칭적임을 볼 수 있습니다. ∀a∀b((a,b)∈R→(b,a)∈R). 비슷하게, 집합 A 자신으로의 관계 R이 반대칭적임을 확인할 수도 있습니다. ∀a∀b(((a,b) ∈ R ∧ (b,a) ∈ R) → (a=b))
즉, 관계가 대칭적이라고 했을 때 a가 b와 연관성이 있다면 b가 a와도 연관이 있음을 의미합니다. 관계가 반대칭적이라고 했을 때 a가 b와 연관있고 b가 a와 연관되는 구별되는 엘리먼트 a와 b 쌍이 존재하지 않음을 뜻합니다. 즉, a와 b가 연관되고 b가 a와 연관되는 유일한 방법은 a와 b가 동일한 엘리먼트일 때입니다. 대칭적과 반대칭적은 반대의미를 가진 것이 아닙니다. 왜냐하면 한 관계가 두 특성을 동시에 가지거나 두 특성을 동시에 가지지 않음을 볼 수도 있습니다. 만약 관계가 a≠b인 순서쌍 (a,b)를 포함할 때, 이 관계는 대칭적인 동시에 반대칭적일 수 없습니다.
* n개의 엘리먼트들로 이루어진 집합 자기 자신으로의 2^(n^2) 개의 관계 들중에서 상대적으로 적은 갯수가 대칭적이거나 반대칭적입니다. 수가 보여주듯이, 중요한 관계들은 이런 특성들을 가지게 됩니다.
예제 10
예제 7에서 대칭적인 것과 반대칭적인 것을 선택해보세요.
R1 = {(1,1), (1,2), (2,1), (2,2), (3,4), (4,1), (4,4)}
R2 = {(1,1), (1,2), (2,1)}
R3 = {(1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4)}
R4 = {(2,1), (3,1), (3,2), (4,1), (4,2), (4,3)}
R5 = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3), (3,4), (4,4)}
R6 = {(3,4)}
*** 대칭적임은 ∀a∀b((a,b)∈R→(b,a)∈R)를 의미합니다. 따라서 R2, R3이 대칭적입니다. 반대칭적임은 ∀a∀b(((a,b) ∈ R ∧ (b,a) ∈ R) → (a=b))를 의미합니다. 따라서 R4, R5, R6 이 반대칭적입니다. R1, R2, R3은 (1,2) ∈ R ∧(2,1) ∈ R) → (1=2) 이므로 만족하지 못합니다. R4, R5, R6은 ∀a∀b(((a≠b) → (a,b) ∉ R ∨ (b,a) ∉ R)) 을 만족합니다.
예제 11
아래의 예제에서 대칭적인 관계와 반대칭적인 관계를 골라보세요.
R1 = {(a,b) | a<= b }
R2 = {(a,b) | a > b }
R3 = {(a,b) | a=b or a= -b }
R4 = {(a,b) | a=b }
R5 = {(a,b) | a=b+1 }
R6 = {(a,b) | a+b <= 3 }
*** R1은 대칭적이지 않습니다. 관계 {(a,b) | a<= b} 에는 a=a 외의 대칭적인 순서쌍이 존재하지 않습니다. 따라서 ∀a∀b(((a≠b) → (a,b) ∉ R ∨ (b,a) ∉ R))을 만족하므로 반대칭적입니다. R2에도 ∀a∀b(((a≠b) → (a,b) ∉ R ∨ (b,a) ∉ R)) 을 만족하므로 반대칭적입니다. 관계 R3은 {(a, b) | a=b or a =-b} 이므로 대칭적입니다. 그러나 관계내에는 반례로 (1, -1) 과 (-1, 1) 이 존재합니다. 따라서 다음을 만족하지 못하므로 반대칭적이지 않습니다. ∀a∀b(((a≠b) → (a,b) ∉ R ∨ (b,a) ∉ R)) R4는 대칭적이면서 반대칭적입니다. R5는 반대칭적입니다. R5의 관계에 있는 순서쌍은 (a, a-1)과 같습니다. 관계 내에는 (a-1, a) 가 존재할 수 없으므로 ∀a∀b(((a≠b) → (a,b) ∉ R ∨ (b,a) ∉ R))를 만족합니다. R6은 대칭적입니다. a+b<=3을 만족하는 순서쌍 (a,b) 는 (b,a)도 존재하기 때문입니다.
예제 12
양의 정수들의 집합 자신으로의 "나눌 수 있다" 관계는 대칭적입니까? 반대칭적입니까?
*** "나눌 수 있다" 관계는 대칭적이지 않습니다. 1 | 2 이지만, 2 |/ 1 입니다. 이 관계는 반 대칭적입니다. a | b 이면서 b | a 인 것은 a=b이기 때문입니다.
정의 5
A에 속한 임의의 엘리먼트 a, b, c에 대하여, (a,b)∈R 이고 (b,c)∈R일 때 (a,c)∈R이라면 집합 A 자신으로의 관계 R은 이행적transitive 이라고 합니다.
정량자를 사용하여 이행적인 관계 R을 다음과 같이 표현할 수 있습니다.
∀a∀b∀c(((a,b)∈R ∧ (b,c) ∈ R) → (a,c) ∈R)
예제 13
다음의 관계들중에 이행적인 것을 고르시오. (예제 7)
R1 = {(1,1), (1,2), (2,1), (2,2), (3,4), (4,1), (4,4)}
R2 = {(1,1), (1,2), (2,1)}
R3 = {(1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4)}
R4 = {(2,1), (3,1), (3,2), (4,1), (4,2), (4,3)}
R5 = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3), (3,4), (4,4)}
R6 = {(3,4)}
*** R1 은 이행적이지 않습니다. 관계 내에 순서쌍 (3,4)와 (4,1)이 존재하면 (3,1)이 존재해야 이행적입니다. 그러나 관계내에 순서쌍 (3,1)이 존재하지않습니다. R2는 이행적이지 않습니다. 관계 내에 순서쌍 (2,1)과 (1,2)가 존재하지만, (2,2)가 존재하지않습니다. R3은 이행적이지 않습니다. (4,1) 과 (1,2)가 존재하지만 (4,2)가 존재하지 않습니다. R4, R5, R6은 이행적입니다.
예제 15
양의 정수들의 집합 자신으로의 "나눌 수 있는" 관계는 이행적입니까?
*** a가 b를 나눌 수 있고 b가 c를 나눌 수 있다고 가정합시다. 임의의 양의 정수 k와 l은 다음을 만족합니다. b = ak, c = bl. 따라서, c = (ak)l 이므로 a는 c를 나눌 수 있습니다. 따라서, 이 관계는 이행적입니다.
특정한 속성을 가지는 관계들의 수를 판단하는데에 "경우의 수" 방법을 쓸 수 있습니다. 특정한 속성을 가지는 관계들의 수를 알아내는 것은 n개의 엘리먼트를 가진 집합 자신으로의 관계들에서 얼마만큼의 관계들이 그 공통된 속성을 공유하는지의 정보를 제공합니다. 아래의 문제에서 확인해봅시다.
예제 16
n개의 엘리먼트로 이루어진 집합 자신으로의 관계에서 몇 개의 반사적인 관계가 존재합니까?
*** A x A의 부분집합이 관계 R입니다. 따라서, 관계는 A x A 안에 존재하는 n^2개의 순서쌍 중에 어떤 순서쌍이 포함되는지 결정된 것이 R이라는 뜻입니다. 그러나, R이 반사적이라면, A에 포함되는 임의의 a에 대해 (a,a)를 만족하는 ㅡ 즉, n개의 순서쌍이 반드시 R에 있어야 합니다. 다른 n(n-1)개의 순서쌍들은 각각 (a,b)로 표시할 수 있으며, 여기서 a ≠ b 입니다. 이 순서쌍들은 관계 R에 포함될수도 안될수도 있습니다. 따라서, 2^(n*(n-1)) 개의 반사적 관계들이 존재할 수 있습니다.
대칭적 관계들과 반대칭적 관계들에 대한 경우의 수 셈은, 예제 16과 풀이법이 비슷합니다.(문제 47을확인하세요). 그러나, n개의 엘리먼트들로 이루어진 집합 자신으로의 관계들 중 이행적인 관계들에 대한 경우의 수 셈은 현재까지 일반화된 수식으로는 존재하지 않습니다. 현재까지, T(n), n개의 엘리먼트들로 이루어진 집합 자신으로의 관계들 중 이행적 관계들이 몇개 존재하는지의 수는, n<= 17에 대해서만 알려져있습니다. 예로, T(4) = 3,994, T(5) = 154,303, T(6) = 9,415,189 입니다.
문제 47
n 개의 엘리먼트들로 이루어진 집합 자신으로의 관계들 중에 해당 속성을 가진 관계들이 얼마만큼 존재합니까?
a) 대칭적symmetric? **A내 임의의 원소 a, b에 대하여, (a,b)∈R 이면 (b,a)∈R 이다.
b) 반대칭적antisymmetric? **A내 임의의 원소 a, b에 대하여, (a,b)∈R∧(b,a)∈R 이면, a=b이다.
c) 비대칭적asymmetric? **A내 임의의 원소 a, b에 대하여, (a,b)∈R이면 (b,a)∉R이다.
d) 비반사적irreflexive? **A내 임의의 원소 a에 대하여, (a,a)∉R 이다.
e) 반사적이고 대칭적reflexive and symmetric?
f) 반사적이지도 않으며 비반사적이지도 않은neither reflexive nor irreflexive?
*** ㅎㅎ 행렬을 이용하여 풀면 됩니다. n x n 행렬을 이용하면 대각원소들은 반사적인 모습을 뜁니다. 그것을 제외한 원소들의 조합은 2^(n*(n-1)) 개입니다. 따라서 비반사적 관계들은 반사적인 관계들의 수와 같습니다. 대칭적인 관계들은 어떨까요. 대칭적인 관계들은 n개의 대각원소들을 포함하거나 2^n 또는 대각외 원소들이 위쪽 삼각 부분이 포함되거나, 아래쪽 삼각 부분이 포함되거나, 둘 다 포함되지 않는 경우 3^(n*(n-1)/2) 가지 입니다. 따라서, 2^n * 3^(n*(n-1)/2) 입니다. 비대칭적은 어떨까요? 대각원소들은 포함되면 안됩니다. 위 삼각원소 또는 아래 삼각원소들이 포함되거나 또 둘다 포함되지 않는 경우가 있습니다. 따라서 3^(n*(n-1)/2) 입니다. 반사적이고 대칭적인 관계들은 반드시 대각원소들을 포함하여야하고, 위-아래 삼각 행렬들이 포함되거나 포함되지 않아야합니다. 따라서, 경우의 수 2^(n*(n-1)/2) 입니다. 반사적이지도 않으며 비반사적이지도 않은 관계들은 ~(반사적이거나 비반사적인 관계들) [앞의 ~는 여집합입 표시] 입니다. 반사적이거나 비반사적인 관계들은 2^(n*(n-1)) * 2^(n*(n-1)) 입니다. 따라서 그것의 여집합은 2^(n^2) - 2*2^(n*(n-1)) 입니다.
관계 결합하기 Combining Relations
A에서 B로의 관계는 A x B의 부분집합이므로, A에서 B로의 두 관계는 두 집합을 결합(연산)하는 것과 같이 결합 할 수 있습니다. 아래의 예를 확인해 봅시다.
예제 17
A = {1,2,3}, B= {1,2,3,4} 라 합시다. 관계 R1 = {(1,1),(2,2),(3,3)}, R2 = {(1,1),(1,2),(1,3),(1,4)} 를 결합하여 다음과 같은 결과를 얻을 수 있습니다.
R1∪R2 = {(1,1),(1,2),(1,3),(1,4),(2,2),(3,3)}
R1∩R2 = {(1,1)}
R1 - R2 = {(2,2),(3,3)}
R2 - R1 = {(1,2),(1,3),(1,4)}
예제 18
A를 모든 학생들의 집합, B를 모든 강의들의 집합이라고 합시다. R1은 순서쌍 (a,b) 들의 집합입니다. 여기서 a는 b 강의를 수강한 학생입니다. 그리고 R2는 순서쌍 (a,b) 들의 집합입니다. 여기서, a는 졸업하기위해 b를 수강해야하는(졸업요건) 학생입니다. 다음의 관계들은 무엇입니까? R1 ∪ R2, R1 ∩ R2, R1 ⊕ R2, R1 - R2, R2 - R1
*** R1 ∪ R2는 순서쌍 (a,b)로 이루어져있습니다. 여기서 a는 b를 수강한 학생이거나 b를 수강해야만하는 학생입니다. R1 ∩ R2는 순서쌍 (a,b)로 이루어져있습니다. 여기서 a는 b가 졸업요건인 동시에 이미 들은 학생입니다. R1 ⊕ R2는 순서쌍 (a,b)로 이루어져있습니다. 여기서 a는 b를 수강했으나 졸업요건이 아닌 학생이거나 b가 졸업요건이지만 수강하지 않은 학생입니다. R1 - R2는 순서쌍 (a,b)로 이루어져있습니다. 여기서 a는 b가 졸업요건이 아니지만 b를 수강한 학생입니다. R2 - R1는 순서쌍 (a,b)로 이루어져있습니다. 여기서 a는 b가 졸업요건이지만 수강하지 않은 학생입니다.
예제 19
R1을 실수들의 집합 자신으로의 "~보다 작은" 관계라고 하고 R2는 실수들의 집합 자신으로의 "~보다 큰" 관계라고 합시다. 즉, R1 = {(x,y) | x< y}, R2 = {(x,y) | x>y }입니다. R1 ∪ R2, R1 ∩ R2, R1 ⊕ R2, R1 - R2, R2 - R1은 무엇입니까?
*** (x,y) ∈ R1∪R2, 여기서 x < y 이거나 x > y입니다. x < y 또는 x > y 는 x ≠ y와 같습니다. 그러므로, 이 관계를 다음과 같이 표현할 수 있습니다. R1∪R2 = {(x,y)|x≠y}. 다르게 표현해본다면, "~보다 작은" 관계와 "~보다 큰" 관계의 합집합은, "같지않다" 관계입니다. (x,y) ∈ R1 ∩ R2, 여기서 x < y 그리고 x > y 입니다. 따라서 공집합입니다. R1 - R2 = R1, R2 - R1 = R2 이며 R1 ⊕ R2 = R1 ∪ R2 - R1 ∩ R2 = {(x,y)|x≠y}
정의 6
R을 집합 A에서 B로의 관계라고 합시다. 그리고 S를 집합 B에서 C로의 관계라고합시다. R과 S의 합성은 순서쌍(a,c)로 이루어져 있습니다. 여기서 a ∈ A, c ∈ C 이고 (a,b) ∈ R와 (b,c) ∈ S를 만족하는 b ∈B가 존재합니다. 이런 R과 S의 합성을 다음과 같이 표기합니다. S∘R
두 관계의 합성을 연산하는 것은 첫 번째 관계의 순서쌍 두 번째 엘리먼트와 두 번째 관계의 첫 번째 엘리먼트를 필요로합니다.
예제 20
관계 R과 S의 합성은 무엇입니까? 여기서 R은 {1,2,3}에서 {1,2,3,4}로의 관계이며 R={(1,1),(1,4),(2,3),(3,1),(3,4)}, S는 {1,2,3,4}에서 {0,1,2}로의 관계이며 S={(1,0),(2,0),(3,1),(3,2),(4,1)}입니다.
*** S∘R은 R에 있는 순서쌍과 S에 있는 순서쌍으로 이루어져있습니다. 여기서 R의 순서쌍 두 번째 엘리먼트는 S의 순서쌍 첫 번째 엘리먼트와 일치해야합니다. 예로, R의 순서쌍 (2,3) 과 S의 순서쌍(3,1)은S∘R에서 순서쌍 (2,1)을 만들어냅니다. 합성의 모든 순서쌍들을 연산해보면, 다음과 같습니다.
S∘R = {(1,0), (1,1), (2,1), (2,2), (3,0), (3,1)}
예제 21 관계 자신과의 합성
모든 사람들의 집합 자신으로의 관계 R이 있다고하자. (a,b)∈R 이며 a가 b의 부모라고하자. 그렇다면 (a,b)∈R이고 (b,c)∈R를 만족하R는 b가 존재한다면 (a,c)∈R∘R를 만족합니다. 즉, b가 존재해야하는데, 여기서 a가 b의 아버지이고 b가 c의 아버지여야합니다. 다른 표현으로는, a가 c의 할아버지이면 (a,c)∈R∘R 입니다.
관계 R의 제곱은 두 관계의 합성의 정의와 동일하게 정의될 수 있습니다.
정의 7
집합 A 자신으로의 관계 R이 있다고하자. R^n 승은, n=1,2,3 ..., 은 다음과 같이 정의될 수 있습니다.
R^1 = R 이고 R^(n+1) = R^n∘R 입니다.
예제 22
R = {(1,1),(2,1),(3,2),(4,3)} 이라고합시다. R^n 을 구하세요. n = 2,3,4, ...
*** R^2 = R∘R = {(1,1),(2,1),(3,1),(4,2)}, R^3 = R^2∘R = {(1,1),(2,1),(3,1),(4,1)}, R^4 = {(1,1),(2,1),(3,1),(4,1)} ... n=5,6,7 ... 에 대하여 같습니다.
다음의 정리는 이행적 관계의 제곱은 이 관계의 부분집합임을 보여줍니다. 이 정리는 9.4 절에서 사용됩니다.
정리 1
집합 A 자신으로의 관계 R은 이행적이라면 n=1,2,3... 에 대해 R^n⊆R 입니다.(biconditional)
증명
우선 n=1,2,3 ...에 대해 R^n⊆R 가 참이라고 가정 합시다. 우선 R^2⊆R에 대해 살펴봅시다. R이 이행적임을 보이기위하여, (a,b) ∈ R이고 (b,c) ∈ R이면, 합성의 정의에 따라, (a,c) ∈ R^2 입니다. R^2 ⊆R 이므로, 이것은 (a,c)∈R 임을 뜻합니다. 따라서, R은 이행적입니다.
R^n⊆R 이 참이라고 가정합시다. 다음으로, R^(n+1) 또한 R의 부분집합임을 보여야합니다. 그러기위해, (a,b)∈R^(n+1)라 가정합시다. 그러면, R^(n+1) = R^n∘R이기 때문에, 집합 A에 임의의 원소 x가 (a,x) ∈ R이고 (x,b) ∈ R^n 를 만족해야합니다. 그렇다면 R^n⊆R 이므로, R에는 순서쌍 (x,b)가 존재해야합니다. 그리고, R이 이행적이므로, (a,x), (x,b)가 있으므로 R에는 (a,b)가 있다고 결론이 도출됩니다. 우리는 결국 R^(n+1)⊆R 임을 보였습니다.
