뒤스닉-밀러 정리

Dushnik–Miller theorem
Erdős-Dusnik-Miller의 정리와는 혼동하지 말 것.

수학에서 뒤스닉-밀러 정리는 모든 무한 선형 순서는 그 안에 내재된 비식별적 순서가 있다는 것을 기술하는 순서 이론의 결과물이다.[1]1940년 셀 수 있는 선형 순서에 대해 이 정리를 발표한 벤 뒤쉬닉과 E. W. 밀러의 이름을 따서 지은 것이다.더 강하게, 그들은 계산 가능한 경우에 주어진 주문의 적절한 부분집합에 포함된 주문이 존재한다는 것을 보여주었다. 그러나 그들은 이러한 강화가 항상 계산할 수 없는 주문에 대해 유지되는 것은 아니라는 것을 보여주는 예를 제공했다.[2]

역수학에서 계산 가능한 선형 순서에 대한 뒤식-밀러 정리는 2차 산술의 "빅5" 하위 시스템 중 하나인 산술 이해 공리(ACA0)와 동일한 강도를 갖는다.[1][3]이 결과는 (루이즈 헤이와 조셉 로젠슈타인이 증명했듯이) 계산 가능한 비식별성 자가 임베딩이 없는 계산 가능한 선형 순서가 존재한다는 사실과 밀접하게 관련되어 있다.[1][4]

참고 항목

참조

  1. ^ a b c Hirschfeldt, Denis R. (2014), "10.1 The Dushnik–Miller theorem", Slicing the Truth, Lecture Notes Series of the Institute for Mathematical Sciences, National University of Singapore, vol. 28, World Scientific
  2. ^ Dushnik, Ben; Miller, E. W. (1940), "Concerning similarity transformations of linearly ordered sets", Bulletin of the American Mathematical Society, 46 (4): 322–326, doi:10.1090/S0002-9904-1940-07213-1, MR 0001919
  3. ^ Downey, Rodney G.; Jockusch, Carl; Miller, Joseph S. (2006), "On self-embeddings of computable linear orderings", Annals of Pure and Applied Logic, 138 (1–3): 52–76, doi:10.1016/j.apal.2005.06.008, MR 2183808
  4. ^ Rosenstein, Joseph G. (1982), Linear Orderings, Pure and Applied Mathematics, vol. 98, Academic Press, Theorem 16.49, p. 447, ISBN 0-12-597680-1, MR 0662564