1. 증명과 명제, 공리 (Proof, Proposition and Axioms)

증명^Proof은 어떠한 것이 참/거짓임을 밝히는 것을 의미한다. 증명의 예시는 다음과 같다.

• 관측과 실험: 물체가 지구로 떨어진다. -> 중력이 존재한다.
• 반대 사례 찾기: A씨는 개를 싫어한다. -> "모든 사람이 개를 좋아한다."는 거짓이다.
• 판결: 법에 따라, 살인은 죄이다. -> 법이라는 기준에 따라 판결

특히, 수학적 증명은 공리^axiom들에 기반한 논리적 추론^{logical deduction}을 통해, 어떠한 명제^proposition를 증명하는 것을 의미한다.

명제^Proposition

명제는 참이나 거짓이 분명한 문장을 말한다.

• $2+3=5$
• $5-2\neq 5$
• 백지오는 2020년 기준, 21살이다.
• $\forall n \in \mathbb{N} , n^2 + n + 41 \text{ is a prime number.}$

술어^Predicate

술어는 참/거짓이 변수에 의해 바뀌는 명제를 말한다.

오일러의 거듭제곱의 합 추측^{Euler's Conjecture}이 유명한데, 오일러는 아래 식의 양의 자연수 해가 존재하지 않는다고 추측했다.

$$ a^4 + b^4 + c^4 = d^4 $$

이 추측을 식으로 나타내면 아래와 같다.

$$ \nexists a,b,c,d \in \mathbb{N} ^+ , a^4 + b^4 + c^4 = d^4 $$

그러나, 위 식은 $a=95800, b=217519, c=414560, d=432481$에서 성립하므로 위 명제는 거짓이다. 위 명제는 변수에 따라 일부 성립하는 술어이다.

$$ \exists a,b,c,d \in \mathbb{N} ^+ , a^4 + b^4 + c^4 = d^4 $$

함축^Implication

"$p$이면 $q$이다.", "$p$는 $q$를 함축한다.", "$p$는 $q$의 충분조건이다."와 같이, 두 사건의 인과관계가 연관된 경우를 함축이라 하고, $\Rightarrow$ 기호로 나타내고, 조건명제라 부른다.

함축 $p\Rightarrow q$은 p가 거짓이거나 q가 참일때 참이다.

$p$	$q$	$p \Rightarrow q$
T	T	T
T	F	F
F	T	T
F	F	T

쌍방조건명제^{Biconditional}

명제 $p$와 $q$가 서로 동시에 조건이며 명제인 경우에는 쌍방조건명제라 부른다. 이때, $p$와 $q$는 서로를 필요충분조건으로 갖는다.

$p$	$q$	$p \Rightarrow q$ (충분조건)	$q \Leftarrow p$ (필요조건)	$p \Leftrightarrow q$ (필요충분조건)
T	T	T	T	T
T	F	F	T	F
F	T	T	F	F
F	F	T	T	T

공리^Axioms

공리는 참으로 추측되는 명제이다. 명제를 증명하기 위한 근거 중, 가장 기본이 되는 진리와 같은 명제를 공리라 한다. 예를들어, $a=b, b=c \Rightarrow a=c$는 공리이다.

공리계는 일관성^Consistent 혹은 완결성^Complete을 가져야한다. 

일관성은 증명할 수 없지만 확연한 진리를 의미하고($a=b \Rightarrow a+c=b+c$), 완결성은 공리계의 모든 명제가 참/거짓으로 증명될 수 있는 경우를 의미한다.

한 명제가 일관성과 완결성을 모두 가질 수는 없으므로, 수학적으로 증명할 수 없는 명제가 존재할 수밖에 없다.(괴델의 불완전성 정리)