# C4주차 — 양화사와 특성화 :::{admonition} 이 주의 길잡이 :class: keybox **핵심 문장**: 양화사는 열린 문장을 명제로 닫는 두 개의 머리말이고, 특성화는 정의가 아닌 동치를 정의처럼 쓸 권리를 증명으로 사 두는 일이다 — 앞의 것은 문장을 판정 가능하게 만들고, 뒤의 것은 판정할 표현을 고를 수 있게 만든다. **이 주의 위치**: 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을 통독한 뒤 이 문서로 온다. ::: ## 이번 주 목표 1. 양화사 $\forall$$\cdot$$\exists$$\cdot$$\exists!$로 열린 문장을 명제로 닫고, 무대와 열린 문장을 분리해 적을 수 있다. 1. 양화 명제의 진위를 비대칭 표에 따라 판정하고, 참$\cdot$거짓 각각에서 제출해야 할 것(증인의 검증 계산 / 반례의 검증 계산 / 일반 논증)을 구분할 수 있다. 1. 양화 명제의 **부정**을 바깥 층부터 한 겹씩 수행하고, 무대와 자격이 부정에서 보존되는 이유를 사례로 설명할 수 있다. 1. 중첩 양화사에서 $\forall x \exists y$와 $\exists y \forall x$의 차이를 맞춤 증인$\cdot$만능 증인으로 설명하고, 한 방향 교환만 성립하는 이유를 말할 수 있다. 1. **특성화**를 정의하고, 정의와 특성화를 가르는 기준(약속된 iff인가, 증명된 iff인가)을 대며, 특성화를 인용할 때 확인할 것을 한 줄로 적을 수 있다. 본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다. ## 준비 운동 (C3주차 · 1권 11주차 · S8주차 복습) 노트에 먼저 적은 뒤 아래를 읽는다. 1. C3주차 §1의 논리 동치 법칙 중 드모르간 두 줄, 조건문 전개, 조건문 부정, 대우를 쓰시오. 1. 1권 11주차 §1.3의 부정 규칙 총목록 여섯 줄을 쓰시오. 그중 양화사에 관한 두 줄이 이번 주의 재료다. 1. S8주차 §1.4의 의존성 문법(맞춤 증인$\cdot$만능 증인)을 쓰고, S8주차 §1.5의 한 방향 교환 정리를 진술하시오. 1. "정수 $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주차에서 손에 넣은 것은 진리표와 동치의 대수였다. 그 도구만으로 다음 문장을 다뤄 보자. :::{admonition} 시도 — 열린 문장에 진리표를 그리기 :class: quotebox 문장: "$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에서 양화사로 닫는다"고만 적어 두었다. :::{container} quotebox **확인 1.** 멈춘 자리에서 "$x^2 \ge 0$"에 무엇을 덧붙이면 진리값이 정해지는가. 두 가지 방식을 떠올려 보자. ::: :::{admonition} 답 :class: quotebox dropdown 첫째, $x$에 구체적인 값을 **대입**한다 — "$3^2 \ge 0$"은 참인 명제다. 둘째, $x$가 어느 범위를 어떻게 훑는지를 **문장 앞에 선언**한다 — "모든 실수 $x$에 대해 $x^2 \ge 0$"이나 "$x^2 \ge 0$인 실수 $x$가 존재한다"는 진리값이 정해진다. 첫째 방식은 문장을 하나가 아니라 무수히 많이 만들 뿐이라 원래 문장을 닫지 못한다. 이번 주가 다루는 것은 둘째 방식이다. ::: :::{admonition} 이 주 전반부의 기준 :class: quotebox 열린 문장은 진리값이 없다. 진리값을 주는 것은 값 하나가 아니라 **범위를 훑는 방식의 선언**이고, 그 선언을 문장 앞에 붙이는 낱말이 양화사다. ::: ### 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}$ 하나 | :::{container} quotebox **확인 2.** 표의 빈칸 (1)~(4)를 채우고, 네 줄에 쓰인 머리말이 몇 종류인지 세어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) 거짓 (2) 반례 (3) 2가 통과 (4) 증인. 머리말은 "모든"과 "존재한다" **두 종류**뿐이다. 열린 문장과 무대는 얼마든지 바꿀 수 있지만 머리말은 늘 이 둘이다. ::: :::{container} quotebox **확인 3.** 표의 오른쪽 끝 열을 보면 참을 보이는 비용과 거짓을 보이는 비용이 머리말마다 다르다. 어느 쪽이 하나로 끝나고 어느 쪽이 전수 처리인가. ::: :::{admonition} 답 :class: quotebox dropdown "모든"은 참을 보이려면 전수 처리(또는 문자를 쓴 일반 논증)이고 거짓은 반례 하나로 끝난다. "존재한다"는 정반대로 참이 증인 하나이고 거짓이 전수 처리다. 싼 칸과 비싼 칸이 대각선으로 마주 본다 — 1권 10주차 §1.4의 비대칭 표가 그 배치이고, §1.4에서 그 표를 이번 주의 기호로 다시 세운다. ::: 이 관찰에 정식 이름과 형식을 붙인다. 식 자체에 새로운 것은 없다 — 방금 표에서 머리말이라 부른 것에 기호를 주고, 무대를 문장 안에 명시적으로 적을 뿐이다. ### 정의 4.1 — 양화 명제 (quantified statement) [백지 암기 대상] :::{container} quotebox 열린 문장 $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$가 **정확히 하나** 있다(존재와 유일, 두 책임). ::: :::{admonition} 표기 — $\forall$, $\exists$, $\exists!$ :class: quotebox $\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$ | :::{container} quotebox **확인 4.** 무대 조각을 지운 문장이 왜 명제가 아닌지 한 문장으로 적어 보자. §1.1의 열린 문장과 무엇이 같고 무엇이 다른가. ::: :::{admonition} 답 :class: quotebox dropdown 진리값이 하나로 정해지지 않으므로 명제가 아니다. §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$이므로 조건을 만족한다"까지 적어야 완결이다. :::{container} quotebox **확인 5.** 다음 두 제출물은 비대칭 표의 어느 칸에 놓이며, 각각 완결됐는가. (가) "'모든 실수 $x$에 대해 $x^2 \ge x$'는 거짓이다. $x = \frac12$이 반례다." (나) "'$x^2 = -1$인 실수 $x$가 존재한다'는 거짓이다. $x = 1$을 넣으면 $1 \neq -1$이다." ::: :::{admonition} 답 :class: quotebox dropdown (가)는 $\forall$의 거짓 칸이다. 반례 하나면 충분하지만 검증 계산이 빠졌다 — "$(\frac12)^2 = \frac14 < \frac12$"까지 적어야 완결이다. (나)는 $\exists$의 거짓 칸이고, 완결이 아니다. 후보 하나의 탈락은 다른 후보가 통과할 가능성을 남긴다. 이 칸은 전수 처리가 필요하다 — "모든 실수 $x$에서 $x^2 \ge 0 > -1$이므로 등식이 불가능하다"가 그 처리다. 표에서 가장 비싼 칸이고, §1.5의 부정 규칙이 이 칸을 $\forall$의 참 칸으로 옮겨 준다. ::: ### 5 부정 — 절차 해부와 걸음 삭제 실험 $\exists$의 거짓 칸을 직접 처리하는 대신, 부정을 만들어 $\forall$의 참 칸으로 옮기는 것이 표준이다. 1권 11주차 §1.3의 총목록 중 양화사 두 줄을 이번 주의 기호로 적으면 다음과 같다. :::{admonition} 백지 암기 대상 :class: keybox **양화 명제의 부정 규칙** $$ \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에서 "자격은 부정되지 않는다"로 다시 확인한 것이, 여기서 부정 절차의 **한 걸음**이라는 자리를 얻는다. :::{container} quotebox **확인 6.** 자격이 붙은 전칭 "모든 양수 $x$에 대해 $P(x)$"를 무대 $\mathbb{R}$의 조건문으로 풀어 쓰면 어떤 문장인가. 그 문장에 부정 규칙과 C3주차의 조건문 부정을 차례로 적용하면 자격이 어떤 모양으로 살아남는가. ::: :::{admonition} 답 :class: quotebox dropdown 풀어 쓰면 "$\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) $$ :::{container} quotebox **확인 7.** 둘째 걸음을 적어 보자. 이번에 마주치는 바깥 층은 무엇이고, 규칙 두 줄 중 어느 줄을 쓰는가. ::: :::{admonition} 답 :class: quotebox dropdown 바깥 층은 $\exists y$이고, 둘째 줄($\sim \exists \leadsto \forall \sim$)을 쓴다. $$ \exists x\, \forall y\ \sim(\forall z,\ P) $$ 무대가 붙어 있다면 그대로 두고 양화사만 뒤집는다. ::: :::{container} quotebox **확인 8.** 다음 중 절차가 끝난 상태는 어느 쪽인가. 끝나지 않은 쪽은 어느 걸음이 남았는가. (가) $\exists x\, \forall y\ \sim(\forall z,\ P(x,y,z))$ (나) $\exists x\, \forall y\, \exists z,\ \sim P(x,y,z)$ ::: :::{admonition} 답 :class: quotebox dropdown (나)가 끝난 상태다. (가)는 $\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의 순서 규칙). :::{admonition} 백지 암기 대상 :class: keybox **의존성의 문법** $\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$도 참이다. 역은 성립하지 않는다. ::: :::{container} quotebox **확인 9.** 위 두 문장의 진위를 각각 판정해 보자. 참인 쪽은 증인을 제시하고, 거짓인 쪽은 어떤 증인도 실패함을 보이자. ::: :::{admonition} 답 :class: quotebox dropdown 첫째 문장은 **참**이다. $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$이 무너진다. 만능 증인은 존재하지 않는다. ::: :::{container} quotebox **확인 10.** 한 방향 교환 정리가 왜 한 방향뿐인지, 방금의 두 문장으로 설명해 보자. ::: :::{admonition} 답 :class: quotebox dropdown 만능 증인이 있으면 그것을 $x$마다 그대로 재사용하면 되므로 $\exists\forall$에서 $\forall\exists$로는 언제나 갈 수 있다. 거꾸로는 갈 수 없다 — 방금 첫째 문장의 증인 $y = -x$는 $x$에 의존하므로, $x$가 정해지기 전에는 제시할 수 없다. 맞춤 증인을 모아도 만능 증인이 되지는 않는다. 첫째가 참이고 둘째가 거짓인 이 한 쌍이 역의 반례다 (S8주차 §1.5, 문제 17). ::: ### 7 정의만으로 막히는 자리 — 특성화의 필요 여기서부터 이번 주의 후반부다. 이제까지의 도구(정의와 양화사, 부정 절차, 그리고 1권 17주차의 경우 나누기)를 손에 쥐고 다음 명제를 밀어붙여 보자. :::{admonition} 시도 — 정의만으로 밀어붙이기 :class: quotebox 명제: 정수 $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$을 꺼내 주지 않는다. :::{container} quotebox **확인 11.** 멈춘 자리에서 필요한 것은 어떤 문장인가. 그 문장은 짝수의 정의로 곧장 얻어지는가. 1권 17주차의 경우 나누기로 우회할 수 있는가. ::: :::{admonition} 답 :class: quotebox dropdown 필요한 것은 "$n^2$이 짝수이면 $n$은 짝수이다"라는 문장이다. 정의로는 곧장 얻어지지 않는다. 정의는 "짝수"라는 이름과 "$2k$ 꼴"이라는 조건 사이를 양방향으로 번역해 줄 뿐이고, $n^2$의 성질에서 $n$의 성질로 건너가는 다리는 정의에 들어 있지 않다. 경우 나누기로도 우회되지 않는다. $n$을 짝수$\cdot$홀수로 나누면 홀수 경우를 배제해야 하는데, 그 배제에 쓰이는 "$n$이 홀수이면 $n^2$도 홀수이다"가 바로 같은 다리의 대우이기 때문이다. 우회로가 다시 같은 문장으로 돌아온다. 그 문장은 1권 19주차 예제 2.1에서 대우로 **증명한 정리**다. ::: 그러면 정의가 아닌 문장을 정의 자리에 넣어 써도 되는가. 답은 "증명되어 있으면 된다"이고, 이 답을 정식 개념으로 세운 것이 이번 주 후반부다. ### 정의 4.2 — 특성화 (characterization) [백지 암기 대상] :::{container} quotebox 개념 $C$의 **특성화**란, "$x$가 $C$이다 $\iff$ (다른 조건)"의 꼴로 **증명된** 정리다. 일단 증명되면 그 조건은 정의와 똑같이 양방향으로 쓸 수 있다. 정의와 다른 점은 iff의 출처 하나다 — 정의의 iff는 약속이라 공짜로 주어지고, 특성화의 iff는 증명한 뒤에야 손에 들어온다. ::: 이 정의는 세 조각으로 되어 있고, 조각마다 증명에서 맡는 역할이 다르다. | **조각** | **하는 일** | **증명에서의 역할** | |---|---|---| | "$x$가 $C$이다" | 왼쪽 항 고정 | 갈아 끼울 대상이 개념의 **이름**임을 밝힌다 — 조건끼리의 동치는 특성화가 아니다 | | "$\iff$ (다른 조건)" | 양방향 보장 | 이름에서 조건으로도, 조건에서 이름으로도 갈 수 있다 — 한 방향만 증명하면 쓸 수 없다 | | "증명된 정리다" | 사용 자격 | 인용할 때 어디서 증명됐는지 댈 수 있어야 한다 (아래 실험) | **조각 삭제 실험 — "증명된"을 지우면.** 셋째 조각을 지우고 "동치처럼 보이는 조건이면 갈아 끼운다"고 해 보자. 그러면 다음이 통과한다. :::{container} quotebox "정수 $n$이 짝수 $\iff$ $n$이 4의 배수. 따라서 $n$이 짝수이면 $n = 4k$로 쓸 수 있다." ::: $n = 2$가 이 "특성화"의 반례이므로 잘못된 결론이 흘러나온다. 더 나쁜 경우도 있다. 아직 증명하지 않은 참인 동치를 인용하면, 그 동치의 증명 안에서 지금 증명하려는 명제를 쓰게 되는 **순환**이 생긴다 — 문제 16(b)이 그 사례다. 셋째 조각은 형식적인 단서가 아니라 두 종류의 붕괴를 막는 조건이다. :::{container} quotebox **확인 12.** 다음 두 문장 중 어느 쪽이 짝수의 정의이고 어느 쪽이 특성화인가. 그렇게 가른 근거는 무엇인가. (가) 정수 $n$이 짝수라는 것은 $n = 2k$인 정수 $k$가 존재한다는 뜻이다. (나) 정수 $n$이 짝수인 것과 $n \equiv 0 \pmod 2$인 것은 동치이다. ::: :::{admonition} 답 :class: quotebox dropdown (가)가 정의이고 (나)가 특성화다. 근거는 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$묶기 | 그대로 | | ④ 이미 증명한 명제 | 증명이 끝난 정리 | **특성화 정리**가 이 칸의 정식 입주자가 된다 — 인용할 때 어디서 증명됐는지를 함께 적는다 | :::{container} quotebox **확인 13.** 다음 증명 줄에서 인용한 근거는 ①~④ 중 무엇인가. (가) "$n^2$이 짝수이므로 $n$도 짝수이다." (나) "$n$이 짝수이므로 $n = 2a$인 정수 $a$가 존재한다." (다) "$a + b$는 정수이다." ::: :::{admonition} 답 :class: quotebox dropdown (가) 근거 ④ — 특성화 정리의 한 방향이다. 정의로는 나오지 않으므로 "1권 19주차 예제 2.1에서 증명한 특성화에 의해"처럼 출처를 함께 적어야 완결이다. (나) 근거 ① — 짝수의 정의를 푼 것이다. (다) 근거 ② — 닫힘성이다. (가)와 (나)가 겉모습이 비슷해 보이지만 대는 근거가 다르다. 이 구분이 이번 주가 세운 것이고, 이 구분이 없으면 확인 12의 (나)를 정의라 부르는 유형 1로 돌아간다. :::