0. 집합

이전에 집합의 개념을 한 번 다룬 적이 있었는데, 어떤 조건을 만족하는 대상의 모임으로 이해했습니다. 조건, 모임 등이 잘 정의된 용어가 아니라고 생각하는데, 집합의 개념을 잘 정의하려고 합니다.

2화에서 이야기 했던 wff는 명제와 명제함수로 번역하여 사용중입니다. wff는 일반적으로 다음과 같은 induction으로 정의됩니다.

ㄱ. normal propositions are wff.

ㄴ. propositions concatenated with &&, ||, ~ are also wff.

ㄷ. finite applications of ㄱ,ㄴ are also wff.

쉽게 말해 단순 진리값과 유한한 &&, ||, ~로 연결된 단순 진리값을 wff라고 부릅니다. 더 간단하게 얘기하면 진리값을 확실히 갖는 문장들이라고 생각할 수 있습니다. 이후 보충설명식으로 따로 다루겠습니다.

1. 집합과 원소

집합의 원소임을 나타내는 연산자는 "in"으로 쓰겠습니다. 예를 들어 [a in A]는 "a는 A의 원소이다"라는 뜻이고, a가 A의 원소이면 T, 원소가 아니면 F를 결과로 갖는 연산자입니다. a in A는 명제이고, ~(a in A)를 생각할 수 있는데, "a는 A의 원소가 아니다"는 뜻으로 해석해도 무리가 없고, 이를 연산자 "not in"으로 쓸 수도 있습니다. [a not in A]는 a가 A의 원소이면 F, 원소가 아니면 T를 결과로 갖는 연산자입니다.

집합의 정의를 다음과 같이 하겠습니다.

A: s.t. (for all x) ~( x in A <-> x not in A)

천천히 풀어봅시다. x in A는 x가 A의 원소임을 말합니다. x not in A는 x가 A의 원소가 아님을 말합니다. <->로 연결되어 있으므로 진리표를 통해 알아보신 분들은 알겠지만 같은 진리값을 가짐을 뜻합니다. 즉, "x가 A의 원소이고 x가 A의 원소가 아님"이거나 "x가 A의 원소가 아니고 x가 A의 원소임"을 뜻합니다. NOT 연산자에 의해 이것의 부정을 취하고, for all 양화사에 의해 전체집합의 모든 원소에 대해 이것이 성립해야 한다는 것을 의미합니다.

요약하면, 전체집합의 모든 원소 x는, A의 원소이면서 A의 원소가 아닌 경우는 없으며, 둘 중 하나만을 T로 가진다는 의미입니다. 진리표를 통해 확인해보면 for all 양화사 뒤에 나오는 명제는 항상 T인 것 같습니다. 그러나, 연산자 in을 이야기할 수 없는 경우나, 기타 사유로 in과 not in이 동시에 같은 진리값을 가지는 경우에는 일단 보류해둘 필요가 있다는 것입니다.

(개인적인 생각을 덧붙이자면, 이런 형태로 정의를 쌓아 올린 거의 대부분의 수학적 대상은 집합을 통해 규정된다고 보기 때문에 연산자 in은 명제를 제외하면 모두 가능하다고 봅니다.)

2. 전체집합

집합을 정의하면서, 전체집합이라는 개념을 이용하고 있습니다. 전체집합이라는 개념 역시 집합이라는 개념으로 정의할 수 있어 보이는데, 이는 순환논증이 되는 것 같습니다.

전체집합을 이용하는 가장 큰 이유는 양화사의 사용입니다. for all, exist 양화사는 "전체집합의 모든/어떤 원소에 대하여 ... "를 나타내는 말인데, 이 뒤에는 양화사에 의해 묶인 변수가 사용될 것입니다. 이 양화사에 의해 묶인 변수가 사용되는 연산자는 어떤 특정 부류의 대상만 사용할 수 있습니다. 예를 들어 연산자 "&&"는 진리값 또는 명제만을 사용하는 연산자입니다. 즉, 어떤 연산자에 묶여있는 변항에 대한 전체집합이라 함은, 그 연산자가 취할 수 있는 대상을 원소로 하는 대상이 됩니다. ("~ 원소로 하는 집합"이 아님에 유의하자.) 

3. 조건제시법과 러셀의 역설

이전에 조건제시법으로 나타내는 집합에 대해 이야기했습니다. 조건제시법으로 나타내는 집합의 정의를 명제로 다시 정의해봅시다.

p(x)를 x를 변항으로 가지는 명제라고 하면, (for all x) ((p(x)->x in A)&&(~p(x)->x not in A))가 T의 진리값을 가진다고 할 때, 진리표를 통해 x in A와 x not in A가 동시에 참이어야만 하는 x는 없음을 알 수 있고, A는 집합으로 보기에 적당하다는 결론을 얻을 수 있습니다. 이렇게 얻어진 집합 A는 {x|p(x)}라고 쓸 수 있는 것이다. 예를 들면 자연수를 전체집합으로 할 때 x<3은 명제이고, {x|x<3}은 잘 정의된 명제라고 할 수 있는 것입니다.

조건제시법을 소개할 때 러셀의 역설에 대해 소개한 바 있는데, 집합 A를 {x|x not in A}와 같이 조건제시법을 통해 어떤 명제나 허용할 때 생기는 모순이 존재한다고 설명했습니다. 이 정의를 조건제시법의 정의로 가져가봅시다.

우리는 조건제시법의 정의에 따라 집합 A의 정의인 {x|x not in A}는 원래 명제로 (for all x) ((p(x)->x in A)&&(~p(x)->x not in A))처럼 쓰일 수 있어야 합니다. 이때 p(x)를 x not in A라고 하면, (for all x) ((x not in A -> x in A)&&(x in A->x not in A))가 됩니다. 이 식은 연산자 <->의 정의에 의해 (for all x)(x not in A <-> x in A)가 되는데, 진리표를 통해 알아보면 거짓이 됨을 알 수 있습니다. 당초 조건제시법을 통한 집합은 명제 꼴로 나타냈을 때 참이 되어야 한다는 것이 정의였으므로 정의에 어긋나고, 이런 집합은 존재하지 않음을 보일 수 있습니다.

4. 양화사의 해소규칙

양화사와 묶인 변항을 해소하여 변항을 없애는 방법과, 다시 양화사와 변항이 있는 꼴로 고치는 방법은 각각 2개씩 총 4가지가 있습니다.

ㄱ. Universal Specification - 광역특정

줄여서 US라고 부릅니다. US는 for all 양화사를 해소하는 방법으로 전체집합의 특정 원소를 대입하는 규칙입니다. (for all x) p(x)라는 양화사를 포함한 명제에서, x에 대한 전체집합 U의 어떤 원소 a에 대해 p(a)라고 쓰는 것입니다. 예를 들어, "모든 교통수단은 안전벨트를 지닌다"는 명제는 k에 대한 전체집합이 교통수단인 (for all k)(k는 안전벨트를 가진다)라는 양화사를 포함한 명제 식으로 쓸 수 있는데, k에 전체집합의 어떤 특정한 원소를 k에 대, 자동차를 예를 들면, "자동차는 안전벨트를 가진다"라고 쓸 수 있는 것입니다.

ㄴ. Extential Generalization - 존재일반화

줄여서 EG라고 부릅니다. EG는 없는 exist 양화사를 새롭게 만들어 내는 규칙입니다. p(a)라는 명제에 대해 (exist x)p(x)라고 쓰는 것입니다. 예를 들어, "수학 채널에는 간단한 문제 글머리가 있다"라는 명제를 기호로 p(간단한 문제)라고 한다면, exist 양화사를 더해서 (exist x)p(x), 즉 (exist x)(수학 채널에는 x 글머리가 있다)라고 쓸 수 있는 것입니다.

ㄷ. Extential Specification - 존재특정

줄여서 ES라고 부릅니다. ES는 exist 양화사를 해소하는 방법으로 전체집합의 원소를 대입하는 규칙입니다. 단, 새로 대입하게 되는 원소는 이전의 어떤 진술에서도 자유 변항이 아니어야 합니다. 자유 변항은 양화사에 쓰이는 변항 (예를 들면 for all x 의 x)이나, 양화사로 묶여있지 않은 변항입니다. 이 조건을 만족하는 가장 간단한 방법은, 이전 진술에 한 번도 등장하지 않은 문자를 사용하는 것입니다. 예를 들어, (exist x)p(x)라는 명제에서, 이 명제 이전에 나온 어떤 명제나 문장에서도 y라는 문자는 등장하지 않았다면, p(y)라고 할 수 있다는 것입니다. 이때 이러한 x는 존재하는데, 그런 x들의 집합의 대표 심볼을 y라고 정하는 것과 유사한 의미입니다.

여기서 한 가지 트릭이 있는데, US와 ES를 동시에 사용해야 할 때가 있다면, ES를 먼저 적용하고 US를 적용하는 것이 더 자유롭게 특정할 수 있습니다. ES는 이전에 등장하지 않은 문자를 사용하는 것이 좋은데, US는 그런 제약이 없습니다. 이전에 등장했던 문자를 ES를 통해 사용하고 싶다면 그렇게 사용해도 좋은지를 검증해야 하지만, US를 먼저 적용하면 그런 검증이 필요 없어지겠죠.

ㄹ. Universal Generalization - 광역일반화

줄여서 UG라고 부릅니다. UG는 없는 for all 양화사를 새롭게 만들어 내는 규칙입니다. 단, UG에 의해 묶이는 변항은 ES를 통해 특정된 변항에는 적용하지 못합니다. 일반적으로 US를 통해 for all 양화사가 있던 경우 해소된 양화사를 다시 환원해 주는 역할을 합니다.

5. 못다한 증명들

a. A가 B의 서로소집합이면 B도 A의 서로소집합이다.

A가 B의 서로소집합임을 명제 꼴로 쓰면 (for all x)(x in A -> x not in B)이다. 진리표를 통해 (p->q)와 (~q->~p)는 항상 진리값이 같음을 알 수 있다. 이 둘을 대우 관계에 있다고 한다. 대우에 의해 (for all x)(~(x not in B)->~(x in A))이고, ~을 정리하면 (for all x)(x in B -> x not in A)이다. 이는 B가 A의 서로소집합임을 의미한다.

b. 집합은 여집합과 서로소관계이다.

명제 꼴로 쓰면 A가 집합일 때 (for all x) (x in A->x not in A')이다. A'는 명제꼴로 쓰면 (for all x)((x in A->x not in A')&&(x not in A->x in A'))이고, &&연산자의 앞부분이 A와 A'는 서로소관계임을 이야기하고 있다. (이후 증명 파트의 Tautology Rule에서 더 엄밀한 증명을 하겠습니다.)

6. 마치며

뭔가 말이 길어진 듯합니다. 개인적으로 가장 재밌게 공부했던 부분이라 많은 내용을 담고 싶었는데 너무 길어질 것 같아서 짧게 끝내보려고 합니다. 이 부분이 개인연구가 상당히 많이 포함된 부분이라 오류발견시 남겨주시면 좋겠습니다.