이산수학에 관해 짧게 정리한 글

1. 수학적논리 

수학적 논리는 어디에서 출발했을까? 

그 기원은 고대 그리스로 넘어간다 

수학은 두 가지인 듯 보이는 한 가지 기원을 가지고 있다 

첫 번째는 유클리드 <기하학 원론>이다 

기하학 원본은 정의, 첫번째 원리들, 공리들을 통해서 

엄밀한 증명을 거쳐 모든 정리들에 도달한다 이러한 증명은 그 자체로써의 의미도 갖지만

단순히 정리들만을 제공해주는 것을 넘어 수학에 엄청난 노리적인 토대를 구축했다는 것에

의의가 있다 두 번째는 아리스토텔레스의 삼단논법이다 아리스토텔레스는 

모든 사람은 죽는다(대전제)

소크라테스는 사람이다(소전제)

소크라테스는 죽는다(결론)

이라는 간단해 보이는 토대를 구축했는데 후에 이 논리적인 사고가 2000년 가까이 논리학의 가장 큰 기반이 된다

이러한 논리학에서부터 시작되는 듯한 모든 사고활동은 수학세계관 전체에 영향을 미치게 되는데 이후 수학자들 간에 직관주의 논리주의 게임주의(수학은 일종의 언어게임에 불과하다) 등 많은 근본적인 생각이 차이가 나게 된다 다시 말해서 논리학, 수학, 철학 등은 20세기에 이르러 그 경계가 모호하여지고 특히 논리학이 모든 것을 포용하는 역할을 하게 된다 그러나 20세기에 이르기 전 수학은 19세기에 조지 불 과 고틀로프 프레게에 의해서 많은 전환점을 맞이하게 된다 특히 조지 불이 논리 명제들을 순수한 기호언어로 표현하고자 노력했었고 and, or, not이라는 기법을 도입하게 된다 

X or Y = Y or X 

not(not X) = X 

not(X and Y) = (not X) or (not Y)

그리고 고틀로프 프레게에 의해 논리학에 변수를 도입하게 된다 기존의 문장이 "소크라테스는 사람이다" 이런 식의 단순한 문장이었다면 "X는 사람이다"라는 새로운 사고방식을 도입한 것이다

2. 집합과 함수 

위에서 논리학이 수학을 포용하는 역할을 하게 된다고 말했었다(물론 생각에 따라 이 문장에 반대할 수 있다 그 생각도 충분히 타당하다) 그리고 그 출발점은 버트런드 러셀과 화이트헤드이다 아니 조금 더 정확히 말하면 칸토어이다 칸토어는 실수들의 집합은 셀 수 없는 집합이라는 것을 증명했다다 다시 말해서 실수들은 자연수들과 일대일로 대응되지 않는다는 것이다 그는 이이로 인해서 다양한 무한이 있음을 증명했는데 재미삼아서 그 증명의 가장 근본적인 아이디어를 적어보자

P1 = [ 1 0 3 4 9 1 .......            ]

P2 = [ 1 0 3 4 9 9 8 7 6 .....      ]

P3 = [ 0 9 9 8 4 .......               ]

....

....

....

P100000000=[ 7 6 5 4 1 5 ... 7]

이렇게 하나의 수가 1억개로 이루어진 1억 개의 P가 있다고 해보자

이 1억 개의 수와 똑같지 않은 수를 어떻게 찾을 수 있을까? 

방법은 간단하다 각 수의 자리에 있는 수에 전부 1씩 더하면 된다 그러면 P1 과는 첫 번째가 다르고 P2와는 두 번째가 다르고 P100000000과는 1억 번째가 다른 새로운 수가 나오게 된다 이 원릴리를 자연수와 실수에 적용시켜본다면 자연수와 일치하는 실수는 항상 대각선 방법에 의하여 새로운 수가 나온다 그러므로 자연수와 실수는 일대일대응이 불가능하다 ... 이런 식의 집합론은 그 후 수학에 스며들게 되었는데 그 적통을 이어받아 새로운 논리적인 토대를 구축하려고 했던 사람이 버트런드 러셀과 화이트헤드이다 특히 버트런드 러셀은 집합론을 연구하다가 한 가지 괴상한 역설을 발견하게 된다 그 역설은 다음과 같은 간단한 질문에서 출발한다 "자신을 포함하지 않는 모든 집합들의 집합은 자신을 포함할까?"... 답은 다음과 같다 "만일 포함한다면, 포함하지 않는다 또 만일 포함하지 않는다면, 포함한다"라는 식의 역설이 발생하게 된다 이 역설은 고대 그리스 거짓말쟁이 역설과 아주 비슷한데 에우불리데스가 이렇게 말했다 "시민 여러분, 저는 지금 거짓말을 하고 있습니다".. 이 사람이 거짓말을 하고 있다면 참말을 하는 것이고 참말을 하고 있다면 거짓말을 하고 있는 것이다 러셀이 발견한 역설도 거짓말쟁이 역설처럼 '자기언급' 문장이다 얼핏 이건 말장난처럼 들리지만 '집합'이 공통속성을 통해 정의된 집단이라는 생각을 무너뜨린다 

러셀과 화이트헤드는 이러한 사태의 중요성을 파악하고 <수학원리>를 통해서 새로운 수학의 토대를 구축하고자 노력하게 된다 .. 러셀은 이걸 실패로 봤지만 학자들마다 생각이 조금 다르다