뢰벤하임-스콜렘 정리 문서 원본 보기

{{위키데이터 속성 추적}}
[[모형 이론]]에서 '''뢰벤하임-스콜렘 정리'''(Löwenheim-Skolem定理, {{llang|en|Löwenheim–Skolem theorem}})는 논리적 언어의 특정한 크기를 갖는 [[구조 (논리학)|모형]]의 존재에 대한 정리다. [[1차 논리]]의 중요한 특성 가운데 하나이다.

== 정의 ==
부호수 <math>\sigma</math>의 [[구조 (논리학)|구조]] <math>M</math>에 대하여, 다음 두 명제가 성립한다.<ref>{{서적 인용 | 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}}</ref>{{rp|44–48}}<ref name="Enderton"/>{{rp|151–154}}
* ('''상향 뢰벤하임-스콜렘 정리''' {{llang|en|upward Löwenheim–Skolem theorem}}) 만약 <math>|M|\ge\aleph_0</math>이라면, 모든 [[기수 (수학)|기수]] <math>\kappa\ge|M|+|\sigma|</math> 에 대하여, 다음 두 조건을 만족시키는 <math>\sigma</math>-[[구조 (논리학)|구조]] <math>N</math>이 존재한다.
** <math>|N|=\kappa</math>
** [[기본 매장]] <math>j\colon M\hookrightarrow N</math>이 존재한다.
* ('''하향 뢰벤하임-스콜렘 정리''' {{llang|en|downward Löwenheim–Skolem theorem}}) 모든 부분집합 <math>X\subset M</math>에 대하여, 다음 두 조건을 만족시키는 <math>\sigma</math>-구조 <math>N</math>이 존재한다.
** <math>|N|\le|X|+|\sigma|+\aleph_0</math>
** [[기본 매장]] <math>j\colon N\hookrightarrow M</math>이 존재하며, <math>X\subset j(N)\subset M</math>이다.
여기서 <math>|\sigma|</math>는 부호수 <math>\sigma</math>에 속한 연산의 [[집합의 크기]]와 관계의 [[집합의 크기]]의 합이다.

== 고차 논리에서의 부재 ==
표준 모형({{llang|en|standard model}})을 갖춘 [[고차 논리]]에서는 뢰벤하임-스콜렘 정리가 성립하지 않는다.<ref>{{서적 인용|장=Higher-order logic|이름=van Benthem|성=Johan|공저자=Kees Doets|장url=https://staff.science.uva.nl/j.vanbenthem/docs/HOL.pdf|제목=Handbook of philosophical logic, volume 1|출판사=Kluwer|쪽=189–243|날짜=2001|판=2판|doi=10.1007/978-94-015-9833-0_3|zbl=1003.03513|편집자=D. M. Gabbay, F. Guenthner|언어=en|access-date=2014-11-25|archive-date=2017-08-10|archive-url=https://web.archive.org/web/20170810035556/https://staff.science.uva.nl/j.vanbenthem/docs/HOL.pdf|url-status=dead}}</ref> 다만, 고차 논리에서 헹킨 모형({{llang|en|Henkin model}} 또는 {{llang|en|general model}})을 사용하면, 고차 논리는 사실상 [[1차 논리]]가 된다. 이 경우, 뢰벤하임-스콜렘 정리가 자명하게 적용된다.

== 증명 ==
뢰벤하임-스콜렘 정리는 다음과 같이 증명될 수 있다.

=== 하향 뢰벤하임-스콜렘 정리 ===
임의의 자연수 <math>n</math> 및 <math>M</math>의 각 1차 논리 명제 <math>\phi(x_1,\dots,x_n,y)</math>에 대하여, [[선택 공리]]를 사용하여 다음 성질을 만족시키는 함수 <math>f_\phi\colon M^n\to M</math>를 정의할 수 있다.
* <math>M\models\exists y\colon\phi(\vec x,f_\phi(\vec x))</math>이거나, 아니면 <math>M\models\lnot\exists y\colon\phi(\vec x,y)</math>이다.
이러한 함수를 '''스콜렘 함수'''({{llang|en|Skolem function}})
<math>X\subset M</math>에 대하여, 다음을 정의하자.
:<math>X_0=X</math>
:<math>X_{i+1}=\{f_\phi(\vec x)\colon n\in\mathbb N,\;\vec x\in M^n,\;\phi\in\sigma\}</math>
<math>\phi</math>를 <math>x=y</math>로 놓으면, <math>X_{i+1}\supset X_i</math>인 것을 알 수 있다. 또한,
:<math>|X_i|\le |X_{i+1}|\le|X_i|+|\sigma|+\aleph_0</math>
이다. 그렇다면
:<math>N=\bigcup_{i\in\mathbb N}X_i\supset X</math>
는 타르스키-보트 판정법({{llang|en|Tarski–Vaught test}})에 따라서 <math>M</math>의 기본 부분 구조이며,
:<math>|N|\le|X|+|\sigma|+\aleph_0</math>
이다.

=== 상향 뢰벤하임-스콜렘 정리 ===
부호수 <math>\sigma</math>에, <math>M</math>의 각 원소에 대응하는 0항 연산을 추가한 부호수 <math>\sigma\sqcup M</math>을 정의하자. 그렇다면, <math>M</math>의 <math>\sigma\sqcup M</math>에 대한 이론 <math>\operatorname{Th}_{\sigma\sqcup M}(M)</math>을 생각하자. 이를 <math>M</math>의 '''기본 도표'''({{llang|en|elementary diagram}})라고 한다. <math>\sigma\sqcup M</math>에 <math>\kappa</math>개의 새 0항 연산 <math>\{c_i\}_{i\in I}</math>를 추가하고, 기본 도표 <math>\operatorname{Th}_{\sigma\sqcup M}(M)</math>에 <math>\kappa^2</math>개의 명제
:<math>c_i\ne c_j\qquad(i,j\in I,\;i\ne j)</math>
를 추가하자. 이 이론은 [[콤팩트성 정리]]에 따라 모형을 가지며, 그 모형의 크기는 항상 <math>\kappa</math> 이상이다. 그렇다면 이 모형에서 추가한 0항 연산들을 망각하고, 하향 뢰벤하임-스콜렘 정리를 사용하여 크기가 정확히 <math>\kappa</math>인 <math>\sigma</math>-모형을 찾을 수 있으며, 이 모형은 정의에 따라 <math>M</math>을 기본 부분 구조로 갖는다.

== 예 ==
[[1차 논리]]로 서술된 [[집합론]](예를 들어, [[선택 공리]]를 추가한 [[체르멜로-프렝켈 집합론]])을 생각하자. 만약 이 집합론이 충분히 강력하다면, 이 집합론에서 [[가산 집합|비가산 집합]]의 존재를 증명할 수 있다. 그러나 하향 뢰벤하임-스콜렘 정리에 따르면 이 집합론은 [[가산 집합|가산 무한]] 모형을 가진다. 이를 '''스콜렘 역설'''({{llang|en|Skolem’s paradox}})이라고 하며, [[토랄프 스콜렘]]이 1922년에 지적하였다.<ref>{{서적 인용|장=Einige Bemerkungen zur axiomatischen Begründung der Mengenlehre|이름=Thoralf|성=Skolem|저자링크=토랄프 스콜렘|jfm=49.0138.02|제목=Fünften Kongress der skandinavischen Mathematiker in Helsingfors vom 4. bis 7. Juli 1922|쪽=217–232|날짜=1923|언어=de}}</ref>

스콜렘 역설은 모순이 아니며, 다음과 같이 해소된다. [[집합론]]에서는 함수 역시 집합의 일종으로 구현된다. 비가산 집합의 존재는 다음 성질을 만족시키는 집합 <math>S</math>의 존재를 의미한다.
* [[단사 함수]] <math>f\colon\mathbb N\to S</math>가 존재한다.
* [[전사 함수]] <math>f\colon\mathbb N\to S</math>는 존재하지 않는다.
집합론의 가산 모형에서, 이는 다음과 같이 해석된다.
* 모형 속에서, [[단사 함수]] <math>f\colon\mathbb N\to S</math>를 나타내는 원소가 존재한다.
* 모형 속에서, [[전사 함수]] <math>f\colon\mathbb N\to S</math>를 나타내는 원소는 존재하지 않는다. (그러나 물론 모형이 가산 모형이므로 모형 밖에서는 이러한 전사 함수를 정의할 수 있다.)

== 역사 ==
[[독일]]의 수리논리학자 [[레오폴트 뢰벤하임]](Leopold Löwenheim)과 [[노르웨이]]의 수리논리학자 [[토랄프 스콜렘]]이 [[1915년]]에 증명하였다.<ref name="Enderton">{{서적 인용|이름=Herbert B.|성=Enderton|날짜=2002|제목=A mathematical introduction to logic|url=http://www.math.ucla.edu/~hbe/amil/|출판사=Academic Press|doi=10.1016/B978-0-08-049646-7.50001-1|판=2판|isbn=978-0-12-238452-3|zbl=0992.03001|언어=en|확인날짜=2014년 11월 24일|보존url=https://web.archive.org/web/20141126034120/http://www.math.ucla.edu/~hbe/amil/|보존날짜=2014년 11월 26일|url-status=dead}}</ref>{{rp|151}}

== 같이 보기 ==
* [[괴델의 완전성 정리]]
* [[콤팩트성 정리]]

== 각주 ==
{{각주}}
* {{저널 인용|제목=Zermelo and the Skolem paradox|이름=Dirk|성=Van Dalen|공저자=Heinz-Dieter Ebbinghaus|jstor=421203|doi=10.2307/421203|저널=The Bulletin of Symbolic Logic|쪽=145–161|mr=1782347|zbl=0976.03002|언어=en}}
* {{서적 인용|장= Löwenheim-Skolem theorems|이름=Heinz-Dieter|성=Ebbinghaus|제목=Philosophy of logic|총서=Handbook of the Philosophy of Science|날짜=2007|쪽=587–614|doi=10.1016/B978-044451541-4/50018-X|isbn=978-0-444-51541-4|출판사=North-Holland|편집자=Dale Jacquette|zbl=1107.03001|언어=en}}
* {{서적 인용|장=The Mathematics of Skolem’s Paradox|이름=Timothy|성=Bays|장url=https://www3.nd.edu/~tbays/papers/spmath.pdf|제목=Philosophy of logic|총서=Handbook of the Philosophy of Science|날짜=2007|쪽=615–648|doi=10.1016/B978-044451541-4/50019-1|isbn=978-0-444-51541-4|출판사=North-Holland|편집자=Dale Jacquette|zbl=1107.03001|언어=en}}

== 외부 링크 ==
* {{매스월드|id=Loewenheim-SkolemTheorem|title=Löwenheim-Skolem theorem}}
* {{매스월드|id=SkolemParadox|title=Skolem paradox}}
* {{웹 인용|url=http://plato.stanford.edu/entries/paradox-skolem/|제목=Skolem’s paradox|웹사이트=Stanford Encyclopedia of Philosophy|날짜=2014-11-11|성=Bays|이름=Timothy|언어=en}}
* {{웹 인용|url=http://legacy.earlham.edu/~peters/courses/logsys/low-skol.htm|제목=The Löwenheim-Skolem theorem|날짜=2002|이름=Peter|성=Suber|언어=en}}
* {{웹 인용|url=http://ncatlab.org/nlab/show/Löwenheim-Skolem+theorem|제목=Löwenheim-Skolem theorem|웹사이트=nLab|언어=en}}
* {{웹 인용|url=http://ncatlab.org/nlab/show/Skolem's+paradox|제목=Skolem's paradox|웹사이트=nLab|언어=en}}

{{전거 통제}}

[[분류:수학기초론 정리]]
[[분류:모형 이론]]