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 }\}\}$

멱집합에 대한 중요한 정리(theorem)들중 하나는 모든 집합 A에 대해 아래 수식이 성립한다는 것이다:

$|A|<|{𝒫}(A)|$

즉, 집합 A의 크기보다 멱집합이 항상 더 크다.

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)$꼴

Finite and Infinite Set

유한집합의 정의는 아래와 같다:

임의의 $f:A\to A$가 injection이면 곧 surjection이라는 것을 의미한다. 즉, injection과 surjection이 서로 구분되지 않는다. 

이때 유한하지 않는 집합은 모두 무한(infinite)하다. 이때 무한 집합의 개념을 다른 방식으로 도출해보자. 이를 위해 어떤 수 X의 후자 집합(successor)에 대해 알아보자. X의 후자 집합이란 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)$

유한집합의 무한집합과의 가장 큰 차이는 자기 자신의 진부분집합(proper subset)과 일대일 대응(bijection)을 만들 수 없다는 것이다. 예를 들어, $\{A\}\leftrightarrow \{B\}$과 같은 대응은 불가능하다. 반면 무한집합은 자기 자신의 진부분집합과도 일대일대응이 가능하다. 예를 들어 자연수 $\mathbb{\mathbb{N}}$과 짝수 집합 $2\mathbb{\mathbb{N}}$은 bijection $n\leftrightarrow 2n$으로 대응 가능하다.

또한 어떤 유한집합 A는 $\mathbb{\mathbb{N}}$의 어떤 초기 부분과 일대일 대응 관계가 성립할 수 있다. 즉, 크기가 n인 유한 집합은 $\{0,1,\cdots ,n-1\}$과 일대일 대응이 가능하다.

Countable and Uncountable Sets

집합이 가산 무한(countably infinite) 이라는 것은 자연수 전체 집합$\mathbb{\mathbb{N}}$과 일대일 대응이 가능하다는 것을 의미한다. 가산 집합(countable set)은 유한이거나 가산 무한인 집합을 의미하며, 비가산 집합(uncountable set)은 가산이 아닌 집합을 의미한다. 예를 들어 함수 $n\leftrightarrow 2n$은 자연수 집합과 짝수 집합 사이의 bijection이므로, 짝수 집합도 가산 무한 집합이다.

이에 따라 집합 A가 가산 집합이라는 것은 자연수에서 A로 가는 전사 함수(surjection)가 존재한다는 것을 의미한다.

Countability of the Rational Numbers

유리수 집합 $\mathbb{\mathbb{Q}}$는 가산 집합이다. 해당 문단에서는 이를 증명한다.

• 유리수는 $p/q$꼴이다.
• 이 분수들을 (p,q) 격자 형태로 나열하면 자연수와 일대일 대응기 가능하다. 이는 아래와 같은 꼴이다.

0/1	0/2	0/3	...
1/1	1/2	1/3	...
2/1	2/2	2/3	...
3/1	3/2	3/3	...
...	...	...

위 표에서 대각선 순서들을로 하나씩 세어 나가면 $\mathbb{\mathbb{Q}}$ 전체를 열거할 수 있다. 따라서 유리수 집합 $\mathbb{\mathbb{Q}}$은 가산 집합이다.

Existence of Uncountable Sets

해당 문단에서는 어떤 비가산 집합이 존재함을 증명하고, 이를 실수 집합에 확장한다. 증명하고자 하는 명제는 "모든 함수 $f:\mathbb{\mathbb{N}}\to \{0,1\}$의 집합은 비가산 집합이다."이다. 이는 칸토어의 대각선 논법에 의해서 증명될 수 있으며, 이는 아래와 같다:

• $B=\{f:\mathbb{\mathbb{N}}\to \{0,1\}\}$이라고 하자.
• B가 가산 집합이라고 가정하자. 이는 $f_0,f_1,f_2,...$와 같은 꼴로 나열 된다. 아래와 같은 표를 생각하자.

$f_0(0)$	$f_0(1)$	$f_0(2)$	...
$f_1(0)$	$f_1(1)$	$f_1(2)$	...
...	...	...

• 이때 새로운 함수 f를 $f(k)=1-f_k(k)$와 같이 정의하자.
• 해당 $f$는 어떠한 $f_i$와도 같은 수 없으므로 나열에 포함되지 않으며, B는 비가산이다.

이 증명은 곧 실수 집합 $\mathbb{ℝ}$도 비가산임을 보여주는 핵심적인 아이디어이다.

Russell's Paradox

이는 집합에 대한 역설이다. 이는 아래와 같다:

• 모든 집합들의 집합A를 가정하자.
• 어떤 집합 X에 대해, $X\notin X$(스스로 자신을 원소로 포함하지 않는 집합)이라고 가정하자.
• 그런 집합들만 모아서 $B=\{X\in A|X\notin X\}$라는 집합을 만든다고 해보면 모순이 발생한다.
  • $B\in B$라면, 정의상 $B\notin B$여야 한다.
  • $B\notin B$라면, 정의상 $B\in B$여야 한다.
  • 따라서 모순이 발생한다.

이런 역설을 피하려면, "어떤 것이 집합이 될 수 있는가"를 엄밀히 제한해야 한다. 이로 인해 ZFC 집합론 같은 공리 체계가 등장하였다.

Languages

언어(language)란, 특정한 알파벳 위에서 정의된 문자열들의 집합을 말한다. 즉, 언어는 단순한 기호의 나열이 아니라, 수학적으로는 집합이라는 기본적인 수학적 객체(Mathematical Object)로 이해할 수 있다. Languages 문서에서는 이러한 언어에 대한 집합론적인 설명에 대해 다룬다.