나무 (집합론)

순서론과 집합론에서 나무()는 임의의 원소에 대하여 그 미만의 원소들로 구성된 부분 집합이 정렬 전순서 집합을 이루는 부분 순서 집합이다.
정의.
나무의 개념은 순서론적으로 특정 조건을 만족시키는 부분 순서 집합으로 정의할 수 있으며, 또 범주론적으로 순서수 위의 준층으로 생각할 수도 있다.
순서론적 정의.
부분 순서 집합 formula_1가 다음 조건을 만족시킨다면, 나무라고 한다.
를 정의한다. 높이가 0인 원소는 극소 원소이며, 나무의 극소 원소를 뿌리()라고 한다.
나무 formula_9의 formula_10번째 단계(段階, )는 높이 formula_10의 원소들의 집합이다. 이를 formula_12로 표기하자. 나무 formula_9의 너비()는 그 단계들의 크기들의 상한이다.
나무 formula_9의 높이 formula_15는 모든 원소들의 높이를 초과하는 최소의 순서수이다.
나무 formula_9의 가지()는 극대 사슬이다. 나무의 가지 역시 정렬 전순서 집합을 이루며, 따라서 가지의 높이를 정의할 수 있다. formula_9의 가지들의 집합을 formula_19라고 하자.
나무 formula_9가 다음 두 조건을 만족시킨다면, formula_9를 정돈된 나무(整頓-, )라고 한다.
범주론적 정의.
임의의 순서수 formula_28에 대하여,
는 정렬 전순서 집합이므로 작은 얇은 범주로 간주할 수 있다.
높이 formula_28 이하의 나무는 formula_28 위의 준층이다. 즉, 함자
이다. 즉, 구체적으로 다음과 같은 데이터로 구성된다.
이 데이터는 다음과 같은 함자 조건을 만족시켜야 한다.
이 경우, 분리 합집합
위에 다음과 같은 부분 순서를 줄 수 있다.
종류.
기수 formula_45에 대하여, formula_45-아론샤인 나무()는 다음 세 조건들을 만족시키는 나무 formula_9이다.
만약 formula_45가 주어지지 않았으면 formula_52을 뜻한다.
기수 formula_45에 대하여, formula_45-수슬린 나무(Суслин-, )는 다음 조건을 만족시키는 나무이다.
만약 formula_45가 주어지지 않았으면 formula_52을 뜻한다. 모든 단계는 반사슬이므로, formula_45-수슬린 나무는 항상 formula_45-아론샤인 나무이다.
만약 formula_45가 무한 기수라면, 모든 formula_45-수슬린 나무는 formula_45-아론샤인 나무이나, 그 역은 성립하지 않는다.
기수 formula_45에 대하여, formula_45-쿠레파 나무(Курепа-, )는 다음 조건을 만족시키는 나무이다.
만약 formula_45가 주어지지 않았으면 formula_52을 뜻한다.
"formula_73-수슬린 나무(또는 수슬린 직선)가 존재하지 않는다"는 명제를 수슬린 가설(Суслин假說, ) formula_74이라고 한다. "formula_73-쿠레파 나무가 존재한다"는 명제를 쿠레파 가설(Курепа假說, ) formula_76라고 한다. (역사적 이유로 인하여, 수슬린 가설과 쿠레파 가설의 정의는 서로 반대이다.)
formula_45-특수 아론샤인 나무()는 다음 조건을 만족시키는 formula_45-아론샤인 나무 formula_9이다.
구성.
일부 나무들은 특정 전순서 집합과 밀접한 관계를 갖는다.
나무에 대응하는 전순서 집합.
나무 formula_9의 마디()는 다음 조건을 만족시키는 부분 집합 formula_83이다.
나무 formula_9가 주어졌으며, 각 마디 formula_83에 대하여 formula_87 위의 전순서가 주어졌다고 하자. 그렇다면, 가지 집합 formula_19 위에 다음과 같은 전순서를 줄 수 있다.
이를 formula_9의 가지 공간()이라고 한다.
임의의 기수 formula_45에 대하여, 정돈된 나무 formula_9가 formula_45-강상향 반사슬 조건을 만족시킨다면, formula_95에 대하여, formula_96 역시 formula_45-강상향 반사슬 조건을 만족시킨다.
증명:
formula_9가 정돈된 나무라고 하자. 즉, 모든 가지들의 높이가 formula_15라고 하자.
귀류법을 사용하여,
가 formula_45개의, 공집합이 아닌 서로소 열린구간들의 집합이라고 하자. 그렇다면, 각 formula_102에 대하여, formula_103를 고르고, 또한 순서수열
을 정의하자. 여기서
는 두 가지가 공유하지 않는 최소의 단계를 뜻하며, 만약 formula_106라면 잘 정의된다.
그렇다면,
는 formula_9의, 크기 formula_45의 (강상향) 반사슬을 이룬다. 따라서 formula_9는 formula_45-강상향 반사슬 조건을 만족시키지 않는다.
전순서 집합에 대응하는 나무.
최대·최소 원소를 갖지 않는 전순서 집합 formula_112이 주어졌으며, formula_113의 (순서 위상에서의) 최소 조밀 집합의 크기가 formula_45라고 하고, 또한 formula_45가 무한 기수라고 하자. 그렇다면, formula_113의, 공집합이 아닌 열린구간들의 집합 formula_117를 부여하였을 때, 다음과 같은 원소열 formula_118, formula_119을 정의할 수 있다.
그렇다면, formula_123는 포함 관계에 대하여 부분 순서 집합을 이루며, 그 반대 부분 순서 집합 formula_9는 formula_113에 대응하는 나무이다.
수슬린 직선.
다음 두 조건을 만족시키는 전순서 집합 formula_113을 수슬린 직선(Суслин直線, )이라고 한다.
정돈된 수슬린 직선(整頓-Суслин直線)은 다음 조건을 추가로 만족시키는 수슬린 직선이다.
만약 수슬린 직선이 존재한다면, 정돈된 수슬린 직선이 존재한다.
다음이 성립한다.
따라서, 수슬린 나무의 존재와 수슬린 직선의 존재는 서로 동치이다.
성질.
순서론적 성질.
나무에서, 모든 반사슬은 강상향 반사슬이다. 즉, 반사슬과 강상향 반사슬의 개념이 일치한다.
나무의 경우 다음 두 조건이 서로 동치이다.
다음 세 개념이 서로 동치이다.
논리학적 성질.
쾨니그 보조정리에 의하면, formula_134-아론샤인 나무는 존재하지 않는다. ZFC만으로, formula_73-아론샤인 나무가 존재한다는 것을 증명할 수 있다. 그러나 formula_73-수슬린 나무의 존재(수슬린 가설)는 (ZFC가 무모순적이라면) ZFC와 독립적이다.
만약 구성 가능성 공리 formula_137이 참이라면, 모든 순서수 formula_10에 대하여 formula_139-수슬린 나무가 존재한다.
도달 불가능한 기수 formula_45에 대하여 다음 두 조건이 서로 동치이다.
또한, 다음이 성립한다.
ZFC만으로, 모든 분해 가능 공간인 수슬린 직선은 formula_145와 순서 동형임을 증명할 수 있다. 이는 게오르크 칸토어가 증명하였다.
강제법.
다음 데이터가 주어졌다고 하자.
그렇다면, 강제법 모형 formula_155를 생각할 수 있다. 그렇다면, 다음이 성립한다.
예.
자명한 나무.
임의의 집합 formula_159에 대하여, 자명한 부분 순서 formula_160를 주면, formula_159는 나무를 이룬다. 그 높이는 만약 formula_159가 공집합이라면 0이며, 만약 formula_159가 공집합이 아니라면 1이다.
임의의 순서수 formula_10는 (폰 노이만 정의에서) 높이 formula_10의 나무를 이룬다.
완비 나무.
임의의 순서수 formula_10와 집합 formula_167에 대하여,
는 formula_169에 대한 열 formula_170들의 집합이다. 여기에 부분 순서
를 부여하면, 이는 높이 formula_10의 나무를 이룬다. 이를 높이 formula_10의 완비 formula_167진 나무()라고 한다. 만약 formula_167가 한원소 집합이라면, 높이 formula_10의 완비 formula_167진 나무는 formula_10와 순서 동형이다.
묘사적 집합론에서의 나무.
집합 formula_167가 주어졌다고 하자. 그렇다면, 높이 formula_180의 완비 formula_167진 나무 formula_182를 생각하자. 그렇다면, formula_182의 하집합은 나무를 이룬다.
묘사적 집합론()에서는 위와 같은 나무들을 주로 사용한다. 이러한 나무 formula_184의 경우, 높이 formula_180의 가지들의 집합은 보통 formula_186로 표기하며, 나무의 몸통()이라고 한다. 이 경우, 자연스럽게 formula_187가 된다.
formula_167를 이산 공간으로 간주하며, formula_189를 그 가산 무한 곱공간으로 생각하자. 그렇다면, 임의의 부분 집합 formula_190에 대하여 다음 두 조건이 서로 동치이다.
증명:
임의의 하집합 formula_184에 대하여, 그 몸통의 여집합은
인데, 우변의 각 항들은 formula_189의 열린집합이다.
반대로, 임의의 닫힌집합 formula_190가 주어졌다고 하자. 그렇다면, 다음과 같은 나무를 생각하자.
그렇다면, formula_200가 된다.
정렬 전순서 집합 formula_201 및 하집합 formula_184에 대하여, 다음 두 조건이 서로 동치이다.
만약 formula_206라면,
이므로 formula_208는 정렬 전순서가 아니다.
반대로, 만약
라면,
이다. formula_201가 정렬 전순서 집합이므로,
인 formula_215 및 formula_214가 존재한다. 이 경우, formula_217이므로 formula_218이다. 마찬가지로,
이므로,
라고 하자. 이 경우 formula_222이므로 formula_223이다. 이를 반복하면
를 얻는다.
역사.
19세기~20세기 초.
게오르크 칸토어는 1895년에 최대·최소 원소를 갖지 않는, 분해 가능 선형 연속체가 항상 실수의 전순서 집합과 순서 동형임을 증명하였다. 미하일 수슬린은 1920년에 사후 출판된 원고에서 칸토어의 위 정리에서 분해 가능 공간 조건을 가산 강하향 반사슬 조건으로 약화시키면 어떻게 되는지 여부에 대한 문제를 제시하였다. 이 논문에서 수슬린 가설은 다음과 같이 3번 문제로 수록되어 있다.
이후 주로 쿠레파가 수슬린 나무의 개념을 도입하였고, 수슬린 가설을 수슬린 나무로서 서술할 수 있음을 보였다. 이처럼 역사적으로 수슬린 가설은 전순서 집합의 이론에서 유래하였지만, 케네스 쿠넌은 다음과 같이 적었다.
아론샤인 나무는 1938년에 주로 쿠레파의 논문에서 최초로 등장하였다. 쿠레파는 이 개념을 "아론샤인 씨의 분기 집합"()이라고 일컬었으며, 이 논문에서 다음과 같이 적었다.
쿠레파 나무 역시 주로 쿠레파가 도입하였다.
20세기 중반~21세기.
토마시 예흐()와 스탠리 테넨바움이 수슬린 나무가 존재하는 강제법 모형을 제시하였다. 곧 또한 로널드 비언 젠슨()은 다이아몬드 원리를 가정하면 수슬린 나무가 존재함을 증명하였다.
1971년에 로버트 솔로베이와 스탠리 테넨바움은 반복 강제법을 도입하여, 연속체 가설의 부정과 마틴 공리를 가정하면 수슬린 나무가 존재하지 않음을 증명하였다.
같은 해에 잭 하워드 실버()는 쿠레파 가설 역시 (ZFC가 무모순적이라면) ZFC와 독립적임을 증명하였다.
수슬린 문제에 대하여 메리 엘런 루딘은 다음과 같이 적었다.
즉, 수슬린 문제는 사실과 달리 "당연히 참"이거나 "당연히 거짓"인 것처럼 보인다는 것이다.
얀 미치엘스키는 수슬린 가설을 옹호하기 위하여 다음과 같이 적었다.