열린 식의 참거짓은 어떻게 정하나요?

P가 어떤 성질을 뜻하는지, 그 성질을 가진 대상이 누구인지, 그리고 x가 지금 누구를 맡는지 알아야 합니다. 앞의 두 정보는 구조 M에, 마지막 정보는 변수 배정 g에 담겠습니다. 중급에서 작은 세계를 만들던 방법을 더 정확히 적는 것입니다.

네. 열린 식의 만족 여부는 구조와 배정을 함께 정해 말합니다. “열린 식은 참거짓을 전혀 다룰 수 없다”는 뜻으로 이해할 필요는 없습니다. 어떤 구조의 어떤 배정에서 평가하는지를 붙여 주면 됩니다.

대상의 집합과 기호의 해석을 묶어 적습니다. 이번 편에서 사용할 언어의 비논리 기호는 이름 a·b·k, 한 자리 함수기호 f, 한 자리 술어 P·Q, 두 자리 술어 R입니다. 동일성 기호 =는 두 항의 값이 같은 대상인지 판단하는 표준 뜻으로 사용합니다.

이 구조는 관계를 완전히 지정했습니다. 표에 쓴 세 쌍에서만 R이 성립하고 나머지 쌍에서는 성립하지 않습니다. 실제 기록이 불완전한 상황에서는 “목록에서 못 찾았다”와 “관계가 없다”를 따로 구별해야 하지만, 지금은 가상 해석의 정의가 모두 주어졌습니다.

R(x,y)는 두 대상 사이의 관계가 성립하는지를 묻는 식입니다. f(x)는 한 대상을 입력하여 그 대상에게 지정된 연락인 한 사람을 가리키는 항입니다. f(x) 자체를 참 또는 거짓이라고 평가하지 않습니다.

현재의 표준 의미론에서 함수기호는 영역의 모든 입력에 값이 있어야 합니다. 연락인이 없거나 여러 명인 실제 자료를 표현하려면 그 자료에 맞는 관계 술어를 쓰거나, 어떤 한 연락인을 지정하는 별도 약속이 필요합니다. 값이 빠진 표를 이 과정의 전체 함수 해석이라고 할 수는 없습니다.

평가할 때 서로 다른 역할을 구별하려고 나눕니다. a의 값은 구조 M이 정한 aᴹ입니다. x의 값은 배정 g가 정한 g(x)입니다. 구조를 고정한 채 다른 배정 h를 선택해도 aᴹ는 그대로지만 h(x)는 달라질 수 있습니다.

정의상 배정은 모든 변수에서 D로 가는 함수입니다. 기호로 g: 변수들의 집합→D라고 씁니다. 식이 실제로 사용하는 변수는 유한하게 적혀 있지만, 배정을 처음부터 모든 변수에 정의해 두면 양화사와 더 큰 식을 같은 규칙으로 평가하기 편합니다.

안쪽부터 계산합니다. ⟦t⟧ᴹ,g라는 표시는 “구조 M과 배정 g에서 항 t가 가리키는 대상”입니다. 오른쪽의 M,g는 어떤 세계와 배정으로 계산했는지를 기억시키는 표시입니다.

네. 각 입력 항의 값을 먼저 구한 다음, 구조가 그 함수기호에 부여한 함수를 그 값들의 순서쌍이나 순서튜플에 적용합니다. 두 자리 함수라면 D의 모든 순서쌍마다 D의 결과가 하나 정해져 있어야 합니다. 이번 계산은 한 자리 f로 충분히 연습하겠습니다.

먼저 f(x)의 값인 보라를 구합니다. 그다음 보라가 Pᴹ에 들어 있는지 확인합니다. 이번 Pᴹ에는 아라와 찬우만 있으므로 보라는 포함되지 않습니다. 따라서 기본 배정에서 P(f(x))는 거짓입니다.

그렇습니다. M,g⊨A는 “M과 g에서 식 A가 만족된다”고 읽습니다. 만족되지 않을 때는 M,g⊭A라고 씁니다. 고전 이값 해석에서는 전자가 참인 경우와 후자가 참인 경우가 정확히 나뉩니다. ⊨는 여기서 식 자체의 기호가 아니라, 식이 만족되는지를 설명하는 기호입니다.

이미 구한 작은 식의 값을 연결하면 됩니다. 같은 M,g에서 P(f(x))는 거짓이고 R(x,y)는 참입니다. ∨는 적어도 한쪽이 참일 때 참이므로 전체 식도 참입니다. 여기서 한쪽만 다른 배정으로 계산하면 안 됩니다.

그때 사용할 표기가 g[x↦d]입니다. d는 여기서 영역 안의 한 대상을 대신 부르는 설명용 표시입니다. 이 배정은 x에 d를 주고, 다른 변수에는 g와 같은 값을 줍니다. 이름이나 함수의 해석은 구조 M에 남아 있으므로 바뀌지 않습니다.

원래 g를 잃어버리지 않는 새 배정이라고 생각하세요. g와 g[x↦찬우]를 나란히 놓고 비교할 수 있습니다. 새 배정이 필요한 부분식 안에서 그것을 사용하며, 다른 부분식을 평가할 때는 그 부분이 요구하는 배정을 다시 확인합니다.

∃x가 맡는 것은 x의 값입니다. y는 자유롭게 남으므로 기본 g(y)=보라를 유지합니다. x를 아라·보라·찬우로 각각 바꾸어 P(x)∧R(x,y)를 평가합니다.

아라를 넣은 갱신 배정에서 몸통이 참이므로 전체 존재식은 만족됩니다. 이를 일반적으로 쓰면, M,g⊨∃xA는 어떤 d∈D에 대해 M,g[x↦d]⊨A가 성립한다는 뜻입니다. 기호 ∈는 “그 집합에 속한다”는 말입니다.

이 식 전체에서 x는 ∃x에 묶여 있습니다. ∃x는 시작 배정의 x 값과 관계없이 모든 후보를 살필 수 있습니다. 기본 g 대신 x만 보라로 바꾼 h를 사용해도, 아라를 증거 대상으로 고를 수 있어 같은 결과입니다.

이번 유한한 구조에서는 그렇습니다. 일반적으로 M,g⊨∀xA는 모든 d∈D에 대해 M,g[x↦d]⊨A가 성립한다는 뜻입니다. 영역이 무한할 때에도 정의는 같습니다. 그때에는 전체에 적용되는 이유로 판단해야 할 수 있습니다.

맞습니다. 모든 대상을 요구하는 문장에는 한 반례가 충분합니다. 반대로 ∀x(f(f(f(x)))=x)는 이번 구조에서 참입니다. 어느 사람에서 시작해도 f를 세 번 적용하면 그 사람에게 돌아오기 때문입니다. 이 결과는 지금의 순환 함수에 관한 사실입니다.

식이 (∃xP(x))∧R(x,y)라면 그렇게 읽지 않습니다. 전체 연언의 두 부분은 각각 원래의 g에서 평가합니다. 왼쪽 ∃x의 몸통에 들어갈 때만 갱신 배정을 사용합니다. 오른쪽의 자유로운 x는 g(x)=아라를 유지합니다.

이 의미론은 g를 전역적으로 수정하는 실행 과정이 아닙니다. 해당 부분식에 넘겨 주는 배정을 구별하는 정의입니다. 표에서 쓴 “P(찬우의 대상)”은 평가 내용을 설명하는 말이며, 언어에 새 이름을 넣어 만든 식이라는 뜻은 아닙니다.

볼 수 있습니다. 관계 R의 행은 인사한 사람 x, 열은 인사를 받은 사람 y입니다. 양화사가 겹치면 바깥에서 x를 갱신하고 그 배정 아래에서 y를 갱신하는 식으로 읽습니다.

특정한 d와 e를 이미 정했다면 두 갱신은 같은 배정을 만듭니다. 하지만 양화문은 그 d와 e를 어떤 조건으로 고르는지까지 말합니다. “모든 d마다 어떤 e”와 “어떤 한 e가 모든 d에 대해”라는 선택 조건은 다릅니다. 갱신의 순서 교환만으로 양화사의 순서 교환을 정당화할 수 없습니다.

같은 구조를 유지한다면 식의 자유변수들에 준 값만 같아도 만족 여부가 같습니다. 이를 여기서는 배정의 일치 보조정리라고 부르겠습니다. 항의 값도 그 항에 등장하는 변수들의 값에만 의존합니다. 함수기호의 해석과 이름의 해석은 고정된 M에서 사용합니다.

∃x를 평가할 때 같은 후보 d를 양쪽에 넣어 보세요. g[x↦d]와 h[x↦d]는 x에 똑같은 d를 주고, 나머지 자유변수 y에도 같은 값을 줍니다. 몸통을 구성하는 작은 식들에서 결과가 같다는 가정을 적용할 수 있습니다. 따라서 한쪽에 증거 d가 있으면 다른 쪽에도 같은 d가 증거가 됩니다.

맞습니다. 두 배정이 일치해야 할 자유변수가 없으므로 일치 보조정리의 조건이 항상 충족됩니다. 닫힌 문장 A가 M에서 참일 때 M⊨A라고 쓰고 배정을 생략할 수 있습니다. 그 배정 독립성은 구조까지 무관하다는 뜻으로 넓어지지 않습니다.

타당성은 모든 허용 구조까지 살펴야 합니다. 같은 세 사람을 영역으로 두되 P의 외연을 공집합으로 바꾼 구조 N에서는 ∃xP(x)가 거짓입니다. 따라서 이 문장은 M에서 참이지만 타당하지는 않습니다. 반면 ∀x(x=x)는 표준 동일성 해석의 모든 구조에서 참입니다.

그 흐름을 붙잡으세요. 긴 식도 구조와 배정을 정확히 적은 뒤 작은 부분부터 계산하면 됩니다. 계산 중 양화사에 들어갈 때는 갱신한 배정을, 그 범위 밖에서는 해당 부분식의 원래 배정을 확인합니다.

다음 편에서는 x 자리에 a나 f(y) 같은 항을 써 넣는 일을 살펴보겠습니다. 식의 글자를 바꾸는 대입과 변수의 대상을 바꾸는 배정 갱신이 어떻게 연결되는지, 포획을 피해야 하는 이유까지 확인하겠습니다.