구조 (논리학)

모형 이론에서, 구조(構造, 영어: 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 F\to \mathbb {N}$는 함수이다. $r\in R$에 대하여 $\operatorname {arity} _{R}(r)=n$이라면, $f$를 $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)이라고 한다.

관계를 포함하지 않는 형을 대수적 형이라고 하고, 대수적 형의 구조를 대수적 구조라고 한다.

형의 언어와 명제의 만족

형 $(F,R,\operatorname {arity} _{F},\operatorname {arity} _{R})$의 (1차 논리) 언어(영어: language) ${\mathcal {L}}$는 다음과 같이 재귀적으로 정의되는 명제들의 집합 및 항(영어: term)의 집합이다.

• 변수 $x_{i}$는 항이다 ($i\in \mathbb {N}$).
• 항 $t_{1},\dots ,t_{n}$ 및 $n$항 연산 $f\in F$에 대하여, $f(t_{1},\dots ,t_{n})$은 항이다.
• 항 $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 \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)라고 한다.

형 $\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$은 메타 언어의 논리 기호와 구별하기 위하여 따옴표 ${\text{'}}\cdots {\text{'}}$ 속에 적었다.

• $M\models {\text{'}}t_{1}=t_{2}{\text{'}}[{\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 R(t_{1},\dots ,t_{n})[{\vec {a}}/{\vec {x}}]\iff R_{M}(t_{1}/[{\vec {a}}/{\vec {x}}],\dots ,t_{n}[{\vec {a}}/{\vec {x}}])$
• $M\models {\text{'}}\phi \land \chi {\text{'}}\iff (M\models \phi )\land (M\models \chi )$
• $M\models {\text{'}}\forall y\colon \phi (y){\text{'}}[{\vec {a}}/{\vec {x}}]\iff \forall b\in M\colon M\models \phi [({\vec {a}},b)/({\vec {x}},y)]$

참고 문헌

• 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. 
• Poizat, Bruno (2000). 《A course in model theory: an introduction to contemporary mathematical logic》. Universitext. Springer. doi:10.1007/978-1-4419-8622-1. ISBN 978-1-4612-6446-0. ISSN 0172-5939. 

바깥 고리

• “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.