누군가 있다는 사실로 무엇까지 추론하나요?

네. 다음 가상 모임의 접수 상황을 보겠습니다. 이번 편에서는 참가자 전체가 영역이고, P(x)는 ‘x가 오후 4시까지 서류를 냈다’, Q(x)는 ‘x가 오후 4시까지 접수증을 받았다’입니다. 식을 읽을 때 같은 시각과 같은 뜻을 유지하겠습니다.

맞습니다. a를 아라의 이름으로 정했다면, 존재문만으로 제출자가 아라라고 지목할 수 없습니다. 어느 사람인지는 정하지 않은 채 그 사람에게 적용되는 근거를 살펴보겠습니다.

그렇게 하겠습니다. 다만 d는 이번 증명에서 아직 쓰지 않은 새 이름이어야 합니다. 10편에서 d를 아라의 별명으로 썼던 약속은 이번 증명에 가져오지 않습니다. 여기서는 존재문을 만족하는 어느 대상에 붙이는 임시 이름입니다.

영역에 새 사람을 보태는 것이 아닙니다. 존재문이 이미 영역 안에 P인 대상이 있다고 알려 주었습니다. 그 대상을 생각할 때 사용할 이름을 잠시 마련한 것입니다. d가 아라와 같을 수도 있고 다른 사람일 수도 있습니다.

증명표에서는 P(d)를 임시 가정으로 표시하고 그 안에서 추론합니다. ∃xP(x)를 곧바로 특정 이름에 대한 독립된 사실로 바꾸는 규칙은 쓰지 않습니다.

3번의 의미는 ‘존재문을 만족하는 대상을 d라고 놓고 살펴보자’입니다. 그 가정 안에서 우리가 얻으려는 것은 d의 신원을 말하지 않는 결론입니다. 이 경우 목표는 ∃xQ(x)입니다.

네. 존재문이 보장하는 성질만을 가진 대상으로 생각해야 합니다. d가 회장이라거나 아라라는 식의 추가 조건을 몰래 넣지 않겠습니다.

2번의 ‘제출자는 모두 접수증을 받았다’를 d에게 적용합니다. 12편의 전칭 제거로 P(d)→Q(d)를 얻습니다. 그다음 P(d)와 결합하면 Q(d)가 나옵니다.

그렇습니다. 가정 안에서 d가 접수증을 받았음을 얻었으니, 13편의 존재 도입으로 접수증을 받은 사람이 있다고 말할 수 있습니다. 이제 밖으로 가져갈 결론의 모양을 얻었습니다. 다만 6번은 아직 가정 안에 있는 줄이라는 점을 표시해 두세요.

가정 안에서 얻었다는 점이 아직 남아 있습니다. 이제 1번 존재문과 3~6번의 추론을 함께 사용해 가정을 닫습니다. 그러고 나서 같은 결론을 가정 밖의 7번에 적겠습니다.

이 마지막 규칙을 존재 제거, ∃E라고 적습니다. E는 제거를 뜻하는 영어 elimination의 첫 글자입니다. ‘제거’는 사람이 사라진다는 뜻이 아닙니다. 존재문의 정보를 사용해 다음 결론을 얻는 규칙의 이름입니다.

다음 세 곳을 확인하겠습니다. d는 임시 가정 안에서 사용하는 이름이므로, 그 가정 밖의 정보와 결론에 묶여 있지 않아야 합니다.

그리고 임시 가정은 존재문의 x 자리에 d를 일관되게 대입한 식이어야 합니다. 예를 들어 ∃x(P(x)∧Q(x))를 사용할 때에는 P(d)∧Q(d)로 시작합니다. 한 사람에 대한 두 조건을 서로 다른 사람으로 나누지 않습니다.

밖으로 가져가는 결론에 임시 이름 d가 남기 때문입니다. d는 P인 대상을 살펴보는 가정 안에서만 사용했습니다. 그 가정을 닫으면서도 특정 이름의 사실을 독립된 결론으로 남기면, 원래 존재문이 알려 주지 않은 신원을 붙들게 됩니다.

네. 같은 이유로 P(d) 가정 안에서 Q(d)를 얻은 뒤 ∀xQ(x)로 일반화할 수도 없습니다. d가 열린 가정 P(d)에 들어 있으므로 14편의 전칭 도입 조건에 걸립니다.

그 이름에 관한 정보가 다른 전제에 있을 수 있습니다. 다음은 오류를 확인할 별도 가상 사례입니다. a는 아라이고 P의 뜻은 그대로 ‘서류를 냈다’입니다. 전제는 P(a)와 ∃x¬P(x)입니다.

6번의 식에는 a가 없습니다. 그런데도 증명은 허용되지 않습니다. 3번의 이름 a가 다른 전제 P(a)에 이미 나타나기 때문입니다. 아라가 제출했다는 정보와 누군가 제출하지 않았다는 정보를 같은 사람에게 겹쳐 버린 셈입니다.

그렇습니다. 이 절에서는 관계의 뜻을 새로 약속하겠습니다. R(x,y)는 ‘x가 y의 이름을 기억한다’이고 a는 아라입니다. 존재문 ∃xR(a,x)는 아라가 누군가의 이름을 기억한다고 말합니다.

잘못된 두 번째 가정에서 ∃xR(x,x)를 얻으면 ‘자기 이름을 기억하는 사람이 있다’고 주장하게 됩니다. 하지만 아라가 보라의 이름만 기억하고, 보라와 찬우는 누구의 이름도 기억하지 않는 세계를 생각해 보세요. 원래 존재문은 참이고, 자기 이름을 기억하는 사람은 없습니다.

이 절에서는 그 두 존재문만 전제입니다. 앞의 ‘모든 제출자는 접수증을 받았다’는 전제는 사용하지 않습니다. 각 존재문이 알려 주는 대상이 같은지 다른지는 이 두 전제만으로 결정되지 않습니다.

두 세계에서 ∃xP(x)와 ∃xQ(x)는 모두 참입니다. 같은 이름 d를 두 존재문의 증거 대상으로 미리 정하면 세계 B를 놓칩니다. 이름 d와 e를 따로 고르는 경우에도 두 글자가 반드시 서로 다른 대상을 가리킨다고 판단하면 세계 A를 놓칩니다.

맞습니다. 한 증명에서 두 임시 가정을 함께 열려면 각 존재 제거의 새 이름 조건을 지켜야 합니다. 두 이름이 같은 대상을 가리킬 가능성은 남아 있습니다. 실제로 다르다는 결론에는 별도 근거가 필요합니다.

첫 접수 사례의 두 전제로 돌아가겠습니다. ∃xP(x)와 ∀x(P(x)→Q(x))가 함께 있으면 됩니다. P인 임시 대상 d에게 Q도 따라오므로, 같은 대상의 두 성질을 묶을 수 있습니다.

이 증명에서 두 성질을 같은 대상에게 묶을 수 있는 이유는 2번 전제입니다. 제출한 d에게 접수증 수령도 따라온다는 연결 근거가 있습니다. 두 개의 독립된 존재문만 주어진 앞 절의 상황과 이 근거를 구별해 두세요.

결론에 반드시 ∃가 있어야 하는 것은 아닙니다. 필요한 것은 임시 이름이 없는 결론과 규칙의 조건입니다. 이번에는 서로 함께 참일 수 없는 두 전제를 살펴보겠습니다.

임시 가정을 닫은 뒤에도 모순이 남습니다. 따라서 두 원래 전제는 함께 참일 수 없습니다. 실제 접수 현장에서 누가 어떤 모순된 행동을 했다고 알아낸 것이 아닙니다. 같은 조건으로 읽은 두 설명의 양립 가능성을 검토한 것입니다.

네. 원래 전제가 ∀x(P(x)→Q(x)) 하나라고 합시다. 조건문의 앞부분 ∃xP(x)를 바깥 가정으로 엽니다. 그 안에서 존재 제거를 위한 P(d) 가정을 하나 더 엽니다.

맞습니다. 존재 제거를 할 때에는 원래 전제뿐 아니라 먼저 열려 있던 바깥 가정도 확인합니다. 여기서 d는 1번과 2번에 없고, 사용한 존재문 2번과 결론 7번에도 없습니다. 따라서 안쪽 가정을 올바르게 닫을 수 있습니다.

그 순서를 기억하면 좋습니다. 다음 질문으로 증명의 각 줄을 확인해 보세요.

이제 전칭 제거, 존재 도입, 전칭 도입, 존재 제거를 모두 만났습니다. 16편에서는 목표를 먼저 읽고 필요한 규칙을 고르면서, 여러 단계를 하나의 증명으로 이어 보겠습니다.