2강에서 함수는 각 입력에 값을 하나 대응시키는 규칙이었습니다. 그런데 세상의 많은 대응은 "하나에 하나"가 아닙니다. "x는 y와 친구다", "x는 y보다 작다", "x와 y는 나머지가 같다"처럼 원소 사이의 이런저런 얽힘을 다루는 것이 관계입니다. 이 강의는 관계를 정의하고, 그중 가장 중요한 동치관계가 집합을 어떻게 조각내는지 봅니다.
- 관계를 곱집합의 부분집합으로 정의할 수 있습니다.
- 반사, 대칭, 추이, 반대칭 성질을 판정할 수 있습니다.
- 동치관계의 세 조건을 확인할 수 있습니다.
- 동치류를 구하고, 동치관계가 집합을 분할함을 설명할 수 있습니다.
- 합동 a≡b(modn)이 동치관계임을 보이고 나머지류를 구할 수 있습니다.
- 부분순서와 전순서를 구분할 수 있습니다.
| 기호 |
읽는 법 |
뜻 |
| R |
관계 R |
집합 위의 관계, A×A의 부분집합 |
| aRb |
a와 b가 관계 R에 있다 |
(a,b)∈R |
| a∼b |
a와 b는 동치 |
동치관계에서 a와 b가 관계됨 |
| [a] |
a의 동치류 |
a와 동치인 모든 원소의 집합 |
| A/∼ |
A를 ∼으로 나눈 몫집합 |
동치류 전체의 집합 |
| a≡b(modn) |
a와 b는 n을 법으로 합동 |
a−b가 n의 배수 |
| a∣b |
a는 b를 나눈다 |
b가 a의 배수 |
| ≤ |
순서관계 |
부분순서 또는 전순서 |
정의. 집합 A 위의 관계 R은 곱집합 A×A의 부분집합입니다. (a,b)∈R이면 "a는 b와 관계 R에 있다"고 하고 aRb로 씁니다.
2강에서 곱집합 A×A는 순서쌍 (a,b)의 모임이었습니다. 그중 "관계된 짝"만 골라 모은 것이 관계입니다. 어떤 짝을 고를지가 곧 관계의 정의입니다.
예를 들어 A={1,2,3}에서 "작다" 관계 <는
R={(1,2),(1,3),(2,3)}
입니다. (1,2)∈R이므로 1<2이고, (2,1)∈/R이므로 2<1은 성립하지 않습니다. 함수는 각 입력에 값이 하나였지만, 관계는 한 원소가 여러 원소와 관계될 수 있고(1은 2, 3과 모두 관계) 아무와도 관계 안 될 수도 있습니다.
문제 1. (기초) A={1,2,3}에서 "같다" 관계를 순서쌍 집합으로 쓰십시오.
답. {(1,1),(2,2),(3,3)}
풀이. "같다"는 자기 자신하고만 성립하므로 (1,1),(2,2),(3,3)만 포함됩니다.
문제 2. (기초) A={1,2,3}에서 R={(1,2),(2,3)}일 때 2R3과 3R2의 참·거짓을 말하십시오.
답. 2R3은 참, 3R2는 거짓.
풀이. (2,3)∈R이므로 2R3은 참입니다. (3,2)∈/R이므로 3R2는 거짓입니다.
문제 3. (표준) A={1,2} 위의 관계는 모두 몇 개인지 구하십시오.
답. 16
풀이. 관계는 A×A의 부분집합입니다. ∣A×A∣=2×2=4이므로 부분집합은 24=16개입니다. 따라서 관계는 16개입니다.
정의. 집합 A 위의 관계 R에 대해,
- 반사적: 모든 a∈A에 대해 aRa. (∀a(aRa))
- 대칭적: aRb이면 bRa. (∀a,b(aRb→bRa))
- 추이적: aRb이고 bRc이면 aRc. (∀a,b,c((aRb∧bRc)→aRc))
직관은 이렇습니다. 반사는 "누구나 자기 자신과 관계된다", 대칭은 "방향을 바꿔도 성립한다", 추이는 "이어 붙이면 성립한다"입니다.
예를 들어 "같다"(=)는 세 성질을 모두 만족합니다. "작거나 같다"(≤)는 반사적(a≤a)이고 추이적이지만 대칭적이 아닙니다(1≤2인데 2≤1은 거짓). "작다"(<)는 추이적이지만 반사적이 아닙니다(a<a는 거짓).
한 가지 더, 반대칭적은 순서관계에서 쓰입니다. aRb이고 bRa이면 a=b라는 성질입니다. ≤가 대표적입니다.
문제 1. (기초) 실수에서 "≤"가 반사적인지 판정하십시오.
답. 반사적입니다.
풀이. 모든 실수 a에 대해 a≤a가 성립하므로(a는 자기 자신과 같거나 크지 않음) 반사적입니다.
문제 2. (표준) 실수에서 "<"가 대칭적이 아님을 반례로 보이십시오.
답. 1<2이지만 2<1은 거짓이므로 대칭적이 아닙니다.
풀이. 대칭성은 aRb→bRa를 요구합니다. a=1,b=2에서 1<2는 참이지만 2<1은 거짓이라 이 조건이 깨집니다. 따라서 대칭적이 아닙니다.
문제 3. (심화) "a와 b는 서로 소이다"(최대공약수가 1) 관계가 추이적이 아님을 반례로 보이십시오.
답. 2와 3은 서로 소이고 3과 4도 서로 소이지만, 2와 4는 최대공약수가 2라 서로 소가 아닙니다.
풀이. 추이성은 aRb∧bRc→aRc를 요구합니다. a=2,b=3,c=4로 잡으면 gcd(2,3)=1, gcd(3,4)=1로 앞 두 관계는 성립하지만 gcd(2,4)=2=1이라 aRc가 깨집니다. 따라서 추이적이 아닙니다.
정의. 관계 R이 반사적, 대칭적, 추이적을 모두 만족하면 동치관계라 하고, 보통 ∼으로 씁니다.
동치관계는 "본질적으로 같다고 볼 만한 관계"를 형식화한 것입니다. 완전히 같지는 않아도, 우리가 관심 있는 기준에서 같은 것으로 묶을 수 있는 관계입니다. 예를 들어 "같은 반이다", "나이가 같다", "n으로 나눈 나머지가 같다"가 동치관계입니다.
동치관계를 확인할 때는 세 성질을 하나씩 검사합니다. 하나라도 빠지면 동치관계가 아닙니다.
문제 1. (기초) "같다"(=)가 동치관계임을 세 성질로 확인하십시오.
답. 반사(a=a), 대칭(a=b⇒b=a), 추이(a=b,b=c⇒a=c)를 모두 만족하므로 동치관계입니다.
풀이. 등호는 항상 자기 자신과 성립하고(반사), 좌우를 바꿔도 성립하며(대칭), 두 등식을 이으면 성립합니다(추이). 세 조건을 다 만족하므로 동치관계입니다.
문제 2. (표준) 사람들의 집합에서 "a와 b는 나이가 같다" 관계가 동치관계임을 보이십시오.
답. 반사·대칭·추이를 모두 만족하므로 동치관계입니다.
풀이. 누구나 자기 자신과 나이가 같으므로 반사적입니다. a의 나이가 b와 같으면 b의 나이도 a와 같으므로 대칭적입니다. a와 b가 같고 b와 c가 같으면 a와 c의 나이도 같으므로 추이적입니다. 따라서 동치관계입니다.
문제 3. (심화) "a≤b" 관계가 동치관계가 아닌 이유를 말하십시오.
답. 반사적·추이적이지만 대칭적이 아니라서 동치관계가 아닙니다.
풀이. a≤a이므로 반사적이고, a≤b≤c이면 a≤c이므로 추이적입니다. 그러나 1≤2인데 2≤1은 거짓이라 대칭성이 깨집니다. 동치관계는 세 성질을 모두 요구하므로 ≤는 동치관계가 아닙니다(대신 순서관계입니다).
정의. 동치관계 ∼이 있는 집합 A에서, 원소 a의 동치류는 a와 동치인 모든 원소의 집합입니다.
[a]={x∈A∣x∼a}
동치류의 핵심 성질은 다음입니다.
- 모든 a에 대해 a∈[a]이다(반사성 때문). 즉 동치류는 비어 있지 않다.
- a∼b이면 [a]=[b]이고, a∼b이면 [a]∩[b]=∅이다. 즉 두 동치류는 완전히 같거나 완전히 겹치지 않는다.
- 모든 동치류를 합치면 A 전체가 된다.
이 세 성질을 합치면 동치관계는 집합을 서로 겹치지 않는 조각들로 완전히 나눈다는 결론이 나옵니다. 이렇게 집합을 겹침 없이 빈틈없이 조각내는 것을 분할이라 합니다. 동치류 전체의 집합 A/∼={[a]∣a∈A}를 몫집합이라 합니다.
성질 2를 잠깐 보겠습니다. a∼b라 하면, x∈[a]인 임의의 x에 대해 x∼a이고 추이성으로 x∼b이므로 x∈[b]입니다. 반대 방향도 같은 방식이라 [a]=[b]입니다. 반대로 [a]∩[b]=∅이면 공통 원소 c가 있어 c∼a, c∼b이고, 대칭·추이로 a∼b가 나옵니다. 따라서 두 동치류가 조금이라도 겹치면 완전히 같아야 합니다.
문제 1. (기초) A={1,2,3,4}에서 "짝홀이 같다"를 동치관계로 볼 때 [1]을 구하십시오.
답. {1,3}
풀이. 1과 짝홀이 같은(둘 다 홀수인) 원소는 1과 3입니다. 따라서 [1]={1,3}입니다.
문제 2. (표준) 위와 같은 관계에서 A의 분할을 모두 쓰십시오.
답. {{1,3},{2,4}}
풀이. 홀수끼리 {1,3}, 짝수끼리 {2,4}로 묶입니다. 두 동치류는 겹치지 않고 합치면 A 전체가 되므로 이것이 분할입니다.
문제 3. (심화) 서로 다른 두 동치류가 겹치지 않는 이유를 추이성을 이용해 설명하십시오.
답. 두 동치류에 공통 원소가 있으면 대칭·추이성으로 두 대표원소가 동치가 되어 동치류가 같아지므로, 다른 동치류는 겹칠 수 없습니다.
풀이. [a]와 [b]에 공통 원소 c가 있다고 하면 c∼a와 c∼b입니다. 대칭성으로 a∼c, 추이성으로 a∼b가 됩니다. 그러면 성질에 의해 [a]=[b]입니다. 즉 두 동치류가 조금이라도 겹치면 완전히 같아야 하므로, 서로 다른 동치류는 아예 겹치지 않습니다.
정의. 양의 정수 n에 대해, 두 정수 a, b가 n을 법으로 합동이라는 것은 a−b가 n의 배수라는 뜻입니다.
a≡b(modn)⟺n∣(a−b)
이것은 "a와 b를 n으로 나눈 나머지가 같다"와 같은 말입니다. 예를 들어 17≡5(mod12)인데, 17−5=12가 12의 배수이기 때문입니다(시계에서 17시가 5시와 같은 자리인 것과 같습니다).
합동은 동치관계입니다. 세 성질을 확인해 봅니다.
- 반사: a−a=0은 n의 배수이므로 a≡a(modn).
- 대칭: a−b가 n의 배수이면 b−a=−(a−b)도 n의 배수이므로 b≡a(modn).
- 추이: a−b=nk, b−c=nl이면 a−c=(a−b)+(b−c)=n(k+l)이 n의 배수이므로 a≡c(modn).
세 성질을 모두 만족하므로 합동은 동치관계이고, 정수 전체를 n개의 나머지류 [0],[1],…,[n−1]로 분할합니다. 이 몫집합을 Z/nZ라 하며, 8강 정수론과 암호의 바탕이 됩니다.
문제 1. (기초) 23≡?(mod5)에서 0 이상 4 이하의 값을 구하십시오.
답. 3
풀이. 23=5×4+3이므로 23을 5로 나눈 나머지는 3입니다. 따라서 23≡3(mod5)입니다.
문제 2. (표준) (mod3)에서 정수 전체의 나머지류를 모두 쓰고 각 류의 원소 예를 드십시오.
답. [0]={…,−3,0,3,…}, [1]={…,−2,1,4,…}, [2]={…,−1,2,5,…}
풀이. 3으로 나눈 나머지는 0,1,2 세 가지뿐이므로 정수는 세 류로 나뉩니다. [0]은 3의 배수, [1]은 나머지 1인 수, [2]는 나머지 2인 수입니다.
문제 3. (심화) 합동이 추이적임을 정의를 이용해 증명하십시오.
답. a−b=nk, b−c=nl이면 a−c=n(k+l)이 n의 배수이므로 a≡c(modn)입니다.
풀이. a≡b(modn)이면 정의상 a−b=nk인 정수 k가 있습니다. b≡c(modn)이면 b−c=nl인 정수 l이 있습니다. 두 식을 더하면 a−c=(a−b)+(b−c)=nk+nl=n(k+l)입니다. k+l이 정수이므로 a−c는 n의 배수이고, 따라서 a≡c(modn)입니다.
정의. 관계 R이 반사적, 반대칭적, 추이적을 만족하면 부분순서라 합니다. 여기에 더해 임의의 두 원소가 항상 비교되면(모든 a,b에 대해 aRb 또는 bRa) 전순서라 합니다.
동치관계와 순서관계는 "대칭이냐 반대칭이냐"에서 갈립니다. 동치관계는 대칭적("방향을 바꿔도 성립")이고, 순서관계는 반대칭적("양방향 성립은 같을 때뿐")입니다.
실수에서 ≤는 전순서입니다. 임의의 두 실수는 항상 크기를 비교할 수 있기 때문입니다. 반면 집합의 포함관계 ⊆는 부분순서이지만 전순서는 아닙니다. {1}과 {2}처럼 어느 쪽도 다른 쪽을 포함하지 않는 두 집합이 있어 비교되지 않기 때문입니다.
문제 1. (기초) 실수에서 ≤가 전순서인 이유를 말하십시오.
답. 임의의 두 실수 a,b에 대해 a≤b 또는 b≤a가 항상 성립하기 때문입니다.
풀이. ≤는 반사·반대칭·추이를 만족하는 부분순서이고, 더하여 어떤 두 실수든 대소를 비교할 수 있으므로 전순서입니다.
문제 2. (표준) 집합의 포함관계 ⊆가 전순서가 아님을 반례로 보이십시오.
답. {1}과 {2}는 서로 포함하지 않아 비교되지 않으므로 전순서가 아닙니다.
풀이. 전순서는 임의의 두 원소가 비교되어야 합니다. {1}⊆{2}도 거짓, {2}⊆{1}도 거짓이라 두 집합은 비교되지 않습니다. 따라서 ⊆는 부분순서이지만 전순서는 아닙니다.
문제 3. (심화) "a∣b"(약수 관계) 관계가 양의 정수에서 부분순서임을 확인하고, 전순서가 아님을 보이십시오.
답. 반사·반대칭·추이를 만족해 부분순서이고, 2와 3이 서로 나누지 못해 전순서는 아닙니다.
풀이. 반사: a∣a(모든 수는 자신의 약수). 반대칭: 양의 정수에서 a∣b이고 b∣a이면 a=b. 추이: a∣b, b∣c이면 a∣c. 세 성질을 만족하므로 부분순서입니다. 그러나 2∤3이고 3∤2라 2와 3은 비교되지 않으므로 전순서는 아닙니다.
| 유형 |
핵심 규칙 |
| 관계 정의 |
A 위의 관계는 A×A의 부분집합 |
| 반사적 |
∀a(aRa) |
| 대칭적 |
aRb→bRa |
| 추이적 |
(aRb∧bRc)→aRc |
| 반대칭적 |
(aRb∧bRa)→a=b |
| 동치관계 |
반사 + 대칭 + 추이 |
| 동치류 |
[a]={x∣x∼a}, 서로 같거나 안 겹침 |
| 분할 |
동치관계는 집합을 겹침 없이 완전 분할 |
| 합동 |
a≡b(modn)⟺n∣(a−b), 동치관계 |
| 부분순서 |
반사 + 반대칭 + 추이 |
| 전순서 |
부분순서 + 임의의 두 원소 비교 가능 |
문제 1. (기초) A={1,2,3}에서 R={(1,1),(2,2),(3,3),(1,2),(2,1)}이 반사적인지 판정하십시오.
답. 반사적입니다.
풀이. (1,1),(2,2),(3,3)이 모두 R에 있으므로 모든 원소가 자기 자신과 관계됩니다. 따라서 반사적입니다.
문제 2. (기초) 위 R이 대칭적인지 판정하십시오.
답. 대칭적입니다.
풀이. R에 든 짝 중 (1,2)가 있으면 (2,1)도 있습니다. 나머지는 자기 자신 짝이라 대칭성에 문제가 없습니다. 따라서 대칭적입니다.
문제 3. (기초) 15≡?(mod4)에서 0 이상 3 이하의 값을 구하십시오.
답. 3
풀이. 15=4×3+3이므로 나머지는 3입니다.
문제 4. (표준) A={1,2,3}에서 R={(1,1),(2,2),(3,3),(1,2),(2,1)}이 동치관계인지 판정하십시오.
답. 동치관계입니다.
풀이. 반사적(문제 1), 대칭적(문제 2)이고, 추이성은 (1,2)와 (2,1)로부터 (1,1)이 필요한데 R에 있으며 다른 조합도 문제없어 추이적입니다. 세 성질을 모두 만족하므로 동치관계입니다.
문제 5. (표준) 문제 4의 동치관계에서 A의 분할을 구하십시오.
답. {{1,2},{3}}
풀이. 1∼2이므로 [1]=[2]={1,2}입니다. 3은 자기하고만 관계되어 [3]={3}입니다. 두 동치류로 이루어진 분할은 {{1,2},{3}}입니다.
문제 6. (표준) "a−b가 짝수" 관계가 정수에서 동치관계임을 말하고 동치류의 개수를 구하십시오.
답. 동치관계이며 동치류는 짝수류와 홀수류의 2개입니다.
풀이. 이 관계는 a≡b(mod2)와 같아 동치관계입니다(2.5의 합동). (mod2)의 나머지는 0,1뿐이므로 정수는 짝수 [0]과 홀수 [1]의 두 동치류로 분할됩니다.
문제 7. (표준) 실수에서 "∣a∣=∣b∣" 관계가 동치관계임을 보이고 [3]을 구하십시오.
답. 동치관계이며 [3]={3,−3}입니다.
풀이. 반사(∣a∣=∣a∣), 대칭(∣a∣=∣b∣⇒∣b∣=∣a∣), 추이(∣a∣=∣b∣,∣b∣=∣c∣⇒∣a∣=∣c∣)를 모두 만족하므로 동치관계입니다. 3과 절댓값이 같은 실수는 3과 −3이므로 [3]={3,−3}입니다.
문제 8. (표준) "a는 b의 형제다"(자기 자신 제외) 관계가 반사적이 아닌 이유를 말하십시오.
답. 자기 자신은 자기 형제가 아니므로 aRa가 성립하지 않아 반사적이 아닙니다.
풀이. 반사성은 모든 a에 대해 aRa를 요구합니다. 자기 자신을 형제로 세지 않으면 a가 자기 형제가 아니므로 aRa가 거짓이 되어 반사성이 깨집니다.
문제 9. (심화) (mod5)에서 [2]+[4]를 대표원소로 계산하십시오(합동의 덧셈).
답. [1]
풀이. 대표원소를 더하면 2+4=6이고 6≡1(mod5)이므로 [2]+[4]=[6]=[1]입니다. 합동에서는 각 류의 대표를 더한 뒤 다시 나머지를 취해 류를 정합니다.
문제 10. (심화) 크기 n인 집합 위에서 반사적 관계는 모두 몇 개인지 구하십시오.
답. 2n2−n
풀이. 관계는 A×A의 부분집합이고 ∣A×A∣=n2입니다. 반사적이려면 대각선 원소 (a,a) n개는 반드시 포함되어야 하므로 자유롭게 고를 수 있는 짝은 n2−n개입니다. 각 짝을 넣거나 뺄 수 있으므로 2n2−n개입니다.
문제 11. (심화) 동치관계에서 [a]=[b]와 a∼b가 서로 동치임을 보이십시오.
답. a∼b이면 추이성으로 두 동치류가 같고, [a]=[b]이면 a∈[a]=[b]라 a∼b이므로 서로 동치입니다.
풀이. (⇒) a∼b라 하면 임의의 x∈[a]에 대해 x∼a∼b이므로 x∈[b]이고, 반대도 같아 [a]=[b]입니다. (⇐) [a]=[b]라 하면 a∈[a](반사성)이므로 a∈[b], 즉 a∼b입니다. 두 방향이 모두 성립하므로 동치입니다.
문제 12. (심화) ⊆가 반대칭적임을 집합의 상등 정의로 설명하십시오.
답. A⊆B이고 B⊆A이면 상등 정의에 의해 A=B이므로 반대칭적입니다.
풀이. 2강에서 집합의 상등은 A=B⟺(A⊆B)∧(B⊆A)로 정의했습니다. 따라서 A⊆B와 B⊆A가 동시에 성립하면 곧바로 A=B가 되어, 반대칭성 (A⊆B∧B⊆A)→A=B가 성립합니다.
- 관계를 곱집합의 언어로 정의할 수 있는가?
- 반사, 대칭, 추이를 각각 예로 설명할 수 있는가?
- 동치관계의 세 조건을 말할 수 있는가?
- 동치류가 왜 서로 겹치지 않는지 추이성으로 설명할 수 있는가?
- 합동 a≡b(modn)의 정의를 쓸 수 있는가?
- 합동이 동치관계임을 세 성질로 확인할 수 있는가?
- 동치관계와 순서관계의 차이(대칭 대 반대칭)를 말할 수 있는가?
정답 요지: (1) A 위의 관계는 A×A의 부분집합. (2) 반사 a≤a, 대칭 =, 추이 <. (3) 반사·대칭·추이. (4) 겹치면 공통 원소를 통해 두 대표가 동치가 되어 동치류가 같아짐. (5) n∣(a−b). (6) 반사 a−a=0, 대칭 부호, 추이 배수의 합. (7) 동치는 대칭, 순서는 반대칭.