추이적 집합

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

1. 개요

추이적 집합은 집합론에서 사용되는 개념으로, 집합 X의 모든 원소 A에 대해 A가 X의 부분집합인 경우를 말한다. 추이적 집합은 여러 가지 조건과 동치 관계를 가지며, 초추이적 집합, α-초추이적 집합 등 다양한 확장 개념이 존재한다. 순서수는 추이적 집합만을 원소로 하는 추이적 집합의 예시이며, 집합론의 모형을 정의하고 상대적 해석을 구성하는 데 사용된다. 또한 추이적 모임과 원소 관계를 갖는 구조 사이의 동형 사상은 항등 함수뿐이며, 모형 이론과 내부 모델 구성에 중요한 역할을 한다.

추이적 집합

📚 더 읽어볼만한 페이지

집합론 - 퍼지 집합
퍼지 집합은 각 원소가 0과 1 사이의 소속도를 가지며, 소속 함수를 통해 정의되고, 여집합, 합집합, 교집합 등의 연산을 수행하며, 퍼지 논리, 퍼지 수, 엔트로피 등의 개념과 L-퍼지 집합, 직관적 퍼지 집합 등으로 확장된다.
집합론 - 무한 집합
무한 집합은 유한 집합이 아니며, 자연수보다 큰 크기를 가지고 자신의 진부분집합과 일대일 대응을 가지며, 가산 무한 집합과 비가산 무한 집합으로 나뉜다.

1. 개요
2. 정의
- 2.1. 초추이적 집합
3. 성질
- 3.1. 연산에 대한 닫힘
- 3.2. 자명하지 않은 동형의 부재
4. 추이적 폐포
5. 예
6. 집합론에서의 추이적 모델

2. 정의

집합 $X$ 에 대하여 다음 조건들이 동치이며, 이를 만족시키는 집합을 추이적 집합이라고 한다.

* 임의의 $B\in A\in X$ 에 대하여, $B\in X$
* 임의의 $A\in X$ 에 대하여, $A\subseteq X$
* $\bigcup X\subseteq X$
* $X\subseteq\mathcal P(X)$

마찬가지로, 추이적 모임(transitive class^영어)을 정의할 수 있다.

집합 $X$ 의 추이적 폐포(transitive closure^영어)는 $X$ 를 포함하는 가장 작은 추이적 집합이며, 다음과 같다.

: $\bigcup_{n=0}^\infty\operatorname{\overbrace{\bigcup\cdots\bigcup}^{\mathit n}}X=X\cup\bigcup X\cup\bigcup\bigcup X\cup\cdots$

우레엘리먼트를 포함하지 않는 집합 $X$ 는 자기 자신의 멱집합의 부분집합( $X \subseteq \mathcal{P}(X)$ )일 필요충분 조건을 만족할 때 추이적 집합이다.

2.1. 초추이적 집합

집합 $X$ 에 대하여 다음 두 조건이 동치이며, 이를 만족시키는 집합을 초추이적 집합(supertransitive set^영어)이라고 한다.
* 임의의 $A\in X$ 에 대하여, 만약 $B\subseteq A$ 또는 $B\in A$ 라면, $B\in X$
* 임의의 $A\in X$ 에 대하여, $A\cup\mathcal P(A)\subseteq X$
초추이적 집합은 추이적 집합이다.

보다 일반적으로, 순서수 $\alpha$ 에 대하여, 다음과 같은 누적 위계
: $\mathcal P^\alpha(X)=\begin{cases}\mathcal P(\mathcal P^\beta(X))&\exists\beta\colon\beta+1=\alpha\\X\cup\bigcup_{\gamma<\alpha}\mathcal P^\gamma(X)&\nexists\beta\colon\beta+1=\alpha\end{cases}$
를 생각하자. 이 경우, 다음 조건을 만족시키는 집합을 $\alpha$ -초추이적 집합( $\alpha$ -supertransitive set^영어)이라고 한다.
* 임의의 $A\in X$ 및 순서수 $\beta<\alpha$ 에 대하여, $\mathcal P^\beta(A)\subseteq X$
즉, 모든 집합은 0-초추이적 집합이며, 1-초추이적 집합은 추이적 집합이며, 2-초추이적 집합은 초추이적 집합이다.

집합 $X$ 의 $\alpha$ -초추이적 폐포는 $X$ 를 포함하는 가장 작은 $\alpha$ -초추이적 집합이며, 다음과 같다.
: $X\cup Q(X)\cup Q(Q(X))\cup\cdots$
: $Q(X)=\bigcup_{A\in X}\bigcup_{\beta<\alpha}\mathcal P^\beta(A)$

3. 성질

어떤 집합이 추이적 집합이 되기 위한 필요충분조건은 그 집합의 모든 원소들의 합집합이 그 집합의 부분집합이 되는 것이다. 즉, 집합 X에 대해 $\bigcup X \subseteq X$ 이며, $\bigcup X = \{y \mid \exists x \in X: y \in x\}$ 이다.

우레엘리먼트를 포함하지 않는 집합 X가 추이적 집합이 되기 위한 또 다른 필요충분조건은 X가 자신의 멱집합의 부분집합이 되는 것이다. 즉, $X \subseteq \mathcal{P}(X)$ 이다. 우레엘리먼트가 없는 추이적 집합의 멱집합은 추이적 집합이다.

3.1. 연산에 대한 닫힘

임의의 추이적 집합 $X$ 에 대하여, $\bigcup X$ 와 $X\cup\{X\}$ 역시 추이적 집합이다. 임의의 추이적 집합들의 족 $\mathcal X$ 에 대하여, $\bigcup\mathcal X$ 와 $\bigcap\mathcal X$ 역시 추이적 집합이다.

집합 $X$ 가 추이적 집합이 될 필요충분 조건은 $\bigcup X \subseteq X$ 이며, 여기서 $\bigcup X$ 는 집합 $X$ 의 모든 원소의 합집합이고, $\bigcup X = \{y \mid \exists x \in X: y \in x\}$ 이다.

만약 $X$ 가 추이적 집합이면, $\bigcup X$ 도 추이적 집합이다.

만약 $X$ 와 $Y$ 가 추이적 집합이면, $X\cup Y$ 와 $X \cup Y \cup \{X,Y\}$ 도 추이적 집합이다. 일반적으로, 만약 $Z$ 가 모든 원소가 추이적 집합인 클래스이면, $\bigcup Z$ 와 $Z\cup\bigcup Z$ 도 추이적 집합이다.

3.2. 자명하지 않은 동형의 부재

추이적 모임과 원소 관계로 이루어진 구조 사이의 동형 사상은 항등 함수밖에 없다. 즉, 추이적 모임 사이의 전단사 함수 $f\colon X\to Y$ 가 다음을 만족시킨다면,
: $A\in B\in X\iff f(A)\in f(B)\in Y$
, $X=Y$ 이며, $f=\operatorname{id}_X$ 이다. 이는 정칙성 공리를 사용하여 증명할 수 있다. 특히, 폰 노이만 전체는 자명하지 않은 자기 동형 사상을 갖지 않는다.

임의의 $A\in X$ 에 대하여, $f(A)=A$ 임을 보이는 것으로 충분하다. 정칙성 공리에 의하여, 모든 모임이 정초 모임임을 보일 수 있으며, 따라서 $(X,\in)$ 위에서 초한 귀납법을 사용할 수 있다. 이제, 임의의 $B\in A$ 에 대하여 $f(B)=B$ 라고 가정하자. 다음 두 가지를 보이면 충분하다.

* $A\subseteq f(A)$
임의의 $B\in A$ 에 대하여, $B=f(B)\in f(A)$ 이다.
* $f(A)\subseteq A$
임의의 $f(B)\in f(A)$ 에 대하여, $B\in A$ 이므로, $f(B)=B\in A$ 이다.

4. 추이적 폐포

집합 $X$ 의 추이적 폐포(transitive closure^영어)는 $X$ 를 포함하는 가장 작은 추이적 집합이다. 즉, 다음과 같다.
: $\bigcup_{n=0}^\infty\operatorname{\overbrace{\bigcup\cdots\bigcup}^{\mathit n}}X=X\cup\bigcup X\cup\bigcup\bigcup X\cup\cdots$

집합 $X$ 의 추이적 폐포는 $X$ 를 포함하는 (포함 관계에 대해) 가장 작은 추이적 집합이다 (즉, $X \subseteq \operatorname{TC}(X)$ ). 집합 $X$ 가 주어졌을 때, $X$ 의 추이적 폐포는 다음과 같다.

$\operatorname{TC}(X) = \bigcup \left\{ X,\; \bigcup X,\; \bigcup\bigcup X,\; \bigcup\bigcup\bigcup X,\; \bigcup\bigcup\bigcup\bigcup X, \ldots\right\}.$

이에 대한 증명은 다음과 같다. $X_0 = X$ 및 $X_{n+1} = \bigcup X_n$ 이라고 정의한다. 그러면 집합

$T = \operatorname{TC}(X) = \bigcup_{n=0}^\infty X_n$

는 추이적이며, $X$ 를 포함하는 임의의 추이적 집합 $T_1$ 에 대해 $T \subseteq T_1$ 이다.

$y \in x \in T$ 라고 가정하면, 어떤 $n$ 에 대해 $x \in X_n$ 이 성립하고, 따라서 $y \in \bigcup X_n = X_{n+1}$ 이다. $X_{n+1} \subseteq T$ 이므로, $y \in T$ 이다. 따라서 $T$ 는 추이적이다.

이제 $T_1$ 이 $X$ 를 포함하는 추이적 집합이라고 하자. 모든 $n$ 에 대해 $X_n \subseteq T_1$ 임을 귀납법으로 증명하여 $T \subseteq T_1$ 임을 보일 수 있다. $X_0 = X \subseteq T_1$ 이므로 기본 경우는 성립한다. $X_n \subseteq T_1$ 이라고 가정하면, $X_{n+1} = \bigcup X_n \subseteq \bigcup T_1$ 이다. $T_1$ 은 추이적이므로 $\bigcup T_1 \subseteq T_1$ 이고, 따라서 $X_{n+1} \subseteq T_1$ 이다.

이는 집합의 합집합이 멤버십 관계의 관계 결합으로 표현될 수 있으므로, 멤버십 관계의 추이적 폐포로 $X$ 와 관련된 모든 객체의 집합이다.

5. 예

순서수는 폰 노이만 정의에 따라, 추이적 집합만을 원소로 하는 추이적 집합이다. 폰 노이만 전체 및 구성 가능 전체의 각 단계는 추이적 집합이며, 전체 역시 추이적 고유 모임이다.

최대 20개의 중괄호를 가진 유한 추이적 집합의 예시는 다음과 같다:

* $\{\}$
* $\{\{\}\}$
* $\{\{\}, \{\{\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\}, \{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\}\}, \{\{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}, \{\{\}\}\}\}, \{\{\}, \{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}, \{\{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\}, \{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\}, \{\{\}\}\}, \{\{\{\}\}, \{\{\}, \{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\}, \{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\}\}, \{\{\}, \{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\{\{\{\}\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\}, \{\{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\}, \{\{\}\}\}\}, \{\{\}, \{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\{\}\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\}, \{\{\{\{\}\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\{\}\}, \{\{\{\}\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\}, \{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\{\}\}, \{\{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\{\}\}, \{\{\{\{\}\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\}, \{\{\}\}, \{\{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\}, \{\{\{\}\}\}\}\}, \{\{\}, \{\{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\{\}\}, \{\{\}, \{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\}\}, \{\{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\{\}\}\}\}, \{\{\{\}\}, \{\{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\{\{\}\}\}, \{\{\{\{\}\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\}, \{\{\}\}, \{\{\{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\{\{\}\}\}, \{\{\}, \{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\}\}, \{\{\}, \{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\{\}\}\}\}, \{\{\}, \{\{\}, \{\{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\{\}\}\}\}, \{\{\}, \{\{\}\}, \{\{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}, \{\{\}\}\}\}, \{\{\{\}, \{\{\}\}\}\}, \{\{\}, \{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}, \{\{\}\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\}, \{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}, \{\{\{\}\}\}\}\}, \{\{\{\}\}, \{\{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\{\}\}\}\}, \{\{\{\}\}, \{\{\}, \{\{\{\}\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\}\}, \{\{\{\}\}\}\}, \{\{\}, \{\{\}\}, \{\{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}, \{\{\}\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\{\}, \{\{\}\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}, \{\{\}\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\{\}\}, \{\{\}, \{\{\}\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\{\{\{\}\}\}\}\}, \{\{\}, \{\{\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\{\}, \{\{\}\}\}\}, \{\{\}, \{\{\}\}\}$
* $\{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\{\}\}\}\}$

6. 집합론에서의 추이적 모델

추이적 집합 · 모임은 모형 이론에서 집합론의 모형을 정의하기 위하여 쓰인다. 모스토프스키 붕괴 보조정리에 의하여, "괜찮은" 모형은 항상 추이적 모형으로 나타낼 수 있다.

추이적 집합은 종종 집합론 자체의 상대적 해석을 구성하는 데 사용되며, 일반적으로 내부 모형이라고 불린다. 그 이유는 제한된 양화사로 정의된 속성이 추이적 집합에 대해 절대적이기 때문이다.

집합론의 형식적 체계의 모형인 추이적 집합(또는 클래스)은 시스템의 추이적 모형이라고 불린다(모형의 원소 관계가 실제 원소 관계를 모형의 우주로 제한한 경우). 추이성은 공식의 절대성을 결정하는 데 중요한 요소이다.

비표준 해석에 대한 상부 구조 접근 방식에서 비표준 우주는 강한 추이성을 만족시킨다. 여기서, 클래스 $\mathcal{C}$ 는 각 집합 $S\in\mathcal{C}$ 에 대해 $S\subseteq T\subseteq\mathcal{C}$ 를 만족하는 추이적 상위 집합 $T$ 가 존재하면 강하게 추이적이라고 정의된다. 강하게 추이적인 클래스는 자동으로 추이적이다. 이 강화된 추이성 가정은 예를 들어 $\mathcal{C}$ 가 $\mathcal{C}$ 의 모든 이항 관계의 영역을 포함한다고 결론 내릴 수 있게 해준다.