체르멜로-프렝켈 집합론

사실 치킨집이다.

수학에서, 체르멜로-프렝켈 집합론(Zermelo-Fraekel set theory, ZF)과 선택 공리를 포함하는 체르멜로-프렝켈 집합론(ZF with the axiom of Choice, ZFC)은 가장 보편적인 공리적 집합론의 일종으로, 표준적인 수학기초론으로 사용된다. ZF(C)에서 몇 개의 공리를 제외한 것을 체르멜로 집합론(Zermelo set theory, Z)이라고 한다.

진술

Z

• 확장 공리 또는 외연 공리(axiom of extensionality)

  두 집합의 상동을 정의하는 공리. 두 집합의 상동은 그 원소들만으로 결정된다. 확장 공리는 합집합 공리, 멱집합 공리, 치환 공리꼴, 선택 공리와 독립적(증명될 수 없음)이다.

  [math]\displaystyle{ \forall A \forall B[\forall x (x \in A \leftrightarrow x \in B)\Longrightarrow a=b]. }[/math]

• 짝 공리(axiom of pairing)

  어떤 두 집합을 원소로서 가지는 집합이 존재한다는 공리이다. 더욱 특정하게, 그 두 집합만을 원소로 하는 집합이 존재한다고도 한다. 여기에서 순서쌍의 존재성이 증명될 수 있다.

  [math]\displaystyle{ \forall x \forall y \exists A \forall z[z\in A \Longleftrightarrow (z=x \lor z=y)]. }[/math]

• 분류 공리꼴(axiom schema of specification, axiom schema of comprehension (restricted))

  어떤 집합과 성질이 정의되어 있을 때, 그 집합의 원소들 중(restricted) 주어진 성질을 만족하는 것들을 모은 집합이 존재한다. 범위를 주어진 집합보다 작게 제한한 이유는 모임이 너무 커서 생기는 러셀의 역설 등을 피하기 위한 것이다. 집합이 아닌 class를 정의하는 공리계의 경우, 특정한 집합의 원소들만을 모을 필요가 없다. NBG 참조.

  [math]\displaystyle{ \varphi }[/math]가 [math]\displaystyle{ x, w_1, \cdots, w_n, A }[/math]를 자유변수(free-variable)로 갖는 formula이면,

  [math]\displaystyle{ \forall w_1, \cdots, w_n \forall A \exists B \forall x \left(x\in B \Leftrightarrow [x\in A \wedge \varphi(x, w_1, \cdots, w_n, A)]\right) }[/math]

• 합집합 공리(axiom of union)

  어떤 집합족이 주어지면, 그 합집합이 존재한다.

  [math]\displaystyle{ \forall \mathcal F \exists U \forall x[x\in U \Longleftrightarrow \exists A(x\in A \wedge A \in \mathcal F) ]. }[/math]

• 멱집합 공리(axiom of power set)

  어떤 집합이 주어지면, 그 멱집합이 존재한다.

  [math]\displaystyle{ \forall A \exists \mathcal P \forall B[\forall x(x\in B \rightarrow y\in A)\Longleftrightarrow B\in \mathcal P]. }[/math]

• 무한 공리(axiom of infinity)

  공집합을 포함하며, 어떤 원소의 (transitive하게 정의되는) successor 역시 원소로 가지는 집합이 존재한다.

  [math]\displaystyle{ \exists I [\emptyset \in I \wedge (x\in I \Rightarrow x^+\in I)], \quad \text{where } x^+:=x\cup \{x\}. }[/math]

  • 무한공리는 ZFC의 다른 공리들과 독립적이며, ZF의 다른 공리들을 가정하면 다음 명제들과 동치이다:

  1. 무한 집합이 존재한다. (이것이 이 명제의 이름을 결정했을 것이다.)
  2. 무한 서수 [math]\displaystyle{ \omega }[/math]가 집합이다.
  3. 귀납적인 집합(inductive set)이 존재한다.

ZF

• 치환 공리꼴(axiom schema of replacement)

  주어진 형식적으로 정의된 함수(definable class function)에 대하여 그 정의역이 집합일 때, 그 치역이 집합이 된다.

  [math]\displaystyle{ \varphi }[/math]가 [math]\displaystyle{ x, y, w_1, \cdots, w_n, A }[/math]를 자유변수(free-variable)로 갖는 formula이면,

  [math]\displaystyle{ \forall w_1, \cdots, w_n \forall A \left[\left(\forall x \in A \exists ! y [\varphi (x, y, w_1, \cdots, w_n, A)] \Longrightarrow \exists B \forall y [y \in B \Leftrightarrow \exists x \in A \varphi(x, y, w_1, \cdots, w_n, A)]\right)\right]. }[/math]

  • 치환 공리꼴과 비슷한 공리꼴로 모임 공리꼴(axiom schema of collection)이라는 것이 있다. 치환 공리꼴은 치역 자체가 집합이 되어야 하지만, 모임 공리꼴이 진술하는 것은, 그 치역을 포함하는 집합의 존재성이다. 그 치역 자체는 집합이 될 필요가 없으며, 그 superclass 중 하나가 집합이기만 하면 된다.

• 정칙성 공리(axiom of regularity) 또는 기초 공리(axiom of foundation)

  공집합이 아닌 모든 집합은 자신과 서로소인 원소만을 포함한다. 이 공리에 따라 자기 자신을 포함하는 집합 등은 존재할 수 없다. 이를 달리 쓰면 관계 [math]\displaystyle{ \in }[/math]가 well-founded되어 있다 ― 즉 임의의 집합이 [math]\displaystyle{ \in }[/math]-최소원을 갖는다 ― 고 해석할 수 있다.

  [math]\displaystyle{ \forall x[x\ne\emptyset \Longrightarrow \exists y \in x(y \cap x = \emptyset)], }[/math]

  혹은 [math]\displaystyle{ \forall x[x\ne \emptyset \Longrightarrow \exists y \in x \forall z(z\in x \Rightarrow z \notin y)]. }[/math]

  • 참고로, 정칙성 공리는 ZFC 중 가장 쓸데없는존재 이유를 알기 힘든 공리로 꼽히는데, 왜냐하면 무언가를 증명할 때에 이 공리가 쓰이는 일이 거의 없기 때문이다. 하지만 이 공리로 다음과 같은 것들을 보일 수 있다:
  • 정칙성 공리로 무한한 감소 집합렬, 즉 [math]\displaystyle{ A_0 \ni A_1 \ni \cdots }[/math]를 만족하는 집합렬 [math]\displaystyle{ \{ A_n \}_{n\in\mathbb N} }[/math]은 존재하지 않음을 보일 수 있다. 만약 DC를 가정하면 반대로 이 명제에서 정칙성을 이끌어낼 수도 있다.
  • 정칙성 공리를 가정하면 von Neumann universe와 모든 집합들의 class가 같다.

C

이와 관련한 주제는 선택 공리에서 다룹니다.

선택 공리((the) Axiom of Choice)는 임의의 집합족의 각 집합에서 원소를 하나씩 선택하여 모아 만든 새로운 집합을 구성할 수 있음을 주장하는 공리이다. 다음과 같은 몇 개의 버전이 있으며, 다음은 모두 동치이다:

1. [math]\displaystyle{ \mathcal A }[/math]를 mutually disjoint한 공이 아닌 집합들의 족이라 하자. 그렇다면 [math]\displaystyle{ \mathcal A }[/math]의 각각의 집합으로부터 하나의 원소-씩으로 구성된 집합이 존재한다.
2. [math]\displaystyle{ \mathcal A = \{A_i\}_{i\in I} }[/math]를 index를 가진 집합족이라 하자. [math]\displaystyle{ I\ne \emptyset }[/math]이면, [math]\displaystyle{ \prod_{i \in I} A_i \ne \emptyset }[/math]이다.
3. [math]\displaystyle{ \mathcal A = \{A_i\}_{i\in I} }[/math]를 index를 가진 집합족이라 하자. [math]\displaystyle{ I\ne \emptyset }[/math]이면, 어떤 집합 [math]\displaystyle{ C }[/math]가 존재하여 [math]\displaystyle{ \forall i \in I [C \cap A_i \text{ is a singleton}] }[/math]이다.
4. 선택함수(choice function)가 존재한다. 더욱 명시적으로, 주어진 집합 [math]\displaystyle{ A }[/math]에 대하여, 함수 [math]\displaystyle{ F:\mathcal P(A) \to A }[/math]가 존재하여 [math]\displaystyle{ \forall X \in A[X\ne \emptyset \Rightarrow F(X) \in X] }[/math]이다.

ZF와의 독립성

쿠르트 괴델은 ZF가 일관적(consistent)임을 가정하고, AC의 부정이 ZF의 정리가 아님을 ZFC를 만족하는 내부 모형을 구성함으로써 보여 결과적으로 ZFC가 일관적임을 보였다. 또 폴 코언은 강제법을 이용하여 ZF¬C인 모형을 구성하고 이것이 일관적임을 보였다. 이 두 결과로부터 우리는 ZF와 AC가 논리적으로 독립임을 알 수 있다.