하나의 논증을 언어·모형·증명으로 끝까지 검토할까요?

이제 고급 논리학의 여러 도구를 한 논증에 적용합니다. 영역 D={아라,보라}를 정하고 상수 a는 아라를, 단항 술어 P는 신청자, Q는 확인받은 사람을, 이항 관계 R(x,y)는 x가 y에게 확인 요청을 보냈다는 뜻으로 읽겠습니다.

우리는 먼저 문장과 모형의 기호를 분명히 구분합니다. P와 Q는 개별 대상의 속성이고 R은 순서가 있는 두 대상의 관계입니다. R(a,y)에서 y는 자유변수이므로 평가할 때 변수 배정이 필요합니다.

논증의 전제 집합 Γ를 다음처럼 정합니다. ① ∀x(P(x)→∃yR(x,y)): 신청자는 누군가에게 확인 요청을 보냅니다. ② P(a): 아라는 신청자입니다. ③ ∀y(R(a,y)→Q(y)): 아라가 요청을 보낸 사람은 모두 확인받았습니다.

결론을 C := ∃y(R(a,y)∧Q(y))로 잡습니다. 이는 아라가 확인 요청을 보냈고 확인받은 사람이 적어도 한 명 있다는 뜻입니다. 모든 전제와 결론은 닫힌 문장이므로 변수 배정에 의존하지 않습니다.

D={아라,보라}, a=아라, P={아라}, Q={보라}, R={(아라,보라)}로 해석하겠습니다. 아라는 신청자이고 보라에게 요청을 보냈습니다. 보라는 확인받았으므로 세 전제 모두 참입니다.

첫 전제는 P인 아라에 대해 보라를 증인으로 만족합니다. P가 거짓인 보라는 조건문 앞부분이 거짓이므로 첫 전제를 깨뜨리지 않습니다. 셋째 전제에서는 아라가 요청을 보낸 보라만 확인하면 됩니다.

∀x(P(x)→∃yR(x,y))에 전칭 제거를 적용해 P(a)→∃yR(a,y)를 얻습니다. 항 a는 x 자리에 안전하게 들어갑니다. 둘째 전제 P(a)를 조건문 제거에 사용하면 ∃yR(a,y)를 얻습니다.

이 단계에서는 ‘요청받은 사람이 누구인지’를 아직 결정하지 않습니다. 결론에 필요한 것은 어떤 y가 존재한다는 사실이며, 다음 단계에서 임시 증인 이름을 사용해 논증을 전개합니다.

존재 제거 규칙을 위해 아직 어느 외부 전제·결론에도 등장하지 않는 새로운 상수 c를 고릅니다. R(a,c)를 임시 가정하고, 이 가정에 의존하여 결론 C를 도출한 뒤 임시 가정을 해제합니다.

중요한 조건은 c가 원래 Γ와 최종 결론 C에 등장하지 않는다는 것입니다. c를 ‘특정한 보라’라고 미리 확정하면 안 됩니다. 모형이 무엇이든 존재문의 어떤 증인을 나타내는 가명입니다.

셋째 전제 ∀y(R(a,y)→Q(y))를 c에 적용하여 R(a,c)→Q(c)를 얻습니다. 임시 가정 R(a,c)와 함께 Q(c)를 도출합니다. 두 식을 연언으로 묶으면 R(a,c)∧Q(c)입니다.

존재 도입 규칙으로 ∃y(R(a,y)∧Q(y)), 곧 C를 얻습니다. C에는 c가 없으므로 신선성 조건을 지켜 존재 제거의 부분 증명을 닫고 원래 전제 Γ만으로 C를 얻었습니다.

정리하면 Γ ⊢ C입니다. 처음에는 전칭 제거와 조건문 제거로 요청 대상이 존재함을 얻고, 신선한 c로 존재 제거 부분 증명을 열어, 전칭 제거·조건문 제거·연언 도입·존재 도입으로 C를 증명했습니다.

모든 논리 규칙은 5~6편에서 건전성을 설명했습니다. 따라서 Γ ⊢ C라면 Γ ⊨ C입니다. 이 결론은 앞 절의 두 사람 모형뿐 아니라 Γ를 만족하는 모든 일차논리 모형에 해당합니다.

∃yR(a,y)에서 ∀yR(a,y)를 도출한다고 누군가 제안했다고 합시다. 영역을 D={아라,보라}, 상수 a를 아라, 관계 R을 {(아라,보라)}로 해석하면 존재문은 참입니다.

하지만 R(아라,아라)는 거짓이므로 전칭문은 거짓입니다. 따라서 ∃yR(a,y) ⊭ ∀yR(a,y)입니다. 하나의 반모형이 이 추론이 일반적으로 타당하지 않음을 보여 줍니다.

건전성은 증명에서 모든 모형의 귀결로 가는 방향입니다. 일차논리의 의미론적 완전성은 Γ ⊨ C ⇒ Γ ⊢ C라는 역방향을 보장합니다. Γ가 무한해도 하나의 형식 증명에 쓰이는 전제는 유한 개입니다.

우리가 직접 발견한 증명은 완전성 정리의 구체적 한 예가 됩니다. 완전성은 ‘어떤 증명을 반드시 금방 찾는다’는 실행 시간 보장을 주는 것은 아닙니다. 존재하는 증명을 유한 절차로 열거하는 일과 보편 판정은 구별합니다.

12편의 콤팩트성은 문장 집합의 모든 유한 부분이 만족 가능하면 전체도 만족 가능하다고 말합니다. 13편의 뢴벤하임–스콜렘 정리는 언어의 크기와 무한 모형의 존재에 따라 크기가 다른 모형을 얻는 조건을 설명합니다.

14편에서는 표준 자연수에서 참인 문장 전체 Th(ℕ)에도 비표준 모형이 있음을 보았습니다. 이런 정리들은 오늘의 짧은 유한 증명과 경쟁하는 설명이 아니라, 일차논리로 표현할 수 있는 구조들의 범위를 다루는 별도 질문입니다.

명제논리의 유한 진리표는 타당성을 결정하지만, 일반 일차논리의 타당성은 반결정 가능하며 결정 불가능합니다. 16편의 괴델–로서 제1불완전성은 일관성·효과적 공리화·기초 산술 Q의 포함을 만족하는 이론 T 안에서 결정되지 않는 산술 문장이 존재한다는 별도 정리입니다.

두 정리를 ‘논리로 아무것도 증명할 수 없다’는 뜻으로 연결하면 잘못입니다. 우리가 방금 Γ에서 C를 증명했고, 많은 이론의 정리들이 정확하게 도출됩니다. 각 정리의 문제와 조건을 먼저 확인하면 서로 다른 한계를 구별할 수 있습니다.

일차논리 모형의 영역·함수·관계를 정의했듯이, 양상논리에서는 W·R·V와 현재 세계를 명시합니다. □p는 모든 접근 세계, ◇p는 적어도 하나의 접근 세계를 뜻합니다.

□p→p가 타당하려면 반사적 프레임 조건이 필요합니다. 시간·지식·의무마다 R의 해석이 다를 수 있으므로 한 분야의 기본 가정을 다른 분야에 아무 조건 없이 옮길 수 없습니다. 오늘의 최종 습관은 ‘어느 언어, 어느 모형, 어느 증명 체계, 어느 적용 조건인가?’를 차례로 밝히는 것입니다.