뢰벤하임-스콜렘 정리

위키백과, 우리 모두의 백과사전.
Chobot (토론 | 기여)님의 2013년 3월 16일 (토) 07:45 판 (봇:인터위키 링크 14 개가 위키데이터의 Q1068283 항목으로 옮겨짐. 이동 완료.; 예쁘게 바꿈)

뢰벤하임-스콜렘 정리(Löwenheim - Skolem theorem, -定理)는 수리논리학의 정리로, 독일 수리논리학자 레오폴트 뢰벤하임(Leopold Löwenheim)과 노르웨이 수리논리학자 토랄프 스콜렘(Thoralf Skolem)의 이름이 붙어 있다. 1915년 처음 제출되었다.[1]

공식화

일차 논리학

뢰벤하임-스콜렘 정리의 기본적인 형식은 1915년 처음 증명된 다음 두 명제를 이른다.[1] 이 정리는 일차 논리학에서 성립한다.

  1. G가 가산 언어 상에서 정의된 충족가능한 논리식들의 집합이라 하자. 그러면, G는 어떤 가산 구조 상에서 충족가능하다.
  2. S가 가산 언어 상에서 정의된 문장[2]들의 집합이라 하자. 만약 S가 모형을 가지면, S는 가산 모형을 가진다.

이 정리의 보다 일반화된 형식은 다음과 같다.[3]

  1. G가 기수 l을 갖는 언어 상에서 정의된 충족가능한 논리식들의 집합이라 하자. 그러면, G는 어떤 l보다 크지 않은 기수를 갖는 구조 상에서 충족가능하다.
  2. S가 기수 l을 갖는 언어 상에서 정의된 문장들의 집합이라 하자. 만약 S가 모형을 가지면, S는 기수가 l보다 크지 않은 모형을 가진다.

뢰벤하임-스콜렘-타르스키 정리

다음 정리는 뢰벤하임-스콜렘 정리에 폴란드 논리학자 알프레트 타르스키(Alfred Tarski)의 이름이 붙어 '뢰벤하임-스콜렘-타르스키 정리'(LST 정리)라 불린다.[4] 이 정리 역시 일차 논리학에서 성립한다.

  1. G가 기수 l을 갖는 언어 상에서 정의된 논리식들의 집합이라 하자. 만약 G가 어떤 무한 구조 상에서 충족가능하다면, l보다 작지 않은 모든 기수 k에 대하여, G가 충족가능한 기수 k의 구조가 존재한다.

위의 뢰벤하임-스콜렘 정리 형식을 '아래쪽'(downward) 형식이라 하고, 이 LST 정리를 '위쪽'(upward) 형식이라 부르기도 한다. 보통 뢰벤하임-스콜렘 정리는 위의 아래쪽 형식을 의미한다.[4]

이차 논리학

뢰벤하임-스콜렘 정리는 이차 논리학에서도 성립하는 정리이다. 이차 논리학에서 이 정리는 다음과 같이 쓸 수 있다.[5]

  1. S가 가산 이차 언어 상에서 정의된 문장들의 집합이라 하자. 만약 S가 일반 모형(general model)을 가지면, S는 가산 일반 모형을 가진다.

주석

  1. ↑ 가 나 Herbert B. Enderton (2002), A mathematical introduction to logic, Academic Press(Elsevier), p. 151.
  2. ↑ 자유변수를 갖지 않는 정식.
  3. ↑ Ibid. , p. 153.
  4. ↑ 가 나 Ibid. , p. 154.
  5. ↑ Ibid. , p. 302.

참고 문헌

  • Herbert B. Enderton (2002), A mathematical introduction to logic, Academic Press(Elsevier)
원본 주소 "https://ko.wikipedia.org/w/index.php?title=뢰벤하임-스콜렘_정리&oldid=10438170"