Sets

상위 문서: 계산 이론 개론

개요

집합은 수학의 데이터 구조라고 할 수 있으며, 모든 수학적 객체는 순수 집합(pure sets)로부터 구성할 수 있다. 집합론은 작은 공리(axioms)들과 추론 규칙(rule of inference)를 통해 공식화될 수 있다.

Properties of Sets

Extensionality

집합론은 1차 논리(first-order logic)로 표현 가능하며, 이를 위한 기본 술어(predicates)는 $\in ,=$이다. 이에 따라 두 집합이 같다는 것과 부분 집합 관계를 아래와 같이 표현할 수 있다:

$A=B\equiv \mathrm{\forall }X.X\in A\leftrightarrow X\in B$
$A\subseteq B\equiv \mathrm{\forall }X.X\in A\to X\in B$

Comprehension and Empty Set

포괄성(Comprehension)은 집합 A와 조건(술어) P(X)가 주어지면, A 속에서 P(X)를 만족하는 원소만 모은 부분집합 B가 존재한다는 것을 의미한다. 이는 아래와 같이 나타낼 수 있다.

$X\in A.P(X)$

공집합(Empty Set)아무 원소도 가지지 않는 집합을 의미한다. 이는 아래와 같이 나타낼 수 있으며, $\mathrm{\varnothing }$또는 {}와 같이 표기한다:

$\mathrm{\exists }A.\mathrm{\forall }X.X\notin A$

Paring

임의의 두 집합 A, B에 대해, 이 둘을 원소로 가지는 집합이 존재하며, 이는 순서 없는 쌍(unordered pair)로 간주된다. 이는 아래와 같이 나타내어 진다:

$A,B$

Union and Intersection

합집합(Union)이란 A 또는 B에 속하는 원소들을 모은 집합을 의미한다. 이는 아래와 같이 나타내어 진다:

$A\cup B\equiv \{X|X\in A\vee X\in B\}$

교집합이란 A와 B에 동시에 속하는 원소들의 집합을 의미한다. 이는 아래와 같이 나타내어 진다:

$A\cap B\equiv \{X|X\in A\wedge X\in B\}$

Big Union and Big Intersection

대합집합(Big-∪)이란 집합 A가 집합들의 집합일 때, A의 원소들 속에 들어 있는 모든 원소들의 모임을 의미한다. 또한 대교집합(Big-∩)이이란 집합 A의 원소들 모두에 공통으로 속하는 원소들의 집합을 의미한다. 이는 아래와 같은 예시를 통해 나타낼 수 있다:

$A=\{\{1,2\},\{2,3\}\}$이면
$\bigcup A=\{1,2,3\}$
$\bigcap A=\{2\}$

Powerset

멱집합(Powerset)이란 어떤 집합 A가 있을 때, A의 부분집합들 전체를 모은 집합을 의미한다. 이는 아래와 같이 정의된다:

${𝒫}(A)=X|X\subseteq A$

예를 들어:

${𝒫}(\mathrm{\varnothing })=\{\mathrm{\varnothing }\}$
${𝒫}({𝒫}(\mathrm{\varnothing }))=\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}$

Derived Constructions

Ordered Pair

집합만으로 순서쌍 (A, B) 를 정의할 수 있으며, 이는 아래와 같다.

$Orderedpair(A,B)=\{\{A\},\{A,B\}\}$

이와 같은 구조를 통해서 $(A,B)$와 $(B,A)$가 다른 구조가 되며, 순서를 반영할 수 있다. 이때 집합 A, B는 순서쌍 $(A,B)$를 통해 유일하게 결정된다. 이는 아래와 같이 설명할 수 있다:

$(A,B)=(C,D)\iff A=C,B=D$

Cartesian Product

데카르트 곱(Cartesian Product)의 정의는 아래와 같다:

$A\times B=\{(x,y)|x\in A,y\in B\}$

즉, A의 원소와 B의 원소로 만들 수 있는 모든 순서쌍의 집합을 의미한다. 예를 들어:

$A=\{1,2\},B=\{a,b\}$이면
$A\times B=\{(1,a),(1,b),(2,a),(2,b)\}$

이 개념을 확정하여 튜플(tuple)을 만들수 있다. 튜플은 쉽게 말하자면 항이 세개 이상인 순서쌍이다. 예를 들어,

$A_1\times A_2\times A_3\to$ 원소가 $(x_1,x_2,x_3)$꼴
$A_1\times A_2\times A_3\times A_4\to$ 원소가 $(x_1,x_2,x_3,x_4)$꼴

Infinity Set

어떤 수 X의 후자 집합(successor)는 X 자신과 그 원소들을 모두 포함하는 집합을 의미한다. 예를 들어:

$S(X)=X\cup \{X\}$
$S(0)=\{0\}=1$
$S(1)=\{0,1\}=2$
$S(2)=\{0,1,2\}=3$

이를 통해서 무한집합의 개념을 도출할 수 있다. 이는 "공집합 $\mathrm{\varnothing }$를 포함하고, 해당 원소 Y가 있으면 항상 $S(Y)$또한 포함해야 한다는 집합 $X$가 존재해야 한다"는 명제로부터 이끌어낼 수 있다. 이는 수식으로 아래와 같이 표현된다:

$\mathrm{\exists }X.\mathrm{\varnothing }\in X\wedge \mathrm{\forall }Y(Y\in X\to S(Y)\in X)$