귀류법(Proof by contradiction)

귀류법(歸謬法)은 "P이면 Q이다."라는 명제에서 결론인 Q를 부정함으로써 생기는 새로운 명제 "P이면서 Q가 아니다."에서 모순이 발생함을 증명하여 원래의 명제가 참임을 증명하는 간접 증명법입니다. 배리법(背理法) 또는 반증법(反證法)이라고도 불리는 이 방법은 현재 고등학교 1학년 학생이 배우는 과목에서도 등장하는 증명법으로, 가장 유명한 문제는 다음과 같은 명제를 증명하는 것입니다. $\sqrt{2}$는 유리수가 아니다. 고등학교 교과과정에서는 다음과 같은 과정을 거쳐 이 명제를 증명합니다. 결론을 부정하여 $\sqrt{2}$가 유리수라고 가정한다. 유리수의 정의에 의해 서로소인 어떤 두 정수 $p$와 $q$를 이용하여 $\sqrt{2} = \frac{p}{q} (q \neq 0)$의 꼴로 나타낼 수..

2021.04.16

중국인의 나머지 정리(Chinese Remainder Theorem)

중국인의 나머지 정리(Chinese remainder theorem, CRT)는 손자(孫子)라는 인물이 기원후 3세기에서 5세기 사이에 집필하였다고 추정되는 문헌인 《손자산경》(孫子算經) 하권(下券)에 등장하는 다음과 같은 문제에서 비롯된 정리입니다. 개수를 알지 못하는 것들이 있다. 셋씩 센다면 두 개가 남고, 다섯씩 센다면 세 개가 남고, 일곱씩 센다면 두 개가 남는다. 질문: 총 몇 개인가? 이 문제는 다음과 같은 연립합동식의 해를 구하는 것과 같습니다. $$\begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \\ x \equiv 2 \pmod{7} \end{cases}$$ 손자산경에서는 이 문제를 다음과 같이 풀었습니다. 셋씩 세어 두 개가 남으면..

2021.04.13

립시츠 연속성(Lipschitz continuity)

립시츠 연속성(Lipschitz continuity)은 독일의 수학자 Rudolf Lipschitz(1832-1903)에 의해 정의된 함수의 특성입니다. 만약 두 거리 공간(metric space) $(X, d_X)$와 $(Y, d_Y)$에 대해 다음과 같은 식을 만족하는 양의 실수 $K$가 모든 $x_1$과 $x_2$에 대해 존재한다면, 함수 $f$는 립시츠 연속 함수(Lipschitz continuous function)라고 부릅니다. $$d_Y (f(x_1), f(x_2)) \leq K d_X (x_1, x_2)$$ 또한, $K$가 될 수 있는 모든 양의 실수는 립시츠 상수(Lipschitz constant)라고 불립니다. 실제로는 $K$가 될 수 있는 실수 중 가장 작은 값만을 주로 립시츠 상수라..

2021.03.09