# 26주차 — 존재 증명과 유일성 :::{admonition} 이 주의 길잡이 :class: keybox **핵심 문장**: 존재는 증인 하나로, 유일성은 둘을 가정해 하나로. **이 주의 위치**: 50주 과정의 26주차. 6부(비조건 명제)의 마지막 주 — 10주차의 증인과 15주차의 증인 제작에 "그것이 하나뿐인가"라는 두 번째 의무를 더한다. **원서 대응**: BoP(Book of Proof) 7.3 (Existence Proofs), 7.4 (Constructive vs. Non-Constructive) — 병행자 참고용. 원서 없이 읽을 수 있다. ::: ## 이번 주 목표 1. 구성적 존재 증명(증인 제작 + 전 조건 검증)을 서식으로 완성한다. 1. **비구성적 존재 증명** — 증인을 특정하지 않고 존재를 확정하는 논법 — 을 읽고 쓸 수 있다. 1. 유일성 증명의 표준 틀("둘이라 가정하고 같음을 보인다")을 백지에서 재현한다. 1. $\exists!$(유일 존재)의 뜻과 "존재 + 유일"의 2단 서식을 쓰고, 두 의무가 독립임을 예로 설명한다. 본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다. ## 준비 운동 (25주차 복습) 1. iff 증명의 서식을 쓰시오. 1. "$\exists x \in S,\ P(x)$"가 참임을 보이는 데 필요한 것이 무엇인지 쓰시오. (10주차 비대칭 표) 1. 10주차 문제 18에서 "모든 $y$에 대해 $x + y = y$인 $x$가 유일"함을 어떻게 보였는지 기억을 떠올려 쓰시오. 답은 §6 해설 맨 앞에 있다. 채점까지 마친 뒤 본문으로 들어간다. ### 자주 나오는 세 가지 답 — 3번 문항 3번에 대한 답은 대개 다음 세 유형 중 하나로 갈린다. 셋 다 옳은 부분이 있고, 셋 다 이번 주에 메울 정확한 간격이 있다. - **유형 1 — 후보를 하나씩 배제.** "$x = 1$이면 $1 + y \neq y$, $x = 2$면 역시 아니다, $x = -1$도 아니다 — 그러니 0뿐이다"라고 적는다. 확인한 후보에 대해서는 옳다. 간격은 후보의 개수다 — 실수는 무한히 많으므로 배제는 끝나지 않는다. 1주차 준비 운동의 유형 1(예시 확인)이 유일성 쪽으로 옮겨 온 것이고, 이번 주 §1.1이 그 막힘을 다시 보인다. - **유형 2 — 증인만 다시 제시.** "$x = 0$이 조건을 만족하므로 유일하다"라고 적는다. 증인과 검증은 옳다. 빠진 것은 유일성 자체다 — "0이 조건을 만족한다"는 다른 수가 조건을 만족하지 **않는다**는 말을 한 마디도 하지 않는다. 존재와 유일이 별개의 의무라는 것이 §1.5의 주제다. - **유형 3 — 대입은 했는데 결합이 없다.** "$y = 1$을 넣으면 $x = 0$이 나온다"까지 적고 멈춘다. 계산은 옳고, 사실 유일성 증명의 핵심 계산을 이미 손에 쥐고 있다. 빠진 것은 그 계산을 **두 후보에 각각** 적용하고 두 결과를 잇는 문장이다 — "$x_1 = 0$이고 $x_2 = 0$이므로 $x_1 = x_2$". 이 두 줄이 표준 틀의 전부이며 §1.4에서 서식으로 굳힌다. ## 개념 — 존재와 유일 ### 1 증인 제작만으로 시도하면 어디서 막히는가 15주차까지 세운 도구는 존재 명제 하나를 처리한다 — 증인을 제작하고 조건을 검증하면 끝이다. 이번 주의 대표 명제를 그 도구만으로 밀어붙여 보자. :::{admonition} 시도 — 증인 제시로 밀어붙이기 :class: quotebox 명제: 짝수인 소수는 **유일하게** 존재한다. "2를 증인으로 제시한다. 2는 짝수이고, 양의 약수가 1과 2뿐이므로 소수이다. 따라서 짝수인 소수는 존재한다. 다른 짝수도 확인해 보자. 4는 $2 \times 2$이므로 소수가 아니고, 6은 $2 \times 3$이므로 소수가 아니고, 8도, 10도 아니다. 따라서 … " ::: 여기서 멈춘다. 짝수는 무한히 많으므로 이 확인은 끝나지 않는다. 존재 파트는 증인 하나로 끝났는데, "하나뿐"이라는 주장은 확인해야 할 대상이 무한하다. :::{container} quotebox **확인 1.** 멈춘 자리에서 다음 줄이 나오려면, 4$\cdot$6$\cdot$8을 하나씩 확인하는 대신 무엇을 무대에 올려야 하는가. 1주차에서 무한한 사례를 한 번에 처리한 방법을 떠올려 한 구절로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown **문자**를 올린다 — "$p$를 짝수인 소수라 하자"로 시작해, 특정 짝수가 아니라 조건을 만족하는 **아무** 대상 하나를 대표시킨다. 그 뒤에 $p = 2$를 유도하면 확인하지 않은 나머지 전부가 한 번에 처리된다. 1주차에서 "모든 짝수"를 문자 $m$으로 처리한 것과 정확히 같은 수법이고, 대상이 "조건을 만족하는 후보"로 바뀌었을 뿐이다. ::: :::{admonition} 이 주 전체의 기준 :class: quotebox 존재는 대상 **하나**를 만들어 내면 끝난다. 유일성은 대상을 세는 일이 아니라, 후보 **둘**을 문자로 잡아 같음을 보이는 일이다. 두 일은 서로 다른 일이므로 증명도 따로 쓴다. ::: ### 2 존재 증명 — 표를 채워 서식 만들기 먼저 존재 쪽을 정리한다. 이미 여러 번 해 본 일이므로, 한 일을 표로 모아 놓고 공통 절차를 뽑아내는 순서로 간다. 각 행에서 증인과 검증할 조건을 채워 보자. | **존재 명제** | **증인** | **검증해야 할 조건** | |---|---|---| | $2x = 6$인 정수 $x$가 존재한다 | $x = 3$ | ① $2 \cdot 3 = 6$ ② $3$은 정수 | | $n^2 = n$인 0이 아닌 실수가 존재한다 | $n = \underline{\quad(1)\quad}$ | ① $\underline{\quad(2)\quad}$ ② $n \neq 0$ | | $0 < c < 1$인 유리수 $c$가 존재한다 | $c = \underline{\quad(3)\quad}$ | ① $c$는 유리수 ② $\underline{\quad(4)\quad}$ | :::{container} quotebox **확인 2.** 빈칸 (1)~(4)를 채우고, 세 행이 공통으로 하는 일을 두 단계로 요약해 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) $1$ (2) $1^2 = 1$ (3) $\frac{1}{2}$ (다른 유리수여도 된다) (4) $0 < \frac{1}{2} < 1$. 공통 절차는 두 단계다 — ① 조건을 만족할 것 같은 대상 **하나**를 제시한다 ② 그 대상이 조건을 **전부** 만족함을 계산으로 확인한다. **세 행 모두 조건이 두 개**라는 점에 주의한다 — 첫째 행은 등식과 무대(정수), 둘째 행은 등식과 $n \neq 0$, 셋째 행은 무대(유리수)와 부등식이다. 조건 개수를 먼저 세고 검증 줄을 그 개수에 맞춘다. 셋째 행에서 유리수인지만 확인하고 사이에 있는지를 빠뜨리면 검증이 반쪽이다(15주차 문제 17에서 같은 지적을 했다). 둘째 행의 무대가 자연수가 아니라 실수인 것은 이 과정의 규약 $\mathbb{N} = \{1, 2, 3, \dots\}$(3주차) 때문이다 — 자연수 무대에서는 $n \neq 0$이 결코 실패할 수 없어 검증 칸이 죽는다. 조건은 어길 수 있어야 조건이다. ::: 이 절차에 정식 이름과 형식을 붙인다. 서식 자체에 새로운 것은 없다 — 방금 표에서 한 일을 문장으로 굳혔을 뿐이다. ### 정의 26.1 — 구성적 존재 증명 (constructive existence proof) [백지 암기 대상] :::{container} quotebox **명제.** $\exists x,\ P(x)$. **증명.** $x = (\text{구체적 대상 또는 제작식})$을 생각하자. (검증) 이 $x$가 $P$의 조건을 **전부** 만족함을 확인한다. $\blacksquare$ ::: 증인은 상수($x = 3$)일 수도 있고, 가정의 재료로 만든 식($y = x + 1$, $c = \frac{a+b}{2}$)일 수도 있다(15주차 예제 2.3, 문제 17). 어느 쪽이든 증명의 분량은 검증 쪽이 대부분을 차지한다. ### 3 정의 해부 — 조각마다 하는 일 이 서식은 네 조각으로 되어 있고, 조각마다 증명에서 맡는 역할이 다르다. | **조각** | **하는 일** | **증명에서의 역할** | |---|---|---| | "$x = (\text{구체적 대상 또는 제작식})$" | 증인의 지정 | 무한한 후보를 하나로 좁힌다 — 존재의 부담이 여기서 끝난다 | | "을 생각하자" | 무대 등록 | 뒤따르는 검증 계산이 가리킬 대상을 확정한다 | | "(검증)" | 자격 심사 | 제시만으로는 미완성이다 — 검증이 증명의 본체다 | | "조건을 **전부**" | 누락 금지 | 조건이 여러 개면 하나만 확인해도 미완성이다 | **조각 삭제 실험.** 넷째 조각의 "전부"를 지워 보자. 그러면 명제 "$x^2 = x$이고 $x < 0$인 실수가 존재한다"에 증인 $x = 0$을 내고 $0^2 = 0$ 한 줄만 적어도 검증이 통과된다. 그런데 이 명제는 **거짓**이다 — $x^2 = x$를 만족하는 실수는 $0$과 $1$뿐이고 둘 다 음수가 아니므로 조건을 만족하는 실수는 하나도 없다. 통과시킨 증인 $0$도 둘째 조건 "$x < 0$"을 어긴다. :::{container} quotebox **확인 3.** "전부"를 지우는 순간 정확히 무엇이 무너지는가. ($x = 0$만의 문제인지, 조건이 세 개 이상인 명제에서는 어떤지 함께 생각해 보자.) ::: :::{admonition} 답 :class: quotebox dropdown **거짓 명제도 증명되어 버린다.** 방금 실험한 명제가 실제로 거짓인데도 한 줄짜리 "증명"이 통과했다. 조건 중 하나만 골라 확인해도 되는 규칙이라면, 그 하나만 만족하는 대상을 아무거나 내밀어 어떤 존재 명제든 "증명"할 수 있다. 조건이 세 개면 빠뜨릴 자리가 두 개로 늘어난다 — 조건이 늘수록 검증 줄 수가 늘어야 한다. 검증 줄 수를 조건 개수와 맞추는 것이 이번 주의 채점 기준이다. ::: ### 4 증인을 특정하지 않는 존재 증명 존재 명제 중에는 증인을 지정해도 검증을 끝낼 수 없는 것이 있다. 그래도 존재가 확정되는 길이 있다. 예제 2.2에서 다룰 명제를 미리 놓고 보면 — "$a^b$가 유리수인 무리수 $a, b$가 존재한다"에서 후보를 지정하는 것까지는 되지만, 그 수가 무리수인지 판정할 도구가 이 과정에는 없다. 정의 26.1의 검증 조각이 어느 후보에 대해서도 닫히지 않는다. 이때 쓰는 것이 다음 두 논법이다. ### 정의 26.2 — 비구성적 존재 증명 (non-constructive proof) :::{container} quotebox 증인을 특정하지 않은 채 "증인이 존재한다"만 확정하는 존재 증명. ① **경우 나누기** — 경우마다 증인을 마련하되, 실제로 어느 경우인지는 판정하지 않는다. ② **귀류법** — "그런 대상이 존재하지 않는다"를 가정해 모순을 얻는다. ::: ①이 성립하려면 나눈 경우들이 전체를 빠짐없이 덮어야 한다(17주차의 채점 기준 그대로). 예제 2.2에서는 "어떤 수든 유리수이거나 무리수이다"가 그 역할을 한다. 이처럼 "명제와 그 부정 중 하나는 반드시 참"이라는 원리를 **배중률**(law of excluded middle)이라 한다. 이름은 새롭지만 17주차부터 경우 나누기가 전체를 덮는 근거로 쓰던 것이다. :::{container} quotebox **확인 4.** 22주차 문제 13(실수 $x_1, \dots, x_n$의 평균이 $\mu$이면 적어도 하나의 $x_i$가 $\mu$ 이상)은 위 두 논법 중 어느 쪽인가. 그리고 그 증명이 끝난 뒤에도 특정되지 않는 것은 무엇인가. ::: :::{admonition} 답 :class: quotebox dropdown ② 귀류법이다 — "모든 $x_i$가 $\mu$ 미만"을 가정해 총합에서 모순을 얻었다. 증명이 끝난 뒤에도 **어느 $i$가** $\mu$ 이상인지는 특정되지 않는다. 존재가 확정되는 것과 증인이 특정되는 것은 별개다. 이번 주 문제 19가 같은 구조의 문제다. ::: **여담.** 비구성적 증명은 "있다"만 알려 주고 "무엇인지"는 알려 주지 않는다. 이를 증명으로 인정할지를 두고 20세기 초에 논쟁이 있었다(직관주의). 현대 주류 수학은 인정하고, 이 과정도 그렇게 다룬다. 다만 장단점은 문제 20에서 정리한다. ### 5 유일성 — 표를 채워 틀 만들기 §1.1에서 막힌 자리로 돌아간다. 후보를 하나씩 배제하는 대신 문자 둘을 잡는다. 각 행에서 "둘을 가정하면 무엇이 손에 들어오고, 그 둘을 결합하면 무엇이 나오는지"를 채워 보자. | **유일성 주장** | **조건을 만족하는 것 둘을 가정하면** | **두 조건을 결합하면** | |---|---|---| | $5x = 20$인 실수 $x$ | $5x_1 = 20$, $5x_2 = 20$ | $5x_1 = 5x_2$이므로 $x_1 = x_2$ | | $x + 7 = 2$인 실수 $x$ | $x_1 + 7 = 2$, $\underline{\quad(1)\quad}$ | $x_1 + 7 = x_2 + 7$이므로 $\underline{\quad(2)\quad}$ | | 모든 $y$에 대해 $x + y = y$인 실수 $x$ | 모든 $y$에 대해 $x_1 + y = y$, $\underline{\quad(3)\quad}$ | $y = 1$을 대입하면 $x_1 = 0$, $x_2 = 0$이므로 $\underline{\quad(4)\quad}$ | :::{container} quotebox **확인 5.** 빈칸 (1)~(4)를 채우고, 세 행이 공통으로 하는 일을 한 문장으로 적어 보자. 세 행 어디에도 나오지 **않은** 가정이 하나 있다 — 무엇인가. ::: :::{admonition} 답 :class: quotebox dropdown (1) $x_2 + 7 = 2$ (2) $x_1 = x_2$ (3) 모든 $y$에 대해 $x_2 + y = y$ (4) $x_1 = x_2$. 공통으로 하는 일: 조건을 **두 번** 발동해 등식 두 개를 확보하고, 그 둘을 결합해 $x_1 = x_2$를 유도한다. 나오지 않은 가정은 "$x_1 \neq x_2$"다. 결론이 "같다"이므로 다르다는 가정은 필요 없고, 실제로 어느 행에서도 쓰이지 않았다. ::: 이 절차에 이름과 형식을 붙인다. ### 정의 26.3 — 유일성 증명의 표준 틀 [백지 암기 대상] :::{container} quotebox "$P(x)$를 만족하는 $x$는 유일하다"의 증명: $x_1$과 $x_2$가 모두 $P$를 만족한다고 가정하자. $\quad\vdots$ (두 조건을 결합한다) 따라서 $x_1 = x_2$이다. $\blacksquare$ ::: 조각마다 하는 일은 이렇다. | **조각** | **하는 일** | **증명에서의 역할** | |---|---|---| | "$x_1$과 $x_2$가" | 후보 둘의 도입 | 이름이 둘일 뿐 다르다고 가정하지 않는다 — 결론이 "같다"이므로 | | "**모두** $P$를 만족한다고" | 조건의 이중 발동 | 정의를 두 번 풀어 결합할 등식 두 개를 확보한다 | | "가정하자" | 임의성의 선언 | 특정한 두 수가 아니라 조건을 만족하는 아무 둘 — 그래야 전체가 덮인다 | | "따라서 $x_1 = x_2$" | 도착점 | "서로 다른 둘은 있을 수 없다"를 등식으로 적은 것 | **조각 삭제 실험.** 둘째 조각의 "모두"를 지워 $x_1$만 $P$를 만족한다고 해 보자. 그러면 손에 들어오는 등식이 하나뿐이라 결합할 상대가 없고, $x_2$에 대해서는 아무 말도 할 수 없다. 유일성 증명이 반드시 두 개의 등식에서 출발하는 이유가 이 조각이다. :::{container} quotebox **확인 6.** "$x_1 \neq x_2$인 두 해가 있다고 가정하자"로 시작해도 되는가. 된다면 그 증명은 어떻게 끝나야 하는가. ::: :::{admonition} 답 :class: quotebox dropdown 된다. 그 경우는 귀류 형태이므로 **모순**으로 끝나야 한다 — $x_1 = x_2$를 유도한 뒤 "이는 $x_1 \neq x_2$와 모순이다"를 반드시 적는다. 흔한 형태는 $x_1 \neq x_2$를 가정해 놓고 $x_1 = x_2$를 얻은 뒤 그대로 끝내는 것인데, 그러면 마지막 모순 선언이 빠져 증명이 닫히지 않는다. 표준 틀은 쓰이지도 않는 가정을 얹지 않으므로 그런 누락 자체가 생기지 않는다. ::: ### 6 유일 존재 $\exists!$ 존재와 유일을 한 기호로 묶은 것이 다음이다. ### 정의 26.4 — 유일 존재 $\exists!$ (unique existence) [백지 암기 대상] :::{container} quotebox $\exists!\, x,\ P(x)$는 "$P(x)$인 $x$가 **존재하고**(존재), 그런 $x$는 **유일하다**(유일)"를 뜻한다. ::: 기호 $\exists!\, x,\ P(x)$는 "$P(x)$인 $x$가 유일하게 존재한다"로 읽는다. $\exists$ 뒤에 붙은 표시가 "하나뿐"을 나타낸다. 읽는 법까지가 정의다. 증명은 두 문단으로 쓴다. 두 의무는 서로를 함의하지 않으므로, 한쪽을 썼다고 다른 쪽이 따라오지 않는다. | **의무** | **무엇을 하는가** | **빠뜨리면 남는 것** | |---|---|---| | (존재) | 증인 제시 + 전 조건 검증 (정의 26.1) | "있다면 하나뿐" — 조건을 만족하는 것이 0개여도 참인 진술 | | (유일) | 둘 가정 $\to$ 같음 (정의 26.3) | 증인이 여럿일 가능성이 그대로 남는다 | :::{container} quotebox **확인 7.** "$x^2 = -1$인 실수는 있다면 하나뿐이다"는 참인가. 그리고 "$x^2 = -1$인 실수가 존재한다"는 참인가. ::: :::{admonition} 답 :class: quotebox dropdown 앞은 참이고 뒤는 거짓이다. 앞: 유일성 주장은 "$x_1^2 = -1$이고 $x_2^2 = -1$이면 $x_1 = x_2$"라는 조건문인데, 실수의 제곱은 음수가 될 수 없으므로 가정이 결코 성립하지 않는다. 가정이 거짓인 조건문은 참이다 — 4주차 §1.4의 공허한 참이 유일성 쪽에서 재등장했다. 뒤: 증인이 존재하지 않으므로 거짓이다. 유일성이 존재를 전혀 보장하지 않는다는 것이 이 한 쌍으로 확인된다. 문제 5와 문제 18이 정확히 이 지점을 묻는다. ::: ### 7 근거 목록 갱신 — 칸은 그대로 네 개 1주차에서 세우고 매주 갱신해 온 허용 근거 목록에 이번 주의 항목을 더한다. 칸의 개수는 늘지 않는다. | **근거** | **내용** | **이번 주에는 이렇게 쓴다** | |---|---|---| | ① 정의 | 기존 정의들 + **정의 26.4**($\exists!$의 뜻) | "$\exists!$"를 "존재 그리고 유일" 두 의무로 번역한다 | | ② 닫힘성 | 정수의 합$\cdot$차$\cdot$곱은 정수 | 증인 검증 계산에서 "$k+1$은 정수이므로"를 그대로 쓴다 | | ③ 등식의 성질 | 양변 연산 / 대입 / 소거 / **추이성** | 유일성의 "결합" 단계는 대부분 이 근거 하나로 끝난다 — 두 값이 같은 것과 같으면 서로 같다 | | ④ 이미 증명한 명제 | 기존 주차의 결과 + **15주차 문제 17**, **22주차 문제 13**, **배중률**(§1.4 — 증명 없이 인정하고 사용, 17주차 "빠짐없음" 근거의 이름) | 기증명 존재 정리를 인용해 새 존재를 얻는다(문제 12). 경우 나누기가 전체를 덮는다는 한 줄을 배중률의 이름으로 인용한다(예제 2.2) | 정의 26.1$\cdot$26.2$\cdot$26.3은 **근거가 아니라 서식**이다 — 증명의 내용을 정당화하는 것이 아니라 증명을 어떤 순서로 적을지를 정한다. 근거 목록에 들어가는 것은 정의 26.4와 배중률이다. 이 구분이 흐려지면 "서식대로 썼으니 맞다"는 답안이 나오는데, 서식은 빈칸의 배치일 뿐이고 각 빈칸을 채우는 것은 여전히 근거 ①~④다. :::{container} quotebox **확인 8.** 어떤 답안에 다음 세 문장이 나왔다. 각각 허용되는가. 허용된다면 몇 번 근거인가. (가) "$x = 4$를 대입하면 $3 \cdot 4 - 12 = 0$이므로 조건을 만족한다" (나) "15주차 문제 17에 의해 $a$와 $b$ 사이에 유리수가 존재한다" (다) "다른 짝수를 몇 개 확인해 보니 전부 소수가 아니었으므로 2뿐이다" ::: :::{admonition} 답 :class: quotebox dropdown (가) 허용 — 검증 계산은 근거 ③(등식의 성질)이고, 그 계산이 조건을 만족한다는 판정은 근거 ①이다. 존재 파트의 정상적인 한 줄이다. (나) 허용 — 근거 ④. 이미 증명된 존재 정리를 부품으로 쓰는 것이며, 문제 12가 이 인용 위에 세워진다. (다) 불허 — 확인한 짝수에 대해서만 참인 관찰이다. §1.1에서 멈춘 그 자리이며, 유일성 주장의 근거가 되지 않는다. :::