26주차 — 존재 증명과 유일성

26주차 — 존재 증명과 유일성#

이 주의 길잡이

핵심 문장: 존재는 증인 하나로, 유일성은 둘을 가정해 하나로.

이 주의 위치: 50주 과정의 26주차. 6부(비조건 명제)의 마지막 주 — 10주차의 증인과 15주차의 증인 제작에 “그것이 하나뿐인가”라는 두 번째 의무를 더한다.

원서 대응: BoP(Book of Proof) 7.3 (Existence Proofs), 7.4 (Constructive vs. Non-Constructive) — 병행자 참고용. 원서 없이 읽을 수 있다.

이번 주 목표#

  1. 구성적 존재 증명(증인 제작 + 전 조건 검증)을 서식으로 완성한다.

  2. 비구성적 존재 증명 — 증인을 특정하지 않고 존재를 확정하는 논법 — 을 읽고 쓸 수 있다.

  3. 유일성 증명의 표준 틀(“둘이라 가정하고 같음을 보인다”)을 백지에서 재현한다.

  4. \(\exists!\)(유일 존재)의 뜻과 “존재 + 유일”의 2단 서식을 쓰고, 두 의무가 독립임을 예로 설명한다.

본문 곳곳의 확인 상자는 연필로 먼저 답하는 자리다. 바로 아래의 답 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다.

준비 운동 (25주차 복습)#

  1. iff 증명의 서식을 쓰시오.

  2. “\(\exists x \in S,\ P(x)\)”가 참임을 보이는 데 필요한 것이 무엇인지 쓰시오. (10주차 비대칭 표)

  3. 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주차까지 세운 도구는 존재 명제 하나를 처리한다 — 증인을 제작하고 조건을 검증하면 끝이다. 이번 주의 대표 명제를 그 도구만으로 밀어붙여 보자.

시도 — 증인 제시로 밀어붙이기

명제: 짝수인 소수는 유일하게 존재한다.

“2를 증인으로 제시한다. 2는 짝수이고, 양의 약수가 1과 2뿐이므로 소수이다.

따라서 짝수인 소수는 존재한다.

다른 짝수도 확인해 보자. 4는 \(2 \times 2\)이므로 소수가 아니고, 6은

\(2 \times 3\)이므로 소수가 아니고, 8도, 10도 아니다. 따라서 … “

여기서 멈춘다. 짝수는 무한히 많으므로 이 확인은 끝나지 않는다. 존재 파트는 증인 하나로 끝났는데, “하나뿐”이라는 주장은 확인해야 할 대상이 무한하다.

확인 1. 멈춘 자리에서 다음 줄이 나오려면, 4\(\cdot\)6\(\cdot\)8을 하나씩 확인하는 대신

무엇을 무대에 올려야 하는가. 1주차에서 무한한 사례를 한 번에 처리한 방법을

떠올려 한 구절로 적어 보자.

답

문자를 올린다 — “\(p\)를 짝수인 소수라 하자”로 시작해, 특정 짝수가 아니라

조건을 만족하는 아무 대상 하나를 대표시킨다. 그 뒤에 \(p = 2\)를 유도하면

확인하지 않은 나머지 전부가 한 번에 처리된다.

1주차에서 “모든 짝수”를 문자 \(m\)으로 처리한 것과 정확히 같은 수법이고,

대상이 “조건을 만족하는 후보”로 바뀌었을 뿐이다.

이 주 전체의 기준

존재는 대상 하나를 만들어 내면 끝난다.

유일성은 대상을 세는 일이 아니라, 후보 둘을 문자로 잡아 같음을 보이는 일이다.

두 일은 서로 다른 일이므로 증명도 따로 쓴다.

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}\)

확인 2. 빈칸 (1)~(4)를 채우고, 세 행이 공통으로 하는 일을 두 단계로

요약해 보자.

답

(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) [백지 암기 대상]#

명제. \(\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\)”을 어긴다.

확인 3. “전부”를 지우는 순간 정확히 무엇이 무너지는가. (\(x = 0\)만의

문제인지, 조건이 세 개 이상인 명제에서는 어떤지 함께 생각해 보자.)

답

거짓 명제도 증명되어 버린다. 방금 실험한 명제가 실제로 거짓인데도

한 줄짜리 “증명”이 통과했다. 조건 중 하나만 골라 확인해도 되는 규칙이라면,

그 하나만 만족하는 대상을 아무거나 내밀어 어떤 존재 명제든 “증명”할 수 있다.

조건이 세 개면 빠뜨릴 자리가 두 개로 늘어난다 — 조건이 늘수록 검증 줄 수가

늘어야 한다. 검증 줄 수를 조건 개수와 맞추는 것이 이번 주의 채점 기준이다.

4 증인을 특정하지 않는 존재 증명#

존재 명제 중에는 증인을 지정해도 검증을 끝낼 수 없는 것이 있다. 그래도 존재가 확정되는 길이 있다. 예제 2.2에서 다룰 명제를 미리 놓고 보면 — “\(a^b\)가 유리수인 무리수 \(a, b\)가 존재한다”에서 후보를 지정하는 것까지는 되지만, 그 수가 무리수인지 판정할 도구가 이 과정에는 없다. 정의 26.1의 검증 조각이 어느 후보에 대해서도 닫히지 않는다.

이때 쓰는 것이 다음 두 논법이다.

정의 26.2 — 비구성적 존재 증명 (non-constructive proof)#

증인을 특정하지 않은 채 “증인이 존재한다”만 확정하는 존재 증명.

① 경우 나누기 — 경우마다 증인을 마련하되, 실제로 어느 경우인지는 판정하지 않는다.

② 귀류법 — “그런 대상이 존재하지 않는다”를 가정해 모순을 얻는다.

①이 성립하려면 나눈 경우들이 전체를 빠짐없이 덮어야 한다(17주차의 채점 기준 그대로). 예제 2.2에서는 “어떤 수든 유리수이거나 무리수이다”가 그 역할을 한다. 이처럼 “명제와 그 부정 중 하나는 반드시 참”이라는 원리를 배중률(law of excluded middle)이라 한다. 이름은 새롭지만 17주차부터 경우 나누기가 전체를 덮는 근거로 쓰던 것이다.

확인 4. 22주차 문제 13(실수 \(x_1, \dots, x_n\)의 평균이 \(\mu\)이면 적어도

하나의 \(x_i\)가 \(\mu\) 이상)은 위 두 논법 중 어느 쪽인가. 그리고 그 증명이

끝난 뒤에도 특정되지 않는 것은 무엇인가.

답

② 귀류법이다 — “모든 \(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}\)

확인 5. 빈칸 (1)~(4)를 채우고, 세 행이 공통으로 하는 일을 한 문장으로

적어 보자. 세 행 어디에도 나오지 않은 가정이 하나 있다 — 무엇인가.

답

(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 — 유일성 증명의 표준 틀 [백지 암기 대상]#

“\(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\)에 대해서는 아무 말도 할 수 없다. 유일성 증명이 반드시 두 개의 등식에서 출발하는 이유가 이 조각이다.

확인 6. “\(x_1 \neq x_2\)인 두 해가 있다고 가정하자”로 시작해도 되는가.

된다면 그 증명은 어떻게 끝나야 하는가.

답

된다. 그 경우는 귀류 형태이므로 모순으로 끝나야 한다 — \(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) [백지 암기 대상]#

\(\exists!\, x,\ P(x)\)는 “\(P(x)\)인 \(x\)가 존재하고(존재), 그런 \(x\)는 유일하다(유일)”를 뜻한다.

기호 \(\exists!\, x,\ P(x)\)는 “\(P(x)\)인 \(x\)가 유일하게 존재한다”로 읽는다. \(\exists\) 뒤에 붙은 표시가 “하나뿐”을 나타낸다. 읽는 법까지가 정의다.

증명은 두 문단으로 쓴다. 두 의무는 서로를 함의하지 않으므로, 한쪽을 썼다고 다른 쪽이 따라오지 않는다.

의무

무엇을 하는가

빠뜨리면 남는 것

(존재)

증인 제시 + 전 조건 검증 (정의 26.1)

“있다면 하나뿐” — 조건을 만족하는 것이 0개여도 참인 진술

(유일)

둘 가정 \(\to\) 같음 (정의 26.3)

증인이 여럿일 가능성이 그대로 남는다

확인 7. “\(x^2 = -1\)인 실수는 있다면 하나뿐이다”는 참인가. 그리고

“\(x^2 = -1\)인 실수가 존재한다”는 참인가.

답

앞은 참이고 뒤는 거짓이다.

앞: 유일성 주장은 “\(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와 배중률이다. 이 구분이 흐려지면 “서식대로 썼으니 맞다”는 답안이 나오는데, 서식은 빈칸의 배치일 뿐이고 각 빈칸을 채우는 것은 여전히 근거 ①~④다.

확인 8. 어떤 답안에 다음 세 문장이 나왔다. 각각 허용되는가.

허용된다면 몇 번 근거인가.

(가) “\(x = 4\)를 대입하면 \(3 \cdot 4 - 12 = 0\)이므로 조건을 만족한다”

(나) “15주차 문제 17에 의해 \(a\)와 \(b\) 사이에 유리수가 존재한다”

(다) “다른 짝수를 몇 개 확인해 보니 전부 소수가 아니었으므로 2뿐이다”

답

(가) 허용 — 검증 계산은 근거 ③(등식의 성질)이고, 그 계산이 조건을 만족한다는

판정은 근거 ①이다. 존재 파트의 정상적인 한 줄이다.

(나) 허용 — 근거 ④. 이미 증명된 존재 정리를 부품으로 쓰는 것이며, 문제 12가

이 인용 위에 세워진다.

(다) 불허 — 확인한 짝수에 대해서만 참인 관찰이다. §1.1에서 멈춘 그 자리이며,

유일성 주장의 근거가 되지 않는다.