상위 문서: 계산 이론 개론
개요
집합은 수학의 데이터 구조라고 할 수 있으며, 모든 수학적 객체는 순수 집합(pure sets)로부터 구성할 수 있다. 집합론은 작은 공리(axioms)들과 추론 규칙(rule of inference)를 통해 공식화될 수 있다.
Properties of Sets
Extensionality
집합론은 1차 논리(first-order logic)로 표현 가능하며, 이를 위한 기본 술어(predicates)는 [math]\displaystyle{ \in, = }[/math]이다. 이에 따라 두 집합이 같다는 것과 부분 집합 관계를 아래와 같이 표현할 수 있다:
[math]\displaystyle{ A = B \equiv \forall X. X \in A \leftrightarrow X \in B }[/math] [math]\displaystyle{ A\subseteq B \equiv \forall X. X \in A \rightarrow X \in B }[/math]
Comprehension and Empty Set
포괄성(Comprehension)은 집합 A와 조건(술어) P(X)가 주어지면, A 속에서 P(X)를 만족하는 원소만 모은 부분집합 B가 존재한다는 것을 의미한다. 이는 아래와 같이 나타낼 수 있다.
[math]\displaystyle{ {X \in A. P(X)} }[/math]
공집합(Empty Set)아무 원소도 가지지 않는 집합을 의미한다. 이는 아래와 같이 나타낼 수 있으며, [math]\displaystyle{ \empty }[/math]또는 {}와 같이 표기한다:
[math]\displaystyle{ \exists A. \forall X. X\notin A }[/math]
Paring
임의의 두 집합 A, B에 대해, 이 둘을 원소로 가지는 집합이 존재하며, 이는 순서 없는 쌍(unordered pair)로 간주된다. 이는 아래와 같이 나타내어 진다:
[math]\displaystyle{ {A, B} }[/math]
Union and Intersection
합집합(Union)이란 A 또는 B에 속하는 원소들을 모은 집합을 의미한다. 이는 아래와 같이 나타내어 진다:
[math]\displaystyle{ A \cup B \equiv \{X| X\in A \lor X\in B\} }[/math]
교집합이란 A와 B에 동시에 속하는 원소들의 집합을 의미한다. 이는 아래와 같이 나타내어 진다:
[math]\displaystyle{ A \cap B \equiv \{X| X\in A \land X\in B\} }[/math]
Big Union and Big Intersection
대합집합(Big-∪)이란 집합 A가 집합들의 집합일 때, A의 원소들 속에 들어 있는 모든 원소들의 모임을 의미한다. 또한 대교집합(Big-∩)이이란 집합 A의 원소들 모두에 공통으로 속하는 원소들의 집합을 의미한다. 이는 아래와 같은 예시를 통해 나타낼 수 있다:
[math]\displaystyle{ A = \{\{1, 2\},\{2, 3\}\} }[/math]이면 [math]\displaystyle{ \bigcup A = \{1,2,3\} }[/math] [math]\displaystyle{ \bigcap A = \{2\} }[/math]
Powerset
멱집합(Powerset)이란 어떤 집합 A가 있을 때, A의 부분집합들 전체를 모은 집합을 의미한다. 이는 아래와 같이 정의된다:
[math]\displaystyle{ \mathcal{P}(A) = {X|X\subseteq A} }[/math]
예를 들어:
[math]\displaystyle{ \mathcal{P}(\empty) = \{\empty\} }[/math] [math]\displaystyle{ \mathcal{P}(\mathcal{P}(\empty)) = \{\empty, \{\empty\}\} }[/math]
Derived Constructions
Ordered Pair
집합만으로 순서쌍 (A, B) 를 정의할 수 있으며, 이는 아래와 같다.
[math]\displaystyle{ Ordered pair (A, B) = \{\{A\}, \{A, B\}\} }[/math]
이와 같은 구조를 통해서 [math]\displaystyle{ (A, B) }[/math]와 [math]\displaystyle{ (B, A) }[/math]가 다른 구조가 되며, 순서를 반영할 수 있다. 이때 집합 A, B는 순서쌍 [math]\displaystyle{ (A, B) }[/math]를 통해 유일하게 결정된다. 이는 아래와 같이 설명할 수 있다:
[math]\displaystyle{ (A, B) = (C, D) \Leftrightarrow A = C, B = D }[/math]
Cartesian Product
데카르트 곱(Cartesian Product)의 정의는 아래와 같다:
[math]\displaystyle{ A \times B = \{(x, y)|x\in A, y \in B\} }[/math]
즉, A의 원소와 B의 원소로 만들 수 있는 모든 순서쌍의 집합을 의미한다. 예를 들어:
[math]\displaystyle{ A = \{1,2\}, B = \{a, b\} }[/math]이면 [math]\displaystyle{ A\times B = \{(1,a),(1,b),(2,a),(2,b)\} }[/math]
이 개념을 확정하여 튜플(tuple)을 만들수 있다. 튜플은 쉽게 말하자면 항이 세개 이상인 순서쌍이다. 예를 들어,
[math]\displaystyle{ A_1 \times A_2 \times A_3 \rightarrow }[/math] 원소가 [math]\displaystyle{ (x_1, x_2, x_3) }[/math]꼴 [math]\displaystyle{ A_1 \times A_2 \times A_3 \times A_4 \rightarrow }[/math] 원소가 [math]\displaystyle{ (x_1, x_2, x_3, x_4) }[/math]꼴
Infinity Set
어떤 수 X의 후자 집합(successor)는 X 자신과 그 원소들을 모두 포함하는 집합을 의미한다. 예를 들어:
[math]\displaystyle{ S(X)=X\cup\{X\} }[/math] [math]\displaystyle{ S(0) = \{0\} = 1 }[/math] [math]\displaystyle{ S(1) = \{0,1\} = 2 }[/math] [math]\displaystyle{ S(2) = \{0,1,2\} = 3 }[/math]
이를 통해서 무한집합의 개념을 도출할 수 있다. 이는 "공집합 [math]\displaystyle{ \empty }[/math]를 포함하고, 해당 원소 Y가 있으면 항상 [math]\displaystyle{ S(Y) }[/math]또한 포함해야 한다는 집합 [math]\displaystyle{ X }[/math]가 존재해야 한다"는 명제로부터 이끌어낼 수 있다. 이는 수식으로 아래와 같이 표현된다:
[math]\displaystyle{ \exists X. \empty \in X \land \forall Y(Y\in X \rightarrow S(Y) \in X) }[/math]
Russell's Paradox
이는 집합에 대한 역설이다. 이는 아래와 같다:
- 모든 집합들의 집합A를 가정하자.
- 어떤 집합 X에 대해, [math]\displaystyle{ X \notin X }[/math](스스로 자신을 원소로 포함하지 않는 집합)이라고 가정하자.
- 그런 집합들만 모아서 [math]\displaystyle{ B = \{X\in A|X \notin X\} }[/math]라는 집합을 만든다고 해보면 모순이 발생한다.
- [math]\displaystyle{ B \in B }[/math]라면, 정의상 [math]\displaystyle{ B \notin B }[/math]여야 한다.
- [math]\displaystyle{ B \notin B }[/math]라면, 정의상 [math]\displaystyle{ B \in B }[/math]여야 한다.
- 따라서 모순이 발생한다.
이런 역설을 피하려면, "어떤 것이 집합이 될 수 있는가"를 엄밀히 제한해야 한다. 이로 인해 ZFC 집합론 같은 공리 체계가 등장하였다.