Elementary Number Theory - 1.1 Mathmetical Induction

Elementary Number Theory - 1.1 Mathmetical Induction

David M.Burton

용어 정리

원리

정리(theorem)

수학적 귀납법

기초적인 숫자에 대한 이론은 정수와 1, 2, 3 같은 자연수의 성질에 대한 것으로 생각 되었다. 하지만 이것은 잘못된 생각에서 나온 잘못된 표기이다. 이러한 잘못된 표기의 기원은 '숫자'라는 단어가 '양의 정수'만을 의미하던 시절인 고대 그리스로 거슬러 올라간다.

자연수는 오랫동안 수학자 레오파드 크로네커가 이야기 한것 처럼, "신은 자연수를 만들었고, 나머지는 인간이 만들었다"와 같이 생각 되었다. 하늘의 선물과는 상관 없이, 숫자 이론은 오랜 시간 때로는 아픈 성장을 해왔다. 이 이야기는 다음 페이지에서 하기로 하겠다.

우리는 정수를 공리적으로 만드는 시도를 하지 않을 것이다. 다신 대부분의 독자들이 정수의 요소들에 대해 알고있다고 가정하고 이 글을 쓸 써나갈 것이다. 그 중 하나가 정렬성 원리이다. 기억을 되살리기 위해 한번 다시 알아보도록 하자.

정렬성의 원리 Well Ordering Principle

공집합이 아니고, 음의 정수가 아닌 집합 S는 최소한 하나의 원소를 가지고 있다. 집합 S에 있는 a라는 정수(가지런한 수)는 집합 S의 원소인 b에 대해 a가 b보다 작거나 같다는 조건을 만족한다.

공집합이 아니고 음수가 아닌 정수를 1개 이상 가지고 있는 모든 집합 S는 적어도 1개의 원소를 가지고 있다. 집합 S에 있는 a라는 정수는 집합 S의 원소 b에 대해 a <= b를 만족한다.

같은 내용을 반복해서 쓴 것은 처음 번역 했을 때랑 두번째 번역했을때 뉘앙스를 둘다 알면 이해 하기가 좀 더 편해서 이다.

예를들어 공집합([ ])이 아닌 S라는 집합이 있다고 하자.

S = [ 1 ] 일 때 S라는 집합은 1이라는 한개의 원소를 가지고 있다.

그러면 여기에서 한개를 뽑아서 a라는 변수에 넣어보자.

a = 1

이렇게 된다.

그리고 s에서 또 하나의 수를 뽑는다. 그리고 b에 넣어본다. 그런데 앞에서 하나 뽑았기 때문에 또 하나를 뽑는다고 하면 헷갈릴 수 도 있는데 S라는 다른 집합이 있는게 아니고 위에서 1을 뽑았던 그 집합이다.

b = 1

1이 또 나올 수 밖에 없는데 S에는 원소가 하나밖에 없기 때문이다. 뭐를 몇번을 뽑아도 1이 계속 나올 수 밖에 없다. 너무나 당연한 이야기를 구구절절 설명을 하고 이해를 왜 해야 하는지도 이해가 안가는데 증명의 출발은 이런 빠져나갈 수 없는 구멍들을 만들어 놓는 것에서 출발한다.

자 그럼 a와 b를 뽑았다. a도 1이고 b도 1이니까 a <= b 를 만족한다.

이 이야기가 위에 정렬성의 원리이다.

자 그러면 유사한 다른 집합을 보자.

S = [ 1 , 2 ]

원소는 2개이고 1과 2가 들어있다.

여기에서도 

공집합이 아니고 음수가 아닌 정수를 1개 이상 가지고 있는 모든 집합 S는 적어도 1개의 원소를 가지고 있다. 집합 S에 있는 a라는 정수는 집합 S의 원소 b에 대해 a <= b를 만족한다.

이 원리는 적용이 된다.

a, b순서로 1, 2를 뽑아도 a <= b를 만족 한다.

2, 2순서로 뽑아도 a <= b를 만족 한다.

그런데 2, 1 이렇게 뽑으면 a <= b는 만족을 안한다. 그래서 이해가 좀 안될 수도 있는데 정리는 a를 뽑으면 무조껀 b보다 작다는게 정리가 아니고 무언가 원소를 뽑았을 때 a <= b를 만족하는게 존재 한다는 것이다.

그러니까 아닌것도 있는데 어쨌든 적어도 최소한 1개는 존재 한다는 뜻이다.

이 원리는 이번장과 다음장에 나오는 증명에서 중요한 역할을 한다. 양의 정수 집합은 아르키메데스 프로퍼티를 만족한다는 것을 증명하는데 사용한다.

띠어럼 1.1 아르키메디안 프로퍼티. a와 b가 양의 정수라면 na>=b를 만족하는 양의 정수 n이 존재한다.

증명. 위 띠어럼이 틀리다고 가정하자, 그랬을 때 어떤 a와 b가 na < b를 모든 양의 정수에 넣었을 때도 맞다는게 된다.

S = {b - na | n은 양의 정수}

정렬성 법칙에 의해, 집합S는 b - ma를 만족하는 최소 원소를 가지게 될 것이다. 하지만 b - (m + 1)a 는 S에서는 거짓이다. 왜냐하면 S는 모든 정수를 포함하고 있기 때문이다.

archimedean property

a, b가 positive integer 일 때, na >= b 가 되게 하는 natural number n이 존재한다.

proof) assume na >= b 인 positive integer n이 존재하지 않는다는 것은 아래와 같은 말이다.

every natural number n은 na < b( b - na > 0) 이다.

set S, S = { b - na | n is positive integer} = { b - 1a, b - 2a, c - 3a, ····}

S의 모든 element는 positive integer이다.

for well-ordering principle, S have least element. n이 m일 때가 최소라고 했을때 m-ma가 S의 least element.

그런데 m+1도 자연수이므로 b-(m+1)a도 S의 원소이다.