1단원의 네 강의(1강 명제와 논리, 2강 집합과 함수, 3강 관계와 동치, 4강 증명법)를 강의별로 묶어 정리한 누적 문제집입니다. 각 문제는 문제·답·풀이 세 줄로 되어 있으며, 본문 강의보다 한 단계 어렵게 구성했습니다. 증명 서술형이 많으니 답만 맞히지 말고 풀이의 논리 전개를 따라가며 스스로 다시 써 보는 것이 좋습니다. 표기는 KaTeX를 따릅니다.
문제 1. (표준) P,Q,R에 대해 (P∧Q)→R과 P→(Q→R)가 동치임을 진리표로 증명하십시오(수출법칙). 답. 여덟 경우 모두 두 식의 진리값이 같습니다. 풀이. 두 식이 거짓이 되는 경우만 찾으면 됩니다. (P∧Q)→R은 P∧Q가 참이고 R이 거짓일 때, 즉 (P,Q,R)=(T,T,F)일 때만 거짓입니다. P→(Q→R)은 P가 참이고 Q→R이 거짓일 때, 곧 P=T,Q=T,R=F일 때만 거짓입니다. 두 식 모두 정확히 (T,T,F) 한 경우에서만 거짓이고 나머지 일곱 경우에서 참이므로 동치입니다. □
문제 2. (표준) P→Q, Q→R, R→P가 모두 참이면 P,Q,R의 진리값이 서로 같음을 보이십시오. 답. 세 조건이 순환 함의를 이루어 셋 중 하나가 참이면 모두 참, 하나가 거짓이면 모두 거짓이 됩니다. 풀이.P가 참이라 하면 P→Q에서 Q가 참, Q→R에서 R이 참입니다. P가 거짓이라 하면 R→P가 참이려면 R이 거짓이어야 하고(R이 참이고 P가 거짓이면 R→P가 거짓), Q→R이 참이려면 Q도 거짓이어야 합니다. 두 경우 모두 셋의 진리값이 일치하므로 P≡Q≡R입니다. □
문제 3. (표준) 명제 [(P→Q)∧¬Q]→¬P가 항진명제(항상 참)임을 보이십시오(후건부정). 답. 전건이 참인 경우 후건도 반드시 참이라 조건명제가 거짓이 되는 경우가 없습니다. 풀이. 조건명제가 거짓이 되려면 전건 (P→Q)∧¬Q가 참이고 후건 ¬P가 거짓, 즉 P가 참이어야 합니다. 그런데 P가 참이고 P→Q가 참이면 Q가 참이 되어 ¬Q가 거짓이므로 전건이 거짓이 됩니다. 이는 "전건이 참"이라는 요구와 모순입니다. 따라서 거짓이 되는 경우가 없어 항진명제입니다. □
문제 4. (표준) "∀x(P(x)→Q(x))"가 참이고 "∃xP(x)"가 참이면 "∃xQ(x)"가 참임을 논증하십시오. 답.P(a)가 참인 a를 잡으면 P(a)→Q(a)에서 Q(a)가 참이라 Q를 만족하는 원소가 존재합니다. 풀이.∃xP(x)가 참이므로 P(a)를 참으로 만드는 원소 a가 있습니다. 전체명제 ∀x(P(x)→Q(x))에서 x=a를 대입하면 P(a)→Q(a)가 참입니다. P(a)가 참이므로 조건명제에서 Q(a)가 참입니다. 곧 Q를 만족하는 원소 a가 존재하므로 ∃xQ(x)가 참입니다. □
문제 5. (심화) "∀x∃yP(x,y)"의 부정을 한정기호로 정확히 쓰고, P(x,y):x<y를 실수에서 대입해 원명제와 부정 중 어느 쪽이 참인지 판정하십시오. 답. 부정은 ∃x∀y¬P(x,y)이며, 원명제 ∀x∃y(x<y)가 참입니다. 풀이.¬∀x∃yP≡∃x¬∃yP≡∃x∀y¬P입니다. P(x,y):x<y이면 원명제는 "어떤 실수 x에도 그보다 큰 y가 있다"로, y=x+1로 참입니다. 부정은 "어떤 x가 있어 모든 y에 대해 x≥y"인데 최대 실수가 없어 거짓입니다. 따라서 원명제가 참입니다.
문제 6. (심화) 배타적 논리합 P⊕Q("정확히 하나만 참")를 ∧,∨,¬로 나타내고, P⊕Q≡¬(P↔Q)임을 보이십시오. 답.P⊕Q≡(P∧¬Q)∨(¬P∧Q)이며, 이는 P↔Q의 부정과 같습니다. 풀이. "정확히 하나만 참"은 "P 참·Q 거짓" 또는 "P 거짓·Q 참"이므로 (P∧¬Q)∨(¬P∧Q)입니다. 한편 P↔Q는 두 진리값이 같을 때만 참이므로, 그 부정은 두 값이 다를 때만 참입니다. "값이 다르다"가 곧 "정확히 하나만 참"이므로 P⊕Q≡¬(P↔Q)입니다. 네 경우의 진리표를 그려도 (T,F),(F,T)에서만 참으로 일치합니다. □
문제 7. (심화) "이 마을 이발사는 스스로 면도하지 않는 사람만 면도한다"에서 이발사가 자신을 면도하는지 물으면 모순이 생김을 논리로 설명하십시오(이발사 역설). 답. 면도한다고 하면 규칙상 면도하지 않아야 하고, 안 한다고 하면 규칙상 면도해야 해서 어느 쪽도 성립하지 않습니다. 풀이. 규칙은 "x를 면도한다 ⟺x가 스스로 면도하지 않는다"입니다. x에 이발사 자신을 넣으면 "이발사가 자신을 면도한다 ⟺ 이발사가 자신을 면도하지 않는다", 곧 R↔¬R 꼴이 됩니다. R이 참이면 우변이 거짓, R이 거짓이면 우변이 참이라 항상 좌우가 어긋나 이 쌍조건은 결코 참일 수 없습니다. 따라서 그런 이발사는 존재할 수 없습니다.
문제 8. (표준) 임의의 집합 A,B,C에 대해 분배법칙 A∩(B∪C)=(A∩B)∪(A∩C)를 원소의 소속으로 증명하십시오. 답. 양변에 속할 조건이 논리의 분배법칙으로 같음을 보입니다. 풀이.x∈A∩(B∪C)는 x∈A∧(x∈B∨x∈C)와 같습니다. 1강의 논리 분배법칙 p∧(q∨r)≡(p∧q)∨(p∧r)에 의해 이는 (x∈A∧x∈B)∨(x∈A∧x∈C), 곧 x∈(A∩B)∨x∈(A∩C), 즉 x∈(A∩B)∪(A∩C)와 같습니다. 임의의 x에 대해 좌변 소속과 우변 소속이 동치이므로 두 집합은 서로 부분집합이 되어 상등입니다. □
문제 9. (표준) A⊆B이면 A∩C⊆B∩C임을 증명하십시오. 답.A∩C의 임의 원소는 A와 C에 모두 속하고 A⊆B라 B에도 속하므로 B∩C에 듭니다. 풀이.x∈A∩C를 임의로 잡으면 x∈A이고 x∈C입니다. A⊆B이므로 x∈A에서 x∈B입니다. 따라서 x∈B이고 x∈C이므로 x∈B∩C입니다. 임의의 x에서 이것이 성립하므로 A∩C⊆B∩C입니다. □
문제 10. (표준) ∣A∣=m, ∣B∣=n일 때 A에서 B로 가는 함수의 개수가 nm임을 설명하십시오. 답.A의 각 원소마다 B의 원소 하나를 독립적으로 고르므로 nm입니다. 풀이. 함수는 A의 원소 각각에 B의 값을 정확히 하나 대응시킵니다. A의 원소 m개 각각에 대해 대응할 값을 B의 n개 중에서 자유롭게 고를 수 있고 선택이 서로 독립적입니다. 따라서 곱의 법칙으로 mn×⋯×n=nm개입니다.
문제 11. (표준) f:A→B가 단사이고 g:B→C가 단사이면 g∘f도 단사임을 증명하십시오. 답.(g∘f)(x1)=(g∘f)(x2)에서 g 단사로 f(x1)=f(x2), f 단사로 x1=x2입니다. 풀이.(g∘f)(x1)=(g∘f)(x2)라 하면 g(f(x1))=g(f(x2))입니다. g가 단사이므로 f(x1)=f(x2)이고, f가 단사이므로 x1=x2입니다. 따라서 서로 다른 입력이 같은 값을 가질 수 없어 g∘f는 단사입니다. □
문제 12. (심화) f:A→B에 대해 g∘f=idA(항등함수)인 g:B→A가 존재하면 f가 단사임을 증명하십시오. 답.f(x1)=f(x2)에 g를 적용하면 x1=g(f(x1))=g(f(x2))=x2입니다. 풀이.f(x1)=f(x2)라 하면 양변에 g를 적용해 g(f(x1))=g(f(x2))입니다. 가정 g∘f=idA에서 g(f(x))=x이므로 좌변은 x1, 우변은 x2가 됩니다. 곧 x1=x2이므로 f는 단사입니다. (g를 f의 왼쪽 역이라 하며, 왼쪽 역의 존재가 단사와 대응합니다.) □
문제 13. (심화) 유한집합 A에 대해 f:A→A가 단사이면 전사임을 증명하십시오. 답. 단사이면 상 f(A)의 크기가 ∣A∣와 같고, 그 부분집합이 전체와 크기가 같으므로 f(A)=A가 됩니다. 풀이.f가 단사이면 서로 다른 입력이 서로 다른 값으로 가므로 치역 f(A)의 원소 개수는 정의역 A의 개수와 같아 ∣f(A)∣=∣A∣입니다. f(A)⊆A인데 유한집합에서 부분집합의 크기가 전체와 같으면 그 둘은 같아야 하므로 f(A)=A입니다. 곧 치역이 공역과 같아 전사입니다. (무한집합에서는 이 성질이 깨집니다. 예: N에서 n↦n+1은 단사지만 전사가 아닙니다.) □
문제 14. (심화) A={1,2,…,n}의 부분집합 전체의 집합(멱집합)과 A에서 {0,1}로 가는 함수 전체가 크기가 같음을 대응으로 설명하십시오. 답. 각 부분집합 S에 "S에 속하면 1, 아니면 0"인 지시함수를 대응시키면 전단사가 됩니다. 풀이. 부분집합 S⊆A마다 함수 χS:A→{0,1}을 χS(x)=1(x∈S), 0(x∈/S)으로 정의합니다. 서로 다른 부분집합은 소속이 다른 원소가 있어 지시함수도 달라지므로 단사이고, 임의의 함수 g:A→{0,1}에는 S={x∣g(x)=1}이 대응하므로 전사입니다. 따라서 멱집합과 함수 집합 사이에 전단사가 있어 크기가 같고, 둘 다 2n개입니다. □
문제 15. (표준) A={1,2,3} 위의 관계 R={(1,1),(2,2),(3,3),(1,2)}가 반대칭적이지만 대칭적이 아님을 보이십시오. 답.(1,2)∈R이나 (2,1)∈/R이라 대칭적이 아니고, 서로 다른 원소로 양방향이 동시에 든 짝이 없어 반대칭적입니다. 풀이. 대칭성은 (1,2)∈R이면 (2,1)∈R을 요구하지만 (2,1)∈/R이라 깨집니다. 반대칭성은 "aRb이고 bRa이면 a=b"인데, R에서 양방향이 모두 든 짝은 대각선 (1,1),(2,2),(3,3)뿐이라 모두 a=b를 만족합니다. 서로 다른 두 원소가 양방향으로 관계된 경우가 없으므로 반대칭적입니다.
문제 16. (표준) 정수에서 a∼b⟺a+b가 짝수로 정의된 관계가 동치관계임을 증명하고 동치류를 구하십시오. 답. 반사·대칭·추이를 만족하는 동치관계이며 동치류는 짝수류·홀수류 둘입니다. 풀이. 반사: a+a=2a가 짝수라 a∼a. 대칭: a+b가 짝수이면 b+a도 같은 값이라 짝수, b∼a. 추이: a+b와 b+c가 짝수이면 그 합 a+2b+c가 짝수이고 2b가 짝수라 a+c도 짝수, a∼c. 세 성질을 만족하므로 동치관계입니다. a+b가 짝수인 것은 a,b의 홀짝이 같음과 같으므로(a≡b(mod2)), 동치류는 짝수 전체 [0]과 홀수 전체 [1]의 두 개입니다. □
문제 17. (표준) 반사적이고 추이적이지만 대칭적이 아닌, 그러면서 반대칭적도 아닌 관계의 예를 하나 들고 이유를 밝히십시오. 답. "∣a∣≤∣b∣" 관계가 이에 해당합니다. 풀이. 정수에서 aRb⟺∣a∣≤∣b∣로 둡니다. 반사: ∣a∣≤∣a∣. 추이: ∣a∣≤∣b∣≤∣c∣이면 ∣a∣≤∣c∣. 대칭 아님: ∣1∣≤∣2∣이나 ∣2∣≤∣1∣은 거짓. 반대칭 아님: ∣1∣≤∣−1∣이고 ∣−1∣≤∣1∣이지만 1=−1이라 "aRb∧bRa⇒a=b"가 깨집니다. 이렇게 대칭도 반대칭도 아닌 관계가 존재합니다(둘은 서로 배타적 개념이 아닙니다).
문제 18. (심화) 동치관계 ∼에서 a∼b이면 [a]∩[b]=∅임을 대우로 증명하십시오. 답. 대우 "[a]∩[b]=∅이면 a∼b"를 공통 원소로 보입니다. 풀이. 원명제의 대우는 "[a]∩[b]=∅이면 a∼b"입니다. 공통 원소 c∈[a]∩[b]가 있으면 c∼a이고 c∼b입니다. 대칭성으로 a∼c, 추이성으로 a∼c∼b에서 a∼b입니다. 대우가 참이므로 원명제 "a∼b⇒[a]∩[b]=∅"도 참입니다. 곧 서로 다른 동치류는 겹치지 않습니다. □
문제 19. (심화) 집합 A의 한 분할 P가 주어지면 "같은 조각에 속함"이 동치관계가 됨을 증명하십시오(분할과 동치관계의 대응). 답. 분할의 세 성질(빈틈없음·겹침없음)에서 반사·대칭·추이가 각각 따라옵니다. 풀이.a∼b를 "a와 b가 P의 같은 조각에 속함"으로 정의합니다. 반사: 분할은 A를 빈틈없이 덮으므로 각 a는 어떤 조각에 속하고 자기 자신과 같은 조각이라 a∼a. 대칭: a,b가 같은 조각이면 b,a도 같은 조각이라 b∼a. 추이: a,b가 같은 조각 X, b,c가 같은 조각 Y라면 b∈X∩Y이고 분할의 조각들은 겹치지 않으므로 X=Y, 따라서 a,c가 같은 조각이라 a∼c. 세 성질을 모두 만족하므로 동치관계입니다. 이 동치관계의 동치류가 바로 원래 분할의 조각과 일치합니다. □
문제 20. (심화) (modn)의 합동에서 a≡b이고 c≡d이면 a+c≡b+d이고 ac≡bd임을 증명하십시오(합동의 연산 보존). 답.a−b=nk, c−d=nl을 이용해 (a+c)−(b+d)와 ac−bd가 각각 n의 배수임을 보입니다. 풀이. 가정에서 a−b=nk, c−d=nl인 정수 k,l이 있습니다. 덧셈: (a+c)−(b+d)=(a−b)+(c−d)=n(k+l)이 n의 배수라 a+c≡b+d입니다. 곱셈: ac−bd=ac−bc+bc−bd=c(a−b)+b(c−d)=c⋅nk+b⋅nl=n(ck+bl)이 n의 배수라 ac≡bd입니다. 따라서 합동은 덧셈과 곱셈을 보존하며, 이 성질로 나머지류 위의 사칙연산이 잘 정의됩니다. □
문제 21. (표준) "n이 정수일 때 n2을 4로 나눈 나머지는 0 또는 1이다"를 경우로 나누어 증명하십시오. 답.n이 짝수면 n2은 4의 배수, 홀수면 나머지가 1입니다. 풀이.n이 짝수이면 n=2k라 n2=4k2이고 나머지가 0입니다. n이 홀수이면 n=2k+1이라 n2=4k2+4k+1=4(k2+k)+1이고 나머지가 1입니다. 모든 정수는 짝수 아니면 홀수이므로 n2을 4로 나눈 나머지는 항상 0 또는 1입니다. □
문제 22. (표준) 위 결과를 이용해 "4k+3 꼴의 수는 두 정수의 제곱의 합으로 표현되지 않는다"를 귀류법으로 증명하십시오. 답. 제곱수의 나머지가 0,1뿐이라 두 제곱의 합의 나머지는 0,1,2만 가능해 3이 될 수 없습니다. 풀이. 어떤 4k+3 꼴 수가 a2+b2으로 표현된다고 가정합니다. 문제 21에서 a2,b2을 4로 나눈 나머지는 각각 0 또는 1입니다. 두 나머지의 합이 가질 수 있는 값은 0,1,2뿐이라 a2+b2을 4로 나눈 나머지는 0,1,2 중 하나입니다. 그런데 4k+3의 나머지는 3이므로 모순입니다. 따라서 4k+3 꼴 수는 두 제곱의 합이 아닙니다. □
문제 23. (표준) 모든 자연수 n에 대해 i=1∑ni⋅i!=(n+1)!−1임을 귀납법으로 증명하십시오. 답. 기저 n=1: 1=2!−1. 귀납: (k+1)!−1+(k+1)(k+1)!=(k+2)!−1. 풀이. 기저단계: n=1이면 좌변 1⋅1!=1, 우변 2!−1=1로 참입니다. 귀납단계: ∑i=1ki⋅i!=(k+1)!−1이라 가정하면, n=k+1일 때 좌변은
문제 24. (표준) "7n−1은 모든 자연수 n에서 6의 배수이다"를 귀납법으로 증명하십시오. 답. 기저 n=1: 6. 귀납: 7k+1−1=7(7k−1)+6이라 두 항 모두 6의 배수입니다. 풀이. 기저단계: n=1이면 7−1=6이 6의 배수입니다. 귀납단계: 7k−1이 6의 배수라 가정하면 7k+1−1=7⋅7k−1=7(7k−1)+7−1=7(7k−1)+6입니다. 첫 항은 귀납가정으로 6의 배수, 둘째 항 6도 6의 배수라 합이 6의 배수입니다. 따라서 모든 자연수에서 성립합니다. □
문제 25. (표준) "두 유리수 사이에는 항상 또 다른 유리수가 있다"를 구성으로 증명하십시오(유리수의 조밀성). 답. 서로 다른 유리수 a<b의 평균 2a+b가 둘 사이의 유리수입니다. 풀이. 유리수 a,b(a<b)에 대해 m=2a+b를 봅니다. 유리수의 합과 2로 나눈 몫은 유리수이므로 m은 유리수입니다. 또 a<b에서 a=2a+a<2a+b<2b+b=b이므로 a<m<b입니다. 곧 a와 b 사이에 유리수 m이 존재합니다. 이 과정을 반복하면 두 유리수 사이에 무한히 많은 유리수가 있음도 알 수 있습니다. □
문제 27. (심화) n≥5인 모든 자연수에 대해 2n>n2임을 귀납법으로 증명하십시오. 답. 기저 n=5: 32>25. 귀납: n≥5에서 2n+1=2⋅2n>2n2≥(n+1)2. 풀이. 기저단계: n=5이면 25=32>25=52로 참입니다. 귀납단계: n≥5에서 2n>n2이라 가정하면 2n+1=2⋅2n>2n2입니다. 이제 2n2≥(n+1)2임을 보이면 됩니다. 2n2−(n+1)2=n2−2n−1=(n−1)2−2이고 n≥5에서 (n−1)2≥16>2이라 양수이므로 2n2>(n+1)2입니다. 따라서 2n+1>(n+1)2이고, n≥5인 모든 자연수에서 성립합니다. □
문제 28. (심화) 평면 위의 n≥1개의 직선이 어느 둘도 평행하지 않고 어느 셋도 한 점에서 만나지 않으면 교점의 개수가 2n(n−1)임을 귀납법으로 증명하십시오. 답. 기저 n=1: 0. 귀납: 새 직선은 기존 k개와 각각 한 점에서 만나 교점 k개를 더합니다. 풀이. 기저단계: n=1이면 교점이 0개이고 21⋅0=0으로 참입니다. 귀납단계: k개의 직선이 위 조건에서 2k(k−1)개의 교점을 가진다고 가정합니다. (k+1)번째 직선을 추가하면, 이 직선은 기존 k개 직선 각각과 평행하지 않아 정확히 한 점에서 만나고, 어느 셋도 한 점에서 만나지 않으므로 이 교점들은 모두 서로 다른 새 점입니다. 따라서 교점이 k개 늘어나 총
2k(k−1)+k=2k(k−1)+2k=2k(k+1)=2(k+1)((k+1)−1)
입니다. 공식에 n=k+1을 넣은 값과 같으므로 모든 자연수에서 성립합니다. □
문제 29. (심화) 크기 n인 집합의 부분집합 개수가 2n임을 귀납법으로 증명하십시오. 답. 기저 n=0: 20=1(공집합의 부분집합은 자신뿐). 귀납: 원소를 하나 추가하면 부분집합이 두 배가 됩니다. 풀이. 기저단계: n=0이면 집합은 ∅이고 그 부분집합은 ∅ 하나뿐이라 20=1로 참입니다. 귀납단계: 크기 k인 집합의 부분집합이 2k개라 가정합니다. 크기 k+1인 집합 A∪{x}(x∈/A, ∣A∣=k)의 부분집합은 "x를 포함하지 않는 것"과 "x를 포함하는 것"으로 나뉩니다. 앞은 A의 부분집합이라 2k개이고, 뒤는 A의 부분집합에 x를 넣은 것이라 역시 2k개입니다. 둘은 겹치지 않으므로 합쳐 2k+2k=2k+1개입니다. 따라서 모든 n에서 부분집합은 2n개입니다. □
문제 30. (심화) "완전제곱수가 아닌 양의 정수 m에 대해 m은 무리수이다"를 증명하십시오. 답.m=p/q(기약)이면 mq2=p2에서 소인수 지수의 홀짝이 어긋나 모순입니다. 풀이.m이 완전제곱수가 아니라고 하고 m이 유리수라 가정합니다. 서로소인 p,q로 m=qp라 쓰면 p2=mq2입니다. 임의의 소수 r에 대해 p2의 소인수분해에서 r의 지수는 짝수이고, q2의 지수도 짝수입니다. 따라서 p2=mq2에서 m이 기여하는 각 소수의 지수도 짝수여야 하는데, 이는 m의 모든 소인수 지수가 짝수, 곧 m이 완전제곱수임을 뜻합니다. 이는 가정에 모순이므로 m은 무리수입니다. (기약 가정 대신 소인수분해의 유일성을 사용한 증명입니다.) □
문제 31. (심화) 임의의 함수 f:A→A와 유한집합 A에 대해 "f가 전사이면 단사이다"를 증명하십시오(문제 13의 쌍대). 답. 전사이면 치역이 A 전체라 ∣f(A)∣=∣A∣이고, 유한집합에서 이는 겹치는 값이 없음, 곧 단사를 뜻합니다. 풀이.f가 전사이면 치역 f(A)=A이므로 ∣f(A)∣=∣A∣입니다. 만약 f가 단사가 아니라면 f(x1)=f(x2)인 서로 다른 x1,x2가 있어 정의역 ∣A∣개의 입력이 만드는 서로 다른 값은 ∣A∣개 미만이 되어 ∣f(A)∣<∣A∣입니다. 이는 ∣f(A)∣=∣A∣에 모순입니다. 따라서 f는 단사입니다. (유한집합에서 단사·전사·전단사가 서로 동치임을 보여 줍니다.) □
문제 32. (심화) 비둘기집 원리 "n+1개의 물건을 n개의 상자에 넣으면 두 개 이상 든 상자가 있다"를 귀류법으로 증명하십시오. 답. 모든 상자가 최대 한 개면 총합이 n 이하라 n+1개를 넣었다는 사실에 모순입니다. 풀이. 어떤 상자에도 두 개 이상 들지 않는다고 가정합니다. 그러면 각 상자에는 물건이 0개 또는 1개뿐이므로, n개의 상자에 든 물건의 총합은 최대 n개입니다. 그런데 넣은 물건은 n+1개이므로 n+1≤n이 되어 모순입니다. 따라서 적어도 하나의 상자에는 두 개 이상의 물건이 들어 있습니다. □
정답 요지: (1) (P→Q)≡¬P∨Q≡¬Q→¬P, (P∧Q)→R≡P→(Q→R). (2) ¬∀∃≡∃∀¬처럼 기호를 바꾸고 안쪽을 부정. (3) A⊆B∧B⊆A 또는 x∈A⟺x∈B. (4) 단사 합성은 단사, 왼쪽 역 존재는 단사와 대응, 전단사만 역함수. (5) 동치관계 ↔ 분할 ↔ 합동은 모두 "같은 것끼리 조각내기"의 다른 얼굴. (6) 결론 부정이 쉬우면 대우·귀류, 자연수 전체면 귀납, 전체명제 부정은 반례. (7) 상의 크기와 정의역·공역 크기 비교로 단사 ⇔ 전사 ⇔ 전단사.