정렬 순서

위키백과, 우리 모두의 백과사전.
(정렬순서에서 넘어옴)
이동: 둘러보기, 검색

순서론집합론에서, 정렬 순서(整列順序, 영어: well-order)는 모든 부분 집합이 최소 원소를 갖는 전순서이다.

정의[편집]

정초 관계[편집]

집합 위의 이항 관계 가 다음 조건을 만족시킨다면, 정초 관계(整礎關係, 영어: well founded relation)라고 한다.

정초 관계가 주어졌을 때, 다음과 같은 초한 귀납법을 사용할 수 있다. 임의의 술어 에 대하여, 다음 조건이 성립한다고 하자.

  • 임의의 에 대하여, 만약 라면, 이다.

그렇다면, 가 성립한다.

정렬 원순서 집합[편집]

원순서 집합 에 대하여 다음 다섯 조건들이 서로 동치이며, 이를 만족시키는 원순서 집합을 정렬 원순서 집합(整列原順序集合, 영어: well preordered set)이라고 한다.

  • 임의의 무한 열 에 대하여, 이자 이 존재한다.[1]:202, Definition 2.3
  • 임의의 무한 열은 무한 증가 부분열을 갖는다. 즉, 에 대하여, 가 되는 증가 함수 가 존재한다.[1]:Lemma 2.5(2)[2]:298
  • (유한 개의 극소 원소의 존재) 임의의 부분 집합 에 대하여, 만약 이라면, 는 (하나 이상의) 극소 원소들을 가지며, 극소 원소들의 동치류의 수는 유한하다.
  • 멱집합 위에 부분 순서 를 정의하였을 때, 는 정초 관계이다.
  • 다음 두 조건이 성립한다.[1]:202, Lemma 2.4(2)[2]:298
    • 속의 모든 반사슬유한 집합이다.
    • (내림 사슬 조건) 속의 모든 감소열 에 대하여, 모든 에 대하여 가 되는 이 존재한다.

여기서 를 뜻한다.

정렬 원순서 집합인 부분 순서 집합정렬 부분 순서 집합(整列部分順序集合, 영어: well partially ordered set)이라고 한다. 정렬 원순서 집합인 전순서 집합정렬 전순서 집합(整列全順序集合, 영어: well totally ordered set) 또는 정렬 집합(영어: well ordered set)이라고 한다. 즉, 전순서 집합 에 대하여 다음 네 조건이 서로 동치이며, 이를 만족시키는 전순서 집합을 정렬 전순서 집합이라고 한다.

  • 임의의 열 에 대하여, 이자 이 존재한다.
  • 임의의 열 은 증가 부분열을 갖는다.
  • (최소 원소의 존재) 임의의 부분 집합 에 대하여, 만약 이라면, 최소 원소를 갖는다.
  • (내림 사슬 조건) 속의 모든 감소열 에 대하여, 모든 에 대하여 가 되는 이 존재한다.

시뮬레이션[편집]

두 정렬 원순서 집합 , 사이의 시뮬레이션(영어: simulation) 는 다음 성질들을 만족시키는 함수이다.

  • (증가 함수) 만약 에 대하여 라면, 이다.
  • 하집합이다. 즉, 임의의 에 대하여, 만약 라면 가 존재한다.

정렬 전순서 집합과 시뮬레이션들의 범주순서수얇은 범주동치이다.

정렬 전순서의 동형은 정렬 전순서와 시뮬레이션의 범주에서의 동형이다. 이 동형에 대한 동치류순서형(順序型, 영어: order type)이라고 한다. 순서수는 각 순서형의 표준적인 대표원을 제공한다.

성질[편집]

함의 관계[편집]

다음과 같은 함의 관계가 성립한다.

정렬 전순서 집합 정렬 원전순서 집합
전순서 집합 원전순서 집합
부분 순서 집합 원순서 집합
정렬 부분 순서 집합 정렬 원순서 집합

정렬 전순서 집합[편집]

정렬 전순서 집합 의 부분 집합 이 주어졌을 때, 역시 정렬 집합이다.

서로 동형인 두 정렬 전순서 집합은 같은 집합의 크기를 갖는다. 반대로, 집합의 크기가 같은 두 유한 정렬 전순서 집합은 서로 동형이다. 반면, 집합의 크기가 같지만 서로 다른 무한 정렬 전순서 집합이 존재한다. 예를 들어, 순서수 에 대응하는 정렬 전순서 집합과 순서수 에 대응하는 정렬 전순서 집합은 서로 동형이지 않다.

정렬 원순서 집합[편집]

정렬 원순서 집합들의 유한 족 이 주어졌다고 하자. 그렇다면, 분리합집합 위에 순서

를 줄 수 있다. 이 역시 정렬 원순서 집합이다.

정렬 원순서 집합들의 유한 족 이 주어졌다고 하자. 그렇다면, 곱집합 위에 순서

를 준다면, 역시 정렬 원순서 집합이다 (딕슨 보조 정리 영어: Dickson’s lemma).[3][1]:203, Lemma 2.6

증명:

수학적 귀납법을 통해 인 경우를 증명하면 족하다. (은 자명하다.) 속의 점렬 이 주어졌다고 하자. 이제,

의 증가 부분열이라고 하자. 또한,

의 증가 부분열이라고 하자. 그렇다면

의 증가 부분열이다.

정렬 정리[편집]

정렬 정리(整列定理, 영어: well-ordering theorem)에 따르면, 모든 집합은 적어도 하나 이상의 정렬 전순서를 갖는다. (다만, 이 정렬 전순서는 구체적으로 명시하지 못할 수 있다.) 다시 말해, 임의의 크기를 갖는 순서수가 존재한다. 이를 통해, 임의의 집합 위에 초한 귀납법을 적용할 수 있다. 사실, 1차 논리체르멜로-프렝켈 집합론에서, 정렬 정리는 선택 공리초른의 보조정리와 서로 동치이다. 즉, 체르멜로-프렝켈 집합론의 공리들로, 이 셋 가운데 하나가 주어지면 나머지 둘을 증명할 수 있다.

증명 (초른의 보조정리 ⇒ 정렬 정리):

임의의 집합 가 주어졌다고 하자. 부분 집합들 위의 정렬 전순서의 집합 를 생각하자. 여기에 다음과 같은 부분 순서를 주자.

  • 이며 또한 포함 사상 가 시뮬레이션인 것과 동치이다.

이에 따라 부분 순서 집합을 이룬다.

의 임의의 사슬 에 대하여, 는 사슬의 최대 원소이다. 따라서, 의 모든 사슬은 최대 원소를 갖는다.

따라서, 초른의 보조정리에 따라 최대 원소 를 갖는다.

귀류법을 사용하여, 만약 라고 하자. 그렇다면 가 존재하는데, 이 경우 위에 다음과 같은 정렬 전순서를 줄 수 있다.

즉, 의 모든 원소보다 더 크다. 이 정렬 전순서를 주었을 때,

이므로 최대 원소일 수 없다. 즉, 이며, 위의 정렬 전순서이다.

증명 (정렬 정리 ⇒ 선택 공리):

정렬 정리를 가정하자. 공집합이 아닌 집합들의 집합족 가 주어졌다고 하자. 정렬 정리를 사용하여, 에 정렬 전순서를 주자. 이 경우, 함수

위의 선택 함수이므로, 선택 공리는 참이다.

폰 노이만-베르나이스-괴델 집합론이나 모스-켈리 집합론과 같은, 모임을 다루는 이론에서는 모든 모임이 정렬 전순서를 갖는지에 대하여 생각할 수 있다. (선택 공리를 제외한) 이들 체계에서는 다음 두 조건이 서로 동치이다.

  • 모든 모임은 정렬 전순서를 갖는다.
  • (대역적 선택 공리 영어: axiom of global choice) 공집합이 아닌 집합들을 원소로 하는 모든 모임은 선택 함수를 갖는다.

[편집]

정렬 전순서 집합[편집]

모든 유한 원순서 집합은 (자명하게) 정렬 원순서 집합을 이룬다.[1]:203 특히, 자연수 집합의 표준적인 전순서는 정렬 전순서이다.

보다 일반적으로, 임의의 순서수 보다 작은 순서수들의 집합

는 정렬 전순서 집합이다. 모든 순서수고유 모임 (또는 그 임의의 부분 모임)의 표준적인 전순서는 정렬 전순서이다. 선택 공리를 가정할 경우, 기수고유 모임의 표준적인 전순서 역시 정렬 전순서이며, 이 사실은 알레프 수의 정의의 기반을 이룬다.

문자열[편집]

원순서 집합 위의 유한 문자열 집합 (클레이니 스타) 위에 다음과 같은 부분 문자열 관계를 주자. 즉, 에 대하여, 이라는 것은

가 되는 단사 증가 함수

가 존재함을 뜻한다. 이는 원순서이며, 만약 부분 순서라면 부분 문자열 관계는 부분 순서이다. 히그먼 보조 정리(영어: Higman’s lemma)에 따르면, 는 정렬 원순서 집합을 이룬다.[4][1]:204, Theorem 3.2

그래프[편집]

(무향) 유한 그래프들의 가산 무한 집합마이너 관계에 대하여 원순서 집합을 이룬다. 로버트슨-시모어 정리(영어: Robertson–Seymour theorem)에 따르면, 이는 정렬 원순서 집합이다.[5]

반례[편집]

순서체 (예를 들어, 유리수체실수체)는 정렬 전순서 집합이 될 수 없다. 모든 순서체는 를 부분환으로 포함하는데, 이 경우 전체는 최소 원소를 갖지 않기 때문이다. 마찬가지로, 자명환이 아닌 순서환은 항상 정렬 전순서 집합이 될 수 없다.

순서체 에서, 음이 아닌 원소들의 전순서 집합 역시 정렬 전순서 집합이 될 수 없다. 이는 는 양의 유리수들의 집합 을 포함하는데, 이는 최소 원소를 갖지 않기 때문이다.

양의 정수의 집합에 약수 관계 를 부여하면, 이는 부분 순서 집합이지만 정렬 부분 순서 집합이 아니다. 이는 소수의 집합은 무한 반사슬을 이루기 때문이다.

역사[편집]

정렬 전순서 집합(독일어: wohlgeordnete Menge 볼게오르드네테 멩게[*])의 용어 및 개념은 1883년에 게오르크 칸토어가 순서수를 도입하기 위하여 정의하였다.[6]:548, §2 게오르크 칸토어는 정렬 정리가 증명이 필요없을 정도로 자명한 "사고 법칙"(독일어: Denkgesetz 뎅크게제츠[*])이라고 간주했지만, 이를 증명하지 않고 공리로 가정하였다. (칸토어는 선택 공리를 직접적으로 사용하지 않았다.) 그러나 다른 수학자들은 이 "사고 법칙"에 대하여 회의적이었다.[7]:Chapter 1

1904년 8월의 하이델베르크 세계 수학자 대회에서 헝가리의 수학자 쾨니그 줄러(헝가리어: Kőnig Gyula)는 정렬 정리를 반증하였다고 발표하였다.[7]:86, §2.1 그러나 몇 주 뒤 펠릭스 하우스도르프가 이 "반증"의 오류를 지적하였다.

1904년에 에른스트 체르멜로선택 공리를 도입하였고, 이를 통해 정렬 정리를 증명하였다.[8]

1937년에 주로 쿠레파(세르비아어: Ђуро Курепа, 크로아티아어: Đuro Kurepa, 1907~1993)가 "부분 정렬 순서 집합"(프랑스어: ensemble partiellement bien ordonné)이라는 용어를 사용하였으나, 쿠레파는 무한 반사슬의 부재를 가정하지 않았다.[9]:1197[2]:299 1952년에 그레이엄 히그먼(영어: Graham Higman)은 정렬 부분 순서와 동치인 개념을 "유한 기저 성질"(영어: finite basis property)이라는 이름으로 도입하였고, 히그먼 보조 정리를 증명하였다.[4][2]:300 같은 해에 에르되시 팔과 리하르트 라도(독일어: Richard Rado) 역시 한 논문에서 "부분 정렬 순서 집합"(영어: partially well ordered set)이라는 용어를 도입하였다.[10]:256[2]:300

현재까지도, 많은 수학자들은 정렬 정리가 직관적이지 않다고 여긴다. 그러나 이와 동치선택 공리는 대체로 더 직관적이라고 여겨진다. 미국의 수학자 제리 로이드 보나(영어: Jerry Lloyd Bona, 1945~)는 1977년에 이에 대하여 다음과 같이 농담하였다.

선택 공리는 당연히 참이고, 정렬 정리는 당연히 거짓이고, 초른의 보조정리는 글쎄……?

The Axiom of Choice is obviously true; the Well Ordering principle is obviously false; and who can tell about Zorn’s lemma?

 
[11]:145, §6.21

참고 문헌[편집]

  1. Gallier, Jean H. (1991년 9월 19일). “What’s so special about Kruskal’s theorem and the ordinal Γ0? A survey of some results in proof theory”. 《Annals of Pure and Applied Logic》 (영어) 53 (3): 199–260. doi:10.1016/0168-0072(91)90022-E. 
  2. Kruskal, Joseph B. (1972년 11월). “The theory of well-quasi-ordering: a frequently discovered concept”. 《Journal of Combinatorial Theory Series A》 (영어) 13 (3): 297–305. doi:10.1016/0097-3165(72)90063-5. Zbl 0244.06002. 
  3. Dickson, L. E. (1913년 10월). “Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors”. 《American Journal of Mathematics》 (영어) 35 (4): 413–422. doi:10.2307/2370405. JSTOR 2370405. 
  4. Higman, Graham (1952). “Ordering by divisibility in abstract algebras”. 《Proceedings of the London Mathematical Society》 (영어) 2 (1): 326–336. doi:10.1112/plms/s3-2.1.326. Zbl 0047.03402. 
  5. Robertson, Neil; Seymour, P. D. (2004년 11월). “Graph minors XX. Wagner’s conjecture”. 《Journal of Combinatorial Theory Series B》 (영어) 92 (2): 325–357. doi:10.1016/j.jctb.2004.08.001. 
  6. Cantor, Georg (1883). “Ueber unendliche, lineare Punktmannichfaltigkeiten 5”. 《Mathematische Annalen》 (독일어) 21 (4): 545–591. doi:10.1007/bf01446819. JFM 15.0452.03. 
  7. Moore, Gregory H. (1982). 《Zermelo’s axiom of choice: its origins, development, and influence》. Studies in the History of Mathematics and Physical Sciences (영어) 8. Springer-Verlag. doi:10.1007/978-1-4613-9478-5. ISBN 978-1-4613-9480-8. ISSN 0172-570X. 
  8. Zermelo, Ernst (1904). “Beweis, daß jede Menge wohlgeordnet werden kann. (Aus einem an Herrn Hilbert gerichteten Briefe)”. 《Mathematische Annalen》 (독일어) 59 (4): 514–516. doi:10.1007/BF01445300. ISSN 0025-5831. JFM 35.0088.03. 
  9. Kurepa, Georges (1937년 12월 13일). “Théorie des ensembles”. 《Comptes rendus hebdomadaires des séances de l’Académie des Sciences》 (프랑스어) 205: 1196–1198. Zbl 63.0834.01. 
  10. Erdös, Paul; Rado, Richard (1952년 4월). “Sets having a divisor property”. 《American Mathematical Monthly》 (영어) 59: 255-257. doi:10.2307/2306526. JSTOR 2306526. 
  11. Schechter, Eric (1997). 《Handbook of analysis and its foundations》 (영어). Academic Press. doi:10.1016/B978-0-12-622760-4.50033-9. Zbl 0943.26001. 
  • Schmitz, Sylvain; Schnoebelen, Philippe (2012). “Algorithmic aspects of WQO theory” (영어). 
  • Herrlich, Horst (2006). 《Axiom of Choice》. Lecture Notes in Mathematics (영어) 1876. Springer. ISBN 3-540-30989-6. 
  • Howard, Paul; Jean E. Rubin (1998). 《Consequences of the axiom of choice》. Mathematical Surveys and Monographs (영어) 59. American Mathematical Society. ISBN 9780821809778. 

바깥 고리[편집]