Math Logic Intro2

수리논리의 세계 로 돌아가기

수리논리란? - 수리논리의 발전

• 사람은 누구나 생각한다. 숨쉬기나 걸음도 그렇다. 배우지 않아도 다 알아서 한다. 여기에도 더 잘 숨쉬고 더 잘 걷기 기술같은 것을 연구하는 사람들이 있긴 하다. 물론 모든 사람들이 그것을 배우지도 않으면서 제 나름대로 잘 쉬고 잘 걷는다. '논리학'은 '사고(思考)의 법칙' 또는 '사고하는 법칙'을 뜻했다. 목표는 ' 어떻게 하면 사고를 효율적이고 실수 없이 하느냐' 였다. 더 잘 숨쉬기, 더 잘 걷기를 익힌다고 한들 숨쉬기가 항상 고르고 태어나서 죽을 때까지 실수 없이 걸을 수 있을까? 마찬가지로 논리학을 배운다고 해서 그것이 사고의 실수를 완전히 없앨 수는 없다.

수리논리란

수리논리는 더군다나 '사고의 법칙'을 주 연구 대상으로 하지 않는다. '수학적 논리(mathematical logic)'라고 부르는 이유는 그것이 '수학에 대한 논리' 이고 동시에 '논리에 대한 수학적인 탐구' 이기 때문이다.

• 수학에 대한 논리 :
  • 수학의 기초에서 위기와 연관
  • 수학에서 중요한 개념에 대한 숙고 : 증명, 정리, 정의, 계산(알고리듬)
  • 수학적 문장(정리), 수학적 논리(증명)의 성격을 파악 : 오류을 없애는 문장 표시와 증명에 대해서도 말하고, 증명될 수 있는 문장과 증명될 수 없는 문장에 대해서도 말한다.
• 수학적 탐구
  • 수학에서 보통 하는 방법 : 공리, 정리, 증명의 틀
  • 수학의 다른 영역에서 하는 것과 비슷하게 엄격하게 수학적 방법을 쓰고, 수학적 상상력을 펼쳐 연구를 확대
  • 마치, 기계를 만드는 기계 제작 공장 사람이 보기에는 기계 만드는 것은 매일반인 것과 비슷. 그는 기계 자체를 제작하는 기초를 더 잘알 수 있다. 그러나 이것이 그가 기계 자체를 잘 만든다는 것과는 다르다. 오히려 구체적인 기계를 만드는 것에 대해서는 잘 모를 수 있다.

수리 논리의 진화

수리논리의 발전 역사는 다른 분야와 마찬가지로 질서 정연하게 발전해온 것은 아니다. 개념들이 탄생하고 발전해 간 것을 시간 순서로 하지 않고 나름의 논리로 꿰어 보면 이렇게 설명할 수 있다.

불(Boole) : 명제 논리 : 100 여년전

일상에서 쓰는 말들, 논리로부터 문장들을 연결하는 논리적 접속사들을 뽑아내어 이것들의 성질 연구. 정리하면

우리말 표현	영어 표현	기호표현
A 그리고 B , A 이고 B	A and B ,not only A, but B	$A\And B,\ A\land B,\ A\cdot B$
A 또는 B , A 나 B	A or B , either A or B	$A\lor B,A+B$
A 이면, B 이다. 그래서	if ~ then , hence,	$A\rightarrow B,\ A\Rightarrow B,\ A\subset B$
A 가 아니다	not A	$\neg A,\sim A,{\bar {A}}$
A 는 B 와 등가다.	A is logically equivalent to B , if and only ,iff	$A\leftrightarrow B,\ A\Leftrightarrow B$

페아노 산술 (Peano's Arithmetic): 100 여년 전

자연수 세계의 기초를 탐구. 가장 기초적인 대상들로

$0,1,+,\times ,=$

로 보고 이것들의 가장 기초적인 성질인 공리들을 제시하였다. 이로써

" 둘 더하기 셋은 다섯" 은 (1+1)+((1+1)+1) = ((((1+1)+1)+1)+1 로 쓰게 된 것이다.

아리스토텔레스 : '모든'과 '어떤'의 논리 : 2300 여년 전

아리스토텔레스가 이미 분석하여 정립한 단어. '모든 ...'과 '어떤..'

아침에 일찍 일어나는 사람은 건강하다.

비록 '모든'도 '어떤'도 없는 듯 보이지만 이런 문장을 읽을 때는 보통 "아침에 일어나는 모든 사람은 건강하다." 로 이해한다. 또는 더 형식논리나 수학적인 문장을 쓸 때의 습관에 끼워 맞추면, "모든 x 에 대해, x 가 아침에 일찍 일어가면 x 는 건강하다" 로 바꿀 수 있다. 본질적인 뜻은 변함이 없다. 모든을 기호로는 $\forall$ 을 쓰기로 하자. 그리고 'x 가 아침에 일어나다.' 를 'p(x)', 'x 는 건강하다.' 를 'q(x)' 로 쓰자. 이제 문장 전체를 기호로 바꿀 수 있다.

$\forall x\ (p(x)\rightarrow q(x))$

그렇다면 위 문장이 참이 아니라고 할 경우는 어떤 경우일까? 어떤 사람이 있어서 아침에 일찍 일어나는데도 건강하지 않은 사람이 있는 경우다. 그 사람이 바로 위의 문장을 부정하는 반례가 된다. '어떤' 을 '$\exists$ '로 보통 쓰기 때문에 위의 문장의 부정을 기호로 바꾸어 쓰면,

$\exists x\ (p(x)\And \neg q(x))$

다. 이것은 명제 논리에 따라 이상할 것 없다. 왜냐하면 아래 두 문장은 고전 명제논리에서 등가다.

$(A\rightarrow B)\ \leftrightarrow \ (\neg A\lor Q)$

$\neg (\neg A\lor Q)\leftrightarrow (A\And \neg Q)$

단지 '모든'을 부정하는 것이 '어떤'이라는 것만 받아들이면 된다. 따라서,

$\neg \ \forall x\ (p(x)\rightarrow q(x))\ \leftrightarrow \ \exists x\ (p(x)\And \neg q(x))$

프레게(Frege) : 변수들이 있는 문장(predicate logic) : 100 여년 전

명제논리로 일상의 문장이나 수학의 문장을 표현하는 것은 한계가 크다. 당장 위의 예도 그렇거니와 아리스토텔레스 시절부터 중요한 논증법의 하나였던 삼단논법도 그 예다.

모든 사람은 죽는다. 소크라테스는 사람이다. (그래서) 소크라테스도 언젠가는 죽기 마련이다.

라는 문장의 논리적 구조만 보도록 하자. 이것들은 모두 참 거짓을 말할 수 있는 단순 명제로, 명제 논리의 세계의 관점에서 보면 서로 독립적인 세 문장이다. 그래서 p, q, r 로 바꿔 표현할 수 밖에 없다. 그러나 잘 들여다보라. 위의 문장들은 모두 서로 연결되어 있다. 무엇으로? 바로 사람이라는 '변수'와 그 중 구체적인 대상인 소크라테스라는 '상수' 개념으로 연결되어 있다. 이를 기호로 옮기기 위해 'x 는 사람이다' 를 p(x), 'x 는 죽는다.’를 q(x)로 한다면,

${\frac {\forall x(p(x)\rightarrow q(x))\ ,\ p(a)}{q(a)}}$

로 나타낼 수 있다. 여기서 변수의 개념을 앞에서 '모든'과 '어떤'으로 '둘러싼다'. 그 모든과 어떤을 quantifier 라 부른다. 다른 예를 하나더. '4 로 나뉜 수는 2 로도 나뉜다.' 라는 산술의 성질을 보자. :

$\forall x\ (p(x)\rightarrow q(x))$

로 옮길 수 있다. 그런데 만약 이때 변수가 여러개가 들어가는 상황이라면? 예를들어, '어떤 두 자연수도, 서로 같거나, 다른 하나가 더 크다.' 라는 자연수 세계의 기초적인 성질을 나타내려 한다면 이때는 두 개의 변수가 필요하다.

$\forall x,y\ (x=y\ \lor \ x<y\ \lor \ y<x)$

로 써야한다. 명제논리에서 시도했던 것처럼 일상생활의 언어나 수학의 언어를 기호의 형태로 바꾸려면 어쩔 수 없이 명제논리의 틀을 벗어나야 한다.

아리스토텔레스가 시도한 모든과 어떤에 이미 그 씨앗이 있긴했지만, 이것을 전면에 드러내어 확실하게 밀어부친 이는 프레게다. 논리의 세계에 '변수' 개념과 'quatifier' 를 도입하면서 논리학의 기호들과 성질로 수학의 기초를 다지려고 했다. 새로운 기호들이 들어가 '잘 만들어진 식'을 술어라고 한다. 새로운 기호가 들어와 언어가 확장되었기 때문에 새로 등장한 기호들에 대하여 그것의 성질이 무엇인지 정해주어야 할 것이고(공리와 법칙), 이런 경우 참-거짓의 해석 같은 문제(모델)들이 수북하게 쌓인다. 그렇게 새 땅을 일군 사람이 프레게인 것이다. 이것을 술어논리(predicate logic) 또는 first order locgic 이라고 한다. 명제논리는 수학의 세계를 드러내기에는 빈곤한 언어를 가지고 있지만, 술어논리는 벌써 수학의 모든 분야를 나타내기 충분한 언어로 되었다. 이제 수학의 기초를 다지기 위한 결정적인 첫 발을 뗀 것이다.

여기서, 잠깐 ! 일반적으로 말하면 변수는 한두개가 아니다. 모든 나라의 알파벳을 다 동원해도 안될 수도 있다. 하지만, 걱정없다. x 를 변수로 하고 새로운 변수가 나올 때 마다 x', x", ... 하는 식으로 ' 를 덧붙여가면 된다. 그런 방식은 사람에겐 낯설고 재미없고 눈에 걸리고 예쁘지도 않아 보여도 기계에게는 문제가 안된다. 되려 더 좋아할지도 모른다. 정리하면, 산술 세계를 나타내기 위해 고작 몇 개의 기호만 있으면 모든 문장을 나타낼 수 있다.

$\And ,\ \lor ,\rightarrow ,\ \neg ,\ +,\ \cdot ,\ 0,\ 1,\ =,\ \forall ,\ \exists ,\ x,\ ',\ (,\ )$

물론 여기에 정확하게 하기 위해 괄호를 넣어야 주어야 한다. 놀라운 것은 이것들도 필요한 것보다는 많다는 것이다. 명제의 참거짓 표에서도 나오지만, 명제 논리의 네 연산은 $\neg$ 가 들어가고 나머지 셋 중 하나만으로 충분히 표현할 수 있다. 마찬가지로 두 개의 quantifier 도 하나로 줄일 수 있다. 예를들어

$\And ,\ \neg ,\ +,\ \cdot ,\ 0,\ 1,\ =,\ ,\ \exists ,\ x,\ ',\ (,\ )$

( 얼마나 더 줄일 수 있을까? 수학식을 나타내기 위해, 최소 기호는 몇 개일까?)

수학 언어로 말하는 기계

수학의 언어를 몇 개의 기호로 충분히 나타낼 수 있다는 생각에서 한 발 더 떼어본다면? 상상해보자 : 최소한의 기호를 입력하면 그것들을 조합해서 출력해주는 기계를. 예를들어 우리말의 자음과 모음을 입력하면 그것들을 계속 조합해내는 기계. 어떤 일이 일어날까? 이 기계는 셀 수도 없이 말도 안되는 기호들을 만들어내기도 하겠지만, 어떤 부분은 우리에게 친숙한 말들도 만들어 낼 수 밖에 없다.

ㄱㅏㅇ,ㄴㅓ , ㄷ먗 , 아라다랸ㅌ , 사, 개ㅐ재, 그 랑 , 추억ㄱㄱ , 그, 달, 여기 오신 , ...

수학 기계도 그럴 것이다. 예를들어

$=(+)=\ ,\ )0+0(\ ,\ \And \cdot \And \ ,\ \neg \cdot \ ,\ \exists \And =)\cdot ($

처럼 이해안되는 기호나열도 있겠지만,

$1+1=0\ ,\ 1\cdot 0=0\ ,\ x\cdot x=x''\ ,\ ((1+1)+1)+0=(1+1)+1\ ,\ \neg \exists x\neg (x+x'=x'+x)$

와 같이 참과 거짓을 말해볼 수 있는 기호들도 나올 것이다. 기계가 작동하기 위해 미리 규칙을 정해주면 훨씬 이해하기 좋은 말들이 나온다. (아가들의 낚서와 비교해 보라.) 예를들어 "변수나 상수, 같은 방향의 괄호를 빼고는 같은 기호를 두번 반복하지 말라. + 은 변수나 상수를 양쪽에 둔다." 라는 규칙들을 미리 프로그램 해 두었다면, 앞의 말도 안되는 것들 중 여럿이 준다. 여기에, 더 엄정하게 문법을 정해주면 줄수록 이해안되는 말은 기계 스스로 걸러낼 것이다. 이럴 경우 이 기계가 만들어내는 기호는

$\neg ((x\And x)\And \neg x)\ ,\ \neg \exists x\neg ((x\cdot x'=0)\And \neg (\neg (x=0)\And \neg (x'=0))$

기계 언어라 아직 위의 말이 사람에게는 친숙하지 않다. 그렇다면 기계에게 사람에게 친절하도록 할 프로그램을 또 추가한다. 이제 기계는 속으로는 위의 말을 썼더라도 드러낼 때는

$(x\And x)\rightarrow x)\ ,\ \forall x,y\ (x\cdot y=0\rightarrow (x=0\lor y=0))$

로 바꾸어주는 친절을 베풀 것이다. 사람도 나름대로 노력을 해야하니까, 형식 논리 언어를 조금이라도 익히기 위해 노력했다면 위의 말을 이해할 수 있다. 앞의 명제식은 "'그립고 그립다' 이면 '그립다'" 와 같이 이해할 수 있고, 뒤의 식은 "어떤 두 수에 대해서도 그 수를 곱해서 0 이 나오면 둘 중 하나는 0 이다," 라고 사람답게 해석해서 이해할 수 있다. (그 거꾸로의 과정이라고 해서 불가능할까?)

이제 이 기계가 만들어내는 모든 식은 잘못 만들어진 식이 없다. 이 중에는 $\exists x\ (x=0)$ 처럼 너무나 당연해서 재미없는 말도 나오겠지만, $\exists x,y,x\ (x^{2}+y^{2}=z^{2})$ 처럼 수학적으로 매우 의미있는 문장도 있게 된다. 대단하지 않은가? 이것이 전부가 아니다.

정리를 만들고 증명하는 기계

만들어내는 문장들이 우리에게 판독이 된다고 해도 아직 그 기계는 충분히 성숙하지 않다. 이제 우리와의 교감을 깊게 하기 위해 이 기계에 새로운 프로그램을 더하자. 우리가 항상 참일 것이라고 믿는 것들 중 가장 기초적인 문장의 틀을 입력하는 것이다. 유클리드 기하학 같으면 " 두 점을 잇는 직선은 하나다, 두 직선은 기껏해야 한점에서 만난다"와 같이 전체 기하학에서 가장 기초가 되는 문장만 뽑아보는 것이다. 지금 사정으로서는 룸론 사람이 기계에게 베풀어주어야 하는 것이다. 기하학의 세계라면 힐버트가 깊이 연구해서 정리해둔 공리를 프로그램화 하면 되고 산술의 세계라면 Peano 산술의 언어와 공리를 넣으면 된다. 집합에서는 예를들면, Zermaelo-Frankel 시스템일 것이다. 그것보다 기초적인 언어도 필요하다. 논리의 언어인데, 이를 위해서는 술어 논리의 공리를 넣으면 된다. 술어논리도 이미 충분히 완성도 있는 공리 시스템이 있다. 그 공리의 몇개만 써본다.

• $P\rightarrow \ (Q\rightarrow \ P)$
• $(P\rightarrow \ (Q\rightarrow \ R))\rightarrow \ ((P\rightarrow \ Q)\rightarrow \ (P\rightarrow \ R))$
• $(P\land Q)\rightarrow \ P$
• $P\rightarrow \ (P\lor Q)$
• $(\forall x\ p(x))\rightarrow p(t)$
• $p(t)\rightarrow (\exists x\ p(x))$

모두 다 써보아야 고작해야 10 개도 남짓이다. 여기에 예를들어 Peano Arithmetic 이라면 그 언어가 가지는 공리를 추가하면 된다. 이것도 모두 써봐야 10개 남짓이다.

• $\forall x,y\ (x=y\ \rightarrow \ y=x)$
• $\forall x,y\ (x=y\ \rightarrow s(x)=s(y))$

집합론의 공리도 몇 개 써보자. 이것도 마찬가지 10 개가 채 안된다.

• $\forall x,y\ (\forall z(z\in x\leftrightarrow z\in y)\rightarrow x=y)$
• $\forall z\exists y\forall x(x\in y\leftrightarrow (x\in z\And P(x)))$

이런 식으로 수학의 영역들을 공리 시스템으로 표현하고 수학 기계에 하나둘 공리들을 추가하면된다. 그리고 새로운 문장을 이끌어 낼 수 있는 규칙들도 만들어주면 된다. 예를들어 논리의 규칙 에서 나오는 모더스 포넌스.

${\frac {P,\ P\rightarrow Q}{P}}$

그렇다면 이 기계는 공리로 부터 P 와 P → Q 의 꼴에 P 나 Q 대신 어떤 구체적인 문장을 Q 를 얻게 된다. 또 어디선가, Q → R 를 얻게 되면 바로 R 도 얻게 된다. (유도하는 예는 오늘날의 수리논리 를 참고하라. )

자, 이제 프로그램이 끝났다면 우리에게는 무엇이 할 일이 남았을까? 이상없이 프로그램 했다면 기계에 전기를 켜고 시작 버튼을 누르면 된다. 이 기계는 계속 새로운 문장을 만들어내고 그 새로운 문장은 공리와 규칙으로부터 '증명되어' 나오는 '수학적으로 의미있는 정리'들이 쏟아져나온다. 이제 수학자들은 지구상에서 필요없는 존재들이 된 것인가? 아니면 수학자란 수학 기계 앞에 팔짱기고 앉았다가 출력되는 문장들을 정리하는 일만 하면 충분할까?

수학의 종말 ?

수학의 밑바닦이 얼마나 견고한지 탐구하는 과정으로 분석해들어가기 시작한 논리탐구는 그것조차 수학의 도움을 받아 수학적이 되었다. 이는 수학 기계의 탄생을 가능하게 했다. 수학 기계는 이론적으로도 가능하고 실제로도 만들어지고 있다. 그 역사가 고작 100 년도 채 안되었다 점, 엄청나게 많은 계산량을 엄청나게 빠르게 계산해내는 컴퓨터가 탄생한 것은 최근의 일이다. 지금은 어떤 정리를 발견하면 그 정리와 증명의 핵심 문장을 '어느 정도 기계적인 언어로' 바꾸어 기계에 입력하고 기계가 검산하는 단계에 와 있다. 컴퓨터의 하드웨어가 더 발달하고 너 좋은 프로그램 언어가 나오고 더 효율적인 알고리듬이 개발될수록 가속이 붙어 발달해갈 것이다.

그렇다면 수학자들은 수학 연구를 접어야 할 때가 온 것인가? 수학 기계와 경쟁하거나 경쟁을 포기하고 산 속으로 들어가 정자를 짓고 자연과 벗삼아 시를 지으며 살아가야하나? '그 때'가 오면, 수학은 종말을 맞을 것인가 ?

괴델 (K.Godel)

파일:Kurt Gödel.jpg

수학의 논리화와 논리의 수학에서 새지평을 열어젖힌 사람들 중 몇몇의 이름은 앞에서 나왔다. 수리논리 연구에서 첫손가락에 꼽아야할 사람을 아직 말하지 않았다. 그의 이름은 괴델(Kurt Gödel ;1906 - 1978) 이다. 오스트리아 제국(지금의 체코)에서 태어나 미국에서 생을 마감했다. 하도 질문이 많아 어렸을 때 별명은 " 왜? 씨(영어로 Mr.Why)" 였다고 한다. 이론 물리 공부 하러 비엔나로 가지만 수학과 철학 수업을 들으면서 수학의 기초에 흥미를 갖게 된다. 이때 비엔나는 '비엔나 학파'라고 불리는 일군의 수학자, 철학자들이 있었고, 따라서 논리학의 중심지 중 한 곳이었다. 그들의 수업이나 세미나를 들어가면서 러셀의 '수리 철학 입문'을 읽기도 했다. 그러던 중 힐버트가 방문하였을 때 '어떤 논리체계의 무모순성(건전성 soundness, consistency)과 '완전성(completeness)'에 관한 강연을 듣게 되었다. 논리학과 수리논리의 기초에 대한 중요한 저작인 힐터트의 '이론 논리의 원칙들' 이라는 책에 던진 핵심적인 질문 ,

어떤 공리 체계는 그 모델들에서 참인 모든 문장을 이끌어낼 수있는가 ?

다시말해, 공리체계는 완전한가? 라는 질문을 탐구하여 박사학위를 받는다. 괴델은 힐버트의 질문에 이렇게 답했다.

정리 (괴델의 술어 논리에 대한 완전성 정리) : 술어논리체계(first order logic) 는 그것을 보장하는 어떤 모델에 대해서도 참인 문장을 이끌어 낼 수 있다

이때가 바로 1930년의 일이다. 이어서 바로 다음해 역사적인 정리를 발표하게 된다.

정리 (괴델의 산술에 대한 불완전성 정리) : 자연수의 세계를 충분히 설명할 수 있는 '셀 수 있는 공리들의 논리 체계'는 불완전하다.

다시 말해 Peano Arithmetic 이나 Zermelo-Frankel 집합론의 경우 참인데도 이끌어낼 수 없는, 다시 말해 증명할 수 없는 문장이 존재할 수 밖에 없다는 것을 보인다. 더 정확히 말해보자. 자연수 세계를 설명할 수 있는 공리체계가 있는데 공리들은 셀수 있는 집합이라고 하면,

그런 공리체계가 무모순하면 그 공리체계는 불완전하다.

어떤 문장을 증명할 수 없을까? 그 대표적인 예가 바로 '그 공리체계가 무모순하다' 라는 문장이다.

괴델은 그 후로도 기념비적인 사실들을 밝혀냈다. 새로운 천 년이 시작되는 2000 년, 세계 수학자들에게 설문한 자료에 따라 Times 지가 발표한 '20세기의 수학자'로 그가 선정되었다.

Note

Math : Math글쓰기 | Math번역 | MathBoard | Math&Culture | MathMoim
OnLineMathCenter | MathCamp | SoftMathJournal | MathBook | CyberAcademia | Academia