induction

 

교재에 'use induction'이라고 나와있길래, 이상한 걸 생각하고 한참을 헤맸다.

 

보통 induction을 떠올릴 때 inductive assumption P(n)을 전제하고, P(i) where i initial symbol, P(n+1)을 증명하면 P(n)이 모든 자연수에 대해서 성립한다는 것이 생각난다.

 

근데 FOL에 대해서 induction을 건다고 생각하면, 이게 뭔 소리지? 하게 된다. induction 개념을 확장해서 generalized assumption을 가정하고, 미리 존재하는 operations에 대해 assumption이 closed되었는가를 보이는 게 induction이라고 생각하는 게 편하다.

 

형식논리에서 몇 가지 수학적 개념들이 변형되서 사용되는 경우를 보는데, 이 경우 유념해야겠다.