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