[Section 1] 공리계의 성질

대수학 목차 보기

[INTRO] 대수학 미리보기

0. INTRO

수학에서 공리계는 독립적 성질과 함께 완결성, 일관성 그리고 단일성을 갖는다. 이 4개의 특성에 대해 알아보고, 공리계 시스템을 통해 우리가 얻을 수 있는 바를 생각해보자.

1. 독립성(Independece)

수학에서 동등 관계를 의미하는 공리로부터 귀결된 공리계는 독립성을 갖는다. 독립적 성질을 갖는다는 말은 정확히 무슨 뜻일까? 0과 1의 정보만을 가지는 컴퓨터처럼, 어떤 공리 E는 0과 1의 영역만을 가진다고 가정하고, 다음의 공리계를 통해서 독립적 성질을 알아보도록 하자.

 

"어떤 공리계는 반사(reflexivity), 대칭(symmetry), 그리고 추이(transitivity)를 의미하는 3개의 공리를 가진다."

 

"Exy"

 

여기에서 대문자 E는 동등 관계(equivalence relation)를 의미하는 술어를 나타낸다.

A. 반사 관계(reflexivity relation)

반사 관계를 나타내는 공리계 A는 다음과 같다.

 

"(x) Exx"

 

여기에서 대문자 E는 동등 관계(equivalence relation)를 의미하는 술어를 나타낸다.

 

A를 해석(interpretation)을 해보자.

자기 자신과 동일한 원소가 0과 1의 영역 안에 존재하는가?

없다. 그렇다면 공리가 참이기 위해서, 반사 관계를 나타내는 원소는 없어야 한다. 

B. 대칭 관계(symmetry relation)

대칭 관계를 나타내는 공리계 B는 다음과 같다.

 

"(x)(y)(Exy→Eyx)"

 

B를 해석(interpretation)을 해보자.

먼저 Exy를 보자. 동등 관계가 참이려면 어떠한 x와 y가 어떠한 논리 값을 가져야 하는가? 둘 다 참이거나 거짓이면 된다. 어찌 됐건 둘은 같은 진리 값을 가지므로, x와 y가 항상 참이라고 생각하자.

위 명제는 항진식이다. 함의 관계를 생각해 볼 때, 위 명제는 다시 세 가지의 참 조건 그리고 한 가지의 거짓 조건으로 나누어진다.

참 조건 1; Exy, Eyx가 모두 참인 경우이다.

이 경우 부합하는 원소는 x가 0이면, y는 0으로 결정되어야 한다. 마찬가지로 x가 1이면, y도 1이다.

참 조건 2; Exy, Eyx가 각각 거짓, 참인 경우이다.

이 경우 x가 0이면 y는 1이 된다. Eyx는 참이므로 y가 1이면 최종적으로 x는 1이다. 마찬가지로 x가 1이면, y는 0이다. Eyx는 참이므로 y가 0이면 x는 최종적으로 0이 된다.

참 조건 3; Exy, Eyx가 각각 거짓, 거짓인 경우이다.

이 경우 부합하는 원소는 x가 0이면, y는 1로 결정되어야 한다. Eyx 또한 거짓이므로 y가 1이면 x는 0이 된다. 마찬가지로 x가 1이면, y는 0으로 결정되어야 한다. Eyx 또한 거짓이므로 y가 0이면 x는 1이 된다.  

거짓 조건 4; Exy.Eyx가 각각 참, 거짓인 경우이다. 

이 경우 부합하는 원소는 x가 0이면 y는 0으로 결정되고, Eyx가 거짓이므로 y가 0이면 x는 1이 된다. 마찬가지로 x가 1이면 y는 1로 결정되고, Eyx가 거짓이므로 y가 1이면 x는 0이 된다. 

 

B의 해석으로 말미암아, 대칭 관계가 항진 식이 되기 위해서 조건 4에 해당하는 원소가 나타나면 안 된다. 따라서 대칭 관계는 부등호 ≤ 와 같은 결과를 가져온다. 이는 원소의 범위가 커지더라도 마찬가지다.

C. 추이 관계(transitivity relation)

추이 관계를 나타내는 공리계 C는 다음과 같다.

 

"(x)(y)(z)((Exy ⋀ Eyz)→Exz)"

 

C를 해석(interpretation)을 해보자.

위 명제는 항진식이다. 함의 관계를 생각해 볼 때, 위 명제는 다시 세 가지의 참 조건 그리고 한 가지의 거짓 조건으로 나누어진다.

참 조건 1; (Exy ⋀ Eyz)와 Exz가 모두 참인 경우이다.

참 조건 2; (Exy ⋀ Eyz)와 Exz가 각각 거짓, 참인 경우이다.

참 조건 3; (Exy ⋀ Eyz)와 Exz가 각각 거짓, 거짓인 경우이다.

거짓 조건 4; (Exy ⋀ Eyz)와 Exz가 각각 참, 거짓인 경우이다. 

 

공리계 B와 동일한 해석을 통해서 우리는 추이 관계가 다음과 같은 결과와 동일하다는 것을 알 수 있다.

(여기서는 원소의 개수가 적어도 3개 이상이어야 동일하다는 것을 명확히 이해할 수 있다.)

 

"|x-y|≤1"

 

D. 독립성의 의미

동등 관계와 함의 관계의 논리를 통해서 수학 체계에서 나타나는 3가지의 기본 관계를 알았다. 사실 반사 관계를 가지고 독립성을 나타내기에는 충분하다. 하나의 공리를  통해서 유도된 3가지 관계들이 말하는 단 하나의 사실은 수학적 주체들 중 어느 하나도 동일하지 않다는 것을 의미한다. 다만, 귀결된 공리계를 통해서 우리는 수의 성질에 대해 더 자세히 알 수 있다. 즉, 공리계로 정리된 수학 체계는 인간이 세상을 더 이해하기 쉽게 만들어진 논리적 절차이며, 독립성으로 우리는 수의 성질이 서로 다름을 인지할 수 있다.

2. 완결성(Completeness)

수학적으로 귀결된 공리계들은 완결성의 성질을 갖는다. 완결성이란 공리계안에서 명제들이 서로 관련 있는 명제들이라는 성질을 말한다. 이는 항진식(tautology)인 명제로부터 항진식인 공리계가 귀결되었기 때문에 발현되는 성질이라고 봐도 무방하다. 더 자세히 이해하기 위해서 다음의 예시 명제를 보도록 하자.

 

"명제 A가 어떤 공리계 B로부터 귀결되었다."

 

A가 B로부터 귀결되었든, ¬A가 B로부터 귀결되었든 어느 한쪽으로든지 귀결된 공리계의 모든 명제들은 완결성을 갖는다. 이를 분리(disjunction) 관계라고 부르기도 하는데, 이 관계는 대안(alternative) 관계와 확실히 다른 차이를 가지고 있다. 대안 관계와 분리 관계의 논리적 진리표는 다음과 같다.

 

진리표로 보는 대안과 분리의 차이

 

왜 이런 관계를 설명하냐면, 서로 다른 공리계의 비교를 위해서다. 서로 다른 공리계 A와 B는 대안 관계 이거나 분리 관계를 갖는다. 이러한 관계를 갖고 있기 때문에 공리계는 그 자체로서 완전하다. 완전성은 이 의미를 함축적으로 설명한다. 

3. 일관성(Consistency)

완결성과 함께 수학적 공리계들은 의미론적인 일관성(semantic consistency)을 갖는다. 공리로부터 출발한 하나의 공리계 체제는 당연히 모순이 발생하지 않을 것이다. 하지만, 실제 세계를 연구하는 물리학이라는 분야의 관점에서 일관성을 좀 따져보자. 우리는 세상의 가장 작은 원소가 무엇인지도 모르며, 우주 밖의 세상도 알 수 없다. 그럼에도 우리가 세상을 물리학으로 기술할 수는 것은 세상의 모든 동역학 혹은 물질이 단 하나의 사실 혹은 원소에서 출발했을 거라는 믿음 혹은 직관이다. 이렇게 기술된 물리학이라는 공리계는  오로지 한정적 사실 혹은 원소의 영역 내에서만 일관성을 갖는다. 수학 체제의 발전과 함께, 현실을 반영하는 공리계들은 유사한 특징을 갖추게 되었다. 그래도 우리는 일반적으로 공리계는  일관성이 있다고 한다. 예를 들어, 유클리드 기하학이 구축한 공리계는 실제 분석에 모순이 없을 때 일관성이 있다고 하며, 이것을 상대적 일관성의 증명(a proof of relative consistency)이라고 한다.

4. 동형(Isomorphy)

동형이라는 말은 수학적으로 군이론(group theory)에서 다루는 내용과 아주 유사하다. 아직 군 이론에 대해서 배우지 못했으므로, 기하학을 또 예로 들어보자. 유클리드 기하학은 점, 선, 등으로 자연을 해석(interpretation)했다. 그리고 이 점은 이상적인 점으로 정의하였는데, 세 개의 숫자로 점을 대치시킨 해석적 기하학이라는 다른 공리계는 유클리드 기하학과 동형이다. 수학적으로 동형인 계들은 서로 구조가 같다고 본다. 동형에 대한 더 자세한 내용은 군 이론을 통해서 배우기로 하자.

 

 

* 다음강의는 알고리즘과 논리학 증명 시스템입니다.

[Section 1] 알고리즘과 논리학 증명 시스템