# 10주차 — 양화사 (Quantifiers) :::{admonition} 이 주의 길잡이 :class: keybox **핵심 문장**: 양화사의 순서가 바뀌면 명제가 바뀐다 — 먼저 나온 변수가 먼저 정해진다. **이 주의 위치**: 50주 과정의 10주차. 열린 문장(7주차)을 명제로 만드는 마지막 부품 $\forall$$\cdot$$\exists$를 얻어 수학 문장 해독을 완성하고, 부정 만들기(11주차)와 증명 기법(15주차~)의 재료를 마련한다. **원서 대응**: BoP(Book of Proof) 2.7, 2.9 — 원서 없이 읽을 수 있다. ::: ## 이번 주 목표 1. $\forall$(모든)과 $\exists$(존재)의 **정의**를 백지에 쓰고, 열린 문장이 양화사로 명제가 되는 과정을 설명할 수 있다. 1. 참$\cdot$거짓 입증 부담의 **비대칭 표** — $\forall$$\cdot$$\exists$ 각각의 참과 거짓에 무엇이 필요한가 — 를 재현하고 판정에 적용할 수 있다. 1. $\forall x \exists y$와 $\exists y \forall x$의 차이를 순서 규칙으로 설명하고, 그 차이가 드러나는 예를 직접 설계할 수 있다. 1. 한국어$\cdot$영어 수학 문장과 기호 사이를 양방향으로 번역한다 — 겉에 드러나지 않은 숨은 양화사까지 포함해서. 본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다. ## 준비 운동 (9주차 복습) 1. $\neg(P \Rightarrow Q) \equiv \underline{\quad}$ (조건문의 부정) 1. "$n$이 홀수이면 $n^2$이 홀수이다"의 대우를 쓰시오. 1. 드모르간 법칙 2개를 쓰시오. ### 자주 나오는 세 가지 답 — 1번 문항 방금 쓴 1번의 답은 대개 다음 세 유형 중 하나다. 셋 다 옳은 부분이 있고, 셋 다 이번 주 학습 전에 메워 둘 정확한 간격이 있다. - **유형 1 — $P \Rightarrow \neg Q$로 적음.** 부정 기호를 결론에만 통과시킨 것이다. 결론 쪽이 부정되어야 한다는 감각은 옳다. 간격은 조건문 전체의 부정이 더 이상 조건문이 아니라는 점이다 — "가정이 성립하는데 결론이 무너지는 사례가 있다"는 보고, 곧 $P \land \neg Q$다(9주차에서 진리표로 증명했다). - **유형 2 — $\neg P \Rightarrow \neg Q$로 적음.** 대우 만들기 규칙(양쪽 부정 + 자리 교환)의 절반이 적용된 것이다 — 이 꼴은 '이'이고, 부정도 대우도 아니다. 양쪽에 부정을 붙였다는 부분은 대우의 재료로는 옳다. 간격은 두 가지다: 자리가 교환되지 않았고, 애초에 부정은 조건문 꼴로 나오지 않는다. - **유형 3 — $P \land \neg Q$로 정확히 적음.** 남은 간격은 연결이다 — 이 꼴이 곧 반례의 두 조건(① 가정 $P$가 참 ② 결론 $Q$가 거짓)이었다는 것. 이번 주의 비대칭 표(§1.4)에서 이 연결이 "모든" 명제를 반박하는 공식 규칙으로 승격된다. 2번의 대우는 "$n^2$이 홀수가 아니면 $n$은 홀수가 아니다"이고, 3번의 드모르간은 $\neg(P \land Q) \equiv \neg P \lor \neg Q$, $\neg(P \lor Q) \equiv \neg P \land \neg Q$다. 이번 주에는 이 문장들 **앞에** 붙는 낱말 — "모든", "어떤" — 을 다룬다. 그리고 11주차에서 드모르간이 이 낱말들로 확장되는 것을 본다. ## 개념 — 양화사 ### 1 지금의 도구로 시도하면 어디서 막히는가 7주차에서 열린 문장을 만났다: $P(x)$는 $x$가 정해지기 전에는 참도 거짓도 아니어서 명제가 아니다. 8~9주차의 도구(진리표$\cdot$동치$\cdot$대우)는 이미 명제인 문장을 조립하고 변형하는 도구였다. 그 도구만으로 다음 문장을 기호로 적어 보자. :::{admonition} 시도 — 지금의 기호로 밀어붙이기 :class: quotebox 문장: 짝수인 정수가 존재한다. "$P(n)$을 '$n$은 짝수'라 하자. $P(n)$은 열린 문장이므로 명제가 아니다(7주차). $P(4)$는 참인 명제지만 그것은 4 하나에 대한 주장일 뿐이다. '존재한다'는 후보 중 **적어도 하나**가 통과한다는 주장이므로 '또는'으로 잇는다: $P(0) \lor P(1) \lor P(-1) \lor P(2) \lor \cdots$ — " ::: 여기서 멈춘다. 정수는 무한히 많으므로 이 문장은 끝나지 않는다. 6주차의 첨자 합집합에서 예고한 대로 "적어도 하나"는 '또는'의 확장이고 "모든"은 '그리고'의 확장인데, 지금의 언어에는 그 무한 확장을 유한한 기호 하나로 접는 낱말이 없다. :::{container} quotebox **확인 1.** "모든 정수 $n$에 대해 $n^2 \ge 0$이다"를 같은 방식으로 적으면 어떤 모양이 되는가. 진리표로 이 문장의 참을 판정할 수 있는가? ::: :::{admonition} 답 :class: quotebox dropdown $Q(n)$: "$n^2 \ge 0$"이라 하면 $Q(0) \land Q(1) \land Q(-1) \land \cdots$ — '그리고'가 무한 개 필요해 문장이 끝나지 않는다. 진리표도 소용없다 — 진리표는 유한 개의 성분 명제를 전제로 행을 나열하는 도구다. 무한 개의 사례를 유한한 문장 하나로 묶는 새 기호가 필요하다. ::: ### 2 두 개의 머리말 — 표를 채우며 열린 문장을 명제로 만드는 방법을 7주차에서 하나 알았다: 값을 대입한다. 두 번째 방법이 있다 — 문장 앞에 **머리말**을 붙인다. 다음 표의 빈칸을 채워 보자. | **문장** | **명제인가** | **진리값** | |---|---|---| | $x^2 \ge 0$ | 아니다 — $x$가 자유롭다 (7주차) | 없음 | | 모든 실수 $x$에 대해 $x^2 \ge 0$이다 | 명제다 | $\underline{\quad(1)\quad}$ | | $x^2 < 0$인 실수 $x$가 존재한다 | 명제다 | $\underline{\quad(2)\quad}$ | | $2x = 6$인 정수 $x$가 존재한다 | 명제다 | $\underline{\quad(3)\quad}$ | :::{container} quotebox **확인 2.** 빈칸 (1)(2)(3)을 채우고, (3)을 판정할 때 실제로 무엇을 제시했는지 한 구절로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) 참 (2) 거짓 (3) 참 — $x = 3$이 등식 $2 \times 3 = 6$을 성립시킨다. (3)의 판정에 쓴 것은 "성립시키는 값 하나"였다. 같은 열린 문장이라도 머리말 — "모든 ~에 대해" 또는 "~인 ~가 존재한다" — 이 붙는 순간 참$\cdot$거짓이 정해지는 문장, 곧 명제가 된다. 머리말이 판정 규칙까지 정한다는 것이 방금의 경험이다. ::: 이 두 머리말에 정식 이름과 기호를 붙인다. 식 자체에 새로운 것은 없다 — 1주차 정의 1.1의 "…인 정수 $k$가 존재한다"부터 매주 써 온 그 머리말에 기호를 붙였을 뿐이다. ### 정의 10.1 — 양화사 (quantifier) [백지 암기 대상] :::{container} quotebox - **전칭 양화사** $\forall$: "$\forall x \in S,\ P(x)$" = "집합 $S$의 **모든** 원소 $x$에 대해 $P(x)$가 참이다." (for all) - **존재 양화사** $\exists$: "$\exists x \in S,\ P(x)$" = "$P(x)$가 참이 되는 $S$의 원소 $x$가 **적어도 하나 존재**한다." (there exists) ::: 읽는 법: "$\forall x \in \mathbb{R},\ x^2 \ge 0$"은 "모든 실수 엑스에 대해, 엑스 제곱은 영 이상이다"로, "$\exists x \in \mathbb{Z},\ 2x = 6$"은 "이 엑스가 육인 정수 엑스가 존재한다"로 읽는다. 읽는 법까지가 정의다. :::{admonition} 표기 — 기호의 생김새와 쉼표 :class: quotebox $\forall$은 All의 A를, $\exists$는 Exists의 E를 뒤집은 기호다. 쉼표 뒤가 주장의 본문(열린 문장)이고, 쉼표 앞이 "누가 심사받는가"(양화사 + 무대)다. 무대라는 낱말은 2주차 문제 5, 8주차 진리집합에서 쓰던 그대로 — 변수가 값을 고르는 집합이다. ::: ### 3 정의 해부 — 조각마다 하는 일 "$\forall x \in S,\ P(x)$" 한 문장은 네 조각으로 되어 있고, 조각마다 판정에서 맡는 역할이 다르다. | **조각** | **하는 일** | **판정에서의 역할** | |---|---|---| | $\forall$ / $\exists$ | 요구 수준의 선언 | 전원 통과를 요구하는가, 한 명의 통과로 충분한가 | | $x$ | 후보를 부르는 자리 이름 | 문자를 바꿔도 명제는 그대로다 (아래 확인 4) | | $\in S$ (무대) | 후보 범위의 제한 | 같은 열린 문장도 무대가 바뀌면 진리값이 바뀔 수 있다 | | $P(x)$ (열린 문장) | 심사 기준 | 후보 각각의 통과$\cdot$탈락을 정한다 (7주차) | **조각 삭제 실험.** 무대 조각 "$\in S$"를 지워 보자: "$\forall x,\ x^2 \ge x$". 어느 후보들에 대한 주장인지가 정해지지 않아 판정이 아예 시작되지 않는다 — 정의가 무너지는 방식이 1~2주차("모든 수가 짝수가 됨")와 다르다. 그때는 판정이 전부 "참"으로 뭉개졌고, 지금은 판정 자체가 불능이 된다. :::{container} quotebox **확인 3.** $\forall x \in S,\ x^2 \ge x$에서 무대를 (가) $S = \mathbb{N}$ (나) $S = \mathbb{R}$로 각각 지정해 판정해 보자. 판정이 갈린다면 무엇 때문인가. ::: :::{admonition} 답 :class: quotebox dropdown (가) 참 — 자연수는 $x \ge 1$이므로 양변에 양수 $x$를 곱하면 $x^2 \ge x$. (나) 거짓 — 반례 $x = \frac{1}{2}$: $\frac{1}{4} < \frac{1}{2}$. 무대가 후보 목록을 정하므로, 무대가 $\mathbb{R}$로 넓어지며 새로 들어온 후보(0과 1 사이의 실수)가 판정을 뒤집었다. 무대 확인이 판정보다 먼저다 — 2주차 문제 5에서 약수 목록이 무대에 따라 달라진 것과 같은 현상이고, 문제 5에서 무대 확인의 중요성을 다시 만난다. ::: :::{container} quotebox **확인 4.** "$\forall x \in \mathbb{R},\ x^2 \ge 0$"과 "$\forall t \in \mathbb{R},\ t^2 \ge 0$"은 같은 명제인가, 다른 명제인가. ::: :::{admonition} 답 :class: quotebox dropdown 같은 명제다. 양화사에 묶인 문자는 후보를 부르는 자리 이름일 뿐이어서, 문장 밖에서 값을 넣을 자리가 아니다. 7주차의 자유 변수와 대비된다 — $x^2 \ge 0$의 자유로운 $x$는 값에 따라 문장이 달라졌지만, 묶인 $x$는 통째로 바꿔도 주장이 그대로다. 2주차 §1.3의 "정의 문장의 $c$는 자리 이름일 뿐이다"가 같은 사정이었다. ::: ### 4 참·거짓의 비대칭 (비대칭 표) [백지 암기 대상] 머리말이 판정 규칙을 정한다고 했다(확인 2). 그 규칙을 표로 못 박는다. | | **참임을 보이려면** | **거짓임을 보이려면** | |---|---|---| | $\forall x,\ P(x)$ | **모든** $x$를 처리하는 일반 논증 (문자로) | 반례 **하나** | | $\exists x,\ P(x)$ | 예 **하나** (증인) | **모든** $x$가 실패함을 논증 | :::{admonition} 새 낱말 — 증인 (witness) :class: quotebox $\exists$ 명제를 참으로 만드는 원소 하나를 **증인**이라 한다. 증인의 제시는 값만 적으면 끝나지 않는다 — 그 값이 열린 문장을 실제로 통과함을 검증하는 계산 한 줄까지가 제시다. ::: 1주차부터 해 온 일이 전부 이 표 안에 있다. "짝수 + 짝수 = 짝수"의 문자 증명 (1주차 예제 2.1)은 $\forall$의 참 칸이었고, $n^2 + n + 41$의 반례(1주차 문제 18)는 $\forall$의 거짓 칸이었다. 9주차에서 세운 반례의 두 조건($P$ 확인 + $\neg Q$ 확인)은 $\forall$ 거짓 칸의 완결 서식이었다. **증명 전략은 문장의 양화사 구조가 결정한다** — 그래서 문장을 양화사로 번역하는 이번 주가 증명 기법(15주차~)의 마지막 준비물이다. :::{container} quotebox **확인 5.** 다음 각 작업은 비대칭 표의 어느 칸에서 벌어진 일인가. (가) "모든 소수는 홀수이다"를 무너뜨리려고 2를 제시했다 (1주차 문제 19) (나) "홀수와 홀수의 합은 짝수이다"를 문자 $m, n$으로 증명했다 (1주차 예제 2.3) (다) "$2x = 6$인 정수 $x$가 존재한다"에 $x = 3$을 제시했다 (확인 2) ::: :::{admonition} 답 :class: quotebox dropdown (가) $\forall$의 거짓 칸 — 반례 하나. (나) $\forall$의 참 칸 — 일반 논증. (다) $\exists$의 참 칸 — 증인 하나. 하나로 끝나는 싼 칸과 전원을 처리해야 하는 비싼 칸이 대각선으로 마주 보고 있다 — 이 배치가 "비대칭"이라는 이름의 이유다. ::: :::{container} quotebox **확인 6.** 남은 한 칸 — $\exists$의 거짓. "$x^2 = -1$인 정수 $x$는 존재하지 않는다"를 보이는 데 "$x = 1$을 넣어 보니 $1 \neq -1$"이라는 확인 하나로 충분한가? ::: :::{admonition} 답 :class: quotebox dropdown 충분하지 않다. $x = 1$의 탈락은 후보 하나의 탈락일 뿐이고, 존재 명제는 다른 후보가 통과할 가능성을 남긴다. $\exists$의 거짓 칸은 **모든** 정수가 실패함을 처리해야 한다 — 모든 정수 $x$에서 $x^2 \ge 0 > -1$이므로 등식이 불가능하다는 일반 논증이 그 처리다. 이 칸이 표에서 가장 비싼 칸이고, 11주차에서 "$\exists$의 거짓 = $\forall$(부정)의 참"으로 번역하는 법을 배운다. ::: ### 5 숨은 양화사 찾기 수학 문장은 양화사를 자주 숨긴다. 다음 표의 빈칸을 채워 보자. | **겉모습** | **실제 구조** | |---|---| | "짝수의 제곱은 짝수다" | $\forall n \in \mathbb{Z},\ (n \text{ 짝수} \Rightarrow n^2 \text{ 짝수})$ | | "$x > 3 \Rightarrow x^2 > 9$" (8주차의 그 문장) | 앞에 $\underline{\quad(1)\quad}$ 이 생략되어 있다 | | 짝수의 정의 "$n = 2k$인 정수 $k$가 존재" | $\underline{\quad(2)\quad}\ k \in \mathbb{Z},\ n = 2k$ | | "방정식 $x^3 = 2$는 실근을 갖는다" | $\underline{\quad(3)\quad}\ x \in \mathbb{R},\ x^3 = 2$ | :::{container} quotebox **확인 7.** 빈칸 (1)(2)(3)을 채우고, 첫 행처럼 "~의 ~는 ~다" 꼴의 일반 서술이 왜 조건문과 함께 번역되는지 한 문장으로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) $\forall x \in \mathbb{R}$ (2) $\exists$ (3) $\exists$. "짝수의 제곱은"은 겉으로는 주어 하나지만, 실제로는 모든 정수를 무대에 올려 놓고 "짝수인 것들에 한해" 주장하는 문장이다 — 그 "한해"가 조건문 $n \text{ 짝수} \Rightarrow \cdots$로 번역된다. 1~2주차 정의의 "…인 정수 $k$가 존재한다"는 처음부터 $\exists$였다 — 열 주 동안 양화사를 써 왔고, 이번 주에 이름과 기호가 붙었을 뿐이다. ::: 같은 요령으로 항등식과 방정식도 갈라진다 — "$3(x+1) = 3x + 3$"은 모든 $x$에서 성립한다는 $\forall$ 명제이고, "$2x = 6$"을 명제로 만들면 "해가 존재한다"는 $\exists$ 명제다(문제 13). "방정식을 풀어라"는 진리집합(8주차)을 구하라는 지시다. ### 6 양화사 두 개 — 순서가 명제를 바꾼다 이번 주에서 가장 중요한 구분이다. 다음 두 식은 재료가 완전히 같고 순서만 다르다. $$ \forall x \in \mathbb{Z},\ \exists y \in \mathbb{Z},\ y > x \tag{1} $$ $$ \exists y \in \mathbb{Z},\ \forall x \in \mathbb{Z},\ y > x \tag{2} $$ (1)은 "어떤 정수 $x$를 골라도 그보다 큰 정수 $y$가 존재한다"이고, (2)는 "어떤 고정된 정수 $y$가 있어서 모든 정수 $x$보다 크다"이다. :::{container} quotebox **확인 8.** (1)이 참임을 보이려 한다. 비대칭 표에 따르면 임의의 $x$에 대해 증인 $y$를 제시해야 한다. $x$가 주어졌을 때 $y$를 무엇으로 잡으면 되는가. 그 $y$가 $x$에 따라 달라져도 되는가? ::: :::{admonition} 답 :class: quotebox dropdown $y = x + 1$로 잡으면 $x + 1 > x$이므로 통과한다. 달라져도 된다 — $\exists y$가 $\forall x$ **뒤에** 있으므로, $y$를 고르는 시점에는 $x$가 이미 정해져 있고 $y$는 그 $x$를 참조할 수 있다. $x = 5$면 $y = 6$, $x = -100$이면 $y = -99$ — $x$마다 다른 증인을 쓰는 것이 (1)의 존재 의의다. (1)은 참이다. ::: :::{container} quotebox **확인 9.** (2)는 $y$를 **먼저** 정해야 한다. $y = 10$은 성공하는가. $y = 10^{100}$은 성공하는가. (2)의 진리값은 무엇인가? ::: :::{admonition} 답 :class: quotebox dropdown 둘 다 실패한다 — $y = 10$에는 $x = 10$이 반례($10 > 10$ 불성립)이고, $y = 10^{100}$에도 $x = 10^{100}$이 반례다. 일반화하면 어떤 $y$를 제시해도 $x = y$가 그 $y$를 무너뜨린다 — 하나의 $y$가 모든 $x$에 대해 부등식을 만족해야 하는데 그런 만능 정수는 없다. (2)는 거짓이다. 같은 재료, 다른 순서, 다른 진리값 — 순서가 명제를 바꿨다. ::: 방금의 두 판정을 규칙으로 굳힌다. :::{admonition} 백지 암기 대상 :class: keybox **순서 규칙** 왼쪽부터 읽는다. 먼저 나온 변수가 먼저 정해지고, 뒤의 변수는 앞의 변수에 의존할 수 있다. 앞의 변수는 뒤의 변수를 알 수 없다. ::: 한 방향의 함의는 성립한다: $\exists y \forall x$가 참이면 — 만능 $y$가 있으면 — 그 $y$를 $x$마다 재사용하면 되므로 $\forall x \exists y$도 참이다. 역은 성립하지 않는다는 것이 방금 (1)(2)의 교훈이고, 예제 2.3과 문제 16에서 이 관계를 다시 확인한다. 이 순서 감각은 45주차 수열 극한의 정의 — $\forall \varepsilon > 0,\ \exists N \in \mathbb{N},\ \dots$ — 를 읽는 데 그대로 쓰인다. 문제 19가 그 예고편이다. ### 7 번역의 절차, 그리고 근거 목록 갱신 한국어 문장을 기호로 옮기는 절차를 정리한다. 1. 무대(어느 집합에서의 주장인가)를 찾는다 $\to$ $\in S$ 1. "모든/임의의/아무 ~나" $\to$ $\forall$, "어떤/존재한다/~인 것이 있다" $\to$ $\exists$ 1. 나머지 주장 부분을 열린 문장으로 적는다 1. 거꾸로(기호 $\to$ 한국어)는 왼쪽부터 소리 내어 읽으면 된다 :::{container} quotebox **확인 10.** 다음을 번역해 보자. (가) "어떤 실수는 자신의 세제곱과 같다" $\to$ 기호로 (나) "$\forall n \in \mathbb{N},\ n + 1 > n$" $\to$ 한국어로 ::: :::{admonition} 답 :class: quotebox dropdown (가) 무대 $\mathbb{R}$, "어떤 ~는 ~가 있다" 꼴이므로 $\exists$: $\exists x \in \mathbb{R},\ x^3 = x$ (참인 명제다 — 증인 $x = 0$ 또는 $\pm 1$). (나) "모든 자연수 $n$에 대해 $n + 1$은 $n$보다 크다" — 참이다. 번역은 창작이 아니라 절차다: 무대, 양화사, 열린 문장의 세 부품을 차례로 확인하면 문장이 조립된다. ::: **근거 목록 갱신.** 칸은 그대로 네 개다. ① 칸에 정의가 하나 추가되고, ④ 칸에 이번 주의 판정 원리가 등록된다. | **근거** | **내용** | **이번 주에는 이렇게 쓴다** | |---|---|---| | ① 정의 | 정의 1.1, 1.2, 2.1, …, **10.1** | "모든/어떤" 문장 $\leftrightarrow$ $\forall$/$\exists$ 기호 사이를 번역한다 | | ② 닫힘성 | 정수의 합$\cdot$차$\cdot$곱은 정수 | 증인 검증 계산("$x + 1 \in \mathbb{Z}$이므로")에서 그대로 쓴다 | | ③ 등식의 성질 | 대입 / 전개 / 묶기 / 양변 연산 | 일반 논증과 검증 계산의 도구다 | | ④ 이미 증명한 명제 | 1~9주차의 문제들 + **비대칭 표** | 판정 전략을 정하는 근거로 쓴다 — "존재 명제이므로 증인 하나를 제시한다" | :::{container} quotebox **확인 11.** 어떤 답안에 다음 두 문장이 나왔다. 각각 허용되는가? (가) "증인 $x = 3$이 $2x = 6$을 만족하므로 이 존재 명제는 참이다" (나) "$n = 1, 2, 3$에서 모두 성립하므로 이 $\forall$ 명제는 참이다" ::: :::{admonition} 답 :class: quotebox dropdown (가) 허용 — 근거 ①(정의 10.1)과 ④(비대칭 표)에 정확히 맞는 서식이다. 값의 제시와 검증 계산이 다 있다. (나) 불허 — 비대칭 표의 $\forall$ 참 칸은 **모든** 후보를 처리하는 일반 논증을 요구한다. 사례 세 개는 후보 세 명의 통과일 뿐이다. 1주차 준비 운동의 유형 1(예시 확인)이 기호의 세계에서 다시 나타난 것이고, $n^2 + n + 41$(1주차 문제 18)이 이 방식의 붕괴 사례였다. ::: 정의는 외운다 — [백지 암기 대상] 표시가 그 대상이다. 문장을 통째로만 외우지 말고 §1.3의 조각별 역할과 함께 외운다. 조각을 잊어도 역할에서 재구성할 수 있다.