공종 집합

순서론에서 공종 집합(共終集合, 영어: cofinal set)은 그 하폐포가 전체 집합인, 원순서 집합의 부분 집합이다.

정의

원순서 집합 ${\displaystyle (X,\lesssim )}$의 공종 집합(共終集合, 영어: cofinal set) ${\displaystyle S\subseteq X}$는

${\displaystyle X=\downarrow S}$

가 성립하는 부분 집합이다. 여기서 ${\displaystyle \downarrow }$는 하폐포를 뜻한다. 즉, 다음 조건이 성립한다.

${\displaystyle \forall x\in X\exists s\in S\colon x\lesssim s}$

쌍대적으로, 원순서 집합 ${\displaystyle (X,\lesssim )}$의 공시작 집합(共始作共終, 영어: coinitial set) ${\displaystyle S\subseteq X}$는

${\displaystyle X=\uparrow S}$

가 성립하는 부분 집합이다. 여기서 ${\displaystyle \uparrow }$는 상폐포를 뜻한다. 즉, 다음 조건이 성립한다.

${\displaystyle \forall x\in X\exists s\in S\colon x\gtrsim s}$

원순서 집합 ${\displaystyle (X,\lesssim )}$의 공종 집합 및 공시작 집합들은 각각 포함 관계에 따라 부분 순서 집합을 이룬다. 이들을 각각 ${\displaystyle \operatorname {Cofin} (X)}$와 ${\displaystyle \operatorname {Coinit} (X)=\operatorname {Cofin} (X^{\operatorname {op} })}$로 나타내자.

집합 ${\displaystyle X}$ 및 원순서 집합 ${\displaystyle (Y,\lesssim _{Y})}$ 사이의 함수 ${\displaystyle f\colon X\to Y}$의 치역이 ${\displaystyle Y}$의 공종 집합이라면, ${\displaystyle f}$를 공종 함수(영어: cofinal map)라고 한다.

성질

추이성

원순서 집합 ${\displaystyle (X,\lesssim )}$의 두 부분 집합 ${\displaystyle Z\subseteq Y\subseteq X}$에 대하여,

• 만약 ${\displaystyle Z}$가 ${\displaystyle (Y,\lesssim )}$의 공종 집합이며 ${\displaystyle Y}$가 ${\displaystyle (X,\lesssim )}$의 공종 집합이라면 ${\displaystyle Z}$는 ${\displaystyle (X,\lesssim )}$의 공종 집합이다.
• 만약 ${\displaystyle Z}$가 ${\displaystyle (Y,\lesssim )}$의 공시작 집합이며 ${\displaystyle Y}$가 ${\displaystyle (X,\lesssim )}$의 공시작 집합이라면 ${\displaystyle Z}$는 ${\displaystyle (X,\lesssim )}$의 공시작 집합이다.

극대 · 극소 공종 집합

그렇다면, ${\displaystyle \operatorname {Cofin} (X)}$와 ${\displaystyle \operatorname {Coinit} (X)}$의 최대 원소는 ${\displaystyle X}$이다. 또한, 공종 집합들의 족의 합집합은 공종 집합이며, 공시작 집합들의 족의 합집합은 공시작 집합이다. 따라서, 원순서 집합 ${\displaystyle (X,\lesssim )}$에 대하여 ${\displaystyle (\operatorname {Cofin} (X),\subseteq )}$와 ${\displaystyle (\operatorname {Coinit} (X),\subseteq )}$ 둘 다 모든 상한을 갖는다.

그러나 두 공종 집합의 교집합은 공종 집합이 아닐 수 있다. 예를 들어, 자연수의 전순서 집합 ${\displaystyle (\mathbb {N} ,\leq )}$에서, 짝수의 집합 ${\displaystyle 2\mathbb {N} }$과 홀수의 집합 ${\displaystyle 2\mathbb {N} +1}$은 각각 공종 집합이지만, 그 교집합인 공집합은 공종 집합이 아니다.

원순서 집합 ${\displaystyle (X,\lesssim )}$이 다음 조건을 만족시킨다고 하자.

• 임의의 ${\displaystyle x\in X}$에 대하여, ${\displaystyle x}$와 비교 가능한 극대 원소 ${\displaystyle m\geq x}$가 존재한다.

그렇다면, ${\displaystyle X}$의 부분 집합 ${\displaystyle S\subseteq X}$에 대하여 다음 두 조건이 서로 동치이다.

• ${\displaystyle S}$는 ${\displaystyle (X,\lesssim )}$의 공종 집합이다.
• 임의의 극대 원소 ${\displaystyle m\in \max X}$에 대하여, ${\displaystyle x\sim s}$인 ${\displaystyle s\in S}$가 존재한다. 즉, ${\displaystyle [x]_{\sim }\cap S\neq \varnothing }$이다.

특히, ${\displaystyle X}$가 추가로 부분 순서 집합이라면, ${\displaystyle \operatorname {Cofin} (X)}$의 최소 원소는 ${\displaystyle \max X}$ (즉, ${\displaystyle X}$의 최대 원소들의 집합)이다.

예

자연수의 전순서 집합 ${\displaystyle (\mathbb {N} ,\leq )}$의 부분 집합 ${\displaystyle S\subseteq \mathbb {N} }$에 대하여 다음 두 조건이 서로 동치이다.

• ${\displaystyle S}$는 ${\displaystyle (\mathbb {N} ,\leq )}$의 공종 집합이다.
• ${\displaystyle S}$는 무한 집합이다.

전순서 집합 ${\displaystyle (X,\leq )}$의 부분 집합 ${\displaystyle S\subseteq X}$에 대하여 다음 두 조건이 서로 동치이다.

• ${\displaystyle S}$는 ${\displaystyle (X,\leq )}$의 공종 집합이다.
• 만약 ${\displaystyle X}$가 최대 원소 ${\displaystyle m\in X}$를 갖는다면, ${\displaystyle m\in S}$이다. 만약 ${\displaystyle X}$가 최대 원소를 갖지 않는다면, ${\displaystyle S}$는 상계를 갖지 않는다.

외부 링크

• “Cofinal set”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
• “Definition: cofinal subset”. 《ProofWiki》 (영어).
• “Subset of natural numbers is cofinal iff infinite”. 《ProofWiki》 (영어).