C4주차 — 양화사와 특성화

내용

C4주차 — 양화사와 특성화#

이 주의 길잡이

핵심 문장: 양화사는 열린 문장을 명제로 닫는 두 개의 머리말이고, 특성화는 정의가 아닌 동치를 정의처럼 쓸 권리를 증명으로 사 두는 일이다 — 앞의 것은 문장을 판정 가능하게 만들고, 뒤의 것은 판정할 표현을 고를 수 있게 만든다.

이 주의 위치: 2학기 20주의 C4주차이자 논리 파트의 마지막 주. C3주차에서 세운 동치의 대수는 진리값이 정해진 명제에만 작동했고, 열린 문장은 그 대수의 바깥에 남아 있었다. 이번 주가 그 문장들을 안으로 들인다. 1권 10주차의 순서 규칙과 11주차의 부정 규칙, 그리고 S5~S8주차의 양화사 4기법이 여기서 한 장의 판정\(\cdot\)부정 절차로 모이고, 1권 25주차에서 방향마다 기법을 골라 증명하던 iff 명제가 여기서 특성화라는 이름과 사용 권한을 얻는다.

원서 대응: Chartrand 2.10~2.11 (Quantified Statements / Characterizations). 주간 루틴 1일차에 원서 2.10~2.11을 통독한 뒤 이 문서로 온다.

이번 주 목표#

양화사 \(\forall\)\(\cdot\)\(\exists\)\(\cdot\)\(\exists!\)로 열린 문장을 명제로 닫고, 무대와 열린 문장을 분리해 적을 수 있다.
양화 명제의 진위를 비대칭 표에 따라 판정하고, 참\(\cdot\)거짓 각각에서 제출해야 할 것(증인의 검증 계산 / 반례의 검증 계산 / 일반 논증)을 구분할 수 있다.
양화 명제의 부정을 바깥 층부터 한 겹씩 수행하고, 무대와 자격이 부정에서 보존되는 이유를 사례로 설명할 수 있다.
중첩 양화사에서 \(\forall x \exists y\)와 \(\exists y \forall x\)의 차이를 맞춤 증인\(\cdot\)만능 증인으로 설명하고, 한 방향 교환만 성립하는 이유를 말할 수 있다.
특성화를 정의하고, 정의와 특성화를 가르는 기준(약속된 iff인가, 증명된 iff인가)을 대며, 특성화를 인용할 때 확인할 것을 한 줄로 적을 수 있다.

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

준비 운동 (C3주차 · 1권 11주차 · S8주차 복습)#

노트에 먼저 적은 뒤 아래를 읽는다.

C3주차 §1의 논리 동치 법칙 중 드모르간 두 줄, 조건문 전개, 조건문 부정, 대우를 쓰시오.
1권 11주차 §1.3의 부정 규칙 총목록 여섯 줄을 쓰시오. 그중 양화사에 관한 두 줄이 이번 주의 재료다.
S8주차 §1.4의 의존성 문법(맞춤 증인\(\cdot\)만능 증인)을 쓰고, S8주차 §1.5의 한 방향 교환 정리를 진술하시오.
“정수 \(n\)이 짝수이다”를 나타내는 표현을 아는 대로 쓰고, 그중 어느 것이 정의이고 어느 것이 정의가 아닌지 표시하시오. 표시의 근거도 함께 적으시오.

자주 나오는 세 가지 답#

4번에서 대개 “\(n = 2k\)”, “\(2 \mid n\)”, “\(n \equiv 0 \pmod 2\)”, “\(n\)은 홀수가 아니다” 정도가 나오고, 어느 것이 정의인지를 물으면 다음 세 유형 중 하나로 답한다. 셋 다 자연스러운 답이고, 셋 다 이번 주가 메울 정확한 간격이 있다.

유형 1 — 넷 다 정의다. “어느 것으로 판정해도 같은 정수가 걸러지므로 넷 다

짝수의 정의다.” 옳은 부분은 분명하다. 네 표현이 같은 정수를 걸러 낸다는 관찰은 참이고, 그것이 이번 주 후반의 출발점이다. 간격은 “같은 것을 걸러 낸다”가 결과이지 근거가 아니라는 데 있다. 정의는 낱말과 조건을 잇는 약속이므로 하나만 둘 수 있고, 나머지 셋이 그 약속과 같은 것을 걸러 낸다는 사실은 증명해야 얻는다. 넷을 나란히 정의라 부르면 무엇을 증명해야 하는지가 목록에서 사라진다.

유형 2 — 교과서가 쓰니까 쓴다. “\(2 \mid n\)도 \(n \equiv 0 \pmod 2\)도 문헌에서

짝수를 뜻하므로 관례대로 바꿔 쓴다.” 관찰은 옳다 — 실제로 문헌은 넷을 자유롭게 갈아 끼운다. 간격은 그 자유의 출처에 있다. 관례는 근거가 되지 못하고, 근거가 적히지 않은 교체는 검사할 수 없다. §1.7에서 보듯 그 자유는 각 표현마다 따로 증명된 정리에서 나오며, 인용할 때 대야 할 것은 관례가 아니라 그 정리다.

유형 3 — iff로 이어져 있으니 같다. “네 표현이 \(\iff\)로 이어지므로 구분할

이유가 없다.” 이 답이 가장 가깝다. 네 표현이 서로 동치인 것은 사실이다. 간격은 그 \(\iff\)가 어디서 왔는지를 묻지 않은 데 있다. 정의의 \(\iff\)는 약속이라 공짜로 주어지고, 나머지의 \(\iff\)는 증명된 뒤에야 손에 들어온다. 이 둘을 구분하지 않으면 아직 증명하지 않은 동치를 근거로 삼는 순환이 생긴다 — 문제 12와 16이 그 사례다.

개념 — 양화사와 특성화#

1 C3의 대수가 멈추는 자리#

이번 주의 도구가 왜 필요한지부터 확인한다. C3주차에서 손에 넣은 것은 진리표와 동치의 대수였다. 그 도구만으로 다음 문장을 다뤄 보자.

시도 — 열린 문장에 진리표를 그리기

문장: “\(x^2 \ge 0\)”

“진리표를 그린다. \(P\)를 ‘\(x^2 \ge 0\)’이라 두면 \(P\)의 열은 T이거나 F인데 —

\(x = 3\)이면 T, \(x = 0\)이면 T, \(x = -1\)이면 T … 그런데 \(x\)가 정해지지 않았으므로

이 열에 T를 적을 근거가 없다. 표의 한 칸도 채워지지 않는다.”

여기서 멈춘다. C3주차의 대수는 진리값이 정해진 명제에만 작동하고, 이 문장은 아직 명제가 아니다. C3주차 §1은 이런 문장을 열린 문장이라 부르고 “C4에서 양화사로 닫는다”고만 적어 두었다.

확인 1. 멈춘 자리에서 “\(x^2 \ge 0\)”에 무엇을 덧붙이면 진리값이 정해지는가. 두 가지 방식을 떠올려 보자.

답

첫째, \(x\)에 구체적인 값을 대입한다 — “\(3^2 \ge 0\)”은 참인 명제다. 둘째,

\(x\)가 어느 범위를 어떻게 훑는지를 문장 앞에 선언한다 — “모든 실수 \(x\)에 대해

\(x^2 \ge 0\)”이나 “\(x^2 \ge 0\)인 실수 \(x\)가 존재한다”는 진리값이 정해진다.

첫째 방식은 문장을 하나가 아니라 무수히 많이 만들 뿐이라 원래 문장을 닫지 못한다.

이번 주가 다루는 것은 둘째 방식이다.

이 주 전반부의 기준

열린 문장은 진리값이 없다. 진리값을 주는 것은 값 하나가 아니라 범위를 훑는 방식의 선언이고, 그 선언을 문장 앞에 붙이는 낱말이 양화사다.

2 닫는 방식은 두 가지뿐 — 표를 채우며#

열린 문장 \(P(x)\)와 무대를 하나 고정하고, 앞에 붙일 수 있는 머리말을 모아 보자. 무대는 \(S = \{1, 2, 3\}\), 열린 문장은 “\(x \le 5\)”와 “\(x = 2\)” 두 가지로 둔다.

머리말 + 열린 문장	뜻	진리값	판정에 쓴 것
\(S\)의 모든 \(x\)에 대해 \(x \le 5\)	1, 2, 3이 전부 통과	참	세 원소 전수 확인
\(S\)의 모든 \(x\)에 대해 \(x = 2\)	1이 실패	\(\underline{\quad(1)\quad}\)	\(\underline{\quad(2)\quad}\) 하나
\(x \le 5\)인 \(x\)가 \(S\)에 존재	1이 통과	참	통과하는 원소 하나
\(x = 2\)인 \(x\)가 \(S\)에 존재	\(\underline{\quad(3)\quad}\)	참	\(\underline{\quad(4)\quad}\) 하나

확인 2. 표의 빈칸 (1)~(4)를 채우고, 네 줄에 쓰인 머리말이 몇 종류인지 세어 보자.

답

(1) 거짓 (2) 반례 (3) 2가 통과 (4) 증인. 머리말은 “모든”과 “존재한다”

두 종류뿐이다. 열린 문장과 무대는 얼마든지 바꿀 수 있지만 머리말은 늘 이 둘이다.

확인 3. 표의 오른쪽 끝 열을 보면 참을 보이는 비용과 거짓을 보이는 비용이 머리말마다 다르다. 어느 쪽이 하나로 끝나고 어느 쪽이 전수 처리인가.

답

“모든”은 참을 보이려면 전수 처리(또는 문자를 쓴 일반 논증)이고 거짓은 반례

하나로 끝난다. “존재한다”는 정반대로 참이 증인 하나이고 거짓이 전수 처리다.

싼 칸과 비싼 칸이 대각선으로 마주 본다 — 1권 10주차 §1.4의 비대칭 표가 그

배치이고, §1.4에서 그 표를 이번 주의 기호로 다시 세운다.

이 관찰에 정식 이름과 형식을 붙인다. 식 자체에 새로운 것은 없다 — 방금 표에서 머리말이라 부른 것에 기호를 주고, 무대를 문장 안에 명시적으로 적을 뿐이다.

정의 4.1 — 양화 명제 (quantified statement) [백지 암기 대상]#

열린 문장 \(P(x)\)와 무대 \(S\)에 대해,

\[ \forall x \in S,\ P(x) \qquad\text{및}\qquad \exists x \in S,\ P(x) \]

는 명제이며 각각 다음을 뜻한다.

\(\forall x \in S,\ P(x)\) — \(S\)의 모든 \(x\)가 \(P(x)\)를 만족한다. 예외가 하나도 없으면 참이다.
\(\exists x \in S,\ P(x)\) — \(P(x)\)를 만족하는 \(x\)가 \(S\)에 적어도 하나 있다. 그런 \(x\)가 하나라도 있으면 참이다.
\(\exists! x \in S,\ P(x)\) — 그런 \(x\)가 정확히 하나 있다(존재와 유일, 두 책임).

표기 — \(\forall\), \(\exists\), \(\exists!\)

\(\forall\)는 “모든”으로 읽고 전칭 양화사(universal quantifier)라 한다. A를 뒤집은

모양이다. \(\exists\)는 “존재한다”로 읽고 존재 양화사(existential quantifier)라 한다.

E를 뒤집은 모양이다. \(\exists!\)는 “정확히 하나 존재한다”로 읽는다(1권 26주차의

유일성, S13주차의 두 얼굴). “\(\forall x \in S,\ P(x)\)”는 소리 내어 “에스에 속하는

모든 엑스에 대해 피 엑스”로 읽는다. 읽는 법까지가 정의다.

산문에서는 이 기호들을 쓰지 않고 낱말로 적는다(C1주차 원칙 3). 이번 주는 양화사

자체가 논의 대상이므로 C3주차와 같은 예외 구역이다.

3 정의 해부 — 조각마다 하는 일#

“\(\forall x \in S,\ P(x)\)”는 네 조각으로 되어 있고, 조각마다 판정에서 맡는 역할이 다르다.

조각	하는 일	판정에서의 역할
\(\forall\)	훑는 방식의 선언	참의 기준을 “예외 없음”으로 고정한다 — 거짓의 기준이 자동으로 “반례 하나”가 된다
\(x\)	묶인 변수	문장 밖에서 값을 받지 않는다 — 그래서 문장 전체의 진리값이 \(x\)에 의존하지 않는다
\(\in S\)	무대의 선언	심사가 벌어지는 범위 — 이 조각이 진리값을 좌우한다 (아래 실험)
\(P(x)\)	심사 조건	각 원소가 통과\(\cdot\)탈락으로 갈리는 기준

조각 삭제 실험 — 무대를 지우면. 셋째 조각을 지우고 “\(\exists x,\ x^2 = 2\)”라고만 적어 보자. 이 문장의 진위를 물으면 답이 나오지 않는다. \(x\)를 자연수에서 찾으라는 것인지 실수에서 찾으라는 것인지가 정해지지 않았기 때문이다. 실제로 무대를 바꿔 넣어 보면 진리값이 갈린다.

무대	\(\exists x,\ x^2 = 2\)의 진위	근거
\(\mathbb{N}\)	거짓	\(1^2 = 1\), \(2^2 = 4\)이고 그 사이의 자연수가 없다
\(\mathbb{Q}\)	거짓	\(\sqrt2\)는 무리수다 (1권 21주차)
\(\mathbb{R}\)	참	증인 \(x = \sqrt2\), 검증 \((\sqrt2)^2 = 2\)

확인 4. 무대 조각을 지운 문장이 왜 명제가 아닌지 한 문장으로 적어 보자. §1.1의 열린 문장과 무엇이 같고 무엇이 다른가.

답

진리값이 하나로 정해지지 않으므로 명제가 아니다. §1.1의 열린 문장과 같은 점은

진리값이 미정이라는 것이고, 다른 점은 미정의 이유다. 열린 문장은 변수의 값이

정해지지 않아서였고, 무대를 지운 문장은 훑을 범위가 정해지지 않아서다.

그래서 이 책은 무대를 늘 문장 안에 적는다 — 무대는 생략해도 되는 장식이 아니라

진리값을 결정하는 조각이다 (1권 3주차).

4 진위의 비대칭 — 어느 칸에서 무엇을 제출하는가#

확인 3에서 관찰한 비대칭을 표로 못 박는다. 1권 10주차 §1.4의 비대칭 표를 이번 주의 기호로 다시 적은 것이다.

	참임을 보이려면	거짓임을 보이려면
\(\forall x \in S,\ P(x)\)	문자를 잡은 일반 논증 (전수 처리)	반례 하나 + 그 반례가 실제로 탈락함을 보이는 검증 계산
\(\exists x \in S,\ P(x)\)	증인 하나 + 그 증인이 실제로 통과함을 보이는 검증 계산	무대의 모든 원소가 탈락함을 보이는 일반 논증

싼 칸(하나로 끝나는 칸)에서도 제출물은 값 하나가 아니다. 값과 검증 계산까지가 제출물이다. “증인은 \(x = \sqrt2\)”만 적으면 절반이고, “\((\sqrt2)^2 = 2\)이므로 조건을 만족한다”까지 적어야 완결이다.

확인 5. 다음 두 제출물은 비대칭 표의 어느 칸에 놓이며, 각각 완결됐는가.

(가) “‘모든 실수 \(x\)에 대해 \(x^2 \ge x\)’는 거짓이다. \(x = \frac12\)이 반례다.”

(나) “’\(x^2 = -1\)인 실수 \(x\)가 존재한다’는 거짓이다. \(x = 1\)을 넣으면 \(1 \neq -1\)이다.”

답

(가)는 \(\forall\)의 거짓 칸이다. 반례 하나면 충분하지만 검증 계산이 빠졌다 —

“\((\frac12)^2 = \frac14 < \frac12\)”까지 적어야 완결이다. (나)는 \(\exists\)의 거짓

칸이고, 완결이 아니다. 후보 하나의 탈락은 다른 후보가 통과할 가능성을 남긴다.

이 칸은 전수 처리가 필요하다 — “모든 실수 \(x\)에서 \(x^2 \ge 0 > -1\)이므로 등식이

불가능하다”가 그 처리다. 표에서 가장 비싼 칸이고, §1.5의 부정 규칙이 이 칸을

\(\forall\)의 참 칸으로 옮겨 준다.

5 부정 — 절차 해부와 걸음 삭제 실험#

\(\exists\)의 거짓 칸을 직접 처리하는 대신, 부정을 만들어 \(\forall\)의 참 칸으로 옮기는 것이 표준이다. 1권 11주차 §1.3의 총목록 중 양화사 두 줄을 이번 주의 기호로 적으면 다음과 같다.

백지 암기 대상

양화 명제의 부정 규칙

\[ \sim(\forall x \in S,\ P(x)) \equiv \exists x \in S,\ \sim P(x) \]

\[ \sim(\exists x \in S,\ P(x)) \equiv \forall x \in S,\ \sim P(x) \]

“모두 통과”의 실패는 낙제자 하나의 존재다.
“합격자 존재”의 실패는 전원 낙제다.
두 줄 모두에서 무대 \(\in S\)는 그대로 남는다. 뒤집히는 것은 양화사와 심사 조건뿐이다.

겹겹인 문장은 이 두 줄을 바깥 층부터 한 겹씩 적용해 처리한다. 걸음을 표로 해부한다.

걸음	하는 일	이 걸음을 빼면 무엇이 무너지는가
① 층 노출	낱말\(\cdot\)기호에 접혀 있는 양화사를 정의의 문장으로 편다	뒤집을 양화사가 문면에 없어 규칙을 적용할 자리가 없다 — §1.1의 멈춤이 재연된다
② 바깥 한 겹 반전	가장 바깥 양화사 하나만 규칙 한 줄로 뒤집는다	여러 겹을 한 번에 뒤집으려다 안쪽 층의 순서를 뒤바꾼다 (예제 2.1의 자주 하는 실수 상자)
③ 무대\(\cdot\)자격 보존	\(\in S\), “\(> 0\)”, “\(> N\)” 같은 자격은 손대지 않는다	원명제와 무관한 세계가 들어와 진리값이 반대가 아니게 된다 (아래 실험)
④ 안쪽으로 이동	남은 안쪽을 한 겹 줄어든 새 문제로 삼아 ②로 돌아간다	중간 상태에서 멈춰 \(\sim\)가 양화사 밖에 남는다 (확인 8)
⑤ 끝 모양 판정	\(\sim\)가 열린 문장 안까지 흡수됐는지 확인한다	제출물이 부정문의 꼴을 갖추지 못해 다음 증명이 시작되지 않는다

걸음 삭제 실험 — ③을 빼면. 참인 명제 “모든 양수 \(x\)에 대해 \(x^2 > 0\)”을 놓고, 자격 “\(> 0\)”까지 뒤집어 “\(x \le 0\)인 어떤 \(x\)에 대해 \(x^2 \le 0\)”이라 적어 보자. \(x = 0\)을 넣으면 \(x \le 0\)이고 \(0^2 = 0 \le 0\)이므로 이 문장은 참이다. 원문도 참이고 부정도 참이 되었다 — 원문과 부정은 어떤 상황에서도 진리값이 반대여야 한다는 부정의 자격이 무너진 것이다. 자격은 주장의 내용이 아니라 심사가 벌어지는 범위의 선언이므로, 주장을 뒤집어도 범위는 그대로여야 한다. 올바른 부정은 “\(x^2 \le 0\)인 양수 \(x\)가 존재한다”이고, 이 문장은 거짓이다.

1권 11주차 §1.4에서 “무대는 뒤집히지 않는다”로 관찰하고 S10주차 §1.4에서 “자격은 부정되지 않는다”로 다시 확인한 것이, 여기서 부정 절차의 한 걸음이라는 자리를 얻는다.

확인 6. 자격이 붙은 전칭 “모든 양수 \(x\)에 대해 \(P(x)\)”를 무대 \(\mathbb{R}\)의 조건문으로 풀어 쓰면 어떤 문장인가. 그 문장에 부정 규칙과 C3주차의 조건문 부정을 차례로 적용하면 자격이 어떤 모양으로 살아남는가.

답

풀어 쓰면 “\(\forall x \in \mathbb{R},\ (x > 0 \Rightarrow P(x))\)”이다. 여기에

\(\forall\) 반전을 적용하면 “\(\exists x \in \mathbb{R},\ \sim(x > 0 \Rightarrow P(x))\)”

이고, 조건문 부정 \(\sim(P \Rightarrow Q) \equiv P \wedge \sim Q\)를 적용하면

“\(\exists x \in \mathbb{R},\ (x > 0 \wedge \sim P(x))\)”이 된다. 자격 “\(x > 0\)”이

\(\wedge\)의 한쪽으로 살아남고 뒤집힌 것은 \(P\)뿐이다. 걸음 ③은 임의로 둔 예외가

아니라 조건문 부정이 계산으로 보증하는 결과다.

세 겹짜리로 절차를 시연한다. 원문은 “\(\forall x \exists y \forall z,\ P(x,y,z)\)”이다. 바깥 층은 \(\forall x\)이므로 첫 줄은 다음과 같다.

\[ \sim(\forall x\, \exists y\, \forall z,\ P) \equiv \exists x\ \sim(\exists y\, \forall z,\ P) \]

확인 7. 둘째 걸음을 적어 보자. 이번에 마주치는 바깥 층은 무엇이고, 규칙 두 줄 중 어느 줄을 쓰는가.

답

바깥 층은 \(\exists y\)이고, 둘째 줄(\(\sim \exists \leadsto \forall \sim\))을 쓴다.

\[ \exists x\, \forall y\ \sim(\forall z,\ P) \]

무대가 붙어 있다면 그대로 두고 양화사만 뒤집는다.

확인 8. 다음 중 절차가 끝난 상태는 어느 쪽인가. 끝나지 않은 쪽은 어느 걸음이 남았는가.

(가) \(\exists x\, \forall y\ \sim(\forall z,\ P(x,y,z))\) (나) \(\exists x\, \forall y\, \exists z,\ \sim P(x,y,z)\)

답

(나)가 끝난 상태다. (가)는 \(\sim\)가 아직 \(\forall z\) 밖에 남아 있으므로 걸음 ②가

한 번 더 필요한 중간 상태다. 끝 모양의 판정 기준은 하나다 — 부정 기호가 양화사

밖에 하나도 남지 않고 맨 안쪽 열린 문장에만 흡수된 상태.

맨 안쪽에서 \(\sim\)를 흡수할 때 부등호가 뒤집힌다: \(=\)의 부정은 \(\neq\), \(<\)의 부정은

\(\ge\), \(>\)의 부정은 \(\le\)다. 반대 방향 부등호가 아니라 “성립하지 않는 경우 전부”다.

6 순서 — 맞춤 증인과 만능 증인#

양화사가 두 개 이상이면 순서가 명제를 바꾼다. 재료가 완전히 같고 순서만 다른 두 문장을 나란히 둔다.

\[ \forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ x + y = 0 \]

\[ \exists y \in \mathbb{R},\ \forall x \in \mathbb{R},\ x + y = 0 \]

왼쪽부터 읽는다. 먼저 나온 변수가 먼저 정해지고, 뒤의 변수는 앞의 변수를 참조할 수 있지만 앞의 변수는 뒤를 알 수 없다 (1권 10주차 §1.6의 순서 규칙).

백지 암기 대상

의존성의 문법

\(\forall x\, \exists y\) — \(y\)가 \(\forall x\)의 안쪽에 있으므로 \(y\)를 \(x\)의 식으로 둘 수 있다. 이런 증인을 맞춤 증인이라 한다.

\(\exists y\, \forall x\) — \(y\)를 먼저 정해야 하므로 \(y\)의 식에 \(x\)를 쓸 수 없다. 하나의 \(y\)가 모든 \(x\)를 감당해야 한다. 이런 증인을 만능 증인이라 한다.

한 방향 교환 정리(S8주차 §1.5): \(\exists y \forall x,\ P\)가 참이면 \(\forall x \exists y,\ P\)도 참이다. 역은 성립하지 않는다.

확인 9. 위 두 문장의 진위를 각각 판정해 보자. 참인 쪽은 증인을 제시하고, 거짓인 쪽은 어떤 증인도 실패함을 보이자.

답

첫째 문장은 참이다. \(x\)가 주어진 뒤 \(y = -x\)로 두면 \(x + (-x) = 0\)이므로 조건을

만족한다 — \(y\)가 \(x\)의 식이므로 맞춤 증인이고, \(\exists y\)가 \(\forall x\) 안쪽에

있으니 합법이다. 둘째 문장은 거짓이다. 어떤 실수 \(y_0\)을 먼저 제시하더라도

\(x = 1 - y_0\)을 잡으면 \(x + y_0 = 1 \neq 0\)이므로 그 \(y_0\)이 무너진다. 만능 증인은

존재하지 않는다.

확인 10. 한 방향 교환 정리가 왜 한 방향뿐인지, 방금의 두 문장으로 설명해 보자.

답

만능 증인이 있으면 그것을 \(x\)마다 그대로 재사용하면 되므로

\(\exists\forall\)에서 \(\forall\exists\)로는 언제나 갈 수 있다. 거꾸로는 갈 수 없다 —

방금 첫째 문장의 증인 \(y = -x\)는 \(x\)에 의존하므로, \(x\)가 정해지기 전에는 제시할 수

없다. 맞춤 증인을 모아도 만능 증인이 되지는 않는다. 첫째가 참이고 둘째가 거짓인

이 한 쌍이 역의 반례다 (S8주차 §1.5, 문제 17).

7 정의만으로 막히는 자리 — 특성화의 필요#

여기서부터 이번 주의 후반부다. 이제까지의 도구(정의와 양화사, 부정 절차, 그리고 1권 17주차의 경우 나누기)를 손에 쥐고 다음 명제를 밀어붙여 보자.

시도 — 정의만으로 밀어붙이기

명제: 정수 \(n\)에 대해, \(n^2\)이 짝수이면 \(n + 2\)도 짝수이다.

“\(n^2\)이 짝수라 하자. 짝수의 정의에 의해 \(n^2 = 2k\)인 정수 \(k\)가 존재한다.

목표는 \(n + 2 = 2 \times (\text{정수})\) 꼴을 만드는 것이다.

\(n + 2\)를 그렇게 묶으려면 \(n\)이 \(2 \times (\text{정수})\)여야 하는데,

손에 있는 등식은 \(n^2 = 2k\)뿐이다. 따라서 … “

여기서 멈춘다. 가정은 \(n^2\)에 대한 등식을 주고 목표는 \(n\)에 대한 등식을 요구하는데, 정의는 \(n^2 = 2k\)에서 \(n\)을 꺼내 주지 않는다.

확인 11. 멈춘 자리에서 필요한 것은 어떤 문장인가. 그 문장은 짝수의 정의로 곧장 얻어지는가. 1권 17주차의 경우 나누기로 우회할 수 있는가.

답

필요한 것은 “\(n^2\)이 짝수이면 \(n\)은 짝수이다”라는 문장이다. 정의로는 곧장 얻어지지

않는다. 정의는 “짝수”라는 이름과 “\(2k\) 꼴”이라는 조건 사이를 양방향으로 번역해 줄

뿐이고, \(n^2\)의 성질에서 \(n\)의 성질로 건너가는 다리는 정의에 들어 있지 않다.

경우 나누기로도 우회되지 않는다. \(n\)을 짝수\(\cdot\)홀수로 나누면 홀수 경우를 배제해야

하는데, 그 배제에 쓰이는 “\(n\)이 홀수이면 \(n^2\)도 홀수이다”가 바로 같은 다리의

대우이기 때문이다. 우회로가 다시 같은 문장으로 돌아온다.

그 문장은 1권 19주차 예제 2.1에서 대우로 증명한 정리다.

그러면 정의가 아닌 문장을 정의 자리에 넣어 써도 되는가. 답은 “증명되어 있으면 된다”이고, 이 답을 정식 개념으로 세운 것이 이번 주 후반부다.

정의 4.2 — 특성화 (characterization) [백지 암기 대상]#

개념 \(C\)의 특성화란, “\(x\)가 \(C\)이다 \(\iff\) (다른 조건)”의 꼴로 증명된 정리다.

일단 증명되면 그 조건은 정의와 똑같이 양방향으로 쓸 수 있다.

정의와 다른 점은 iff의 출처 하나다 — 정의의 iff는 약속이라 공짜로 주어지고, 특성화의 iff는 증명한 뒤에야 손에 들어온다.

이 정의는 세 조각으로 되어 있고, 조각마다 증명에서 맡는 역할이 다르다.

조각	하는 일	증명에서의 역할
“\(x\)가 \(C\)이다”	왼쪽 항 고정	갈아 끼울 대상이 개념의 이름임을 밝힌다 — 조건끼리의 동치는 특성화가 아니다
“\(\iff\) (다른 조건)”	양방향 보장	이름에서 조건으로도, 조건에서 이름으로도 갈 수 있다 — 한 방향만 증명하면 쓸 수 없다
“증명된 정리다”	사용 자격	인용할 때 어디서 증명됐는지 댈 수 있어야 한다 (아래 실험)

조각 삭제 실험 — “증명된”을 지우면. 셋째 조각을 지우고 “동치처럼 보이는 조건이면 갈아 끼운다”고 해 보자. 그러면 다음이 통과한다.

“정수 \(n\)이 짝수 \(\iff\) \(n\)이 4의 배수. 따라서 \(n\)이 짝수이면 \(n = 4k\)로 쓸 수 있다.”

\(n = 2\)가 이 “특성화”의 반례이므로 잘못된 결론이 흘러나온다. 더 나쁜 경우도 있다. 아직 증명하지 않은 참인 동치를 인용하면, 그 동치의 증명 안에서 지금 증명하려는 명제를 쓰게 되는 순환이 생긴다 — 문제 16(b)이 그 사례다. 셋째 조각은 형식적인 단서가 아니라 두 종류의 붕괴를 막는 조건이다.

확인 12. 다음 두 문장 중 어느 쪽이 짝수의 정의이고 어느 쪽이 특성화인가. 그렇게 가른 근거는 무엇인가.

(가) 정수 \(n\)이 짝수라는 것은 \(n = 2k\)인 정수 \(k\)가 존재한다는 뜻이다.

(나) 정수 \(n\)이 짝수인 것과 \(n \equiv 0 \pmod 2\)인 것은 동치이다.

답

(가)가 정의이고 (나)가 특성화다. 근거는 iff의 출처다. (가)는 “짝수”라는 낱말이

무엇을 뜻하는지 약속한 문장이므로 증명할 것이 없다. (나)는 두 조건이 같은 정수를

걸러 낸다는 주장이므로 증명이 필요하다 — 실제로 합동의 정의(1권 20주차 정의 20.1)

\(a \equiv b \pmod n \iff n \mid (a-b)\)를 풀면 \(n \equiv 0 \pmod 2\)는 \(2 \mid n\)이고,

여기서 \(2 \mid n\)은 \(n = 2k\)인 정수 \(k\)의 존재와 같으므로 (가)와 이어진다.

이 몇 줄이 (나)의 값이다.

특성화의 값은 사실 목록과 과녁에 가까운 표현을 골라 쓸 자유를 정리로 사 두는 데 있다. S4주차 §1.6은 이 자유를 “동치인 표현들 중 사실 목록과 과녁의 겉모양에 가까운 것을 고른다”는 조준 규칙으로 이미 썼고, 이번 주는 그 표현들에 이름과 사용 자격을 붙인다. 1권 25주차에서 “방향마다 기법을 따로 고를 수 있는 iff 명제”로 증명하던 것이, 여기서 증명이 끝난 뒤의 사용 권한이라는 이름을 얻는 것이다.

8 근거 목록 갱신 — 칸은 늘지 않고 ④의 입주자가 늘어난다#

증명에서 쓸 수 있는 근거 목록은 1권 이래 네 칸이다. 이번 주에 칸이 늘지는 않는다.

근거	내용	이번 주에 달라지는 것
① 정의	약속된 iff	양화 명제의 정의 4.1과 특성화의 정의 4.2가 여기 들어온다
② 닫힘성	정수\(\cdot\)실수의 연산이 같은 무대 안에 머문다	그대로
③ 등식의 성질	대입\(\cdot\)전개\(\cdot\)묶기	그대로
④ 이미 증명한 명제	증명이 끝난 정리	특성화 정리가 이 칸의 정식 입주자가 된다 — 인용할 때 어디서 증명됐는지를 함께 적는다

확인 13. 다음 증명 줄에서 인용한 근거는 ①~④ 중 무엇인가.

(가) “\(n^2\)이 짝수이므로 \(n\)도 짝수이다.”

(나) “\(n\)이 짝수이므로 \(n = 2a\)인 정수 \(a\)가 존재한다.”

(다) “\(a + b\)는 정수이다.”

답

(가) 근거 ④ — 특성화 정리의 한 방향이다. 정의로는 나오지 않으므로 “1권 19주차

예제 2.1에서 증명한 특성화에 의해”처럼 출처를 함께 적어야 완결이다.

(나) 근거 ① — 짝수의 정의를 푼 것이다. (다) 근거 ② — 닫힘성이다.

(가)와 (나)가 겉모습이 비슷해 보이지만 대는 근거가 다르다. 이 구분이 이번 주가

세운 것이고, 이 구분이 없으면 확인 12의 (나)를 정의라 부르는 유형 1로 돌아간다.