고등학생을 위한 즐거운 이산수학

목적

《이산수학》은 수학적 증명과 정수(整數)에 관한 것을 배우는 책이다. 원래는 《자료구조》와 연계할 목적으로 알고리즘이나 그래프에 대한 내용도 계획했지만, 논증 부분을 앞으로 끌어다가 강화하고 나니, 그 단원의 분량이 애매해질 것 같아서 제외하였다. 《이산수학》은 수학적 증명법에 대한 내용을 담고 있기에 반드시 위계의 최하단에 존재해야만 했고, 《고등학생을 위한 즐거운 기본수학》과 동시에 학습하는 것을 전제로 만들어졌다. 또한 경우의 수나 수열을 담고 있으므로 《고등학생을 위한 즐거운 확률과 통계》나 《고등학생을 위한 즐거운 미적분》을 배우기 전에 선행해야 한다.

명제와 집합

명제와 조건문

명제와 진릿값

명제(Proposition)란 참(T; True)과 거짓(F; False)을 구분할 수 있는 문장을 가리킨다. 여기서 참과 거짓은 명제의 진릿값(Truth value)이다.

2는 짝수다.: 참인 명제
만우절은 3월 32일이다.: 거짓인 명제
구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle x} 는 5다.: 명제가 아님

$x$는 5다.가 명제가 아닌 이유는, $x$가 미지수이기 때문으로, 값이 정의되지 않았기 때문이다. 명제는 항상 명확하고 구체적으로 작성되어야 한다.

진리표와 논리 연산자

진리표

$p$	$q$		$p\land q$	$p\lor q$	$\lnot p$
T	T		T	T	F
T	F		F	T
F	T		F	T	T
F	F		F	F

둘 이상의 명제를 아울러 쓰자면, '그리고'나 '또는'이라는 단어를 쓰게 된다. 우리는 명제 $p$와 $q$에 대해 '$p$ 그리고 $q$'는 $p\land q$로, '$p$ 또는 $q$'는 $p\lor q$로 쓰기로 한다. 또한 각각 단위 명제의 진릿값에 따른, 복합 명제의 진릿값을 따지기 위해 진리표(Truth table)을 작성한다. 그리하여 두 복합 명제가 서로 같은 결론에 다다르면, 그 두 복합 명제는 서로 동치(Equivalent)라고 하고, 기호로는 $\equiv$을 쓴다.

한편, 명제의 부정도 존재하는데, 명제 $p$의 부정은 $\lnot p$로 한다. 한편, $p\equiv \lnot \lnot p$가 성립하며, $p\lor \lnot p$는 항상 참이다. 이렇게 항상 참인 것은 토톨로지(Tautology)라고 한다. 이는 비트겐슈타인이 썼던 용어이기도 한다.

논리 연산 법칙

논리 연산 법칙에는 여러 개가 있으며, 그 중 대표적인 것은 아래와 같다. 또한, 증명은 위에서 배운 진리표만 갖고도 쉽게 할 수 있다.

1. 교환법칙: $p\land q\equiv q\land p$, $p\lor q\equiv q\lor p$
2. 결합법칙: $(p\land q)\land r\equiv p\land (q\land r)$, $(p\lor q)\lor r\equiv p\lor (q\lor r)$
3. 분배법칙: $(p\land q)\lor r\equiv (p\lor r)\land (q\lor r)$, $(p\lor q)\land r\equiv (p\land r)\lor (q\land r)$
4. 멱등법칙: $p\land p\equiv p,p\lor p\equiv p$
5. 흡수법칙: $p\land (p\lor q)\equiv p,p\lor (p\land q)\equiv p$

특히, 프랑스계 영국 수학자인 드 모르간은 명제와 집합의 연산에 관한 기초적인 법칙인, '드 모르간 법칙'을 발견하였다. 그 내용인즉, 아래와 같으며 증명은 위에서 했던 것과 같이, 진리표를 이용해 할 수 있다.

$\lnot (p\lor q)\equiv (\lnot p)\land (\lnot q)$
$\lnot (p\land q)\equiv (\lnot p)\lor (\lnot q)$

조건문

조건문

$p$	$q$		$p\implies q$	$\lnot p\lor q$
T	T		T	T
T	F		F	F
F	T		T	T
F	F		T	T

조건문(Conditional statement)은 한 명제가 참일 때, 다른 한 명제도 참이 되는 문장을 말한다. 예컨대, 두 명제 $p$와 $q$에 대해서 $p$가 참일 때 $q$가 참이면, $p\implies q(\equiv \lnot p\lor q)$라고 쓴다. 여기서 $p$는 $q$에 대한 충분조건, $q$는 $p$에 대한 필요조건이라고 한다. 한편, $p\implies q$와 $q\implies p$가 동시에 참이라면 $p\iff q$라 쓸 수 있다. 이를 필요충분조건이라고 한다. $p$가 거짓이면 $q$의 진릿값에 무관하게 참이 된다는 게 이상하다고 생각될 수도 있다. 그러나 수학에서는 이를 '공허한 참'이라고 부른다. 이에 대한 설명은 집합에 대해 설명할 때 다시 언급하도록 하겠다.

역, 이, 대우

역, 이, 대우

$p\implies q$	← 역 →	$q\implies p$
↑ 이 ↓	↖ 　　 ↗ 대우 ↙ 　　 ↘	↑ 이 ↓
$\lnot p\implies \lnot q$	← 역 →	$\lnot q\implies \lnot p$

조건문 $p\implies q$에서, 가정과 결론을 서로 바꾼 $q\implies p$는 역(易), 가정과 결론을 모두 부정한 $\lnot p\implies \lnot q$는 이(裏), 역과 이를 동시에 한 $\lnot q\implies \lnot p$는 대우라고 한다. 조건문의 역과 이의 진릿값은 다시 계산해서 구해내야 하지만, 대우의 진릿값은 원래 조건문의 진릿값과 같으며, 이 또한 진리표로 증명할 수 있다.

일반성과 존재성에 관하여

어떤 명제가 '모든 $x$(for any $x$/for all $x$)'에 대해 성립할 때, '모든 $x$'를 기호로는 $\forall x$라고 한다. 한편, 어떤 명제를 만족하는 '$x$가 존재한다($x$ exists)'라면, '$x$가 존재한다'를 기호로는 $\exists x$라고 한다. 그렇지 않다면 $\nexists x$로 쓴다. 명제가 $\forall x\in X,p(x)$라 되어 있으면, 그 부정은 $\exists x\in X,\lnot p(x)$가 되고, 명제가 $\exists x\in X,p(x)$면, 그 부정은 $\forall x,\lnot p(x)$가 된다.

한편, $\forall$과 $\exists$를 한 문장에서 동시에 쓸 때에는 그 순서에 유의해야 한다. 예컨대, 아래 두 문장을 보자.

1. $\exists a,\forall b,p(a,b)$
2. $\forall b,\exists a,p(a,b)$

1번 문장은 $a$가 존재하는데, 이는 모든 $b$에 대해 명제 $p(a,b)$가 참이 된다.라는 뜻이다. 2번 문장은 모든 $b$에 대해, 명제 $p(a,b)$가 참이 되는 어떤 $a$가 존재한다.라는 뜻이다. 굉장히 미묘한 차이로 보이지만 따지고 보면 큰 차이다. 1번 문장에서는 모든 $b$에 대해서 주어진 명제 $p(a,b)$가 항상 참이 되는 $a$가 존재해야 한다. 한편, 2번 문장에서는 모든 $b$에 대해 주어진 명제 $p(a,b)$가 참이되는 $a$가 모든 경우에 대해 존재하는지만 구하면 된다. 즉, 1번 문장이 참이면 2번 문장도 참이 되지만, 2번 문장이 거짓이면 1번 문장도 거짓이 된다. 즉, 이 두 문장에 대해 존재할 수 있는 경우의 수는 세 가지이다.

1. 두 문장 모두 참
2. 1번 문장은 거짓, 2번 문장은 참
3. 두 문장 모두 거짓

집합과 그 연산

집합

집합(Set)은 일정한 조건에 부합하는 개별 요소(원소; Element)들의 모임을 의미한다. 어떤 요소 $a$가 집합 $S$의 원소라면, 이를 $a\in S$로 표현한다. 그렇지 않다면 $a\notin S$라고 표현한다. 한편, 집합의 원소로써 집합을 넣는 일은 아주 조심해야 하는 사항이다. 현대수학에서는 모든 것이 원소가 될 수 있는 것은 아니기 때문이다. 그렇지 않다면 '자기 자신을 포함하지 않는 모든 것의 집합'에는 자기 자신을 포함해야 하느냐 말아야 하느냐는 문제가 발생한다. 이를 러셀의 역설(Russell's Paradox)이라 한다. 이 역설의 해결책에 대한 자세한 내용은 《고등학생을 위한 즐거운 고급수학》에서 배울 수 있다.

집합의 표기

집합 안에 어떤 원소가 들어있는지를 나타내는 방법에는 원소나열법과 조건제시법이 있다. 원소나열법은 말 그대로 집합 안의 원소를 일일이 나열하는 것인데, 나열할 때에는 작은 것부터 차례대로 나열하는 것이 좋다. 조건제시법은 특정한 조건을 만족하는 수들이 집합에 속한다는 것을 표시하는 방법이다. 이 두 방법을 통해 짝수의 집합을 나타내는 방법은 아래와 같다.

• 원소나열법: $\left\{2,4,6,\cdots \right\}$
• 조건제시법: $\left\{2n|n\in \mathbb {N} \right\}$
• 벤 다이어그램: 하나의 집합을 하나의 닫힌 곡선으로 그리고, 곡선 안에 집합의 원소를 나타낸다. 다만, 증명으로서는 효력이 없다.

집합의 연산

집합의 연산

$A$	$\left\{1,2,4\right\}$
$B$	$\left\{2,3,5\right\}$
$|A|$	$3$
$A\cup B$	$\left\{1,2,3,4,5\right\}$
$A\cap B$	$\left\{2\right\}$
$A^{C}$	$U-A\equiv U-\left\{1,2,4\right\}$
$A-B$	$A-A\cap B\equiv A\cap B^{C}\equiv \left\{1,4\right\}$
${\mathcal {P}}(A)$	$\left\{\emptyset ,\left\{1\right\},\left\{2\right\},\left\{4\right\},\left\{1,2\right\},\left\{1,4\right\},\left\{2,4\right\},\left\{1,2,4\right\}\right\}$

원소가 없는 집합은 공집합(Empty set)이라 하며 기호는 $\emptyset$으로 한다. 한편, 모든 원소들로 이루어진 집합은 전체집합이라 한다. 이는 Universe에서 따온 $U$로 표기한다.

두 집합 $A$, $B$가 $A:=\left\{x|p(x)\right\}$, $B:=\left\{x|q(x)\right\}$라고 하자.

1. 집합에 있는 원소의 개수를 표시할 때에는 집합에 절댓값 기호를 씌운다.
2. $\left\{x|p(x)\lor q(x)\right\}$는 $A\cup B$라 쓰며, 이를 합집합(Union)이라고 한다.
3. $\left\{x|p(x)\land q(x)\right\}$는 $A\cap B$라 쓰며, 이를 교집합(Intersection)이라고 한다.
4. $\left\{x|\lnot p(x)\right\}$는 $A^{C}$라 쓰며, 이를 여집합(Complement)이라고 한다.
5. $\left\{x|p(x)\land \lnot q(x)\right\}$는 $A-B$라 쓰며, 이를 차집합(Subtraction)이라고 한다. 이때, $A$와 $B$의 교집합에 속한 원소가 없어도 무방하다.
6. $p(x)\implies q(x)$일 때, $A\subset B$라 쓰며, $A$는 $B$의 부분집합(Subset)이라고 한다. 공집합은 모든 집합의 부분집합이고 모든집합은 전체집합의 부분집합이다.
7. $p(x)\iff q(x)$일 때, $A=B$라 쓰며, $A$와 $B$는 같은 집합이다.
8. $\left\{X|X\subset A\right\}$는 ${\mathcal {P}}(A)$ 또는 $2^{A}$라고 하며, 이를 멱집합(Power set)이라고 한다.

앞서 공허한 참에 대해 말했던 것을 다시 떠올려 보자. 조건문 $p\implies q$에서, 명제 $p$와 $q$가 참이 되는 원소들의 집합을 각각 $P$와 $Q$라고 하자. 그러니까 $p\implies q$가 참이라는 것은, $P\subset Q$와 동치다. 그러나 공허한 참의 경우에는 집합 $P$가 공집합이 되는 것인데, 공집합은 모든 집합의 부분집합이므로, 공허한 참 또한 참이 되는 것이다.

논증

노가다법

노가다법은 말 그대로 모든 경우의 수를 따져가며 명제나 조건문이 참인지를 증명하는 방법이다. 진리표를 이용하는 방법도 이에 속한다. 직관적이고 방법도 쉽지만, 시간이 너무 오래 걸린다는 단점이 있다. 이 방법은 반례(Counterexample)를 찾을 때라든가, 아니면 방정식의 해를 구하는 방법을 모를 때에 조금 더 유용하다.

예컨대, $x^{5}-6x^{4}+8x^{3}-97x^{2}-392=0$의 자연수 해를 찾으라고 한다면, 어쩔 수 없이 1부터 차례대로 대입하는 수밖에 없다. 5차 이상의 방정식에는 일반적인 형태의 근의 공식이 없기 때문이다. 한편, 저 방정식의 자연수 해는 $x=7$이다.

직접증명

직접증명은 조건문 $p\implies q$를 증명하기 위해 명제 $p$와 $q$ 사이에 있는 여러 개의 명제들을 $p$로부터 차례대로 도출해 내어 끝내 $q$가 참임을 이끌어내는 방법이다. 여기서 삼단논법이라는 것이 쓰인다. 삼단논법인즉, $[(p\implies q)\land (q\implies r)]\implies (p\implies r)$을 의미한다. 이를 다시 쓰면, $[(\lnot p\lor q)\land (\lnot q\lor r)]\implies (\lnot p\lor r)$이 되며, 이는 진리표를 통해 증명할 수 있다.

예컨대, $(-1)\times (-1)=1$을 증명하라고 하자. 자연수가 아닌 정수는 자연수에서 자연수를 뺀 값으로 정의되었다고 하고, 정수에서도 자연수에서의 분배 법칙이 동일하게 성립되었다는 것이 증명되었다고 친다면, $(-1)\times (-1)=(1-2)\times (1-2)=1-2-2+4=1$이 되어 증명이 끝난다.

귀류법

명제에서의 귀류법은, 명제를 부정하여 거기서 어떤 결론이 도출되는지를 보고, 그 결론에 모순이 있음을 확인하여 원래 명제가 참임을 증명하는 방법이다. 한편 조건문에서의 귀류법은, 결론만을 부정하여 거기서 어떤 결론이 도출되는지를 보고, 그 결론에 모순이 있음을 확인하여, 원래 조건문이 참임을 증명하는 방법이다.

귀류법의 대표적인 예는, 제곱근 2가 무리수냐는 것이다. ${\sqrt {2}}$가 유리수라면, 유리수의 정의에 따라 정수 $a$를 0이 아닌 정수 $b$로 나눈 값인 ${a \over b}$으로 쓸 수 있을 것이다. (여기서 두 정수는 서로소이다.) ${\sqrt {2}}={a \over b}$가 참이면, 양변을 제곱한 $2={a^{2} \over b^{2}}$도 참이고, 여기서 분모를 이항한 $2b^{2}=a^{2}$도 참이 되는데, 좌변은 짝수이므로 우변도 짝수여야 한다. 그래서 $a$를 2의 배수로 하면 다시 식의 우변은 4배수가 되고 $b$도 다시 2의 배수가 되어야 하는데, 이는 $a$, $b$가 서로소라는 조건에 모순된다. 따라서 제곱근 2는 유리수가 아니며, 무리수이다.

대우법

원래 조건문의 진릿값은 대우의 진릿값과 같음을 이용하여, 대우의 진릿값을 찾아낸 뒤 원래 조건문의 진릿값을 알아내는 방법이다. 노가다법으로 증명하기엔 경우의 수가 무한한 경우에 주로 사용한다. 달리 말하자면, 반례 하나만 찾으면 되는 문제에서 공연히 대우법을 쓰기에는 증명할 게 무한히 튀어나올 수 있다는 말이다.

예컨대, 두 자연수 $a$, $b$에 대해 $ab$가 홀수일 때, $a$와 $b$도 모두 홀수라는 것을 증명할 때에는 이것의 대우인 $a$와 $b$ 중 적어도 하나가 짝수일 때, $ab$가 짝수이라는 것을 증명하면 되는 것이다.

수학적 귀납법

어떤 자연수 $k$에 대해 명제 $p(k)$가 성립함을 직접증명으로 구한 뒤, $p(n)$이 참일 때 $p(n+1)$도 참이라는 것을 증명하여, $k$ 이상의 모든 자연수에 대해 명제 $p(n)$이 성립함을 구하는 방법이다. 주로, 어떤 법칙이 모든 자연수에 대해 성립함을 보일 때나, 수열의 일반항을 구할 때 쓰인다. 이에 대한 예시는 수의 체계나 수열에서 나올 것이다.

수의 체계

수의 체계를 설명하는 이유는 논증과도 약간의 연관이 있어서이다. 수학자들이 무언가에 대해 실수 전체에 대해 성립함을 증명하고자 할 때에는 일단 자연수에서 성립함을 먼저 증명한다. (물론 까다로운 문제라면 특정한 자연수들부터 증명한다.) 그 다음은 정수, 유리수, 실수 순으로 증명하기 때문이다. 그렇기 위해서는 각각의 정의와 성질을 알고 적소에 사용할 수 있어야 한다.

자연수

모든 자연수는 1과 그 합으로 나타낼 수 있다. 그리고 우리는 그 자연수의 전체집합을 $\mathbb {N}$이라 쓴다. 이는 영어로 자연수를 의미하는 Natural number에서 따온 것이다. 그러나 이것이 그동안의 직관적인 관념이었다면, 20세기에 들어서면서 자연수를 잘 정의하려는 시도가 이루어지게 된다. 그 중 하나가 페아노 공리계(Peano axioms)다. 이는 다섯 개의 공리(Axiom)로 이루어져 있고, 각 공리는 아래와 같다.

1. 1은 자연수다.
2. 자연수에 속하는 임의의 원소 $n$에 대해 $n$의 다음 수(Successor) $n^{+}$도 자연수이다.
3. 1은 어떤 자연수의 다음 수도 아니다.
4. 1이 아닌 자연수를 다음 수로 갖는 자연수는 유일하다.
5. 자연수의 부분집합 $S$에 대해 1이 $S$의 원소이고, $S$에 속하는 임의의 원소 $n$에 대해 $n^{+}$도 $S$의 원소라면, $S$는 자연수 집합과 같은 집합이다.

한편, 집합을 통한 정의도 있다. 이에 따르면, 0은 공집합의 원소의 개수이고, 0을 포함하는 자연수는 $n^{+}=n\cup \{n\}$으로 정의된다.

자연수에서 덧셈과 곱셈의 정의

덧셈은 아래와 같이 정의된다.

1. $n^{+}=n+1$
2. $m+n^{+}=(m+n)^{+}$

곱셈은 아래와 같이 정의된다.

1. $n\times 1=n$
2. $m\times n^{+}=m\times n+m$

이에 따라 자연수에서의 결합법칙, 분배법칙, 교환법칙은 아래와 같이 증명된다. 그러나 고등학생 입장에서는 그냥 그렇구나 하고 넘어가면 된다.

수학과의 비애

• 덧셈의 결합법칙
  1. $\forall a,b\in \mathbb {N} ,(a+b)+1=(a+b)^{+}=a+b^{+}=a+(b+1)$ (덧셈의 정의)
  2. $c\in \mathbb {N} ,(a+b)+c=a+(b+c)$일 때, $(a+b)+c^{+}=a+(b+c^{+})$ 증명하기 (수학적 귀납법)
     1. $(a+b)+c^{+}=((a+b)+c)^{+}$ (덧셈의 정의)
     2. $((a+b)+c)^{+}=(a+(b+c))^{+}$ ($\because (a+b)+c=a+(b+c)$)
     3. $(a+(b+c))^{+}=a+(b+c)^{+}=a+(b+c^{+})$ (덧셈의 정의)
  3. $\therefore \forall a,b,c\in \mathbb {N} ,(a+b)+c=a+(b+c)$
• 분배법칙
  1. $\forall a,b\in \mathbb {N} ,a(b^{+})=a(b+1)=ab+a$ (곱셈의 정의)
  2. $c\in \mathbb {N} ,a(b+c)=ab+ac$일 때, $a(b+c^{+})=ab+a(c^{+})$ 증명하기 (수학적 귀납법)
     1. $a(b+c^{+})=a((b+c)^{+})=a((b+c)+1)$ (덧셈의 정의)
     2. $a((b+c)+1)=(ab+ac)+a$ ($\because b+c\in \mathbb {N}$)
     3. $(ab+ac)+a=ab+(ac+a)$ (덧셈의 결합법칙)
     4. $ab+(ac+a)=ab+a(c+1)=ab+a(c^{+})$ (곱셈의 정의)
  3. $\therefore \forall a,b,c\in \mathbb {N} ,a(b+c)=ab+ac$
• 곱셈의 결합법칙
  1. $\forall a,b\in \mathbb {N} ,(ab)\cdot 1=ab=a(b\cdot 1)$ (곱셈의 정의)
  2. $c\in \mathbb {N} ,(ab)c=a(bc)$일 때, $(ab)(c^{+})=a(b(c^{+}))$ 증명하기 (수학적 귀납법)
     1. $(ab)(c^{+})=(ab)c+ab$ (곱셈의 정의)
     2. $(ab)c+ab=a(bc)+a(b)$ ($\because (ab)c=a(bc)$)
     3. $a(bc)+a(b)=a(bc+b)$ (분배법칙)
     4. $a(bc+b)=a(b(c^{+}))$ (곱셈의 정의)
  3. $\therefore \forall a,b,c\in \mathbb {N} ,(ab)c=a(bc)$
• 덧셈의 교환법칙
  1. $1+1=1+1$
  2. $a\in \mathbb {N} ,a+1=1+a$일 때, $a^{+}+1=1+a^{+}$ 증명하기 (수학적 귀납법)
     1. $a^{+}+1=(a^{+})^{+}=(a+1)^{+}$ (덧셈의 정의)
     2. $(a+1)^{+}=(1+a)^{+}$ ($\because a+1=1+a$)
     3. $(1+a)^{+}=1+a^{+}$ (덧셈의 정의)
  3. $\therefore \forall a\in \mathbb {N} ,a+1=1+a$
  4. $b\in \mathbb {N} ,a+b=b+a$일 때, $a+b^{+}=b^{+}+a$ 증명하기 (수학적 귀납법)
     1. $a+b^{+}=(a+b)^{+}$ (덧셈의 정의)
     2. $(a+b)^{+}=(b+a)^{+}$ ($\because a+b=b+a$)
     3. $(b+a)^{+}=(b+a)+1$ (덧셈의 정의)
     4. $(b+a)+1=b+(a+1)$ (덧셈의 결합법칙)
     5. $b+(a+1)=b+(1+a)$ ($\because a+1=1+a$)
     6. $b+(1+a)=(b+1)+a$ (덧셈의 결합법칙)
     7. $(b+1)+a=b^{+}+a$ (덧셈의 정의)
  5. $\therefore \forall a,b\in \mathbb {N} ,a+b=b+a$
• 곱셈의 교환법칙
  1. $1\cdot 1=1\cdot 1$
  2. $a\in \mathbb {N} ,a\cdot 1=1\cdot a$일 때, $a^{+}\cdot 1=1\cdot a^{+}$ 증명하기 (수학적 귀납법)
     1. $a^{+}\cdot 1=a^{+}$ (곱셈의 정의)
     2. $a^{+}=a+1$ (덧셈의 정의)
     3. $a+1=1\cdot (a+1)$ (분배법칙)
     4. $1\cdot (a+1)=1\cdot a^{+}$ (덧셈의 정의)
  3. $\therefore \forall a\in \mathbb {N} ,a\cdot 1=1\cdot a$
  4. $b\in \mathbb {N} ,ab=ba$일 때, $a(b^{+})=(b^{+})a$ 증명하기 (수학적 귀납법)
     1. $a\cdot b^{+}=a(b+1)$ (덧셈의 정의)
     2. $a(b+1)=ab+a$ (분배법칙)
     3. $ab+a=ba+a$ ($\because ab=ba$)
     4. $ba+a=(b+1)a$ (분배법칙)
     5. $(b+1)a=(b^{+})a$ (덧셈의 정의)
  5. $\therefore \forall a,b\in \mathbb {N} ,ab=ba$

대신에 1+1=2 쯤이야 쉽게 증명할 수 있다. 왜냐하면 2는 $1^{+}$로 정의된 수기 때문이다. 덧셈의 정의에 따라 $1^{+}=1+1$이므로, 1+1=2다.

정수

정수의 전체집합은 독일어로 수를 의미하는 Zahl에서 따온 $\mathbb {Z}$를 쓴다. 그나저나 일단, 0이란 무엇일까? 앞서 말했듯이 공집합의 원소의 개수라고 할 수도 있지마는, 여기서는 일관성 있게, $0^{+}=1$을 만족하는 수라고 하자. 0과 관련하여 다음이 만족된다.

1. $n\cdot 0=0$
2. $n+0=n$

그리고 $n\in \mathbb {N} ,n+m=0$을 만족하는 $m(=-n)$의 집합을 음의 정수라고 한다. 이로써 뺄셈도 덧셈으로 표현하는 식으로 정의할 수 있다. 예컨대, $\forall a,b\in \mathbb {Z} ,a-b=a+(-b)$라고 하는 식으로 말이다.

정수에서도 자연수에서와 마찬가지로 교환법칙, 분배법칙, 결합법칙이 성립한다. 그런 의미에서, $(-1)\cdot (-1)=1$은 $(0-1)\cdot (0-1)=0-0-0+1=1$로 증명할 수 있다. 다만 뺄셈은 교환법칙이나 결합법칙이 성립하지 않는다. 이는 초등학교/중학교에서 배워 이미 잘 알고 있는 것이다.

유리수

열다섯을 셋으로 똑같이 나눠 묶어 봐.라고 한다면야 당연히 한 묶음에 다섯이 있을 것이다. 그러나 '열다섯'이 아닌 '열넷'이나 '열여섯'이라면? 이런 정수는 존재하지 않는다. 그래서 인류는 굉장히 일찍 유리수를 사용하였다. 과거에는 제 몫을 공평하게 나눠 갖는 것이 중요했기 때문이다. 한편으로는 비율을 구할 때에도 유리수를 사용한다. 그런 의미에서 유리수의 전체 집합은 이탈리아어로 비율을 의미하는 Quoziente에서 유래된 $\mathbb {Q}$를 사용한다.

우선, 단위 분수부터 정의하자.

• $a\in \mathbb {Z} -\{0\},{1 \over a}$이란 $a$를 곱했을 때 1이 되는 수를 의미한다. 이때 $a$는 절대로 0이어서는 안 된다.

그리고 이를 일반화하면 유리수 ${p \over q}(p,q\in \mathbb {Z} ,q\not =0)$는 $q$를 곱해서 $p$가 되는 수를 말한다. 나눗셈은 이렇게 유도되었다.

앞서, 나누는 수가 0이 되어서는 안 된다고 했는데, 이를 꾸역꾸역 기어코 어기고 그 값의 존재성을 가정하여 계산을 하면 아래와 같은 결과가 나와야 할 것이다. 그러나 이는 일부일 뿐이다.

1. ${1 \over 0}\cdot 0=1$이면서, ${1 \over 0}\cdot 0=0$을 동시에 만족한다.
2. ${1 \over 0}={1 \over {0 \over -1}}={-1 \over 0}$. 자기 자신이 자기 자신의 음수가 된다.

'1이면서 0을 동시에 만족할 수 있는가'는 다시 말해서 '1=0'을 증명하는 것이 되고, 1은 $0^{+}$이므로 다시 $0^{+}=0$을 증명하는 게 된다. 그러나 페아노 공리계에서 자연수의 범위에 0이 포함되도록 수정하면, 3번 공리는 0은 어떤 자연수의 다음 수도 아니다.가 된다. 그러므로 이 공리에 따라 $0^{+}=0$가 거짓임을 알 수 있다. 귀류법에 따라 0으로 나눈 수는 존재한다는 것은 모순이며, 0으로 나눈 수는 존재하지 않는다는 것이 참인 게 증명되었다. 그리하여 수학자들은 일찍이 0으로 나누기의 끔찍함을 (단 하나의 모순을 모른 체 했을 뿐임에도 모든 것이 참으로 귀결될 수 있다는 엄청난 끔찍함을) 깨닫고, 이들은 사람들에게 0으로 나누지 말 것을 설교하고 다녀야만 했던 것이다.

실수

함수

개론

우리는 분명 초등학교에서부터 함수라는 것을 여러가지 방법으로 배웠다. 초등학교에서는 수를 상자에 집어넣으니 다른 수가 나왔다든가 하는 식으로 말이다. 그런데 잘 생각해 보면, 하나의 값을 넣으면 꼭 하나의 값만 나온다. 이것이 함수의 기본이다. 함수에 넣을 수 있는 값들을 모조리 넣어도 그 어느 것도 둘 이상을 출력하거나 아무 것도 출력하지 않는 경우가 없다. 정리하자면 이렇다.

함수 $y=f(x)$에 대해 모든 $x$는, 자신의 짝으로서 유일한 $y$를 갖는다.

정의역, 공역, 치역

한편, 중학교에서는 수식을 문자로써 표현하거나 $y={1 \over x}(x\not =0)$이라는 함수를 배우고 그 그래프도 그리는 등 많은 것을 배우기 시작하였다. 그런데, 우리가 배웠던 것 가운데 $y={1 \over x}(x\not =0)$는 조금 독특한 함수다. 우리가 중학교에서 배웠던 다른 함수와는 다르게 $(x\not =0)$라는 단서가 달려 있다. 그리고 우리는 그 이유가, 0으로 나눌 수 없기 때문이라는 것을 잘 알고 있다. 즉, 모든 함수에는 적절한 값만이 입력될 수 있다는 것이다.

우리는 함수에 입력될 수 있는 값들의 집합을 정의역(Domain)이라 한다. 특별한 언급이 없는 한, 보통 함수의 정의역은 실수 전체($\mathbb {R}$)로 여겨진다. 또한 함숫값이 될 수 있는 값들의 집합은 공역(Codomain)이라 하며, '실제 함숫값'들의 집합은 특히 치역(Range)이라 한다. 치역은 공역의 부분집합이며, 공역 또한 특별한 언급이 없는 한, 실수 전체($\mathbb {R}$)로 여겨진다. 그래서 $y={1 \over x}(x\not =0)$, $y={\sqrt {x}}(x\geq 0)$ 같은 함수엔 $(x\not =0)$, $(x\geq 0)$ 같은 단서가 필요한 것이다.

다시 정리하자면 이렇다. 우리는 앞으로 이 단원에서 함수를 정의하기 전에 입출력값의 범위를 먼저 지정할 것이다. 함수의 입출력값의 범위를 지정하는 방법은 아래와 같다.

$f:A\to B$ ($A$에서 $B$로의 함수 $f$)

여기서 $f$는 함수의 이름을 의미하며, $A$는 입력될 수 있는 값의 범위, $B$는 출력될 수 있는 값의 범위이다. 그리고 여기서 우리는 다시 $A$를 정의역, $B$를 공역이라 한다. 고로, 우리가 보통 쓰는 함수들은 대개 아래와 같다.

$f:\mathbb {R} \to \mathbb {R}$

이것이 실수에서 실수로의 함수를 의미하는 수학적 문장이다.

이번에는 공역과 치역에 대해서 자세히 알아보자. 아래와 같은 함수가 있다.

$f:\mathbb {N} \to \mathbb {N}$, $f(x)=x^{2}$

보다시피 정의역과 공역 모두 자연수 전체($\mathbb {N}$)이다. 그런데 함수는 입력값의 제곱을 함숫값으로 출력하게 되어 있다. 즉, 1을 입력하면 1이 출력되고, 2를 입력하면 4가 출력되며, 3을 입력하면 9가 출력된다. 다시 말해서, 실제 함숫값들은 1, 4, 9 등이며, 여기에는 공역에 있는 2, 3, 5, 6 등의 자연수가 포함되지 않는다. 이렇게 실제 함숫값들만 따로 모아놓은 집합을 치역이라고 한다. 치역은 공역보다 작거나 같다.

일대일 함수

일대일 함수, 또는 단사 함수(Injective function)는 함숫값이 서로 겹치지 않는 함수를 의미한다. 앞서 썼던 $f:\mathbb {N} \to \mathbb {N}$, $f(x)=x^{2}$의 경우를 보자. 함숫값이 1이 되는 $x$ 값은 1 뿐이고, 함숫값이 4가 되는 $x$ 값은 2 뿐이며, 함숫값이 9이 되는 $x$ 값은 3 뿐이다. 이렇게 그 어떤 함숫값도 둘 이상의 입력값과 양다리를 걸치지 않는다. 우리는 이를 일대일 함수, 또는 단사 함수라 하며, 수학적으로는 아래와 같이 설명된다.

원래의 정의

$f:A\to B,\ \forall x_{1},x_{2}\in A,\ f(x_{1})=f(x_{2})\implies x_{1}=x_{2}$

---

대우를 취한 정의

$f:A\to B,\ \forall x_{1},x_{2}\in A,\ x_{1}\not =x_{2}\implies f(x_{1})\not =f(x_{2})$

$f:A\to B,\ \not \exists x_{1},x_{2}\in A,\ x_{1}\not =x_{2}\implies f(x_{1})=f(x_{2})$

공역 위로의 함수

공역 위로의 함수, 또는 전사 함수(Surjective function)는 현재 교육과정에서는 사라진 말이다. 만약 어떤 함수의 공역과 치역이 일치하다면, 이를 '공역 위로의 함수'라 한다. 즉, $f:A\to B$가 전사 함수면 이를 $A$에서 $B$ 위로의 함수 $f$라 한다. 수학적으로는 아래와 같이 설명된다.

원래의 정의

$f:A\to B,\ \forall y\in B,\ \exists x\in A,\ y=f(x)$

---

대우를 취한 정의

$f:A\to B,\ \not \exists y\in B,\forall x\in A,y\not =f(x)$

일대일 대응

일대일 대응, 또는 전단사 함수(Bijective function)는 일대일 함수이면서 공역 위로의 함수인 함수를 의미한다. 즉, 공역과 치역이 일치하고 그 어떤 함숫값도 서로 겹치지 않는 함수이다. 만약 정의역과 공역 관계에 있는 두 집합 사이에 일대일 대응이 가능하다면, 우리는 이 두 집합의 크기를 같다고 말한다. (고급수학 참고)

여러 가지 함수들

1. 상수함수: 치역의 원소가 단 하나 뿐인 함수다. ($C_{b}:A\to B,\ C_{b}(x)=b\in B,\ \forall x\in A$)
2. 포함함수: 정의역과 치역이 일치하며, 입력값을 그대로 함숫값으로 출력하는 함수다. ($A\subset B,\iota _{A,B}:A\to B,\ \iota _{A,B}(x)=x,\ \forall x\in A$)
   • 항등함수: 정의역과 공역과 치역이 서로 일치하며, 입력값을 그대로 함숫값으로 출력하는 함수다. ($id_{A}:A\to A,\ id_{A}(x)=x,\ \forall x\in A$)
3. 특성함수: 공역에는 0과 1만이 속해 있으며, 입력값 $x$가 어느 집합 $A$의 원소면 1, 아니면 0을 반환한다. $\left(\mathbb {1} _{A}(x)={\begin{cases}1,&x\in A\\0,&x\not \in A\end{cases}}\right)$

합성함수

함수의 합성은, 두 함수 중 하나의 공역과 다른 하나의 정의역이 같을 때, 이 둘을 또 하나의 새로운 함수로 만들어 연산하는 것이다. 아래 상자를 보자.

$f:A\to B,\ g:B\to C$
$\implies g\circ f:A\to C$

---

$y=f(x),\ z=g(y)$
$\implies z=(g\circ f)(x)$

위에서 보다시피, 합성함수는 고리점을 이용해 연산되며 연산 순서는 뒤에서부터 앞으로, 즉 역순으로 계산한다. 이를 다시 쓰면 다음과 같다.

$y=(g\circ f)(x)\iff y=g\left(f\left(x\right)\right)$

또한 셋 이상의 경우라도 각각의 공역과 정의역을 줄줄이 소시지마냥 선형적으로 이어붙일 수 있다면 여러 함수를 동시에 합성하는 것도 가능하며, 결합 법칙도 성립한다.

$f:A\to B,\ g:B\to C,\ h:C\to D$
$\implies h\circ (g\circ f)=(h\circ g)\circ f:A\to D$
$\iff \forall x\in A,\ \exists y\in D,y=h(g(f(x)))$

($y$는 유일하게 존재함.)

역함수

역함수란 한 함수의 정의역과 공역을 맞바꾸되 서로 관계를 유지시키면서 얻어지는 함수이다. 물론 이 과정에서 역함수의 정의역에서 어떤 원소가 공역의 원소 둘 이상이랑 문어다리를 걸치는 일도 발생하게 되는데, 일단은 이를 '다가함수'라고는 하지만 우리는 현재 이에 대해 다루지는 않을 것이다. 보통 이런 경우가 있다면 함수의 정의에 맞도록 정의역의 범위를 축소시키는 것이 일반적이다.

임의의 함수 $f$에 대해 그 역함수는 $f^{-1}$으로 쓰고 '$f$(의) 역함수' 또는 '$f$ inverse'라고 부른다. 그리고 $f:A\to B$일 때, $f^{-1}:B\to A$이며, 또한 $y=f(x)$일 때, $x=f^{-1}(y)$가 성립한다. 그리고 역함수는 원래 함수의 종류에 따라 셋으로 구분지을 수 있다.

1. 왼쪽 역함수

$f:A\to B$에 대해 $f^{-1}\circ f=id_{A}$를 만족시키는 역함수. 역함수가 고리점의 왼쪽에 있어, 왼쪽 역함수(Left inverse)라 한다.

예컨대, $f:\mathbb {N} \to \mathbb {N} ,\ f(x)=x^{2}$이라 할 때, 그 역함수는 자연수 $x$에 대해 $f^{-1}(x^{2})=x$이기만 한다면 $f^{-1}\circ f=id_{\mathbb {N} }$가 성립된다. 다시 말해서, $f^{-1}(1)$은 1이어야 하고, $f^{-1}(4)$는 2여야 하지만, $f^{-1}(2)$의 함숫값이 무엇인지는 그 누구도 알 바가 아니라는 것이다.

이렇듯, 왼쪽 역함수가 존재하기 위해선, 원래 함수는 일대일 함수가 되어야 한다.

2. 오른쪽 역함수

$f:A\to B$에 대해 $f\circ f^{-1}=id_{B}$를 만족시키는 역함수. 역함수가 고리점의 오른쪽에 있어, 오른쪽 역함수(Right inverse)라 한다.

예컨대, $f:\mathbb {R} \to \mathbb {Z} ,\ f(x)=a,a\in \mathbb {Z} ,0\leq x-a<1$이라 할 때, 그 역함수는 정수 $a$에 대해 $f^{-1}(a)=a$이기만 한다면 $f\circ f^{-1}=id_{\mathbb {Z} }$가 성립된다. 다시 말해서, $f^{-1}(1)$은 1이어야 하고, $f^{-1}(2)$는 2여야 위와 같이 합성했을 때 항등함수가 나오지만, $f^{-1}(1.5)$같은 건 1.5가 역함수의 정의역에 속하지 않으니 논외라는 것이다.

이렇듯, 오른쪽 역함수가 존재하기 위해선, 원래 함수는 공역 위로의 함수가 되어야 한다.

3. 일대일 대응의 역함수

어느 함수의 역함수가 왼쪽 역함수이면서 오른쪽 역함수이면 이 함수는 일대일 대응과 동치다.

진법과 그 변환

개요

2 이상의 자연수 $n$에 대해 $n$진법은 $n$개의 숫자로 수를 표기하는 방법을 뜻한다. 이렇게 표기된 수는 $n$진수라 한다. 우리가 통상 쓰는 것은 10진법이지만, 공학 계열에서는 2진법과 16진법도 사용한다. 그리고 몇 진법을 썼는지는 수의 오른쪽 아래에 작은 글씨와 괄호로 $n$을 써 준다. 예컨대, $n$진법은 아래 숫자들로 구성되어 있다.

• $d_{1}=0$
• $d_{2}=1$
• $d_{3}=2$

$\cdots$

• $d_{n}=(n-1)$

그리고 $n$진수 $a_{1}a_{2}a_{3}\cdots a_{m}(a_{1},a_{2},a_{3}\cdots a_{m}\in \left\{d_{1},d_{2},d_{3},\cdots ,d_{n}\right\})$의 계산은 $a_{1}\cdot n^{m-1}+a_{2}\cdot n^{m-2}+a_{3}\cdot n^{m-3}+\cdots +a_{m}\cdot n^{0}$으로 된다. 물론 음수여도 이렇게 계산하는 것이 가능하고, 소수점이 있더라도 $a_{m}\cdot n^{-1}$ 같은 식으로 하면 되므로 문제 없다. 한편, 어떤 $n$진법 수가 소수점 이하에서 특정 지점에서부터 $n-1$라는 숫자가 무한히 반복된다면 이 수는 다른 방법으로 표기할 수 있는데, 이것이 우리가 중학교에서 짚고 넘어갔던 '0.999…=1'에 관한 것이다. 이에 관한 증명 또한 중학교에서 배웠을 것이지만 이산수학 3단원의 소단원인 〈수열의 극한과 급수〉에서 다시 배우게 될 것이다.

2진수와 10진수의 변환

2진수와 16진수의 변환

10진수와 16진수의 변환

경우의 수

합의 법칙, 곱의 법칙

계승, 조합, 순열

중복조합, 중복순열

수열

등차수열

등비수열

점화식

수열의 극한과 급수

주석