구조 (논리학)

모형 이론에서 구조(構造, 영어: 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)이라고 한다. (이는 만족 가능 문장들로 구성된 이론보다 강한 조건이다.)

참고 문헌

• Marker, David (2002). 《Model theory: an introduction》. Graduate Texts in Mathematics (영어) 217. Springer. doi:10.1007/b98860. ISBN 978-0-387-98760-6. ISSN 0072-5285. Zbl 1003.03034. 
• Poizat, Bruno (2000). 《A course in model theory: an introduction to contemporary mathematical logic》. Universitext (영어). Moses Klein 역. Springer. doi:10.1007/978-1-4419-8622-1. ISBN 978-1-4612-6446-0. ISSN 0172-5939. Zbl 0951.03002. 

외부 링크

• “Algebraic system”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Structure”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Interpretation”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Structure”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Model”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Interpretation”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Satisfiable”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Unsatisfiable”. 《Wolfram MathWorld》 (영어). Wolfram Research.