구조 (논리학)

모형 이론에서 **구조**(構造, structure)는 어떤 주어진 1차 논리 언어의 해석을 갖춘 집합이다.
# 정의
자연수(음이 아닌 정수)의 집합을 \mathbb N이라고 쓰자. **부호수**(符號數, signature) (F,R,\operatorname{arity}_F,\operatorname{arity}_R)는 다음과 같은 튜플이다. * F는 집합이다. F의 원소를 **연산**(演算, operation)이라고 한다. * R는 집합이다. R의 원소를 **관계**(關係, relation)라고 한다. * \operatorname{arity}_F\colon F\to\mathbb N는 함수이다. f\in F에 대하여 \operatorname{arity}_F(f)=n이라면, f를 **n항 연산**(n-ary operation)이라고 한다. * \operatorname{arity}_R\colon R\to\mathbb N는 함수이다. r\in R에 대하여 \operatorname{arity}_R(r)=n이라면, r를 **n항 관계**(n-ary relation)라고 한다. 부호수 (F,R,\operatorname{arity}_F,\operatorname{arity}_R)의 **구조** (M,F_M^n,R_M^n)_{n\in\mathbb N}는 다음과 같은 튜플이다. * M은 집합이다. 이를 구조의 **전체**(全體, universe)라고 한다. * 각 n\in\mathbb N에 대하여, F_M^n\colon\operatorname{arity}_F^{-1}(n)\to M^{M^n}이다. f\in \operatorname{arity}_F^{-1}(n)에 대하여, F_M^n(f)\colon M^{\operatorname{arity}_F(f)}\to M을 보통 f_M이라고 쓰며, n항 연산 f의 M에서의 **해석**(解釋, interpretation)이라고 한다. * 각 n\in\mathbb N에 대하여, R_M^n\colon\operatorname{arity}_R^{-1}(n)\to\mathcal P(M^n)이다. r\in\operatorname{arity}_R^{-1}(n)에 대하여, R_M^n(r)\subset M^{\operatorname{arity}_R(r)}을 보통 r_M이라고 쓰며, n항 관계 r의 M에서의 **해석**(解釋, interpretation)이라고 한다. 관계를 포함하지 않는 부호수를 **대수적 부호수**(algebraic signature)라고 하고, 대수적 부호수의 구조를 **대수 구조**라고 한다.
# 언어
부호수 (F,R,\operatorname{arity}_F,\operatorname{arity}_R)의 (1차 논리) **언어**(言語, language) \mathcal L은 **공식**(公式, formula)과 **항**(項, term)으로 구성된다. \mathcal L의 **항**은 다음과 같이 재귀적으로 정의된다. * 변수 x_i는 항이다 (i\in\mathbb N). * 항 t_1,\dots,t_n 및 n항 연산 f\in F에 대하여, f(t_1,\dots,t_n)은 항이다. \mathcal L의 **공식**은 다음과 같이 재귀적으로 정의된다. * 항 t_1,\dots,t_n 및 n항 관계 r\in R에 대하여, r(t_1,\dots,t_n)는 공식이다. * 항 t_1,t_2에 대하여, t_1=t_2는 공식이다. * 공식 \phi에 대하여, \lnot\phi는 공식이다. * 공식 \phi 및 \psi에 대하여, 만약 \phi에 등장하는 제한 변수가 \psi에 등장하지 않으며, 마찬가지로 \psi에 등장하는 제한 변수가 \phi에 등장하지 않는다면, \phi\land\psi는 공식이다. * 변수 x_i 및 공식 \phi에 대하여, 만약 \phi가 이미 \forall x_i\colon를 포함하지 않는다면, \forall x_i\colon\phi는 공식이다. 만약 \phi 속에 변수 x_i가 등장하지만 \forall x_i\colon가 등장하지 않는다면, x_i를 **자유 변수**(自由變數, free variable)라고 하고, \forall x_i\colon가 등장한다면 x_i를 **제한 변수**(制限變數, bound variable)라고 한다. 자유 변수가 없는 공식을 **문장**(文章, sentence)이라고 한다. 문장들의 집합을 **이론**(理論, theory)이라고 한다.
# 만족
부호수 \sigma의 언어에 속하는 공식 \phi가 n개의 자유 변수 \vec x=(x_1,\dots,x_n)을 갖는다고 하자. 부호수 \sigma의 구조 M 및 \vec a\in M^n에 대하여, 다음과 같이 재귀적으로 정의되는 조건이 성립한다면, M이 \phi를 치환 \vec x\mapsto\vec a 아래 **만족시킨다**(滿足시킨다, satisfy)고 하고, M\models\phi[\vec a/\vec x]라고 쓴다. 여기서 부호수의 언어의 논리 기호 =, \lnot, \land, \forall은 메타 언어의 논리 기호와 구별하기 위하여 괄호 \langle\cdots\rangle 속에 적었다. * M\models\langle t_1=t_2\rangle[\vec a/\vec x]\iff t_1[\vec a/\vec x]=t_2[\vec a/\vec x]. 여기서 t[\vec a/\vec x]는 항 t 속에 등장하는 모든 변수 x_i를 이에 대응하는 a_i로 치환하고, t 속에 등장하는 모든 연산 f\in F를 f_M으로 치환하여 얻은 원소 \in M이다. * M\models\langle R(t_1,\dots,t_n)\rangle[\vec a/\vec x]\iff R_M(t_1[\vec a/\vec x],\dots,t_n[\vec a/\vec x]) * M\models\langle\phi\land\chi\rangle\iff(M\models\phi)\land(M\models\chi) * M\models\langle\lnot\phi\rangle\iff\lnot(M\models\phi) * M\models\langle\forall y\colon\phi(y)\rangle[\vec a/\vec x]\iff\forall b\in M\colon M\models\phi[(\vec a,b)/(\vec x,y)] 부호수 \sigma의 언어에서, n개의 자유 변수 \vec x를 갖는 공식 \phi에 대하여, 만약 M\models\phi[\vec a/\vec x]인 \sigma-구조 M 및 \vec a\in M^n이 존재한다면, \phi를 **만족 가능 공식**(滿足可能命題, satisfiable formula)이라고 한다. 이론 \mathcal T의 **모형**(模型, model)은 모든 \phi\in\mathcal T에 대하여 M\models\phi인 \sigma-구조 M이다. 모형을 갖는 이론을 **만족 가능 이론**(滿足可能理論, satisfiable theory)이라고 한다. (이는 만족 가능 문장들로 구성된 이론보다 강한 조건이다.)