02 실수계의 성질
2.3 수학적 귀납법
자연수 집합, 정수 집합, 유리수 집합은 모두 실수 집합의 부분집합이다. 자연수 중에서 가장 작은 수는 이며 다른 모든 자연수는 다음과 같이 을 거듭 더하여 얻을 수 있다.
, , , , ⋯ 즉 자연수 집합은 다음 두 성질을 가지고 있다.
(ⅰ) 을 원소로 가진다, (ⅱ) 이 원소이면 도 원소이다. (1) 위 두 조건을 모두 만족시키는 집합을 귀납적 집합이라고 부른다. 귀납적 집합의 정의에 따라 자연수 집합은 귀납적 집합이다. 그러나 귀납적인 집합이 자연수 집합만 있는 것은 아니다. 즉 위의 두 조건만으로는 자연수 집합을 정의하기에 충분하지 않다. 예를 들어 집합
⋯ ⋯,
⋯
은 (1)의 두 조건을 모두 만족시키지만 자연수 집합이 아니다. 그러나 (1)의 두 조건을 모두 만족시키는 집합은 항상 자연수 집합을 포함하므로, 귀납적 집합 중 가장 작은 집합을 자연수 집합이라고 정의하면 된다. 따라서 자연수 집합을 다음과 같이 정의한다.
정의 2.3.1 자연수
실수 집합의 부분집합
가 두 조건(ⅰ) ∈
(ⅱ) ∈
⇒ ∈
를 모두 만족시킬 때
를 귀납적 집합(inductive set)이라고 부른다. 실수 집합의 부분집합 중에서 귀납적인 집합들을 모두 교집합한 집합을 자연수 집합이라고 부르며 ℕ으로 나타낸다. ℕ의 원소를 자연수(natural number)라고 부른다.참고
2.3.2 귀납적 집합들의 교집합은 귀납적 집합이다. 따라서 자연수 집합도 귀납적 집합이다.
증명
집합족
∈
의 모든 원소가 귀납적 집합이라고 하자. 그리고
∩
라고 하자. 명백히 모든에 대하여 ∈
이므로 ∈
이다. 또한 ∈
라고 가정하면 모든 에 대하여 ∈
이다. 그런데
는 귀납적 집합이므로 ∈
이다. 따라서 ∈
이다. 즉
는 귀납적 집합이다. ■일반적으로 실수 와 실수 집합의 부분집합
,
에 대하여 다음과 같이 정의한다.∙
≔ ∈
∈
∙
≔ ∈
∈
∙
≔ ∈
∙
≔ ∈
∙
≔ ∈
이러한 표기법을 바탕으로 정수 집합과 유리수 집합을 다음과 같이 정의한다.
47
2.3 수학적 귀납법
정의 2.3.3 정수, 유리수, 무리수
집합 ℤ ≔ ℕ ∪∪ℕ을 정수 집합이라고 부르며, ℤ의 원소를 정수(integer)라고 부른다.
집합 ℚ ≔
∈ℤ ∈ℤ
를 유리수 집합이라고 부르며, ℚ의 원소를 유리수(rational number)라고 부른다. 유리수가 아닌 실수를 무리수(irrational number)라고 부른다.자연수 집합의 표기는 영어 단어 natural의 첫 글자를 딴 것이고, 정수 집합의 표기는 독일어 단어 Zahl의 첫 글자를 딴 것이며 유리수 집합의 표기는 영어 단어 quotient의 첫 글자를 딴 것이다.
유리수 집합은 공리 2.1.1의 모든 조건을 만족시킨다. 즉 유리수 집합은 체(field)이다. 한편 대수학의 이론에 의 하면 표수(characteristic)가 인 임의의 무한체는 ℚ를 부분체로서 포함한다. 이러한 성질 때문에 ℚ를 소체 (prime field)라고 부르기도 한다.
참 또는 거짓을 값으로 갖는 함수를 명제함수라고 부른다. 명제함수 와 유한집합
가 주어졌을 때
의 모든 원소에 대하여 가 참임을 증명하는 것은 어렵지 않다. [물론 의 원소의 개수가 매우 많은 경우에는 다소 시간이 걸릴 수 도 있다.] 예를 들어 집합 의 모든 원소가 방정식 의 근이 된다는 것을 증명하기 위해 서는 직접 대입해보면 된다. 그러나 명제함수 와 무한집합
가 주어졌을 때
의 모든 원소 에 대하여가 참임을 증명하는 것은 쉽지 않다. 이러한 경우 정의역의 특성과 명제함수의 종류에 따라서 여러 가지 방법으로 증명을 시도하게 된다.
특히 어떠한 명제가 임의의 자연수에 대하여 참임을 보일 때에는 수학적 귀납법이라는 유용한 증명 방법을 사 용할 수 있다.
정리 2.3.4 수학적 귀납법(mathematical induction, finite induction) 정의역이 자연수 집합인 명제 가 두 조건
(ⅰ) 이 참이다,
(ⅱ) 가 참이라고 가정하면 도 참이다
를 모두 만족시키면, 임의의 자연수 에 대하여 은 참이다.
증명
의 진리집합을
라고 하자. 즉
∈ℕ 이라고 하자. 먼저 의 정의역이 자연수 집합이므 로
⊆ ℕ이다.다음으로 ℕ ⊆
임을 보이자. 먼저 정리의 조건 (ⅰ)에 의하여 ∈
이다. 또한 정리의 조건 (ⅱ)에 의 하여 ∈
일 때마다 ∈
가 성립한다. 따라서
는 귀납적 집합이다. 자연수 집합은 귀납적 집합 들의 교집합이므로 ℕ ⊆
이다.이로써
⊆ ℕ이고 ℕ ⊆
이므로
ℕ이다.
의 진리집합이 자연수 집합이므로 임의의 자연수 에 대하여 은 참이다. ■
위 정리의 (ⅱ)에서 를 귀납적 가정(inductive assumption)이라고 부른다.
흔히 우리가 명제의 참, 거짓을 말할 때 ‘~가 참이다’라는 말은 생략한다. 예를 들어 ‘ 가 참이다’라고 하는 대신 ‘ 이다’라고 말한다. 이러한 관점에서 정리 2.3.4의 두 조건은 간략하게 다음과 같이 나타낼 수 있다.
(ⅰ) (ⅱ) ⇒
예제
2.3.5 ≥ 일 때, 임의의 자연수 에 대하여 다음 부등식이 성립함을 증명하여라.
≥ (2)
이 부등식을 베르누이(Bernoulli)의 부등식이라고 부른다. [해석학의 증명에서 아주 많이 사용된다.]
풀이
부등식 (2)를 으로 나타내자. 그러면 는 정의역이 자연수 집합인 명제함수가 된다. 이제 수학적 귀 납법을 이용하여 임의의 자연수 에 대하여 이 참임을 보이자.먼저 일 때 ≥ 이므로 은 참이다.
다음으로 자연수 에 대하여 가 참이라고 가정하자. 그러면
≥
이다. ≥ 이므로 위 부등식의 양변에 를 곱하여도 부등호의 방향이 바뀌지 않는다. 즉
≥
이다. 그런데 ≥ 이므로 이 부등식을 위 부등식과 결합하면
≥
를 얻는다. 따라서 도 참이다.
이로써 수학적 귀납법에 의하여 임의의 자연수 에 대하여 은 참이다. □
예제
2.3.6 자연수 집합이 덧셈에 대하여 닫혀있음을 증명하여라.
풀이
임의의 자연수 , 에 대하여 이 자연수가 됨을 증명해야 한다. 그런데 이 명제는 변수가 과으로서 개이므로, 수학적 귀납법을 두 변수에 동시에 적용할 수 없다. 이러한 경우 하나의 변수가 임 의로 주어졌다고 가정하고 다른 변수에 수학적 귀납법을 적용한다.
자연수 이 임의로 주어졌다고 하자. 그리고 명제 ∈ℕ을 으로 나타내자.
먼저 ℕ은 귀납적 집합이고 ∈ℕ이므로 ∈ℕ이다. 따라서 은 참이다.
다음으로 자연수 에 대하여 가 참이라고 가정하자. 즉 ∈ℕ이라고 가정하자. ℕ은 귀납적 집합이므로 ∈ℕ이다. 즉 도 참이다.
따라서 수학적 귀납법에 의하여 임의의 자연수 에 대하여 은 참이다. 이 임의로 주어진 자연수
이므로, 임의의 자연수 , 에 대하여 ∈ℕ은 참이다. □
수학적 귀납법은 정의역이 자연수 집합인 함수를 정의할 때에도 사용된다. 즉 ℕ 위에서 함수 를 정의할 때 (ⅰ) 의 값을 정의하고,
(ⅱ) , , ⋯, 의 값이 정의되어 있다고 가정하고 이를 이용하여 의 값을 정의 하면 임의의 자연수 에 대하여 함숫값 이 정해진다. 함수를 이러한 방법으로 정의하는 것을 귀납적 정의 라고 부른다. 중학교에서 배운 자연수 지수 , 고등학교에서 배운 차례곱 , 이항계수 C, 합 기호
등은 모두 귀납적으로 정의된 함수이다.
귀납적으로 정의된 함수의 성질을 증명할 때에는 수학적 귀납법을 이용하는 경우가 많다.
49
2.3 수학적 귀납법 예제
2.3.7 실수 와 자연수 에 대하여
자연수 지수를 가진 거듭제곱을 다음과 같이 정의한다.(ⅰ) ≔ (ⅱ) ≔ ⋅
이때 실수 와 자연수 , 에 대하여 이 성립함을 증명하여라.
풀이
자연수 이 임의로 주어졌다고 하자. 그리고 에 대한 명제 을 으로 나타내자. 먼 저 자연수 지수의 정의에 의하여 ⋅이므로 은 참이다.다음으로 자연수 에 대하여 가 참이라고 가정하자. 즉 이라고 가정하자. 이 등식의 양변에 를 곱하면 좌변은
이고 우변은 이므로
을 얻는다. 즉 도 참이다.
따라서 수학적 귀납법에 의하여 임의의 자연수 에 대하여 은 참이다. ■
끝으로 자연수 집합에서 부등호의 중요한 성질을 살펴보자.
보조정리
2.3.8
자연수는 다음과 같은 성질을 가진다.(ⅰ) 임의의 자연수 에 대하여 이거나 ∈ℕ이다.
(ⅱ) 자연수 , 에 대하여 이면 은 자연수이다.
(ⅲ) 자연수 에 대하여 인 자연수 은 존재하지 않는다.
증명
(ⅰ) 수학적 귀납법으로 증명하자. 일 때에는 이다. 이제 자연수 에 대하여 일 때 (ⅰ)이 참이라고 가정하자. 만약 이면 ∈ℕ이다. 만약 ∈ℕ이면 ∈ℕ이다. 따라서 일 때에도 정리의 명제는 참이다.
(ⅱ) 에 수학적 귀납법을 적용하자. 인 경우 인 자연수 에 대하여 은 자 연수이다. 이제 가 자연수이고 인 자연수 에 대하여 가 자연수라고 하자. 그러면 은 자연수이고, 이 인 자연수일 때 도 자연수이다. 따라서 일 때에도 인 자연수 에 대하여 정리의 명제는 참이다.
(ⅲ) 인 자연수 이 존재한다고 가정하자. 그러면 ∈ℕ이다. 또한 이 므로 이다. 모든 자연수는 이상이므로 이것은 모순이다. ■
정리 2.3.9 자연수 집합의 정렬성
자연수 집합 ℕ은 순서관계 ≤를 가진 정렬집합이다.
증명
가 ℕ의 부분집합이고 공집합이 아니라고 하자. 이제
가 최소원소를 가짐을 보여야 한다.명제 ‘∈
이면
는 최소원소를 가진다’를 으로 나타내자. 먼저 ∈
이면 이
의 최소원소가 된다. 따라서 은 참이다.이제 자연수 에 대하여 가 참이라고 가정하자. 그리고 ∈
라고 하자. 그러면 귀납적 가정에 의하여
∪는 최소원소를 가진다. 그 최소원소를 이라고 하자. 만약 ∈
이면 은
의 최소 원소가 된다. 만약 ∉
이면 이므로 이
의 최소원소가 된다. 즉 ∈
일 때에도
는 최소원소를 가지므로 도 참이다.따라서 수학적 귀납법에 의하여 임의의 자연수 에 대하여 은 참이다. ■