구조 (논리학) 문서 원본 보기

{{위키데이터 속성 추적}}
[[모형 이론]]에서 '''구조'''(構造, {{llang|en|structure}})는 어떤 주어진 [[1차 논리]] 언어의 해석을 갖춘 집합이다.

== 정의 ==
[[자연수]](음이 아닌 [[정수]])의 집합을 <math>\mathbb N</math>이라고 쓰자.

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

부호수 <math>(F,R,\operatorname{arity}_F,\operatorname{arity}_R)</math>의 '''구조''' <math>(M,F_M^n,R_M^n)_{n\in\mathbb N}</math>는 다음과 같은 [[튜플]]이다.
* <math>M</math>은 [[집합]]이다. 이를 구조의 '''전체'''(全體, {{llang|en|universe}})라고 한다.
* 각 <math>n\in\mathbb N</math>에 대하여, <math>F_M^n\colon\operatorname{arity}_F^{-1}(n)\to M^{M^n}</math>이다. <math>f\in \operatorname{arity}_F^{-1}(n)</math>에 대하여, <math>F_M^n(f)\colon M^{\operatorname{arity}_F(f)}\to M</math>을 보통 <math>f_M</math>이라고 쓰며, <math>n</math>항 연산 <math>f</math>의 <math>M</math>에서의 '''해석'''(解釋, {{llang|en|interpretation}})이라고 한다.
* 각 <math>n\in\mathbb N</math>에 대하여, <math>R_M^n\colon\operatorname{arity}_R^{-1}(n)\to\mathcal P(M^n)</math>이다. <math>r\in\operatorname{arity}_R^{-1}(n)</math>에 대하여, <math>R_M^n(r)\subset M^{\operatorname{arity}_R(r)}</math>을 보통 <math>r_M</math>이라고 쓰며, <math>n</math>항 관계 <math>r</math>의 <math>M</math>에서의 '''해석'''(解釋, {{llang|en|interpretation}})이라고 한다.

관계를 포함하지 않는 부호수를 '''대수적 부호수'''({{llang|en|algebraic signature}})라고 하고, 대수적 부호수의 구조를 '''[[대수 구조]]'''라고 한다.

== 언어 ==
부호수 <math>(F,R,\operatorname{arity}_F,\operatorname{arity}_R)</math>의 ([[1차 논리]]) '''언어'''(言語, {{llang|en|language}}) <math>\mathcal L</math>은 '''공식'''(公式, {{llang|en|formula}})과 '''항'''(項, {{llang|en|term}})으로 구성된다. <math>\mathcal L</math>의 '''항'''은 다음과 같이 재귀적으로 정의된다.
* 변수 <math>x_i</math>는 항이다 (<math>i\in\mathbb N</math>).
* 항 <math>t_1,\dots,t_n</math> 및 <math>n</math>항 연산 <math>f\in F</math>에 대하여, <math>f(t_1,\dots,t_n)</math>은 항이다.
<math>\mathcal L</math>의 '''공식'''은 다음과 같이 재귀적으로 정의된다.
* 항 <math>t_1,\dots,t_n</math> 및 <math>n</math>항 관계 <math>r\in R</math>에 대하여, <math>r(t_1,\dots,t_n)</math>는 공식이다.
* 항 <math>t_1,t_2</math>에 대하여, <math>t_1=t_2</math>는 공식이다.
* 공식 <math>\phi</math>에 대하여, <math>\lnot\phi</math>는 공식이다.
* 공식 <math>\phi</math> 및 <math>\psi</math>에 대하여, 만약 <math>\phi</math>에 등장하는 제한 변수가 <math>\psi</math>에 등장하지 않으며, 마찬가지로 <math>\psi</math>에 등장하는 제한 변수가 <math>\phi</math>에 등장하지 않는다면, <math>\phi\land\psi</math>는 공식이다.
* 변수 <math>x_i</math> 및 공식 <math>\phi</math>에 대하여,  만약 <math>\phi</math>가 이미 <math>\forall x_i\colon</math>를 포함하지 않는다면, <math>\forall x_i\colon\phi</math>는 공식이다.
만약 <math>\phi</math> 속에 변수 <math>x_i</math>가 등장하지만 <math>\forall x_i\colon</math>가 등장하지 않는다면, <math>x_i</math>를 '''자유 변수'''(自由變數, {{llang|en|free variable}})라고 하고, <math>\forall x_i\colon</math>가 등장한다면 <math>x_i</math>를 '''제한 변수'''(制限變數, {{llang|en|bound variable}})라고 한다. 자유 변수가 없는 공식을 '''문장'''(文章, {{llang|en|sentence}})이라고 한다. 문장들의 집합을 '''이론'''(理論, {{llang|en|theory}})이라고 한다.

== 만족 ==
부호수 <math>\sigma</math>의 언어에 속하는 공식 <math>\phi</math>가 <math>n</math>개의 자유 변수 <math>\vec x=(x_1,\dots,x_n)</math>을 갖는다고 하자. 부호수 <math>\sigma</math>의 구조 <math>M</math> 및 <math>\vec a\in M^n</math>에 대하여, 다음과 같이 재귀적으로 정의되는 조건이 성립한다면, <math>M</math>이 <math>\phi</math>를 치환 <math>\vec x\mapsto\vec a</math> 아래 '''만족시킨다'''(滿足시킨다, {{llang|en|satisfy}})고 하고, <math>M\models\phi[\vec a/\vec x]</math>라고 쓴다. 여기서 부호수의 언어의 논리 기호 <math>=</math>, <math>\lnot</math>, <math>\land</math>, <math>\forall</math>은 메타 언어의 논리 기호와 구별하기 위하여 괄호 <math>\langle\cdots\rangle</math> 속에 적었다.
* <math>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]</math>. 여기서 <math>t[\vec a/\vec x]</math>는 항 <math>t</math> 속에 등장하는 모든 변수 <math>x_i</math>를 이에 대응하는 <math>a_i</math>로 치환하고, <math>t</math> 속에 등장하는 모든 연산 <math>f\in F</math>를 <math>f_M</math>으로 치환하여 얻은 원소 <math>\in M</math>이다.
* <math>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])</math>
* <math>M\models\langle\phi\land\chi\rangle\iff(M\models\phi)\land(M\models\chi)</math>
* <math>M\models\langle\lnot\phi\rangle\iff\lnot(M\models\phi)</math>
* <math>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)]</math>
부호수 <math>\sigma</math>의 언어에서, <math>n</math>개의 자유 변수 <math>\vec x</math>를 갖는 공식 <math>\phi</math>에 대하여, 만약 <math>M\models\phi[\vec a/\vec x]</math>인 <math>\sigma</math>-구조 <math>M</math> 및 <math>\vec a\in M^n</math>이 존재한다면, <math>\phi</math>를 '''만족 가능 공식'''(滿足可能命題, {{llang|en|satisfiable formula}})이라고 한다.

이론 <math>\mathcal T</math>의 '''모형'''(模型, {{llang|en|model}})은 모든 <math>\phi\in\mathcal T</math>에 대하여 <math>M\models\phi</math>인 <math>\sigma</math>-구조 <math>M</math>이다. 모형을 갖는 이론을 '''만족 가능 이론'''(滿足可能理論, {{llang|en|satisfiable theory}})이라고 한다. (이는 만족 가능 문장들로 구성된 이론보다 강한 조건이다.)

== 참고 문헌 ==
* {{서적 인용 | last=Marker | first=David | title=Model theory: an introduction | publisher=Springer | isbn=978-0-387-98760-6 | 날짜=2002 | doi = 10.1007/b98860 |총서=Graduate Texts in Mathematics|권=217|issn=0072-5285|zbl=1003.03034|언어=en}}
* {{서적 인용 | last=Poizat | first=Bruno | title=A course in model theory: an introduction to contemporary mathematical logic | url=https://archive.org/details/courseinmodelthe0000poiz | publisher=Springer | 날짜=2000 | 총서=Universitext|기타=Moses Klein 역|isbn= 978-1-4612-6446-0|doi=10.1007/978-1-4419-8622-1|issn=0172-5939|zbl=0951.03002|언어=en}}

== 외부 링크 ==
* {{eom|title=Algebraic system}}
* {{eom|title=Structure}}
* {{eom|title=Interpretation}}
* {{매스월드|id=Structure|title=Structure}}
* {{매스월드|id=Model|title=Model}}
* {{매스월드|id=Interpretation|title=Interpretation}}
* {{매스월드|id=Satisfiable|title=Satisfiable}}
* {{매스월드|id=Unsatisfiable|title=Unsatisfiable}}

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