모든 대상에 관한 사실을 한 대상에 적용해도 되나요?

네. “모든 사람이 모자를 썼다. 그러므로 아라도 모자를 썼다.”를 생각해 보세요. 아라가 우리가 이야기하는 사람들 안에 있다면, 앞의 말을 참으로 두면서 뒤의 말을 거짓으로 만들 수 있을까요?

세 사람을 한꺼번에 다루는 사실이 참이면 그 안의 아라에게도 같은 사실을 적용할 수 있습니다. 오늘의 규칙은 이 이유를 증명에 쓸 수 있게 정리한 것입니다. 다른 사람이 몇 명 더 있는 영역에서도 아라가 그 영역에 속한다면 같은 설명이 성립합니다.

증명의 새 줄에서 “모든 x”를 특정한 대상 하나로 구체화한다는 뜻입니다. 전제였던 원래 줄은 남아 있습니다. ∀xP(x)에서 x 자리에 a를 넣어 P(a)를 새로 적을 수 있습니다.

규칙의 짧은 표시는 ∀E입니다. ∀는 전칭양화사이고, E는 제거를 뜻하는 영어 elimination의 첫 글자입니다. “∀E 1”이라고 적으면 “1줄의 전칭문을 적용했다”는 뜻입니다. 규칙 이름을 외우기보다 어떤 대상에게 적용했는지부터 말해 보세요.

그렇습니다. 전제는 한 번 쓰면 없어지는 물건이 아닙니다. 같은 전칭문에서 필요한 대상들의 사례를 여러 번 얻을 수 있습니다.

그 양화사가 맡은 두 자리를 모두 같은 이름 a로 바꿉니다. R(a,a)가 됩니다. R의 첫 자리는 이름을 기억하는 사람이고 둘째 자리는 그 이름의 주인입니다. 따라서 “아라는 아라의 이름을 기억한다”라는 뜻입니다.

맞습니다. 원래 식은 각 사람이 자기 이름을 기억한다는 내용이었습니다. 두 x를 서로 다른 이름으로 바꾸면 원래 주어진 관계가 달라집니다. 모든 사람이 자기 이름만 기억하는 세계에서는 ∀xR(x,x)가 참이어도 R(a,b)는 거짓입니다.

네. ∀x(P(x) ∧ ∃xQ(x))를 보겠습니다. 맨 앞의 ∀x가 맡는 것은 P(x)의 x입니다. ∃xQ(x) 안의 x는 안쪽 ∃x가 맡습니다. 바깥 ∀x를 아라에게 적용하면 P(a) ∧ ∃xQ(x)를 얻습니다.

정확히는, 맨 앞 ∀x를 벗긴 뒤 남는 부분에서 자유롭게 나타나는 x를 모두 바꿉니다. 여기서 “자유”는 그 남은 부분을 기준으로 합니다. 식 전체에서는 P(x)의 x도 바깥 ∀x에 속박되어 있었습니다.

먼저 모든 학생에 관한 규칙을 아라에게 적용합니다. 그러면 Q(a) → P(a), “아라가 학생이면 아라는 모자를 썼다”를 얻습니다. 여기에 이미 주어진 Q(a)를 함께 사용하면 P(a)가 나옵니다.

기초에서 배운 조건문 제거를 →E라고 적었습니다. 3줄은 아라에게 적용한 규칙이고, 2줄은 아라가 그 조건을 만족한다는 사실입니다. 둘을 함께 사용해야 4줄을 얻습니다.

그 전제만으로는 학생이 존재하는지까지 알 수 없습니다. 사람은 있는 모임이지만 학생 참여자는 없을 수도 있습니다. 영역은 비어 있지 않아도 Q에 해당하는 사람은 한 명도 없을 수 있습니다.

이 세계의 ∀x(Q(x) → P(x))는 참입니다. 학생인데 모자를 쓰지 않은 사람이 없기 때문입니다. 그러나 P(a)도 Q(a)도 거짓입니다. 따라서 이 전제만으로 둘 중 어느 것도 따로 얻을 수 없습니다.

네. 전칭 제거로 얻을 수 있습니다. 이 비교 세계에서는 그 조건문의 앞부분 Q(a)가 거짓이므로 조건문 전체가 참입니다. 전칭 제거 규칙은 그대로 작동합니다.

이번에는 ∀x∀yR(x,y)가 전제로 주어졌다고 하겠습니다. 모든 사람이 모든 사람의 이름을 기억한다는 뜻입니다. 먼저 바깥 x에 a를 적용합니다. 그 결과는 ∀yR(a,y)입니다. 아라가 모든 사람의 이름을 기억한다는 말이지요.

그렇습니다. 첫 적용은 기억하는 사람을 아라로 고정합니다. 둘째 적용은 기억하는 이름의 주인을 보라로 고정합니다. x와 y가 서로 다른 변수이므로, 각각에게 다른 사람을 고를 수 있습니다. 두 자리에 같은 아라를 골라 R(a,a)를 얻는 것도 가능합니다.

전칭 제거로 할 수 있는 첫 단계는 ∃yR(a,y)까지입니다. “아라가 이름을 기억하는 사람이 적어도 한 명 있다”는 뜻입니다. 남은 ∃y는 그 사람이 보라라고 알려 주지 않습니다.

예를 들어 아라는 자기 이름만, 보라는 자기 이름만, 찬우는 자기 이름만 기억한다고 정할 수 있습니다. ∀x∃yR(x,y)는 참이고 ∃yR(a,y)도 참입니다. 하지만 R(a,b)는 거짓입니다. 11편에서 익힌 반모형으로 잘못된 다음 단계를 확인한 셈입니다.

전칭 제거는 그 줄 전체가 전칭문일 때 적용합니다. (∀xP(x)) ∧ Q(a)는 가장 바깥 기호가 ∧입니다. 먼저 연언 제거로 ∀xP(x)를 별도 줄에 꺼내고, 그다음 전칭 제거를 적용할 수 있습니다.

∨는 어느 한쪽만 참이어도 참입니다. 따라서 그 식만으로 왼쪽 ∀xP(x)를 꺼낼 수 없습니다. 아라는 학생이고 아무도 모자를 쓰지 않은 세계를 떠올려 보세요. 전체 ∨ 문장은 참이지만 P(b)는 거짓입니다.

다시 ∀x∃yR(x,y)를 보겠습니다. 바깥 ∀x를 적용하면서 x 자리에 y를 그냥 넣으면 ∃yR(y,y)가 됩니다. 새로 넣은 y까지 안쪽 ∃y가 맡아 버렸습니다. 이 현상을 변수 포획이라고 합니다.

마지막 식의 뜻은 “지금 y에 배정된 사람이 누군가의 이름을 기억한다”입니다. y에 아라를 배정하면 보라를, y에 보라를 배정하면 아라를 z의 증거로 고를 수 있습니다. 누구를 y에 배정하든 원래의 “각 사람마다 누군가”라는 뜻을 유지합니다.

정확한 조건은 이렇습니다. 대입한 변수의 출현이, 원래 그 자리를 둘러싸던 다른 양화사에 새로 속박되면 안 됩니다. 교재에서는 이를 그 자리에 자유롭게 대입 가능하다고 표현합니다. a·b·c 같은 이름에는 변수 글자가 들어 있지 않아 이 종류의 포획이 생기지 않습니다.

증명은 전제가 참이라면 결론도 참이어야 한다는 연결을 보여 줍니다. 실제 모임에서 모든 사람이 모자를 썼는지는 관찰이나 다른 근거로 확인해야 합니다. 전제를 단순히 적었다는 이유로 실제 사실이 되는 것은 아닙니다.

네. 이 수업의 표는 우리가 정한 가상 세계를 완전히 설명합니다. 실제 생활에서는 정보가 부족할 수 있습니다. “모자를 썼는지 모른다”와 “모자를 쓰지 않았다”도 구별해야 합니다. 전칭 제거는 모르는 사실을 임의로 참으로 채워 주는 규칙이 아닙니다.

1줄에 b를 대입하면 조건문의 앞뒤가 함께 남아 Q(b) → P(b)가 됩니다. ∀E만으로 조건문의 앞부분을 없앨 수는 없습니다. 그 조건문을 새 3줄로 쓰고, 2줄과 함께 →E를 사용한 P(b)를 4줄에 적으면 됩니다.

그렇습니다. 익숙해지면 여러 단계를 줄여 적기도 하지만, 배우는 동안에는 서로 다른 규칙을 한 줄에 숨기지 않는 편이 좋습니다. 뒤에서 가정의 범위를 다룰 때에도 이 습관이 도움이 됩니다.

먼저 그 줄 전체가 ∀로 묶였는지 봅니다. 그렇다면 그 ∀가 맡은 자리를 찾고, 적용할 이름 하나를 고릅니다. 그 자리들을 같은 이름으로 바꾸면서 다른 이름·안쪽 양화사·연결사는 보존합니다. 마지막으로 얻은 식을 말로 읽어 뜻이 이어지는지 확인하세요.