수학적 증명 방법 공부 - 3

5 Predicate Logic / 술어 논리
진술과 추론 규칙을 추가해서 확장한 명제 논리를 술어 논리라고 한다. 

5.1 Quantifiers
정의. 
기호 ∀은 "모두를 위해", "모두를 위해" 또는 "각자를 위해"라고 불립니다. 
기호 ∃은 "어떤 것을 위해" 또는 "존재합니다"라고 불립니다. 

5.2 Statements / 명제
정의. x가 임의의 변수이고 W가 x와 같은 유형의 식에 적용될 때 문에 평가되는 람다 식인 경우, (∀x, W(x))와 (∃x, W(x))는 모두 명제입니다. 

5.3 Declarations / 선언
1. 변수(변수 선언) 로 선언 
2. 상수(상수 선언) 로 선언 
3. 임시적인 새로운 표기법으로 정의 
4. 증명 시작 전에 주어진 전제 또는 전역적으로 선언된 전제에서 정리의 진술 

5.4 Rules of Inference / 추론규칙
The rules of inference for these two quantifiers are as follows.

∀+ (Let s be arbitrary ⊢ W(s)) ⊢ (∀x, W(x))
∀− (∀x, W(x)) ⊢ W(t) 
∃+ W(t) ⊢ (∃x, W(x)) 
∃− (∃x, W(x)) ⊢ For some constant c, W(c)

5.5 Equality / 동일성
등식/동일성 
- 반사성 
- A = B <-> B = A
- 대체성
- A = B -> A+B = A + A = 2A

 

증명에서 전체에 대한 증명에서 많이 사용하는 For all (∀) 과 임의의 존재하는(∃) 에 대한 내용들이 나온다. 어떤 증명에서 해당하는 대상전체에 대한 증명어서는 "모든 x에 대해서" 라고 하고, 반례를 이용하여 증명하는 경우에 임의로 존재한다고 가정하는 "임의의 x"에 대해서라고 전개하는 경우에 사용된다. 소수의 무한성에 대한 유클리드의 증명에서 이것들을 생각할 수 있다.

 

소수(prime number)가 유한하다면, ∀ P_i 를 생각할 수 있고, 그 모든 수들을 곱하고 +1 을 하면 특정한 P를 만들수 있다. ∃P는 소수가 아니기 때문에, 1 과 자기 자신을 제외한 약수를 가져아 하지만, 모든 ∀ P_i 에 대해서 나누면 항상 1이 남기때문에 약수로 가질 수 없다. 그러므로, 처음 가정했던 유한성에 오류가 있고, 무한성이 증명되었다.

 

대략 이런 형태로 생각할 수 있겠다.