구조 (논리학)

모형 이론에서 **구조**(構造, )는 어떤 주어진 1차 논리 언어의 해석을 갖춘 집합이다.

## 정의
자연수(음이 아닌 정수)의 집합을 \mathbb N이라고 쓰자.

**부호수**(符號數, ) (F,R,\operatorname{arity}_F,\operatorname{arity}_R)는 다음과 같은 튜플이다.
* F는 집합이다. F의 원소를 **연산**(演算, )이라고 한다.
* R는 집합이다. R의 원소를 **관계**(關係, )라고 한다.
* \operatorname{arity}_F\colon F\to\mathbb N는 함수이다. f\in F에 대하여 \operatorname{arity}_F(f)=n이라면, f를 **<math>n</math>항 연산**()이라고 한다.
* \operatorname{arity}_R\colon R\to\mathbb N는 함수이다. r\in R에 대하여 \operatorname{arity}_R(r)=n이라면, r를 **<math>n</math>항 관계**()라고 한다.

부호수 (F,R,\operatorname{arity}_F,\operatorname{arity}_R)의 **구조** (M,F_M^n,R_M^n)_{n\in\mathbb N}는 다음과 같은 튜플이다.
* M은 집합이다. 이를 구조의 **전체**(全體, )라고 한다.
* 각 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에서의 **해석**(解釋, )이라고 한다.
* 각 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에서의 **해석**(解釋, )이라고 한다.

관계를 포함하지 않는 부호수를 **대수적 부호수**()라고 하고, 대수적 부호수의 구조를 **[[대수 구조]]**라고 한다.

## 언어
부호수 (F,R,\operatorname{arity}_F,\operatorname{arity}_R)의 (1차 논리) **언어**(言語, ) \mathcal L은 **공식**(公式, )과 **항**(項, )으로 구성된다. \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를 **자유 변수**(自由變數, )라고 하고, \forall x_i\colon가 등장한다면 x_i를 **제한 변수**(制限變數, )라고 한다. 자유 변수가 없는 공식을 **문장**(文章, )이라고 한다. 문장들의 집합을 **이론**(理論, )이라고 한다.

## 만족
부호수 \sigma의 언어에 속하는 공식 \phi가 n개의 자유 변수 \vec x=(x_1,\dots,x_n)을 갖는다고 하자. 부호수 \sigma의 구조 M 및 \vec a\in M^n에 대하여, 다음과 같이 재귀적으로 정의되는 조건이 성립한다면, M이 \phi를 치환 \vec x\mapsto\vec a 아래 **만족시킨다**(滿足시킨다, )고 하고, 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를 **만족 가능 공식**(滿足可能命題, )이라고 한다.

이론 \mathcal T의 **모형**(模型, )은 모든 \phi\in\mathcal T에 대하여 M\models\phi인 \sigma-구조 M이다. 모형을 갖는 이론을 **만족 가능 이론**(滿足可能理論, )이라고 한다. (이는 만족 가능 문장들로 구성된 이론보다 강한 조건이다.)

## 참고 문헌
* 
* 

## 외부 링크
* 
* 
* 
* 
* 
* 
* 
* 

분류:모형 이론
분류:보편대수학
분류:수리논리학
분류:수학적 구조