구조 (논리학)

모형 이론에서 구조

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

정의 편집

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

부호수(符號數, 영어: signature)  는 다음과 같은 튜플이다.

  •  집합이다.  의 원소를 연산(演算, 영어: operation)이라고 한다.
  •  집합이다.  의 원소를 관계(關係, 영어: relation)라고 한다.
  •  함수이다.  에 대하여  이라면,   항 연산(영어:  -ary operation)이라고 한다.
  •  함수이다.  에 대하여  이라면,   항 관계(영어:  -ary relation)라고 한다.

부호수  구조  는 다음과 같은 튜플이다.

  •  집합이다. 이를 구조의 전체(全體, 영어: universe)라고 한다.
  •  에 대하여,  이다.  에 대하여,  을 보통  이라고 쓰며,  항 연산   에서의 해석(解釋, 영어: interpretation)이라고 한다.
  •  에 대하여,  이다.  에 대하여,  을 보통  이라고 쓰며,  항 관계   에서의 해석(解釋, 영어: interpretation)이라고 한다.

관계를 포함하지 않는 부호수를 대수적 부호수(영어: algebraic signature)라고 하고, 대수적 부호수의 구조를 대수 구조라고 한다.

언어 편집

부호수  의 (1차 논리) 언어(言語, 영어: language)  공식(公式, 영어: formula)과 (項, 영어: term)으로 구성된다.  은 다음과 같이 재귀적으로 정의된다.

  • 변수  는 항이다 ( ).
  •   항 연산  에 대하여,  은 항이다.

 공식은 다음과 같이 재귀적으로 정의된다.

  •   항 관계  에 대하여,  는 공식이다.
  •  에 대하여,  는 공식이다.
  • 공식  에 대하여,  는 공식이다.
  • 공식   에 대하여, 만약  에 등장하는 제한 변수가  에 등장하지 않으며, 마찬가지로  에 등장하는 제한 변수가  에 등장하지 않는다면,  는 공식이다.
  • 변수   및 공식  에 대하여, 만약  가 이미  를 포함하지 않는다면,  는 공식이다.

만약   속에 변수  가 등장하지만  가 등장하지 않는다면,  자유 변수(自由變數, 영어: free variable)라고 하고,  가 등장한다면  제한 변수(制限變數, 영어: bound variable)라고 한다. 자유 변수가 없는 공식을 문장(文章, 영어: sentence)이라고 한다. 문장들의 집합을 이론(理論, 영어: theory)이라고 한다.

만족 편집

부호수  의 언어에 속하는 공식   개의 자유 변수  을 갖는다고 하자. 부호수  의 구조   에 대하여, 다음과 같이 재귀적으로 정의되는 조건이 성립한다면,   를 치환   아래 만족시킨다(滿足시킨다, 영어: satisfy)고 하고,  라고 쓴다. 여기서 부호수의 언어의 논리 기호  ,  ,  ,  은 메타 언어의 논리 기호와 구별하기 위하여 괄호   속에 적었다.

  •  . 여기서  는 항   속에 등장하는 모든 변수  를 이에 대응하는  로 치환하고,   속에 등장하는 모든 연산   으로 치환하여 얻은 원소  이다.
  •  
  •  
  •  
  •  

부호수  의 언어에서,  개의 자유 변수  를 갖는 공식  에 대하여, 만약   -구조   이 존재한다면,  만족 가능 공식(滿足可能命題, 영어: satisfiable formula)이라고 한다.

이론  모형(模型, 영어: model)은 모든  에 대하여   -구조  이다. 모형을 갖는 이론을 만족 가능 이론(滿足可能理論, 영어: satisfiable theory)이라고 한다. (이는 만족 가능 문장들로 구성된 이론보다 강한 조건이다.)

참고 문헌 편집

외부 링크 편집