[이산구조 개념-10] 존재 증명과 유일성 증명 — "있다"와 "오직 하나"의 수학

1. 존재 증명과 유일성 증명의 차이

먼저 두 증명의 차이를 명확히 잡고 시작한다.

구분존재 증명유일성 증명

증명 대상	∃x P(x)	∃!x P(x)
한국어	"P를 만족하는 x가 적어도 하나 존재"	"P를 만족하는 x가 오직 하나만 존재"
필요 단계	존재성 1단계	존재성 + 유일성 2단계
비유	"보물이 있다"	"보물이 딱 하나 있다"

💡 핵심 차이: 존재 증명은 "있음"만 보이면 끝, 유일성 증명은 "있음 + 그것밖에 없음"을 모두 보여야 한다.

---

2. 존재 증명 (Existence Proof)

정의

특정 조건을 만족하는 요소가 적어도 하나 존재함을 입증하는 증명 전략. ∃x P(x) 형태의 명제를 증명한다.

보물찾기 비유

"이 섬에 보물이 묻혀 있다"를 증명하려면, 딱 하나의 보물만 찾아내면 된다. 모든 곳을 다 파볼 필요 없다.

일상 예시

명제: "만 19세 이상인 한국인이 존재한다." 증명: "김철수(35세)가 만 19세 이상인 한국인이다." → 끝!

특정 한 사람을 지목하면 증명 완료. 모든 한국인이 만 19세 이상일 필요는 없다.

---

3. 존재 증명의 두 가지 방식

존재 증명은 접근 방식에 따라 두 가지로 나뉜다.

방식영문핵심

건설적 증명	Constructive Proof	조건을 만족하는 구체적 예시 c를 직접 제시
비건설적 증명	Non-constructive Proof	구체적 예시 없이, "그런 c가 존재할 수밖에 없음" 간접 증명

---

4. 건설적 존재 증명 (Constructive Proof) ⭐

핵심 원리

조건을 만족하는 구체적인 c를 직접 찾아서 제시한다.

풀이 패턴

단계작업

1	조건을 만족할 만한 후보 c 찾기
2	c가 실제로 조건을 만족함을 검증
3	증명 완료 (제시 = 증명)

---

건설적 증명 예제 1 — 기본형

정리: "어떤 정수 x에 대해 x² = 4가 존재한다."

풀이

예시 제시: x = 2 (또는 x = −2)

검증:

후보계산

x = 2	2² = 4 ✅
x = −2	(−2)² = 4 ✅

조건을 만족하는 정수가 존재함을 직접 보여줌 → 증명 완료 ✅

---

건설적 증명 예제 2 — 고난도 (라마누잔의 1729) ⭐⭐⭐

이산구조 교재의 전설적인 예제다. 인도 수학자 라마누잔의 일화에서 유래한다.

정리: "두 수의 세제곱의 합을 두 가지 서로 다른 방법으로 나타낼 수 있는 양의 정수 n이 존재한다."

즉, n = j³ + k³ = l³ + m³을 만족하는 (j, k) ≠ (l, m)인 양의 정수가 있다.

풀이

예시 제시: n = 1729

검증:

표현 방법계산

9³ + 10³	729 + 1000 = 1729 ✅
1³ + 12³	1 + 1728 = 1729 ✅

서로 다른 두 쌍의 세제곱 합으로 모두 1729가 됨 → 조건을 만족하는 n이 존재 → 증명 완료 ✅

💡 라마누잔과 1729의 일화: 1919년, 영국 수학자 하디(Hardy)가 입원한 라마누잔을 문병하며 "내가 타고 온 택시 번호 1729는 너무 평범한 숫자야"라고 말하자, 라마누잔이 즉시 답했다. "아닙니다, 하디 씨. 1729는 두 가지 방법으로 두 양의 세제곱의 합으로 표현되는 가장 작은 수입니다." 이후 1729는 "하디-라마누잔 수" 또는 택시 수(Taxicab number) 라 불린다.

---

5. 비건설적 존재 증명 (Non-constructive Proof)

핵심 원리

구체적인 c를 제시하지 않고, "그런 c가 존재하지 않으면 모순"임을 증명한다.

주로 모순 증명(귀류법) 과 결합된다.

풀이 패턴

단계작업

1	"조건을 만족하는 c가 존재하지 않는다"고 가정
2	이 가정으로부터 모순 도출
3	모순이므로 c는 존재해야 함

---

비건설적 증명 예제

정리: "두 유리수 사이에 무리수가 존재한다."

이 명제는 특정 무리수를 콕 집어 제시하기 어렵다. 대신 비건설적으로:

1. 두 유리수 a, b (a < b) 사이에 무리수가 없다고 가정
2. 그렇다면 a~b 사이의 모든 수는 유리수
3. 그런데 유리수는 가산집합(셀 수 있는 무한)이고, 실수 구간은 비가산집합 → 모순
4. 따라서 a~b 사이에는 무리수가 존재해야 함 ✅

💡 건설적 vs 비건설적 비교:

• 건설적: "이게 답이야!" (정답을 보여줌)
• 비건설적: "답이 없으면 우주가 무너져!" (없으면 모순)

시험에서는 대부분 건설적 증명이 출제된다. 비건설적은 고급 수학에서 주로 다룬다.

---

6. 유일성 증명 (Uniqueness Proof) ⭐⭐⭐

정의

특정 조건을 만족하는 요소가 '오직 하나만' 존재함을 입증하는 증명 전략. ∃!x P(x) 형태의 명제를 증명한다.

기호 ∃!의 의미

기호의미

∃x P(x)	적어도 하나 존재
∃!x P(x)	유일하게 하나만 존재

일상 예시

"나의 가장 친한 친구는 오직 한 명뿐이다."

증명하려면: ① 가장 친한 친구가 있다 (존재성) ② 다른 누구도 가장 친한 친구가 아니다 (유일성)

둘 다 보여야 한다.

---

7. 유일성 증명의 2단계 구조 ⭐ 핵심

유일성 증명은 반드시 두 단계로 나뉜다.

1단계: 존재성 (Existence)

조건 P를 만족하는 요소 x가 적어도 하나 존재함을 증명한다. → 위에서 배운 존재 증명과 동일.

2단계: 유일성 (Uniqueness)

조건 P를 만족하는 두 요소 x, y가 있다고 가정한 뒤, x = y임을 도출한다. → "둘 다 조건 만족 = 사실 같은 것"

단계가정도출

존재성	—	P(x)를 만족하는 x가 적어도 하나 존재
유일성	P(x), P(y) 모두 참	x = y

💡 유일성 증명의 본질: "다른 후보가 있다고 쳐도, 결국 처음 것과 같다"는 것을 보이는 과정이다.

---

유일성 증명 예제 ⭐

정리: "방정식 2x + 1 = 5를 만족하는 유일한 실수 x가 존재한다."

1단계: 존재성

풀이: 2x + 1 = 5 → 2x = 4 → x = 2

x = 2가 조건을 만족하는 실수임을 직접 제시 → 존재성 증명 완료 ✅

2단계: 유일성

가정: y도 같은 방정식을 만족하는 실수라고 하자. 즉 2y + 1 = 5.

도출:

단계식

1	2y + 1 = 5
2	2y = 4
3	y = 2

결론: y = 2 = x → x = y → 조건을 만족하는 실수는 오직 하나뿐 ✅

---

8. 유일성 증명 일반 패턴

풀이 템플릿

 

 

[1단계: 존재성]
- 조건을 만족하는 c를 직접 제시 (또는 비건설적 증명)
- c가 P(c)를 만족함을 검증

[2단계: 유일성]
- 또 다른 d가 P(d)를 만족한다고 가정
- 논리 전개를 통해 c = d 도출
- 따라서 조건을 만족하는 요소는 오직 c 하나

시험 빈출 응용

분야유일성 적용 예

선형대수	역행렬의 유일성
미적분	함수 극한의 유일성
데이터베이스	UNIQUE 키 — 같은 키 값을 가진 레코드는 단 하나
알고리즘	최단 경로 알고리즘의 유일한 최적해

💡 싱글턴 패턴(Singleton Pattern): 객체지향 프로그래밍에서 클래스의 인스턴스가 오직 하나만 존재하도록 보장하는 디자인 패턴. 이 패턴의 수학적 기반이 바로 유일성 증명이다.

---

9. 존재 증명 vs 유일성 증명 vs 모순 증명 — 종합 비교

이산구조에서 자주 헷갈리는 세 증명을 한 표로 정리한다.

구분증명 대상핵심 단계빈출 사례

존재 증명	∃x P(x)	예시 c 제시 또는 비건설적	라마누잔 1729
유일성 증명	∃!x P(x)	존재성 + 유일성 (2단계)	방정식의 유일 해
모순 증명	p (참)	¬p 가정 → 모순 도출	√2 무리수

---

10. 자주 하는 실수 4가지

실수 ① 존재 증명에서 "모든"을 증명

잘못: "어떤 학생은 장학금을 받는다"를 증명하려고 모든 학생이 받음을 보임

존재 증명은 하나만 보이면 된다. 과잉 증명은 비효율적.

실수 ② 유일성 증명에서 존재성 누락

잘못: "유일하게 존재함"을 증명할 때 유일성만 보이고 존재성 증명을 빠뜨림

∃!x = ∃x + 유일성. 둘 다 필요.

실수 ③ 비건설적 증명을 건설적인 척 표기

잘못: 모순으로 존재 증명한 뒤 "예시 = ?" 으로 끝맺음

비건설적은 비건설적임을 명확히 표기해야 한다.

실수 ④ 유일성 증명에서 x ≠ y로 시작하기

잘못: "x ≠ y인 두 요소가 모두 P를 만족한다고 가정 → 모순 도출"

이 방식도 가능하지만(귀류법), 더 깔끔한 방법은:

"x, y 둘 다 P를 만족한다고 가정 → x = y 도출"

전자는 모순 증명, 후자는 직접 증명. 시험에서는 후자가 채점이 깔끔하다.

---

11. 증명 시리즈 전체 흐름 정리 (1~10강)

이산구조 논리·증명 파트가 모두 끝났다. 전체 학습 흐름을 한눈에 정리한다.

강주제핵심

1강	부울 대수와 명제 논리	명제, AND/OR/NOT, 함축, 진리표
2강	항진·부정·동치	Tautology, Contradiction, 진리표 증명
3강	동치 법칙 12선	드모르간, 분배, 함축 변환 등
특별편	드모르간과 AI	19세기 논리 → 21세기 AI
4강	술어 논리와 중첩 한정자 기초	∀, ∃, 술어, 직독직해
5강	한정자 순서·부정·동치 심화	∀∃ vs ∃∀, 도미노 플립
6강	추론 규칙 7선	Modus Ponens, Resolution 등
7강	형식적 증명	추론 규칙 결합으로 증명 작성
8강	한정자 추론 + 증명 용어	UI, EI, 공리·정리·보조정리
9강	4대 증명 전략	직접·대우·모순·경우별
10강	존재·유일성 증명	∃x P(x), ∃!x P(x)

---

📌 한눈에 보는 핵심정리

개념핵심

존재 증명	∃x P(x) — "적어도 하나 존재"
건설적 증명	구체적 예시 c를 직접 제시
비건설적 증명	c 제시 없이 모순으로 존재 입증
유일성 증명	∃!x P(x) — "오직 하나만 존재"
유일성 2단계	존재성 (∃) + 유일성 (x=y 도출)
유일성 패턴	"P(x), P(y) 가정 → x = y 도출"
라마누잔 1729	9³+10³ = 1³+12³ = 1729 (택시 수)
응용 분야	UNIQUE 키, 싱글턴, 역행렬, 극한
시험 자주 묻는 점	존재 vs 유일 차이, 건설적 vs 비건설적

---

🧠 예상문제 2제

문제 1. 존재 증명 vs 유일성 증명 구분

다음 명제를 증명할 때 반드시 2단계 증명이 필요한 것은?

① ∃x (x² = 16, x는 정수) ② ∃!x (x + 3 = 7, x는 실수) ③ ∃x (x는 짝수 소수) ④ ∃x (x³ = 27, x는 정수)

👉 정답: ②

각 명제 분석:

번호명제증명 방식

①	x² = 16인 정수 존재	존재 증명 (x = 4 또는 −4 제시)
②	x + 3 = 7을 만족하는 유일한 실수 존재	유일성 증명 — 2단계 필수
③	짝수 소수 존재	존재 증명 (x = 2 제시)
④	x³ = 27인 정수 존재	존재 증명 (x = 3 제시)

②번 풀이:

• 1단계 (존재성): x = 4 → 4 + 3 = 7 ✅
• 2단계 (유일성): y + 3 = 7도 만족한다 가정 → y = 4 = x → 유일 ✅

💡 시험 핵심 구분: ∃! 기호가 보이면 무조건 2단계 증명. ∃만 있으면 1단계 존재 증명으로 끝.

---

문제 2. 건설적 존재 증명

다음 정리를 건설적 존재 증명으로 풀 때, 제시할 수 있는 가장 적절한 예시 n은?

정리: "두 양의 정수의 제곱의 합으로 표현 가능한 100 이하의 양의 정수 n이 존재한다."

즉, n = a² + b² (a, b는 양의 정수)을 만족하는 100 이하 n이 있다.

① n = 7 (a, b 제시 불가) ② n = 13 (a = 2, b = 3) ③ n = 11 (a, b 제시 불가) ④ n = 23 (a, b 제시 불가)

👉 정답: ②

각 후보 검증:

n가능한 (a, b)검증

7	없음	1+4=5, 1+9=10, 4+9=13 → 7 표현 불가 ❌
13	(2, 3)	2² + 3² = 4 + 9 = 13 ✅
11	없음	1+9=10, 1+16=17 → 11 표현 불가 ❌
23	없음	양의 정수 제곱의 합으로 표현 불가 ❌

건설적 증명 완성: n = 13, a = 2, b = 3 제시 → 13 = 2² + 3² 검증 → 증명 완료 ✅

💡 건설적 증명의 본질: 단 하나의 사례만 제시하면 끝난다. 모든 가능한 n을 찾을 필요 없고, 검증 가능한 가장 쉬운 예시 하나면 충분하다. 라마누잔의 1729처럼 흥미로운 예시를 찾아내는 것이 수학자들의 매력이다.

💡 추가 학습: 두 제곱의 합으로 표현 가능한 수에 대한 일반 정리는 페르마의 두 제곱수 정리(Fermat's theorem on sums of two squares)로 알려져 있다. "어떤 홀수 소수 p가 두 제곱수의 합으로 표현될 수 있을 필요충분조건은 p ≡ 1 (mod 4)이다." — 이 정리의 증명에는 본문에서 다룬 모든 증명 전략이 동원된다.