상집합

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
- 2.1. 상집합과 하집합
- 2.2. 상폐포와 하폐포
3. 성질
4. 예
참조

1. 개요

상집합은 원순서 집합의 부분 집합으로, 특정 조건을 만족하는 집합을 의미한다. 원순서 집합 (X, ≲)의 부분 집합 S가 상집합이 되려면, S의 모든 원소 x와 X의 원소 y에 대해 x ≲ y이면 y가 S에 속해야 한다. 하집합은 상집합의 쌍대 개념으로, x ≲ y일 때 y가 S에 속하면 x가 S에 속하는 부분 집합이다. 상집합은 상향으로 닫혀 있고, 하집합은 하향으로 닫혀 있다고 표현된다. 상폐포는 S를 포함하는 최소 상집합이고, 하폐포는 S를 포함하는 최소 하집합이다. 상집합과 하집합은 원순서 집합의 성질을 분석하는 데 사용되며, 특히 실수의 전순서 집합, 순서수 등에서 그 예시를 찾을 수 있다.

더 읽어볼만한 페이지

순서론 - 스콧 위상
스콧 위상은 부분 순서 집합 위에 정의되는 위상으로, 하향 집합과 directed set의 상한에 대해 닫혀있는 집합을 닫힌 집합으로 정의하며, 컴퓨터 과학, 특히 프로그램 의미론에서 연속 함수의 개념을 일반화하고 프로그램의 계산 과정을 모델링하는 데 사용된다.
순서론 - 사전식 순서
사전식 순서는 정렬된 집합의 순서를 일반화하여 곱집합의 순서를 정의하는 데 사용되며, 단어 순서 정렬 방식과 유사하게 다양한 분야에 응용되는 수학적 개념이다.

상집합
개요
정의	전순서 집합의 부분 집합 S에 대해 S보다 크거나 같은 모든 원소를 포함하는 S의 상계 집합
설명	만약 어떤 순서집합 P의 모든 원소 x에 대하여, x가 S의 원소이면 x보다 크거나 같은 P의 모든 원소가 S의 원소일 때, S를 상집합이라고 한다.
영어 명칭	Upper set (업퍼 셋)
다른 이름	Upward-closed set (업워드 클로즈드 셋) Upset (업셋)
예시
예시 1	전순서 집합 {1, 2, 3}에서 {1}의 상집합은 {1, 2, 3}이다.
예시 2	전순서 집합 {1, 2, 3}에서 {3}의 상집합은 {3}이다.
예시 3	전순서 집합 {1, 2, 3}에서 {1, 2}의 상집합은 {1, 2, 3}이다.
하집합과의 관계
관계	상집합의 반대 개념으로, 어떤 순서집합 P의 모든 원소 x에 대하여, x가 S의 원소이면 x보다 작거나 같은 P의 모든 원소가 S의 원소일 때, S를 하집합이라고 한다.
영어 명칭	Lower set (로워 셋)
다른 이름	Downward-closed set (다운워드 클로즈드 셋) Downset (다운셋)
참고 문헌
참고 문헌	Dolecki, Szymon; Mynard, Frederic (2016)

2. 정의

원순서 집합 $(X, \lesssim)$ 의 부분 집합 $S\subseteq X$ 에 대해, 상집합과 하집합, 상폐포와 하폐포를 정의한다.

상집합과 하집합의 정의는 하위 섹션 "상집합과 하집합"에서 자세히 다루고 있으며, 여기서는 상폐포와 하폐포에 대해서 정의한다.

원순서 집합 $(X, \lesssim)$ 의 부분 집합 $S\subseteq X$ 의 '''상폐포'''(上閉包, upper closure^영어)는 다음과 같은 부분 집합이다.

: $\uparrow S=\{x\in X\colon\exists s\in S\colon s\lesssim x\}$

이는 $S$ 를 포함하는 최소 상집합이다.

원순서 집합 $(X, \lesssim)$ 의 부분 집합 $S\subseteq X$ 의 '''하폐포'''(下閉包, lower closure^영어)는 다음과 같은 부분 집합이다.

: $\downarrow S=\{x\in X\colon\exists s\in S\colon x\lesssim s\}$

이는 $S$ 를 포함하는 최소 하집합이다.

부분 순서 집합 $(X, \leq)$ 의 원소 $x$ 의 상방 폐포는 $\uparrow\! x = \{ u \in X : x \leq u\}$ 와 같이 정의되며, 하방 폐포는 $\downarrow\! x = \{l \in X : l \leq x\}$ 와 같이 정의된다.

$\uparrow\! x$ 와 $\downarrow\! x$ 는 각각 $x$ 를 원소로 포함하는 가장 작은 상집합과 하집합이다.

더 일반적으로, 부분 집합 $A \subseteq X$ 가 주어졌을 때, $A$ 의 상폐포와 하폐포는 다음과 같이 정의된다.

: $A^{\uparrow X} = \bigcup_{a \in A} \uparrow\!a$

: $A^{\downarrow X} = \bigcup_{a \in A} \downarrow\!a.$

$\uparrow x = \uparrow\{x\}$ 및 $\downarrow x = \downarrow\{x\}$ 이며, 이러한 형태의 상집합과 하집합은 '''주폐포'''라고 불린다. 집합의 상폐포와 하폐포는 각각 그것을 포함하는 가장 작은 상집합과 하집합이다.

상폐포와 하폐포는 폐포 연산자의 쿠라토프스키 폐포 공리를 만족한다.^[1] 집합의 상폐포는 그것을 포함하는 모든 상집합의 교집합과 같으며, 하집합도 마찬가지이다.^[1]

2. 1. 상집합과 하집합

원순서 집합

(X, \lesssim)

의 부분 집합

S\subseteq X

에 대하여 다음 조건들이 모두 서로 동치이며, 이를 만족시키는 부분 집합을 '''상집합'''(上集合, upper set^영어)이라고 한다.

임의의 $x\in S$ 및 $y\in X$ 에 대하여, $x\lesssim y$ 라면 $y\in S$ 이다.
$\uparrow S\subseteq S$
$\uparrow S=S$
$s\in S$ 및 사슬 $C\subseteq X$ 에 대하여, 만약 $\{s\}=\min C$ 라면, $C\subseteq S$ 이다.
$X\setminus S$ 는 하집합이다.

원순서 집합

(X, \lesssim)

의 부분 집합

S\subseteq X

에 대하여 다음 조건들이 모두 서로 동치이며, 이를 만족시키는 부분 집합을 '''하집합'''(下集合, lower set^영어)이라고 한다.

임의의 $x\in S$ 및 $y\in X$ 에 대하여, $y\lesssim x$ 라면 $y\in S$ 이다.
$\downarrow S\subseteq S$
$\downarrow S=S$
$s\in S$ 및 사슬 $C\subseteq X$ 에 대하여, 만약 $\{s\}=\max C$ 라면, $C\subseteq S$ 이다.
$X\setminus S$ 는 상집합이다.

(X, \leq)

를 전순서 집합이라고 할 때,

X

의 부분 집합 '''상집합'''은 "상향으로 닫혀" 있다. 즉, 모든

u \in U

와 모든

x \in X

에 대해, 만약

u \leq x

이면

x \in U

이다.

쌍대 개념은 '''하집합'''이며, "하향으로 닫혀" 있다. 즉, 모든

l \in L

와 모든

x \in X

에 대해, 만약

x \leq l

이면

x \in L

이다.

'''순서 아이디얼''' 또는 '''아이디얼'''이라는 용어는 때때로 하집합의 동의어로 사용된다.^[3]^[1]^[2] 그러나 이 용어는 격자의 아이디얼 개념을 반영하지 못한다.^[3]

순서 집합은 그 자체가 자신에 대한 상집합이다.
상집합족의 교집합과 합집합은 또한 상집합이다.
상집합의 여집합은 하집합이다. 반대도 마찬가지다.
$(X, \leq),$ 를 반순서 집합으로 하고, $X$ 의 상집합 전체에 포함 관계로 순서를 부여한 것은 완비 격자를 이루며, '''상집합 격자'''라고 불린다.
상향 유향 하집합을 순서 아이디얼이라고 부른다.

2. 2. 상폐포와 하폐포

원순서 집합

(X, \lesssim)

의 부분 집합

S\subseteq X

의 '''상폐포'''(上閉包, upper closure^영어)는 다음과 같은 부분 집합이다.

:

\uparrow S=\{x\in X\colon\exists s\in S\colon s\lesssim x\}

이는

S

를 포함하는 최소 상집합이다.

원순서 집합

(X, \lesssim)

의 부분 집합

S\subseteq X

의 '''하폐포'''(下閉包, lower closure^영어)는 다음과 같은 부분 집합이다.

:

\downarrow S=\{x\in X\colon\exists s\in S\colon x\lesssim s\}

이는

S

를 포함하는 최소 하집합이다.

부분 순서 집합

(X, \leq)

의 원소

x

의 '''상폐포''' 또는 '''상향 폐포'''는

x^{\uparrow X},

x^{\uparrow},

또는

\uparrow\! x

로 표시되며 다음과 같이 정의된다.

:

x^{\uparrow X} =\; \uparrow\! x = \{ u \in X : x \leq u\}

x

의 '''하폐포''' 또는 '''하향 폐포'''는

x^{\downarrow X},

x^{\downarrow},

또는

\downarrow\! x

로 표시되며 다음과 같이 정의된다.

:

x^{\downarrow X} =\; \downarrow\! x = \{l \in X : l \leq x\}.

\uparrow\! x

와

\downarrow\! x

는 각각

x

를 원소로 포함하는 가장 작은 상집합과 하집합이다.

더 일반적으로, 부분 집합

A \subseteq X,

가 주어졌을 때,

A

의 '''상'''/'''상향 폐포'''와 '''하'''/'''하향 폐포'''는 각각

A^{\uparrow X}

와

A^{\downarrow X}

로 표시되며 다음과 같이 정의된다.

:

A^{\uparrow X} = A^{\uparrow} = \bigcup_{a \in A} \uparrow\!a

:

A^{\downarrow X} = A^{\downarrow} = \bigcup_{a \in A} \downarrow\!a.

\uparrow x = \uparrow\{x\}

및

\downarrow x = \downarrow\{x\}

이며, 이러한 형태의 상집합과 하집합은 '''주폐포'''라고 불린다. 집합의 상폐포와 하폐포는 각각 그것을 포함하는 가장 작은 상집합과 하집합이다.

상폐포와 하폐포는

X

의 멱집합에서 자기 자신으로의 함수로 볼 때, 모든 폐포 연산자의 쿠라토프스키 폐포 공리를 만족한다.^[1] 집합의 상폐포는 그것을 포함하는 모든 상집합의 교집합과 같으며, 하집합도 마찬가지이다.^[1]

3. 성질

원순서 집합 $(X,\lesssim)$ 의 상집합들의 족 $(U_i)_{i\in I}$ 의 교집합 및 합집합 역시 상집합이다. 마찬가지로, 하집합들의 족의 교집합과 합집합 역시 하집합이다.

따라서, 원순서 집합 $(X,\lesssim)$ 의 상집합들의 족은 (부분 집합 관계에 대하여) 완비 격자를 이룬다. 마찬가지로, $(X,\le)$ 의 하집합들의 족 역시 완비 격자를 이룬다.

부분 순서 집합 $(X,\le)$ 의 상집합 $U\subseteq X$ 의 극소 원소들의 집합 $\min U$ 는 $X$ 의 반사슬을 이룬다. 마찬가지로, $(X,\le)$ 의 하집합 $L\subseteq X$ 의 극대 원소들의 집합 $\max L$ 은 $X$ 의 반사슬을 이룬다.

반대로, 부분 순서 집합 $(X,\le)$ 의 반사슬 $A\subseteq X$ 가 주어졌을 때, $\uparrow A$ 는 상집합이며

: $\min\uparrow A=A$

: $\max\downarrow A=A$

이다. 따라서, $X$ 의 반사슬 집합에서 상집합 집합으로 가는 함수

: $\uparrow\colon\operatorname{Antichain}(X,\le)\to\operatorname{Upper}(X,\le)$

는 단사 함수이며,

: $\max\colon\operatorname{Upper}(X,\le)\to\operatorname{Antichain}(X,\le)$

는 그 왼쪽 역사상이자 전사 함수이다.

만약 $(X,\le)$ 가 내림 사슬 조건을 만족시킨다면 이 두 함수는 전단사 함수이다. 그러나 일반적 부분 순서 집합에 대해서는 전단사 함수가 아닐 수 있다. 예를 들어, 실수의 전순서 집합에서 양의 실수의 부분 집합 $\mathbb R^+\subseteq\mathbb R$ 는 상집합이지만 극소 원소를 갖지 않는다.

모든 부분 순서 집합은 그 자체의 상집합이다.
어떤 상집합족의 교집합과 합집합은 다시 상집합이다.
어떤 상집합의 여집합은 하집합이고, 그 역도 성립한다.
부분 순서 집합 $(X, \leq)$ 가 주어졌을 때, 포함 관계로 정렬된 $X$ 의 상집합족은 완비 격자이며, 이를 '''상집합 격자'''라고 한다.
부분 순서 집합 $X$ 의 임의의 부분 집합 $Y$ 가 주어졌을 때, $Y$ 를 포함하는 가장 작은 상집합은 위쪽 화살표를 사용하여 $\uparrow Y$ 로 표기한다.
유한 부분 순서 집합 $X$ 의 모든 하집합 $Y$ 는 $Y$ 의 모든 극대 원소를 포함하는 가장 작은 하집합과 같다.
* $\downarrow Y = \downarrow \operatorname{Max}(Y)$ ( $\operatorname{Max}(Y)$ 는 $Y$ 의 극대 원소를 포함하는 집합)
내림 사슬 조건을 만족하는 부분 순서 집합의 경우, 안티체인과 상집합은 전단사를 통해 일대일 대응을 이룬다. 각 안티체인을 해당 상폐포에 매핑하고, 반대로 각 상집합을 해당 최소 원소의 집합에 매핑한다. 이 대응은 더 일반적인 부분 순서 집합에서는 성립하지 않는다. 예를 들어, 실수의 집합 $\{ x \in \R: x > 0 \}$ 과 $\{ x \in \R: x > 1 \}$ 는 모두 빈 안티체인에 매핑된다.

4. 예

순서 집합은 그 자체가 자신에 대한 상집합이다.
상집합족의 교집합과 합집합은 또한 상집합이다.
상집합의 여집합은 하집합이며, 반대의 경우도 마찬가지이다.
상향 유향 하집합을 순서 아이디얼이라고 부른다.
실수 전체의 집합에서 $\{ x \in \R: x > 0 \}$ 과 $\{ x \in \R: x > 1 \}$ 은 둘 다 빈 반사슬에 매핑된다.

4. 1. 자명한 상집합·하집합

임의의 원순서 집합

(X,\lesssim)

에 대하여,

X

는 스스로의 상집합이자 하집합이며, 공집합

\varnothing\subseteq X

역시

X

의 상집합이자 하집합이다.^[1]

4. 2. 주 필터와 주 아이디얼

원순서 집합

(X,\lesssim)

의 원소

x\in X

에 대하여, 상집합

\uparrow\{x\}=\{y\in X\colon x\lesssim y\}

와 하집합

\downarrow\{x\}=\{y\in X\colon y\lesssim x\}

는 각각 필터와 아이디얼을 이룬다.^[6]^[4]^[5]

4. 3. 실수

실수의 전순서 집합

(\mathbb R,\le)

의 상집합은 항상 다음 네 가지 가운데 하나이다.

$(a,\infty)$ ( $a\in\mathbb R$ )
$[a,\infty)$ ( $a\in\mathbb R$ )
$\mathbb R$
$\varnothing$

마찬가지로, 실수의 전순서 집합

(\mathbb R,\le)

의 하집합은 항상 다음 네 가지 가운데 하나이다.

$(-\infty,a)$ ( $a\in\mathbb R$ )
$(-\infty,a]$ ( $a\in\mathbb R$ )
$\mathbb R$
$\varnothing$

4. 4. 정렬 집합

순서수는 자기 자신보다 작은 순서수들의 집합으로 간주할 수 있다. 이때, 두 순서수

\alpha,\beta

에 대해

\alpha\le\beta

이면

\alpha

는

\beta

의 하집합이다.

순서수

\alpha

의 모든 상집합은 다음과 같은 형태이다.

:

\{\beta\in\operatorname{Ord}\colon\beta_0\le\beta<\alpha\}

(

\beta_0\le\alpha+1

)

순서수

\alpha

의 모든 하집합은 다음과 같은 형태이다.

:

\{\beta\in\operatorname{Ord}\colon\beta<\beta_0\}

(

\beta_0\le\alpha+1

)

서수는 일반적으로 더 작은 모든 서수의 집합과 동일시된다. 따라서 각 서수는 집합 포함에 의해 전순서가 매겨진 모든 서수의 클래스에서 하위 집합을 형성한다.

(X, \leq)

를 전순서 집합이라고 하자.

X

에서의 '''상집합'''은 부분 집합

U \subseteq X

로서, 임의의

u \in U

와

x \in X

에 대해

u \leq x

이면

x \in U

가 성립하는 것이다.

쌍대 개념으로 '''하방 집합'''이 있다. 이는 부분 집합

L \subseteq X

로, 임의의

l \in L

과

x \in X

에 대해,

x \leq l

이면

x \in L

를 만족한다. 하방 집합의 동의어로 '''아이디얼'''이 사용될 수 있다.^[6]^[4]^[5]

순서수는 일반적으로 그것보다 작은 순서수 전체로 이루어진 집합으로 정의된다. 즉, 각 순서수는 순서수 전체로 이루어진 클래스에서의 하방 집합 형태를 띤다. 순서는 집합의 포함 관계에 의한 전순서이다.

참조

_[1] 서적 Enumerative combinatorics Cambridge University Press
_[2] 서적 Inverse semigroups: the theory of partial symmetries https://archive.org/[...] World Scientific
_[3] 서적 Introduction to Lattices and Order Cambridge University Press
_[4] 서적 Enumerative combinatorics Cambridge University Press
_[5] 서적 Inverse semigroups: the theory of partial symmetries https://archive.org/[...] World Scientific
_[6] 서적 Introduction to Lattices and Order Cambridge University Press

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com