10주차 — 양화사 (Quantifiers)

10주차 — 양화사 (Quantifiers)#

이 주의 길잡이

핵심 문장: 양화사의 순서가 바뀌면 명제가 바뀐다 — 먼저 나온 변수가 먼저 정해진다.

이 주의 위치: 50주 과정의 10주차. 열린 문장(7주차)을 명제로 만드는 마지막 부품 \(\forall\)\(\cdot\)\(\exists\)를 얻어 수학 문장 해독을 완성하고, 부정 만들기(11주차)와 증명 기법(15주차~)의 재료를 마련한다.

원서 대응: BoP(Book of Proof) 2.7, 2.9 — 원서 없이 읽을 수 있다.

이번 주 목표#

  1. \(\forall\)(모든)과 \(\exists\)(존재)의 정의를 백지에 쓰고, 열린 문장이 양화사로 명제가 되는 과정을 설명할 수 있다.

  2. 참\(\cdot\)거짓 입증 부담의 비대칭 표 — \(\forall\)\(\cdot\)\(\exists\) 각각의 참과 거짓에 무엇이 필요한가 — 를 재현하고 판정에 적용할 수 있다.

  3. \(\forall x \exists y\)와 \(\exists y \forall x\)의 차이를 순서 규칙으로 설명하고, 그 차이가 드러나는 예를 직접 설계할 수 있다.

  4. 한국어\(\cdot\)영어 수학 문장과 기호 사이를 양방향으로 번역한다 — 겉에 드러나지 않은 숨은 양화사까지 포함해서.

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

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

  1. \(\neg(P \Rightarrow Q) \equiv \underline{\quad}\) (조건문의 부정)

  2. “\(n\)이 홀수이면 \(n^2\)이 홀수이다”의 대우를 쓰시오.

  3. 드모르간 법칙 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\)대우)는 이미 명제인 문장을 조립하고 변형하는 도구였다. 그 도구만으로 다음 문장을 기호로 적어 보자.

시도 — 지금의 기호로 밀어붙이기

문장: 짝수인 정수가 존재한다.

“\(P(n)\)을 ‘\(n\)은 짝수’라 하자. \(P(n)\)은 열린 문장이므로 명제가 아니다(7주차).

\(P(4)\)는 참인 명제지만 그것은 4 하나에 대한 주장일 뿐이다. ‘존재한다’는

후보 중 적어도 하나가 통과한다는 주장이므로 ‘또는’으로 잇는다:

\(P(0) \lor P(1) \lor P(-1) \lor P(2) \lor \cdots\) — “

여기서 멈춘다. 정수는 무한히 많으므로 이 문장은 끝나지 않는다. 6주차의 첨자 합집합에서 예고한 대로 “적어도 하나”는 ‘또는’의 확장이고 “모든”은 ‘그리고’의 확장인데, 지금의 언어에는 그 무한 확장을 유한한 기호 하나로 접는 낱말이 없다.

확인 1. “모든 정수 \(n\)에 대해 \(n^2 \ge 0\)이다”를 같은 방식으로 적으면 어떤

모양이 되는가. 진리표로 이 문장의 참을 판정할 수 있는가?

답

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

확인 2. 빈칸 (1)(2)(3)을 채우고, (3)을 판정할 때 실제로 무엇을 제시했는지

한 구절로 적어 보자.

답

(1) 참 (2) 거짓 (3) 참 — \(x = 3\)이 등식 \(2 \times 3 = 6\)을 성립시킨다.

(3)의 판정에 쓴 것은 “성립시키는 값 하나”였다. 같은 열린 문장이라도

머리말 — “모든 ~에 대해” 또는 “~인 ~가 존재한다” — 이 붙는 순간

참\(\cdot\)거짓이 정해지는 문장, 곧 명제가 된다. 머리말이 판정 규칙까지 정한다는

것이 방금의 경험이다.

이 두 머리말에 정식 이름과 기호를 붙인다. 식 자체에 새로운 것은 없다 — 1주차 정의 1.1의 “…인 정수 \(k\)가 존재한다”부터 매주 써 온 그 머리말에 기호를 붙였을 뿐이다.

정의 10.1 — 양화사 (quantifier) [백지 암기 대상]#

  • 전칭 양화사 \(\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\)”은 “이 엑스가 육인 정수 엑스가 존재한다”로 읽는다. 읽는 법까지가 정의다.

표기 — 기호의 생김새와 쉼표

\(\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주차(“모든 수가 짝수가 됨”)와 다르다. 그때는 판정이 전부 “참”으로 뭉개졌고, 지금은 판정 자체가 불능이 된다.

확인 3. \(\forall x \in S,\ x^2 \ge x\)에서 무대를 (가) \(S = \mathbb{N}\)

(나) \(S = \mathbb{R}\)로 각각 지정해 판정해 보자. 판정이 갈린다면 무엇 때문인가.

답

(가) 참 — 자연수는 \(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에서 무대 확인의 중요성을 다시 만난다.

확인 4. “\(\forall x \in \mathbb{R},\ x^2 \ge 0\)”과

“\(\forall t \in \mathbb{R},\ t^2 \ge 0\)”은 같은 명제인가, 다른 명제인가.

답

같은 명제다. 양화사에 묶인 문자는 후보를 부르는 자리 이름일 뿐이어서,

문장 밖에서 값을 넣을 자리가 아니다. 7주차의 자유 변수와 대비된다 —

\(x^2 \ge 0\)의 자유로운 \(x\)는 값에 따라 문장이 달라졌지만, 묶인 \(x\)는

통째로 바꿔도 주장이 그대로다. 2주차 §1.3의 “정의 문장의 \(c\)는 자리

이름일 뿐이다”가 같은 사정이었다.

4 참·거짓의 비대칭 (비대칭 표) [백지 암기 대상]#

머리말이 판정 규칙을 정한다고 했다(확인 2). 그 규칙을 표로 못 박는다.

참임을 보이려면

거짓임을 보이려면

\(\forall x,\ P(x)\)

모든 \(x\)를 처리하는 일반 논증 (문자로)

반례 하나

\(\exists x,\ P(x)\)

예 하나 (증인)

모든 \(x\)가 실패함을 논증

새 낱말 — 증인 (witness)

\(\exists\) 명제를 참으로 만드는 원소 하나를 증인이라 한다. 증인의 제시는

값만 적으면 끝나지 않는다 — 그 값이 열린 문장을 실제로 통과함을 검증하는

계산 한 줄까지가 제시다.

1주차부터 해 온 일이 전부 이 표 안에 있다. “짝수 + 짝수 = 짝수”의 문자 증명 (1주차 예제 2.1)은 \(\forall\)의 참 칸이었고, \(n^2 + n + 41\)의 반례(1주차 문제 18)는 \(\forall\)의 거짓 칸이었다. 9주차에서 세운 반례의 두 조건(\(P\) 확인 + \(\neg Q\) 확인)은 \(\forall\) 거짓 칸의 완결 서식이었다. 증명 전략은 문장의 양화사 구조가 결정한다 — 그래서 문장을 양화사로 번역하는 이번 주가 증명 기법(15주차~)의 마지막 준비물이다.

확인 5. 다음 각 작업은 비대칭 표의 어느 칸에서 벌어진 일인가.

(가) “모든 소수는 홀수이다”를 무너뜨리려고 2를 제시했다 (1주차 문제 19)

(나) “홀수와 홀수의 합은 짝수이다”를 문자 \(m, n\)으로 증명했다 (1주차 예제 2.3)

(다) “\(2x = 6\)인 정수 \(x\)가 존재한다”에 \(x = 3\)을 제시했다 (확인 2)

답

(가) \(\forall\)의 거짓 칸 — 반례 하나. (나) \(\forall\)의 참 칸 — 일반 논증.

(다) \(\exists\)의 참 칸 — 증인 하나. 하나로 끝나는 싼 칸과 전원을 처리해야

하는 비싼 칸이 대각선으로 마주 보고 있다 — 이 배치가 “비대칭”이라는

이름의 이유다.

확인 6. 남은 한 칸 — \(\exists\)의 거짓. “\(x^2 = -1\)인 정수 \(x\)는 존재하지

않는다”를 보이는 데 “\(x = 1\)을 넣어 보니 \(1 \neq -1\)”이라는 확인 하나로

충분한가?

답

충분하지 않다. \(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\)

확인 7. 빈칸 (1)(2)(3)을 채우고, 첫 행처럼 “~의 ~는 ~다” 꼴의 일반

서술이 왜 조건문과 함께 번역되는지 한 문장으로 적어 보자.

답

(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\)보다 크다”이다.

확인 8. (1)이 참임을 보이려 한다. 비대칭 표에 따르면 임의의 \(x\)에 대해

증인 \(y\)를 제시해야 한다. \(x\)가 주어졌을 때 \(y\)를 무엇으로 잡으면 되는가.

그 \(y\)가 \(x\)에 따라 달라져도 되는가?

답

\(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)은 참이다.

확인 9. (2)는 \(y\)를 먼저 정해야 한다. \(y = 10\)은 성공하는가.

\(y = 10^{100}\)은 성공하는가. (2)의 진리값은 무엇인가?

답

둘 다 실패한다 — \(y = 10\)에는 \(x = 10\)이 반례(\(10 > 10\) 불성립)이고,

\(y = 10^{100}\)에도 \(x = 10^{100}\)이 반례다. 일반화하면 어떤 \(y\)를 제시해도

\(x = y\)가 그 \(y\)를 무너뜨린다 — 하나의 \(y\)가 모든 \(x\)에 대해 부등식을

만족해야 하는데 그런 만능 정수는 없다. (2)는 거짓이다. 같은 재료, 다른 순서, 다른 진리값 —

순서가 명제를 바꿨다.

방금의 두 판정을 규칙으로 굳힌다.

백지 암기 대상

순서 규칙

왼쪽부터 읽는다. 먼저 나온 변수가 먼저 정해지고, 뒤의 변수는 앞의 변수에

의존할 수 있다. 앞의 변수는 뒤의 변수를 알 수 없다.

한 방향의 함의는 성립한다: \(\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\)

  2. “모든/임의의/아무 ~나” \(\to\) \(\forall\), “어떤/존재한다/~인 것이 있다” \(\to\) \(\exists\)

  3. 나머지 주장 부분을 열린 문장으로 적는다

  4. 거꾸로(기호 \(\to\) 한국어)는 왼쪽부터 소리 내어 읽으면 된다

확인 10. 다음을 번역해 보자.

(가) “어떤 실수는 자신의 세제곱과 같다” \(\to\) 기호로

(나) “\(\forall n \in \mathbb{N},\ n + 1 > n\)” \(\to\) 한국어로

답

(가) 무대 \(\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주차의 문제들 + 비대칭 표

판정 전략을 정하는 근거로 쓴다 — “존재 명제이므로 증인 하나를 제시한다”

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

(가) “증인 \(x = 3\)이 \(2x = 6\)을 만족하므로 이 존재 명제는 참이다”

(나) “\(n = 1, 2, 3\)에서 모두 성립하므로 이 \(\forall\) 명제는 참이다”

답

(가) 허용 — 근거 ①(정의 10.1)과 ④(비대칭 표)에 정확히 맞는 서식이다.

값의 제시와 검증 계산이 다 있다.

(나) 불허 — 비대칭 표의 \(\forall\) 참 칸은 모든 후보를 처리하는 일반

논증을 요구한다. 사례 세 개는 후보 세 명의 통과일 뿐이다. 1주차 준비

운동의 유형 1(예시 확인)이 기호의 세계에서 다시 나타난 것이고,

\(n^2 + n + 41\)(1주차 문제 18)이 이 방식의 붕괴 사례였다.

정의는 외운다 — [백지 암기 대상] 표시가 그 대상이다. 문장을 통째로만 외우지 말고 §1.3의 조각별 역할과 함께 외운다. 조각을 잊어도 역할에서 재구성할 수 있다.