Sets 문서 원본 보기

[[분류:계산 이론 개론]]
[[분류:컴퓨터 공학]]
상위 문서: [[계산 이론 개론#Mathematical Objects|계산 이론 개론]]

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

==Properties of Sets==
===Extensionality===
집합론은 1차 논리(first-order logic)로 표현 가능하며, 이를 위한 기본 술어(predicates)는 <math>\in, =</math>이다. 이에 따라 두 집합이 같다는 것과 부분 집합 관계를 아래와 같이 표현할 수 있다:
 <math>A = B \equiv \forall X. X \in A \leftrightarrow X \in B</math>
 <math>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>{X \in A. P(X)}</math>
공집합(Empty Set)아무 원소도 가지지 않는 집합을 의미한다. 이는 아래와 같이 나타낼 수 있으며, <math>\empty</math>또는 {}와 같이 표기한다:
 <math>\exists A. \forall X. X\notin A</math>

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

===Union and Intersection===
합집합(Union)이란 A 또는 B에 속하는 원소들을 모은 집합을 의미한다. 이는 아래와 같이 나타내어 진다:
 <math>A \cup B \equiv \{X| X\in A \lor X\in B\}</math>
교집합이란 A와 B에 동시에 속하는 원소들의 집합을 의미한다. 이는 아래와 같이 나타내어 진다:
 <math>A \cap B \equiv \{X| X\in A \land X\in B\}</math>

===Big Union and Big Intersection===
대합집합(Big-∪)이란 집합 A가 집합들의 집합일 때, A의 원소들 속에 들어 있는 모든 원소들의 모임을 의미한다. 또한 대교집합(Big-∩)이이란 집합 A의 원소들 모두에 공통으로 속하는 원소들의 집합을 의미한다. 이는 아래와 같은 예시를 통해 나타낼 수 있다:
 <math>A = \{\{1, 2\},\{2, 3\}\}</math>이면
 <math>\bigcup A = \{1,2,3\}</math>
 <math>\bigcap A = \{2\}</math>

===Powerset===
멱집합(Powerset)이란 어떤 집합 A가 있을 때, A의 부분집합들 전체를 모은 집합을 의미한다. 이는 아래와 같이 정의된다:
 <math>\mathcal{P}(A) = \{X|X\subseteq A\}</math>
예를 들어:
 <math>\mathcal{P}(\empty) = \{\empty\}</math>
 <math>\mathcal{P}(\mathcal{P}(\empty)) = \{\empty, \{\empty\}\}</math>
멱집합에 대한 중요한 정리(theorem)들중 하나는 모든 집합 A에 대해 아래 수식이 성립한다는 것이다:
 <math>|A| < |\mathcal{P}(A)|</math>
즉, 집합 A의 크기보다 멱집합이 항상 더 크다.

==Derived Constructions==
===Ordered Pair===
집합만으로 순서쌍 (A, B) 를 정의할 수 있으며, 이는 아래와 같다.
 <math>Ordered pair (A, B) = \{\{A\}, \{A, B\}\}</math>
이와 같은 구조를 통해서 <math>(A, B)</math>와 <math>(B, A)</math>가 다른 구조가 되며, 순서를 반영할 수 있다. 이때 집합 A, B는 순서쌍 <math>(A, B)</math>를 통해 유일하게 결정된다. 이는 아래와 같이 설명할 수 있다:
 <math>(A, B) = (C, D) \Leftrightarrow A = C, B = D</math>

===Cartesian Product===
데카르트 곱(Cartesian Product)의 정의는 아래와 같다:
 <math>A \times B = \{(x, y)|x\in A, y \in B\}</math>
즉, A의 원소와 B의 원소로 만들 수 있는 모든 순서쌍의 집합을 의미한다. 예를 들어:
 <math>A = \{1,2\}, B = \{a, b\}</math>이면
 <math>A\times B = \{(1,a),(1,b),(2,a),(2,b)\}</math>
이 개념을 확정하여 튜플(tuple)을 만들수 있다. 튜플은 쉽게 말하자면 항이 세개 이상인 순서쌍이다. 예를 들어,
 <math>A_1 \times A_2 \times A_3 \rightarrow</math> 원소가 <math>(x_1, x_2, x_3)</math>꼴
 <math>A_1 \times A_2 \times A_3 \times A_4 \rightarrow</math> 원소가 <math>(x_1, x_2, x_3, x_4)</math>꼴

==Finite and Infinite Set==
유한집합의 정의는 아래와 같다:
 임의의 <math>f: A \rightarrow A</math>가 injection이면 곧 surjection이라는 것을 의미한다. 즉, injection과 surjection이 서로 구분되지 않는다. 

이때 유한하지 않는 집합은 모두 무한(infinite)하다. 이때 무한 집합의 개념을 다른 방식으로 도출해보자. 이를 위해 어떤 수 X의 후자 집합(succespr set)에 대해 알아보자. X의 후자 집합이란 X 자신과 그 원소들을 모두 포함하는 집합을 의미한다. 예를 들어:
 <math>S(X)=X\cup\{X\}</math>
 <math>S(0) = \{0\} = 1</math>
 <math>S(1) = \{0,1\} = 2</math>
 <math>S(2) = \{0,1,2\} = 3</math>
이를 통해서 무한집합의 개념을 도출할 수 있다. 이는 "공집합 <math>\empty</math>를 포함하고, 해당 원소 Y가 있으면 항상 <math>S(Y)</math>또한 포함해야 한다는 집합 <math>X</math>가 존재해야 한다"는 명제로부터 이끌어낼 수 있다. 이는 수식으로 아래와 같이 표현된다:
 <math>\exists X. \empty \in X \land \forall Y(Y\in X \rightarrow S(Y) \in X)</math>
유한집합의 무한집합과의 가장 큰 차이는 자기 자신의 진부분집합(proper subset)과 일대일 대응(bijection)을 만들 수 없다는 것이다. 예를 들어, <math>\{A\}\leftrightarrow\{B\}</math>과 같은 대응은 불가능하다. 반면 무한집합은 자기 자신의 진부분집합과도 일대일대응이 가능하다. 예를 들어 자연수 <math>\mathbb{N}</math>과 짝수 집합 <math>2\mathbb{N}</math>은 bijection <math>n \leftrightarrow 2n</math>으로 대응 가능하다. 

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

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

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

===Countability of the Rational Numbers===
유리수 집합 <math>\mathbb{Q}</math>는 가산 집합이다. 해당 문단에서는 이를 증명한다.
* 유리수는 <math>p/q</math>꼴이다.<ref>이때 p, q는 정수이며, q <math>\neq</math>0 이다.</ref>
*이 분수들을 (p,q) 격자 형태로 나열하면 자연수와 일대일 대응이 가능하다. 이는 아래와 같은 꼴이다.
{| class="wikitable"
|+
!'''0/1'''
!'''0/2'''
!'''0/3'''
!'''...'''
|-
|'''1/1'''
|'''1/2'''
|'''1/3'''
|'''...'''
|-
|'''2/1'''
|'''2/2'''
|'''2/3'''
|'''...'''
|-
|'''3/1'''
|'''3/2'''
|'''3/3'''
|'''...'''
|-
|'''...'''
|'''...'''
|'''...'''
|
|}
위 표에서 대각선 순서들을로 하나씩 세어 나가면 <math>\mathbb{Q}</math> 전체를 열거할 수 있다. 따라서 유리수 집합 <math>\mathbb{Q}</math>은 가산 집합이다.

===Existence of Uncountable Sets===
해당 문단에서는 어떤 비가산 집합이 존재함을 증명하고, 이를 실수 집합에 확장한다. 증명하고자 하는 명제는 "모든 함수 <math>f:\mathbb{N}\rightarrow\{0,1\}</math>의 집합은 비가산 집합이다."이다.<ref><math>\{0,1\}^\mathbb{N}</math>은 비가산이라는 것을 의미하는 명제이다.</ref> 이는 칸토어의 대각선 논법에 의해서 증명될 수 있으며, 이는 아래와 같다:
* <math>B = \{f:\mathbb{N}\rightarrow\{0,1\}\}</math>이라고 하자.
* B가 가산 집합이라고 가정하자. 이는 <math>f_0,f_1,f_2,...</math>와 같은 꼴로 나열 된다. 아래와 같은 표를 생각하자.
{| class="wikitable"
|+
!<math>f_0(0)</math>
!<math>f_0(1)</math>
!<math>f_0(2)</math>
!...
|-
|<math>f_1(0)</math>
|<math>f_1(1)</math>
|<math>f_1(2)</math>
|...
|-
|...
|...
|...
|
|}
* 이때 새로운 함수 f를 <math>f(k) = 1-f_k(k)</math>와 같이 정의하자.<ref>대각선 원소의 값을 반대로 뒤집은 값이다.</ref>
* 해당 <math>f</math>는 어떠한 <math>f_i</math>와도 같은 수 없으므로 나열에 포함되지 않으며, B는 비가산이다.
이 증명은 곧 실수 집합 <math>\mathbb{R}</math>도 비가산임을 보여주는 핵심적인 아이디어이다.

==Russell's Paradox==
이는 집합에 대한 역설이다. 이는 아래와 같다:
* 모든 집합들의 집합A를 가정하자.
* 어떤 집합 X에 대해, <math>X \notin X</math>(스스로 자신을 원소로 포함하지 않는 집합)이라고 가정하자.
* 그런 집합들만 모아서 <math>B = \{X\in A|X \notin X\}</math>라는 집합을 만든다고 해보면 모순이 발생한다.
** <math>B \in B</math>라면, 정의상 <math>B \notin B</math>여야 한다.
** <math>B \notin B</math>라면, 정의상 <math>B \in B</math>여야 한다.
** 따라서 모순이 발생한다.
이런 역설을 피하려면, "어떤 것이 집합이 될 수 있는가"를 엄밀히 제한해야 한다. 이로 인해 ZFC 집합론 같은 공리 체계가 등장하였다.

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

==각주==