논리와 집합의 언어

수학의 문장은 명제로 시작한다

대학 수학에서 가장 먼저 익숙해져야 할 것은 "문장을 정확히 읽는 일"이다. 수학의 문장은 보통 명제의 형태로 나타난다. 명제란 참인지 거짓인지 판단할 수 있는 문장이다.

예를 들어 다음 문장은 명제다.

• 2는 짝수이다.

• 모든 실수 x에 대하여 x² ≥ 0이다.

• 어떤 정수 n은 n² = 2를 만족한다.

첫째 문장과 둘째 문장은 참이고, 셋째 문장은 거짓이다. 중요한 것은 참인지 거짓인지가 아니라, 참과 거짓을 판단할 수 있는 문장인가이다. 반면 "이 함수는 예쁘다", "x는 크다" 같은 문장은 기준이 분명하지 않으므로 그대로는 수학적 명제로 다루기 어렵다.

명제를 보통 P, Q 같은 문자로 나타낸다. 이때 "P이면 Q이다"는 조건문이라 부르고, 기호로는 P ⇒ Q라고 쓴다. 여기서 P는 조건, Q는 결론이다.

예를 들어

n이 4의 배수이면 n은 짝수이다.

라는 명제에서 조건은 "n이 4의 배수이다"이고, 결론은 "n은 짝수이다"이다. 이 명제는 참이다. 4의 배수는 어떤 정수 k에 대해 n = 4k로 쓸 수 있고, 따라서 n = 2(2k)이므로 짝수이기 때문이다.

조건문을 읽을 때는 "조건이 참인 모든 경우에 결론도 따라오는가?"를 확인하면 된다. 위 명제에서는 n이 4의 배수인 경우만 살펴보면 된다. 그때마다 n이 짝수이면 조건문은 참이다. 조건과 결론을 분리해서 읽는 습관은 이후의 정의, 정리, 증명을 이해하는 데 계속 필요하다.

AI 생성 이미지

필요조건과 충분조건

조건문 P ⇒ Q를 읽을 때 자주 헷갈리는 말이 필요조건과 충분조건이다.

P ⇒ Q가 참이라고 하자. 그러면 P가 성립하면 Q가 반드시 성립한다. 이때 P는 Q가 성립하기에 충분한 조건이다. P만 확인하면 Q까지 따라오기 때문이다. 반대로 Q는 P가 성립하기 위해 반드시 필요한 조건이다. P가 성립하면 Q가 빠질 수 없기 때문이다. 따라서 Q는 P의 필요조건이다.

짧게 말하면, 참인 조건문 P ⇒ Q에서 화살표의 왼쪽 P는 충분조건이고, 오른쪽 Q는 필요조건이다.

예를 들어

n이 4의 배수이면 n은 짝수이다.

에서 "4의 배수"는 "짝수"이기 위한 충분조건이다. 4의 배수라는 사실만으로 짝수임을 보장할 수 있다. 그러나 "짝수"는 "4의 배수"이기 위한 필요조건이다. 4의 배수라면 반드시 짝수여야 한다.

하지만 짝수라고 해서 반드시 4의 배수는 아니다. 6은 짝수이지만 4의 배수가 아니다. 그래서 역명제

n이 짝수이면 n은 4의 배수이다.

는 거짓이다.

조건문과 함께 알아야 할 네 가지 형태가 있다.

• 원명제: P ⇒ Q

• 역명제: Q ⇒ P

• 이명제: not P ⇒ not Q

• 대우명제: not Q ⇒ not P

여기서 not P는 "P가 아니다"라는 뜻이다. 원명제와 항상 같은 참거짓을 갖는 것은 대우명제이다. 즉 P ⇒ Q가 참이면 not Q ⇒ not P도 참이고, 반대로도 그렇다. 그래서 어떤 명제를 직접 증명하기 어려울 때는 대우명제를 증명하기도 한다.

주의할 점은 역명제나 이명제가 원명제와 항상 같은 참거짓을 갖지는 않는다는 것이다. "4의 배수이면 짝수이다"는 참이지만, "짝수이면 4의 배수이다"는 거짓이다. 조건문에서 화살표의 방향은 생각보다 중요하다.

"P이면 Q이고, Q이면 P이다"가 모두 성립하면 P와 Q는 동치라고 한다. 기호로는 P ⇔ Q라고 쓴다. 이때 P는 Q의 필요충분조건이다. 예를 들어 정수 n에 대해 "n이 짝수이다"와 "n = 2k인 정수 k가 존재한다"는 서로 동치이다. 사실 이것은 짝수의 정의이기도 하다.

전체집합과 부분집합

논리는 문장의 구조를 다루고, 집합은 대상의 모임을 다룬다. 집합은 대학 수학의 거의 모든 분야에서 기본 언어로 쓰인다. 미적분에서는 함수의 정의역과 치역을 말할 때, 선형대수에서는 벡터들의 모임을 말할 때, 확률에서는 사건의 모임을 말할 때 집합을 사용한다.

집합 A에 원소 x가 속하면 x ∈ A라고 쓴다. 속하지 않으면 x ∉ A라고 쓴다. 예를 들어 A = {1, 2, 3}이면 2 ∈ A이고 5 ∉ A이다.

집합을 다룰 때는 먼저 어떤 범위 안에서 이야기하는지 정해야 한다. 이 전체 범위를 전체집합이라고 한다. 예를 들어 "짝수의 여집합"을 말할 때 전체집합이 정수인지, 자연수인지, 실수인지에 따라 의미가 달라진다. 정수 전체에서 짝수의 여집합은 홀수 전체이다. 그러나 실수 전체에서 짝수의 여집합은 "짝수가 아닌 모든 실수"이므로 1.5나 √2도 포함된다.

집합 A의 모든 원소가 집합 B에도 속하면 A는 B의 부분집합이라고 하고 A ⊆ B라고 쓴다. 이 표기는 A = B인 경우도 포함한다. 일부 책에서는 A ⊂ B를 같은 경우까지 포함해 쓰기도 하고, 어떤 책에서는 A ⊂ B를 A ≠ B인 진부분집합의 뜻으로 쓰기도 하므로, 사용하는 책의 약속을 확인하는 습관이 필요하다.

부분집합의 의미는 다음 한 문장으로 정리된다.

A ⊆ B라는 말은 "모든 x에 대하여 x ∈ A이면 x ∈ B이다"라는 뜻이다.

즉 부분집합은 사실 조건문이다. 집합의 언어와 논리의 언어가 여기서 만난다. A에 들어 있는 원소를 하나 골랐을 때, 그 원소가 항상 B에도 들어 있으면 A ⊆ B이다.

합집합, 교집합, 여집합

두 집합 A, B가 있을 때, A 또는 B에 속하는 모든 원소의 집합을 합집합이라 하고 A ∪ B라고 쓴다.

x ∈ A ∪ B ⇔ x ∈ A 또는 x ∈ B

여기서 "또는"은 둘 중 하나만 성립해도 되고, 둘 다 성립해도 된다는 뜻이다. 예를 들어 x가 A에도 속하고 B에도 속하면 당연히 A ∪ B에 속한다.

A와 B에 동시에 속하는 원소들의 집합은 교집합이라 하고 A ∩ B라고 쓴다.

x ∈ A ∩ B ⇔ x ∈ A 그리고 x ∈ B

전체집합 U가 정해져 있을 때, A에 속하지 않는 U의 원소들의 집합을 A의 여집합이라 하고 Aᶜ라고 쓴다.

x ∈ Aᶜ ⇔ x ∈ U 그리고 x ∉ A

또한 A에는 속하지만 B에는 속하지 않는 원소들의 집합을 차집합이라 하고 A B라고 쓴다.

x ∈ A B ⇔ x ∈ A 그리고 x ∉ B

집합 연산은 논리 연산과 같은 구조를 가진다. 합집합은 "또는", 교집합은 "그리고", 여집합은 "아니다"에 대응한다. 그래서 다음과 같은 드모르간 법칙이 성립한다.

• (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ

• (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

첫째 식을 말로 읽으면 이렇다. "A 또는 B에 속하지 않는다"는 말은 "A에도 속하지 않고 B에도 속하지 않는다"는 뜻이다. 둘째 식도 비슷하다. "A와 B에 동시에 속하지 않는다"는 말은 "A에 속하지 않거나 B에 속하지 않는다"는 뜻이다.

이 법칙은 단순한 공식이 아니라 부정의 방향을 알려 주는 규칙이다. "또는"을 부정하면 "그리고"가 되고, "그리고"를 부정하면 "또는"이 된다. 이 구조는 다음에 나오는 전칭명제와 존재명제의 부정에서도 그대로 반복된다.

전칭명제와 존재명제의 부정

대학 수학에서 가장 자주 나오는 표현은 "모든"과 "어떤"이다. "모든"은 전칭기호 ∀로, "존재한다"는 존재기호 ∃로 쓴다.

예를 들어

모든 실수 x에 대하여 x² ≥ 0이다.

는 다음과 같이 쓸 수 있다.

∀x ∈ R, x² ≥ 0

반면

x² = 4를 만족하는 실수 x가 존재한다.

는 다음과 같이 쓸 수 있다.

∃x ∈ R such that x² = 4

이때 중요한 것은 부정하는 방법이다. "모든 x에 대해 P(x)가 성립한다"가 거짓이라는 말은, P(x)가 성립하지 않는 x가 적어도 하나 있다는 뜻이다.

not(∀x, P(x)) ⇔ ∃x such that not P(x)

예를 들어 "모든 자연수 n은 홀수이다"를 부정하면 "홀수가 아닌 자연수 n이 존재한다"가 된다. 실제로 2가 그런 예이다.

반대로 "P(x)를 만족하는 x가 존재한다"가 거짓이라는 말은, 모든 x가 P(x)를 만족하지 않는다는 뜻이다.

not(∃x, P(x)) ⇔ ∀x, not P(x)

예를 들어 "x² = -1을 만족하는 실수 x가 존재한다"를 부정하면 "모든 실수 x에 대하여 x² ≠ -1이다"가 된다.

이 규칙은 반례를 찾을 때 특히 중요하다. "모든"으로 시작하는 명제를 반박하려면 전체를 다 조사할 필요가 없다. 조건을 만족하면서 결론을 깨뜨리는 예 하나면 충분하다. 반대로 "존재한다"는 명제를 증명하려면 실제 예를 하나 제시하면 된다.

또 하나 조심할 점은 변수의 범위이다. "모든 x"라고만 쓰면 어느 집합 안의 x인지 불분명할 수 있다. 모든 실수인지, 모든 정수인지, 모든 양수인지에 따라 명제의 참거짓이 달라진다. 수학 문장을 읽을 때는 기호뿐 아니라 그 기호가 움직이는 범위까지 함께 읽어야 한다.

증명의 네 가지 기본 흐름

증명은 특별한 재능이 아니라 정해진 흐름을 익히는 훈련이다. 여기서는 가장 기본적인 네 가지 방법을 정리한다.

직접증명

직접증명은 조건에서 출발해 결론에 도달하는 방식이다. P ⇒ Q를 증명할 때 P가 참이라고 가정하고, 정의와 이미 아는 성질을 이용해 Q를 이끌어 낸다.

예를 들어 "짝수 두 개의 합은 짝수이다"를 증명해 보자. a, b가 짝수라고 하자. 그러면 어떤 정수 m, n이 있어 a = 2m, b = 2n이다. 따라서 a + b = 2m + 2n = 2(m + n)이다. m + n은 정수이므로 a + b는 짝수이다.

핵심은 짝수라는 말을 정의에 따라 a = 2m으로 바꾸는 것이다. 대학 수학의 많은 증명은 이처럼 정의를 정확히 펼치는 데서 시작한다.

대우증명

대우증명은 P ⇒ Q 대신 not Q ⇒ not P를 증명하는 방법이다. 두 명제는 항상 같은 참거짓을 가지므로 대우명제를 증명하면 원명제도 증명된다.

예를 들어 "정수 n에 대해 n²이 짝수이면 n도 짝수이다"를 보이자. 직접 보이기보다 대우를 쓰면 쉽다. 대우명제는 "n이 홀수이면 n²은 홀수이다"이다. n이 홀수이면 n = 2k + 1인 정수 k가 있다. 그러면 n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1이므로 홀수이다. 따라서 대우명제가 참이고, 원명제도 참이다.

모순증명

모순증명은 어떤 명제를 부정해서 가정한 뒤, 이미 알고 있는 사실이나 앞에서 둔 조건과 충돌하는 결과를 이끌어 내는 방법이다. 충돌이 생기면 처음의 가정이 잘못된 것이다. 따라서 원래 보이려던 명제가 참이어야 한다.

조건문 P ⇒ Q를 모순증명으로 보일 때는 보통 P가 참이고 Q가 거짓이라고 가정한다. 그런 다음 그 가정에서 말이 안 되는 결과가 나오면, P가 참인 상황에서는 Q가 거짓일 수 없다는 뜻이 된다.

예를 들어 어떤 정수가 동시에 짝수이면서 홀수일 수 없다는 사실을 생각해 보자. 만약 한 정수 n이 짝수이면서 홀수라고 가정하면 n = 2a이고 동시에 n = 2b + 1인 정수 a, b가 존재한다. 그러면 2a = 2b + 1이므로 2(a - b) = 1이다. 왼쪽은 짝수인데 오른쪽은 홀수이다. 모순이다. 따라서 그런 정수 n은 존재하지 않는다.

모순증명은 "존재하지 않는다", "불가능하다", "유일하다" 같은 명제를 다룰 때 자주 쓰인다.

수학적 귀납법

수학적 귀납법은 자연수에 대한 명제를 증명할 때 쓰는 방법이다. 기본 구조는 두 단계다.

1. 처음 경우가 참임을 보인다.

2. 어떤 k에서 참이라고 가정하고, 그다음 k + 1에서도 참임을 보인다.

이 두 단계가 성립하면 처음 경우부터 시작해 모든 자연수에 대해 명제가 참이다. 도미노를 생각하면 된다. 첫 도미노가 쓰러지고, 하나가 쓰러지면 다음 것도 반드시 쓰러진다면, 전체 도미노가 차례로 쓰러진다.

예를 들어 모든 자연수 n에 대해

1 + 2 + ... + n = n(n + 1)/2

임을 보이자. n = 1일 때 왼쪽은 1이고 오른쪽도 1(2)/2 = 1이므로 참이다. 이제 n = k일 때

1 + 2 + ... + k = k(k + 1)/2

라고 가정하자. 그러면

1 + 2 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2

이다. 이는 n = k + 1일 때의 식이다. 따라서 모든 자연수 n에 대해 공식이 성립한다.

여기서 주의할 점은 "k에서 참이라고 가정한다"는 말이 모든 경우를 이미 안다는 뜻이 아니라는 것이다. 귀납 단계 안에서 임시로 사용하는 가정이다. 그리고 처음 경우가 n = 1이면 n = 1부터, n = 0이면 n = 0부터 결론이 이어진다는 점도 함께 기억해 두면 좋다.

데카르트 곱, 관계, 함수

집합은 원소를 모으는 언어이고, 관계는 원소들 사이의 연결을 나타내는 언어이다. 두 집합 A, B가 있을 때, A의 원소와 B의 원소를 순서쌍으로 묶은 전체 집합을 데카르트 곱이라 하고 A × B라고 쓴다.

A × B = {(a, b) | a ∈ A, b ∈ B}

예를 들어 A = {1, 2}, B = {x, y}이면

A × B = {(1, x), (1, y), (2, x), (2, y)}

이다. 여기서 순서쌍은 순서가 중요하다. 일반적으로 (a, b)와 (b, a)는 다르다.

관계는 데카르트 곱의 부분집합이다. 즉 A의 원소와 B의 원소 중 어떤 쌍들이 서로 연결되어 있는지를 골라 놓은 것이다. 예를 들어 학생 집합 S와 과목 집합 C가 있을 때, "학생 s가 과목 c를 수강한다"는 관계는 S × C의 부분집합으로 볼 수 있다.

함수는 특별한 관계이다. A에서 B로 가는 함수 f는 A의 각 원소 a에 대해 B의 원소 하나를 정확히 하나씩 대응시키는 규칙이다. 기호로는 f: A → B라고 쓴다. 즉 함수에서는 입력 하나가 여러 출력으로 갈 수 없고, 정의역의 원소가 대응 없이 빠져 있어도 안 된다. 이때 A를 정의역, B를 공역, 실제로 함수값으로 나오는 원소들의 집합을 치역이라고 한다. 치역은 항상 공역의 부분집합이다.

좌표평면도 데카르트 곱으로 이해할 수 있다. 실수 전체의 집합을 R이라 하면 R × R은 모든 실수 순서쌍 (x, y)의 집합이다. 이것을 보통 R²라고 쓰며, 우리가 아는 좌표평면이다. 마찬가지로 R³는 공간의 점을 나타내는 데 쓰인다.

이 관점은 앞으로 중요해진다. 함수는 단순한 공식이 아니라 두 집합 사이의 대응이다. 벡터는 숫자의 나열이 아니라 특정한 집합의 원소이다. 확률에서 사건은 가능한 결과들의 부분집합이다. 대학 수학의 여러 분야가 서로 달라 보여도, 그 밑에는 논리와 집합이라는 공통 문법이 놓여 있다.

읽는 습관이 곧 실력이다

이 장의 목표는 많은 기호를 외우는 것이 아니다. 수학 문장을 정확히 읽는 습관을 만드는 것이다. 명제를 보면 조건과 결론을 나누고, "모든"과 "존재한다"의 범위를 확인해야 한다. 집합이 나오면 전체집합이 무엇인지, 원소가 무엇인지, 부분집합 관계가 무엇을 뜻하는지 살펴야 한다. 증명을 읽을 때는 어떤 방법을 쓰는지, 어디서 정의가 사용되는지, 어떤 순간에 결론이 나오는지 추적해야 한다.

논리와 집합은 별도의 단원이 아니라 대학 수학 전체의 문법이다. 이 문법이 익숙해지면 미적분의 극한 정의, 선형대수의 부분공간, 확률의 사건, 해석학의 엄밀한 증명이 훨씬 덜 낯설어진다. 다음 장부터는 이 언어를 바탕으로 수와 함수의 구조를 더 체계적으로 살펴볼 것이다.