나무 ( 집합론 ) - 위키백과, 우리 모두의 백과사전 나무 ( 집합론 ) 위키백과, 우리 모두의 백과사전. ( 아론샤인 나무에서 넘어옴 ) 둘러보기로 가기 검색하러 가기 순서론과 집합론에서, 나무 ( 영어 : tree ) 는 임의의 원소에 대하여 그 미만의 원소들로 구성된 부분 집합이 정렬 전순서 집합을 이루는 부분 순서 집합이다. [ 1 ] [ 2 ] 목차 1 정의 1. 1 순서론적 정의 1. 2 범주론적 정의 2 종류 3 구성 3. 1 나무에 대응하는 전순서 집합 3. 2 전순서 집합에 대응하는 나무 3. 3 수슬린 직선 4 성질 4. 1 순서론적 성질 4. 2 논리학적 성질 4. 3 강제법 5 예 5. 1 자명한 나무 5. 2 완비 나무 5. 3 묘사적 집합론에서의 나무 6 역사 6. 1 19세기 ~ 20세기 초 6. 2 20세기 중반 ~ 21세기 7 참고 문헌 8 외부 링크 정의 [ 편집 ] 나무의 개념은 순서론적으로 특정 조건을 만족시키는 부분 순서 집합으로 정의할 수 있으며, 또 범주론적으로 순서수 위의 준층으로 생각할 수도 있다. 순서론적 정의 [ 편집 ] 부분 순서 집합 ( T, [UNK] ) { [UNK] displaystyle ( T, [UNK] leq ) } 가 다음
name { ht } ( T ) = [UNK] min [UNK] left [UNK] { [UNK] alpha [UNK] in [UNK] operatorname { Ord } [UNK] colon [UNK] forall t [UNK] in T [UNK] colon [UNK] alpha > [UNK] operatorname { ht } - { T } ( t ) [UNK] right [UNK] } } 나무 T { [UNK] displaystyle T } 의 가지 ( 영어 : branch ) 는 극대 사슬이다. 나무의 가지 역시 정렬 전순서 집합을 이루며, 따라서 가지의 높이를 정의할 수 있다. T { [UNK] displaystyle T } 의 가지들의 집합을 Br ( T ) { [UNK] displaystyle [UNK] operatorname { Br } ( T ) } 라고 하자. 나무 T { [UNK] displaystyle T } 가 다음 두 조건을 만족시킨다면, T { [UNK] displaystyle T } 를 정돈된 나무 ( [UNK] [UNK] -, 영어 : well pruned tree ) 라고 한다. 임의의 순서수 alpha < beta < ht T { [UNK] displaystyle [UNK] alpha < [UNK] beta < [UNK] operatorname { ht } T } 및 높이 alpha { [UNK] displaystyle [UNK] alpha } 의 원소 s [UNK] T { [UNK] displaystyle s [UNK] in T } 에 대하여,
t [UNK] B [UNK] C } [UNK] Ord { [UNK] displaystyle d ( B, C ) = [UNK] min [UNK] left [UNK] { [UNK] operatorname { ht } ( T ) [UNK] setminus [UNK] { [UNK] operatorname { ht } - { T } ( t ) [UNK] } - { t [UNK] in B [UNK] cap C } [UNK] right [UNK] } [UNK] in [UNK] operatorname { Ord } } 는 두 가지가 공유하지 않는 최소의 단계를 뜻하며, 만약 B [UNK] C { [UNK] displaystyle B [UNK] neq C } 라면 잘 정의된다. 그렇다면, { D alpha ( [UNK] alpha ) } alpha < [UNK] [UNK] T { [UNK] displaystyle [UNK] { D - { [UNK] alpha } ( [UNK] delta - { [UNK] alpha } ) [UNK] } - { [UNK] alpha < [UNK] kappa } [UNK] subseteq T } 는 T { [UNK] displaystyle T } 의, 크기 [UNK] { [UNK] displaystyle [UNK] kappa } 의 ( 강상향 ) 반사슬을 이룬다. 따라서 T { [UNK] displaystyle T } 는 [UNK] { [UNK] displaystyle [UNK] kappa } - 강상향 반사슬 조건을 만족시키지 않는다. 전순서 집합에 대응하는 나무 [
다. 순서론적 정의 [ 편집 ] 부분 순서 집합 ( T, [UNK] ) { [UNK] displaystyle ( T, [UNK] leq ) } 가 다음 조건을 만족시킨다면, 나무라고 한다. 임의의 s [UNK] T { [UNK] displaystyle s [UNK] in T } 에 대하여, 하집합 T s = { t [UNK] T : t < s } { [UNK] displaystyle T - { s } = [UNK] { t [UNK] in T [UNK] colon t < s [UNK] } } 는 정렬 전순서 집합이다. 나무 T { [UNK] displaystyle T } 의 원소 t [UNK] T { [UNK] displaystyle t [UNK] in T } 에 대하여, T t { [UNK] displaystyle T - { t } } 의 순서형인 순서수 ht T ( t ) { [UNK] displaystyle [UNK] operatorname { ht } - { T } ( t ) } 를 t { [UNK] displaystyle t } 의 높이라고 한다. 이는 함수 ht T : T → Ord { [UNK] displaystyle [UNK] operatorname { ht } - { T } [UNK] colon T [UNK] to [UNK] operatorname { Ord } } 를 정의한다. 높이가 0인 원소는 최소 원소이며, 나무의 최소 원소를 뿌리 ( 영어 : root ) 라고 한다. 나무 T
ensemble de ses intervalles ( contenant plus qu'un élément ) n'empiétant pas les uns sur les autres est au plus dénumerable, est - il nécessairement un continue linéaire ( ordinaire ) [UNK] de M. M. Souslin. " 이후 주로 쿠레파가 수슬린 나무의 개념을 도입하였고, 수슬린 가설을 수슬린 나무로서 서술할 수 있음을 보였다. [ 7 ] [ 3 ] : 69, [UNK] II. 5 이처럼 역사적으로 수슬린 가설은 전순서 집합의 이론에서 유래하였지만, 케네스 쿠넌은 다음과 같이 적었다. " 수슬린 가설을 비롯한 여러 조합론적 명제들은 나무에 대한 명제로 이해하는 것이 가장 낫다. Suslin's Hypothesis, as well as a number of other combinatorial statements, are best understood as assertions about trees. " - [ 3 ] : 68, [UNK] II. 5 아론샤인 나무는 1938년에 주로 쿠레파의 논문에서 최초로 등장하였다. [ 13 ] 쿠
{ [UNK] displaystyle T [UNK] in M } T { [UNK] displaystyle T } 의 포괄적 순서 아이디얼 G [UNK] T { [UNK] displaystyle G [UNK] subseteq T } 그렇다면, 강제법 모형 M [ G ] { [UNK] displaystyle M [ G ] } 를 생각할 수 있다. 그렇다면, 다음이 성립한다. [ 3 ] : 229, Theorem VII. 8. 4 M [ G ] { [UNK] displaystyle M [ G ] } 속에서, 나무 T { [UNK] displaystyle T } 는 [UNK] { [UNK] displaystyle [UNK] kappa } - 수슬린 나무가 아니다. 예 [ 편집 ] 자명한 나무 [ 편집 ] 임의의 집합 X { [UNK] displaystyle X } 에 대하여, 자명한 부분 순서 a [UNK] b [UNK] a = b { [UNK] displaystyle a [UNK] leq b [UNK] iff a = b } 를 주면, X { [UNK] displaystyle X } 는 나무를 이룬다. 그 높이는 만약 X { [UNK] displaystyle X } 가 공집합이라면 0이며, 만약 X { [UNK] displaystyle X } 가 공집합이 아니라면 1이다. 임의의 순서수 alpha { [UNK] displaystyle [UNK] alpha } 는 ( 폰 노이만 정의에서 )
ajn tree ". 《 Encyclopedia of Mathematics 》 ( 영어 ). Springer - Verlag. 2001. ISBN 978 - 1 - 55608 - 010 - 4. " Suslin hypothesis ". 《 Encyclopedia of Mathematics 》 ( 영어 ). Springer - Verlag. 2001. ISBN 978 - 1 - 55608 - 010 - 4. " Suslin condition ". 《 Encyclopedia of Mathematics 》 ( 영어 ). Springer - Verlag. 2001. ISBN 978 - 1 - 55608 - 010 - 4. Weisstein, Eric Wolfgang. " Souslin's hypothesis ". 《 Wolfram MathWorld 》 ( 영어 ). Wolfram Research. Jespers, Michiel ( 2013년 8월 15일 ). 《 Souslin's hypothesis 》 ( PDF ) ( 영어 ). 학사 학위 논문. 지도 교수 Klaas Pieter Hart. 레이던 대학교. Rinot, Assaf ( 2012년 8월 7일 ). " The P - Ideal dichotomy and the Souslin hypothesis
playstyle [UNK] kappa } - 강상향 반사슬 조건을 만족시키지 않는다. 전순서 집합에 대응하는 나무 [ 편집 ] 최대 · 최소 원소를 갖지 않는 전순서 집합 ( L, [UNK] ) { [UNK] displaystyle ( L, [UNK] leq ) } 이 주어졌으며, L { [UNK] displaystyle L } 의 ( 순서 위상에서의 ) 최소 조밀 집합의 크기가 [UNK] { [UNK] displaystyle [UNK] kappa } 라고 하고, 또한 [UNK] { [UNK] displaystyle [UNK] kappa } 가 무한 기수라고 하자. 그렇다면, L { [UNK] displaystyle L } 의, 공집합이 아닌 열린구간들의 집합 X = { ( a, b ) : a < b } { [UNK] displaystyle X = [UNK] { ( a, b ) [UNK] colon a < b [UNK] } } 위에 임의의 정렬 전순서 [UNK] [UNK] { [UNK] displaystyle [UNK] leq ^ { [UNK] circ } } 를 부여하였을 때, 다음과 같은 원소열 = ( I alpha ) alpha < [UNK] { [UNK] displaystyle = ( I - { [UNK] alpha } ) - { [UNK] alpha < [UNK] kappa } }, I alpha = { x [UNK] L : a alpha < x <
2 높이가 [UNK] { [UNK] displaystyle [UNK] kappa } 이다. 모든 가지의 크기는 [UNK] { [UNK] displaystyle [UNK] kappa } 미만이다. 모든 단계의 크기는 [UNK] { [UNK] displaystyle [UNK] kappa } 미만이다. 만약 [UNK] { [UNK] displaystyle [UNK] kappa } 가 주어지지 않았으면 [UNK] = [UNK] 1 { [UNK] displaystyle [UNK] kappa = [UNK] aleph - { 1 } } 을 뜻한다. 기수 [UNK] { [UNK] displaystyle [UNK] kappa } 에 대하여, [UNK] { [UNK] displaystyle [UNK] kappa } - 수슬린 나무 ( [UNK] -, 영어 : Souslin tree ) 는 다음 조건을 만족시키는 나무이다. [ 3 ] : 69, Definition II. 5. 4 높이가 [UNK] { [UNK] displaystyle [UNK] kappa } 이다. 모든 사슬의 크기는 [UNK] { [UNK] displaystyle [UNK] kappa } 미만이다. 모든 반사슬의 크기는 [UNK] { [UNK] displaystyle [UNK] kappa } 미만이다. 만약 [UNK] { [UNK] displaystyle [UNK] kappa } 가 주어지지 않았으면 [UNK] = [UNK] 1 { [UNK] displaystyle [UNK] kappa = [UNK] aleph - { 1 } } 을 뜻한다. 모든 단계는 반사슬이므로, [UNK]
a { [UNK] displaystyle [UNK] alpha } 의 원소 s [UNK] T { [UNK] displaystyle s [UNK] in T } 에 대하여, s < t { [UNK] displaystyle s < t } 이자 ht T ( t ) = beta { [UNK] displaystyle [UNK] operatorname { ht } - { T } ( t ) = [UNK] beta } 인 원소 t [UNK] T { [UNK] displaystyle t [UNK] in T } 가 존재한다. 뿌리가 유일하다. 범주론적 정의 [ 편집 ] 임의의 순서수 [UNK] { [UNK] displaystyle [UNK] lambda } 에 대하여, [UNK] = { alpha [UNK] Ord : alpha < [UNK] } { [UNK] displaystyle [UNK] lambda = [UNK] { [UNK] alpha [UNK] in [UNK] operatorname { Ord } [UNK] colon [UNK] alpha < [UNK] lambda [UNK] } } 는 정렬 전순서 집합이므로 작은 얇은 범주로 간주할 수 있다. 높이 [UNK] { [UNK] displaystyle [UNK] lambda } 이하의 나무는 [UNK] { [UNK] displaystyle [UNK] lambda } 위의 준층이다. 즉, 함자 T : [UNK] op → Set { [UNK] displaystyle T [UNK] colon [UNK] lambda ^
순서론과 집합론에서 나무(영어: tree)는 임의의 원소에 대하여 그 미만의 원소들로 구성된 부분 집합이 정렬 전순서 집합을 이루는 부분 순서 집합이다.