술어와 한정기호

개요 — 동기·문제의식

명제논리의 명제는 내부 구조가 없는 참·거짓의 원자였다. 그러나 수학의 일상적 문장인 "$x$는 짝수이다"나 "모든 소수는 약수를 두 개만 가진다"는 명제논리로 표현되지 않는다 — 전자는 $x$가 정해지기 전에는 참도 거짓도 아니어서 명제가 아니고, 후자는 무한히 많은 대상 전체에 대한 주장이어서 유한 개의 $\wedge$로 쓸 수 없다. 술어논리는 문장을 대상(변수)과 대상의 성질(술어)로 분해하고, 전칭 한정기호 $\forall$("모든")와 존재 한정기호 $\exists$("어떤")로 무한한 정의역 전체에 대한 주장을 형식화함으로써 이 한계를 넘는다.

이 확장의 진짜 보상은 표현력만이 아니라 계산 가능성이다. 한정기호가 붙은 문장의 부정을 기계적 규칙($\neg\forall \equiv \exists\neg$)으로 계산할 수 있게 되면, "극한이 $L$이 아니다"나 "함수가 연속이 아니다" 같은 복잡한 문장의 정확한 의미가 손 계산으로 얻어진다. 또 한정기호의 순서가 의미를 결정한다는 사실($\forall x\exists y$와 $\exists y\forall x$는 다른 주장이다)을 이해하면, 수학의 많은 정의가 왜 그 순서로 쓰여 있는지가 보인다. 이 장에서 확립하는 규칙들은 증명 기법에서 배우는 증명 전략 — 무엇을 임의로 잡고, 무엇을 찾아 제시해야 하는가 — 을 직접 결정한다.

직관

술어는 "명제를 값으로 갖는 함수"다. $P(x)$: "$x$는 짝수이다"는 그 자체로는 진리값이 없지만, $x$에 정의역의 원소를 대입하는 순간 $P(4)$(참), $P(7)$(거짓)처럼 명제가 된다. 한정기호는 이 함수의 출력들을 정의역 전체에 걸쳐 결합하는 장치다: $\forall x\,P(x)$는 "모든 대입 결과의 $\wedge$", $\exists x\,P(x)$는 "모든 대입 결과의 $\vee$"라고 읽으면 된다 — 정의역이 유한할 때는 이 읽기가 문자 그대로 성립하고(정리 6), 무한할 때는 그 자연스러운 일반화다. 같은 술어라도 정의역이 바뀌면 진리값이 바뀔 수 있으므로, 한정된 문장은 언제나 "어느 정의역 위에서인가"와 함께 읽어야 한다.

중첩 한정기호는 두 사람이 번갈아 수를 두는 게임으로 읽는 것이 가장 정확하다. $\forall$의 변수는 상대가 고르고 $\exists$의 변수는 내가 고르며, 문장이 참이라는 것은 상대가 어떻게 두든 내가 이길 수 있다는 뜻이다. 순서는 곧 정보다: $\forall x\,\exists y$에서 나는 상대의 $x$를 보고 나서 $y$를 고르므로 $y$가 $x$에 의존해도 되지만, $\exists y\,\forall x$에서는 상대가 무엇을 낼지 모른 채 모든 $x$에 통하는 단 하나의 $y$를 먼저 걸어야 한다. 뒤의 주장이 훨씬 강하다.

정의

술어와 정의역

정의. $n$항 술어(predicate) $P(x_1,\dots,x_n)$는 변수 $x_1,\dots,x_n$에 정의역(domain of discourse) $D$의 원소를 대입할 때마다 명제(참 또는 거짓이 확정되는 문장)가 되는 문장이다. $P(x)$의 진리집합은 $\{x\in D : P(x)\text{가 참}\}$이다(집합과 함수의 조건제시법이 바로 이 구성이다).

정의. 식 안의 변수가 한정기호에 걸려 있으면 속박변수(bound variable), 아니면 자유변수(free variable)다. 모든 변수가 속박된 식은 진리값이 확정된 명제다. 예컨대 $\exists y\,(x+y=0)$에서 $y$는 속박, $x$는 자유이므로 이 식은 $x$에 대한 1항 술어다.

정의. 한정기호의 작용 범위(scope)는 그 기호가 지배하는 부분식이다. 한정기호는 $\neg$처럼 바로 뒤의 식에만 작용하므로 $\forall x\,P(x)\vee Q(x)$는 $(\forall x\,P(x))\vee Q(x)$로 읽히고 마지막 $x$는 자유변수다 — 의도가 전체라면 괄호 $\forall x\,(P(x)\vee Q(x))$가 필요하다. 속박변수의 이름은 진리값에 영향을 주지 않아 자유롭게 바꿀 수 있다: $\forall x\,P(x)\equiv\forall z\,P(z)$.

전칭·존재 한정기호

정의. 전칭 한정(universal quantification) $\forall x\,P(x)$는 정의역의 모든 원소 $a$에 대해 $P(a)$가 참일 때, 그리고 그때에만 참이다. $P(c)$가 거짓인 원소 $c\in D$를 $\forall x\,P(x)$의 반례(counterexample)라 한다.

정의. 존재 한정(existential quantification) $\exists x\,P(x)$는 $P(a)$가 참인 원소 $a\in D$가 적어도 하나 존재할 때, 그리고 그때에만 참이다. 그런 $a$를 증인(witness)이라 한다. 유일존재 $\exists!x\,P(x)$는 그런 원소가 정확히 하나임을 뜻한다(연습문제 6).

두 한정기호의 진리 조건은 서로의 거울상이다 — 이 대칭이 정리 1의 부정 규칙으로 이어진다.

정의 (제한 한정). $A\subseteq D$에 대해 $\forall x\in A\ P(x) :\equiv \forall x\,(x\in A \to P(x))$, $\exists x\in A\ P(x) :\equiv \exists x\,(x\in A \wedge P(x))$. 전칭은 조건문과, 존재는 논리곱과 짝을 이룬다 — 이 짝을 바꿔 쓰면 의미가 무너진다(흔한 오해 참고). $A=\varnothing$이면 전칭은 공허하게 참(vacuously true)이고 존재는 거짓이다.

주요 정리

정리 1 (한정기호의 드모르간 법칙). 임의의 술어 $P$와 임의의 정의역에 대해 $\neg\forall x\,P(x) \equiv \exists x\,\neg P(x)$이고 $\neg\exists x\,P(x) \equiv \forall x\,\neg P(x)$이다.

따름정리 (부정의 내부 이동). 부정은 한정기호 열을 통과하면서 각 $\forall$를 $\exists$로, 각 $\exists$를 $\forall$로 뒤집고 맨 안쪽 술어에 $\neg$로 도달한다: 예컨대 $\neg\forall x\,\exists y\,P(x,y)\equiv\exists x\,\forall y\,\neg P(x,y)$.

정리 2 (같은 종류 한정기호의 교환). $\forall x\,\forall y\,P(x,y)\equiv\forall y\,\forall x\,P(x,y)$이고 $\exists x\,\exists y\,P(x,y)\equiv\exists y\,\exists x\,P(x,y)$이다.

정리 3 ($\exists\forall$는 $\forall\exists$보다 강하다). $\exists y\,\forall x\,P(x,y) \implies \forall x\,\exists y\,P(x,y)$는 항상 성립하지만, 그 역은 일반적으로 성립하지 않는다.

정리 4 (한정기호와 $\wedge,\vee$의 분배). (i) $\forall x\,(P(x)\wedge Q(x))\equiv\forall x\,P(x)\wedge\forall x\,Q(x)$. (ii) $\exists x\,(P(x)\vee Q(x))\equiv\exists x\,P(x)\vee\exists x\,Q(x)$. (iii) $\forall x\,P(x)\vee\forall x\,Q(x)\implies\forall x\,(P(x)\vee Q(x))$이지만 역은 거짓. (iv) $\exists x\,(P(x)\wedge Q(x))\implies\exists x\,P(x)\wedge\exists x\,Q(x)$이지만 역은 거짓.

정리 5 (반례에 의한 반증). $\forall x\in A\ P(x)$가 거짓일 필요충분조건은 반례 — $c\in A$이면서 $P(c)$가 거짓인 $c$ — 가 존재하는 것이다. 따라서 단 하나의 반례가 전칭 명제를 완전히 반증한다.

정리 6 (유한 정의역에서의 전개). $D=\{a_1,\dots,a_n\}$이 유한이면 $\forall x\,P(x)\equiv P(a_1)\wedge\cdots\wedge P(a_n)$이고 $\exists x\,P(x)\equiv P(a_1)\vee\cdots\vee P(a_n)$이다.

예제

예제 1 (정의역이 진리값을 바꾼다). $P(x)$: $x^2\ge x$. $D=\mathbb{Z}$에서 $\forall x\,P(x)$는 참이다($x\ge1$이면 $x^2\ge x$, $x=0$이면 등호, $x\le-1$이면 $x^2>0>x$). 그러나 $D=\mathbb{R}$에서는 거짓이다 — 반례 $x=\tfrac12$: $\tfrac14<\tfrac12$. 마찬가지로 $\exists x\,(x^2=2)$는 $D=\mathbb{Q}$에서 거짓, $D=\mathbb{R}$에서 참($x=\sqrt2$)이다. 한정된 문장은 정의역 명시 없이는 진리값이 없다.

예제 2 (순서가 만드는 차이). $D=\mathbb{Z}$, $P(x,y)$: $y>x$. $\forall x\,\exists y\,(y>x)$는 참이다 — 상대가 $x$를 내면 나는 $y=x+1$을 낸다. $\exists y\,\forall x\,(y>x)$는 거짓이다 — 모든 정수보다 큰 정수 $b$가 있어야 하는데 $x=b$를 대입하면 $b>b$로 모순. "각자에게 맞는 답이 있다"($\forall\exists$)와 "만능 답이 하나 있다"($\exists\forall$)의 차이다.

예제 3 (극한의 $\varepsilon$–$\delta$ 정의 기호화). "$x\to a$일 때 $f(x)\to L$"의 정의는 세 겹의 한정 문장이다: $$\forall\varepsilon>0\ \exists\delta>0\ \forall x\ \bigl(0<\lvert x-a\rvert<\delta \to \lvert f(x)-L\rvert<\varepsilon\bigr).$$ 게임 읽기: 상대가 오차 허용치 $\varepsilon$을 아무리 작게 불러도, 나는 그 $\varepsilon$을 보고 나서 $\delta$를 고를 수 있다 — $\delta$가 $\varepsilon$에 의존하는 것이 허용되는 이유가 순서에 새겨져 있다. 순서를 바꾼 $\exists\delta>0\ \forall\varepsilon>0\ \cdots$는 "모든 $\varepsilon$에 통하는 만능 $\delta$"를 요구하는 훨씬 강한 문장으로, 상수함수 근방에서나 성립할 별개의 주장이다.

예제 4 (부정의 기계적 계산). 예제 3의 부정, 즉 "$f$의 $a$에서의 극한이 $L$이 아니다"를 따름정리로 계산한다. 부정이 세 한정기호를 뒤집으며 통과하고 조건문의 부정이 $\wedge$가 되어: $$\exists\varepsilon>0\ \forall\delta>0\ \exists x\ \bigl(0<\lvert x-a\rvert<\delta \wedge \lvert f(x)-L\rvert\ge\varepsilon\bigr).$$ 읽으면: 어떤 고정된 오차 $\varepsilon$이 있어서, $\delta$를 아무리 줄여도 그 안에 $f$ 값이 $L$에서 $\varepsilon$ 이상 떨어진 점이 남는다. 제한 한정($\varepsilon>0$, $\delta>0$)은 부정해도 제한 조건이 유지된 채 기호만 뒤집힌다는 점, 그리고 $\to$가 $\wedge$로 바뀐다는 점이 계산의 요체다.

예제 5 (수학 문장의 기호화 연습). 정의역 $\mathbb{N}$, $\operatorname{prime}(p)$를 소수 술어로 하자. 골드바흐 추측 "4 이상의 모든 짝수는 두 소수의 합이다"는 $\forall n\,\bigl((n\ge4\wedge 2\mid n)\to\exists p\,\exists q\,(\operatorname{prime}(p)\wedge\operatorname{prime}(q)\wedge n=p+q)\bigr)$. "소수는 무한히 많다"는 최댓값 부재로 기호화한다: $\forall x\,\exists p\,(\operatorname{prime}(p)\wedge p>x)$ — "무한히 많다"를 직접 말하는 대신 "어떤 문턱을 넘어도 또 있다"로 바꾸는 것이 전형적 기법이다. 기호화의 검산은 부정을 계산해 보는 것이다: 뒤 문장의 부정은 $\exists x\,\forall p\,(\operatorname{prime}(p)\to p\le x)$, 즉 "모든 소수를 위에서 막는 문턱이 있다" — 원문의 부정("소수가 유한 개다")과 정확히 일치한다.

예제 6 (반례 하나면 충분하다 — 그리고 사례 확인은 증명이 아니다). $E(n)=n^2+n+41$은 $n=0,1,\dots,39$에서 전부 소수다. 그러나 "$\forall n\in\mathbb{N}$, $E(n)$은 소수"는 거짓이다 — $E(40)=40^2+40+41=1681=41^2$이 반례다. 마찬가지로 페르마는 $F_k=2^{2^k}+1$이 모든 $k$에서 소수라고 추측했지만($k\le4$에서 성립), 오일러가 $F_5=4294967297=641\times 6700417$을 밝혀 반증했다. 정리 5 그대로: 40개의 성공 사례는 아무것도 증명하지 못했고, 반례 하나가 명제를 확정적으로 무너뜨렸다.

흔한 오해와 함정

• "$\forall x\,\exists y$와 $\exists y\,\forall x$는 같은 말이다" — 함의는 $\exists\forall\Rightarrow\forall\exists$ 한 방향뿐이다(정리 3). $\forall x\,\exists y\,(x+y=0)$은 참이지만 $\exists y\,\forall x\,(x+y=0)$은 거짓.
• "$\neg\forall x\,P(x)$는 $\forall x\,\neg P(x)$다" — "모두 그런 것은 아니다"($\exists x\,\neg P$)와 "모두 아니다"($\forall x\,\neg P$)의 혼동. "모든 정수가 짝수인 것은 아니다"(참)와 "모든 정수는 홀수다"(거짓)를 비교하라.
• "제한 한정을 부정할 때 $\to$를 그대로 둔다" — $\neg\forall x\,(x\in A\to P(x))$는 $\exists x\,(x\in A\wedge\neg P(x))$이지 $\exists x\,(x\in A\to\neg P(x))$가 아니다. 후자는 $A$ 밖의 아무 원소로도 공허하게 참이 되는 무의미한 문장이다.
• "사례를 많이 확인하면 전칭 명제가 증명된다" — 무한 정의역에서는 거짓. $n^2+n+41$이 40연속 소수를 내고도 무너진다(예제 6). 전칭의 증명은 임의의 원소에 대한 일반 논증이어야 한다(증명 기법).
• "$\exists x\,P(x)$와 $\exists x\,Q(x)$가 참이면 $\exists x\,(P(x)\wedge Q(x))$도 참" — 두 존재문의 증인이 같으리라는 보장이 없다(정리 4(iv)). 짝수도 존재하고 홀수도 존재하지만 짝수인 홀수는 없다.
• "공집합 위의 전칭 명제는 거짓이다" — 반대로 공허하게 참이다: $\forall x\in\varnothing\ P(x)\equiv\forall x\,(x\in\varnothing\to P(x))$에서 전건이 항상 거짓이므로 조건문이 항상 참. 반면 $\exists x\in\varnothing\ P(x)$는 거짓이다.

큰 그림 / 연결

이 장의 규칙들은 이후 모든 장의 문법이 된다. 증명 기법의 증명 전략은 한정기호 구조를 그대로 읽어낸 것이다 — $\forall$ 문장은 "임의의 $x$를 잡고" 시작하고, $\exists$ 문장은 증인을 제시하거나 간접적으로 존재를 논증하며(비구성적 존재 증명의 극단이 확률적 방법다), 반증은 정리 5에 따라 반례 하나를 찾는 일이다. 집합과 함수의 단사($\forall a\,\forall b\,(f(a)=f(b)\to a=b)$)·전사($\forall b\,\exists a\,(f(a)=b)$) 정의, 셈의 기본 원리의 비둘기집 원리("어떤 상자에는 두 개 이상이 들어 있다"는 $\exists$ 진술), 집합의 크기의 대각선 논법("어떤 목록에도 없는 원소가 존재한다")은 전부 이 장의 언어로 쓰인 문장이며, 그 부정과 증명 구조를 다루는 손놀림이 이 장에서 연습한 계산 그대로다.

더 멀리 보면, 관계와 동치관계에서 다루는 반사성·대칭성·추이성 같은 관계의 성질들도 전부 전칭 문장이며, 어떤 관계가 그 성질을 갖지 않음을 보이는 일은 언제나 정리 5의 반례 찾기다. 한정기호가 번갈아 나타나는 깊이는 문장의 논리적 복잡도를 재는 자연스러운 척도이기도 하다 — 예제 3의 $\forall\exists\forall$ 세 겹 구조가 $\varepsilon$–$\delta$ 논법을 처음 배울 때 어렵게 느껴지는 이유를 정확히 설명한다. 이 장에서 다진 "순서를 읽고, 부정을 밀어 넣고, 증인과 반례를 구별하는" 감각이 이후 수학 언어 전체를 읽는 문해력이 된다.

연습문제

1. 정의역 $\mathbb{Z}$에서 진리값을 판정하라: (a) $\forall x\,(x^2\ge x)$ (b) $\exists x\,(x^2=x)$ (c) $\forall x\,\exists y\,(y^2=x)$ (d) $\exists x\,\forall y\,(xy=y)$.
2. 부정을 술어 바로 앞까지 밀어 넣어라: (a) $\forall x\,\exists y\,(P(x,y)\wedge Q(x,y))$ (b) $\exists x\,\forall y\,(P(x,y)\to Q(x,y))$.
3. 기호화하라(정의역 $\mathbb{Q}$ 또는 $\mathbb{N}$ 명시): (a) "임의의 서로 다른 두 유리수 사이에는 유리수가 있다" (b) "가장 큰 소수는 없다".
4. $D=\mathbb{R}$, $P(x,y)$: $x+y=0$에 대해 $\forall x\,\forall y\,P$, $\forall x\,\exists y\,P$, $\exists x\,\forall y\,P$, $\exists x\,\exists y\,P$의 진리값을 각각 판정하고 이유를 붙여라.
5. 정리 4(iii)의 역 $\forall x\,(P\vee Q)\to(\forall x\,P\vee\forall x\,Q)$가 거짓임을 보이는, 본문과 다른 반례를 하나 제시하라.
6. $\exists!x\,P(x)$를 $\forall,\exists$와 논리 결합자만으로 표현하고, 그 부정을 술어 앞까지 계산한 뒤 두 경우("하나도 없다" 또는 "둘 이상 있다")로 해석하라.
7. 예제 4의 부정 공식을 사용해, 어떤 $L\in\mathbb{R}$에 대해서도 $\lim_{x\to 0}\frac{1}{x}=L$이 성립하지 않음을 증명하라.
8. $\forall x\,(P(x)\to Q(x))\implies(\forall x\,P(x)\to\forall x\,Q(x))$를 증명하고, 역이 거짓임을 보이는 반례를 제시하라.

관련 개념

• 명제논리 — 결합자·조건문의 부정 등 이 장이 딛고 선 기반
• 증명 기법 — $\forall$·$\exists$ 구조를 증명 전략(임의 원소·증인·반례)으로 번역
• 집합과 함수 — 진리집합, 단사·전사의 한정기호 정의
• 집합의 크기 — 중첩 한정 문장의 대표적 활용(대각선 논법)
• 셈의 기본 원리 — 비둘기집 원리라는 존재 진술