1.1 Mathematical preliminaries and notation
앞으로 배울 내용들을 위한 수학적 배경지식과 표기법에 대해 알아보자.
Set (집합)
집합은 원소들의 모음으로, 집합은 대문자로, 원소는 소문자로 표기한다.
\[x \in S\]원소 x가 집합 S에 속한다.
\[x \notin S\]원소 x가 집합 S에 속하지 않는다.
집합은 다음과 같이 자신에 속한 원소들을 보여줄 수 있다.
\[S = {0, 1, 2}\]혹은 조건식을 사용해서 집합에 포함되는 원소들을 표기할 수 있다.
\[\begin{align*} S = & \left\{i\ |\ 0 < i, i\ is\ even \right\} \\ \end{align*}\]위의 식은, 집합 S는 0보다 큰 모든 짝수를 포함한다는 것을 나타낸다.
집합에서 자주 사용하는 연산 기호로는 union (\(\cap\)), intersection (\(\cup\)), 그리고 difference(\(-\))가 있다.
\[\begin{align*} S_1 \cap S_2 = & \left\{x\ |\ x \in S_1\ or\ x \in S_2\right\} \\ S_1 \cup S_2 = & \left\{x\ |\ x \in S_1\ and\ x \in S_2\right\} \\ S_1 - S_2 = & \left\{x\ |\ x \in S_1\ and\ x \notin S_2\right\} \\ \end{align*}\]그리고 다른 기본 연산으로는 complementation이 있다. 집합 S의 complement는 \(\bar{S}\)이며, S에 속하지 않는 모든 원소들의 집합이다. 그리고 좀 더 이해를 돕기 위해 universal set (전체집합) U의 개념이 필요한데, U는 모든 원소들의 집합니다. 따라서 다음과 같이 표현할 수 있다.
\[\begin{align*} \bar{S} = \left\{x\ |\ x \in U\ and\ x \notin S \right\} \\ \end{align*}\]원소가 하나도 없는 집합을 empty set (or null set) (공집합)이라고 하는데, \(\emptyset\)으로 표현한다. 집합의 정의에 의해 다음 식들은 자명하다.
\[\begin{align*} S \cap \emptyset = S - \emptyset = S, \\ S \cup \emptyset = \emptyset, \\ \bar{\emptyset} = U, \\ \bar{\bar{S}} = S. \\ \end{align*}\]DeMorgan’s law (드모르간의 법칙)
$$ \begin{align*} \overline{S_1 \cap S_2} = \bar{S_1} \cup \bar{S_2}, \\ \overline{S_1 \cup S_2} = \bar{S_1} \cap \bar{S_2}, \\ \end{align*} $$
집합 \(S_1\)의 모든 원소가 집합 S의 원소일때, 집합 \(S_1\)은 집합 S의 subset (부분집합) 이라고 하고 아래와 같이 쓴다.
\[\begin{align*} S_1 \subseteq S. \\ \end{align*}\]그리고 만약 집합 S가 집합 \(S_1\)의 원소가 아닌 원소를 갖고 있으면, 집합 \(S_1\)은 집합 S의 proper subset of S (S의 진부분집합) 이라고 하며 아래와 같이 쓴다.
\[\begin{align*} S_1 \subset S. \\ \end{align*}\]만약 집합 \(S_1\)과 집합 \(S_2\)가 공통원소가 없다면, (즉, \(S_1 \cup S_2 = \emptyset\)) 두 집합은 disjoint하다고 한다. 집합의 원소가 유한하면, 유한집합이라고 하고, 무한하면 무한집합이라고 한다. 또한, 유한집합의 경우 원소의 개수를 \(\left\vert S \right\vert\)로 나타낸다.
대부분의 집합은 다양한 부분집합을 갖는다. 집합 S의 모든 부분집합을 나타낸 집합을 powerset of S라고 부르며, \(2^S\)라고 표기한다.
앞으로 우리가 다룰 문제들에서 집합의 원소는 다른 집합의 원소들의 순서가 있는 나열이다. 그리고 이런 집합들을 다른 집합의 Cartesian product라고 부른다. 두 집합의 Cartesian product는 순서쌍의 집합일 것이며 다음과 같이 표기한다.
\[\begin{align*} S = S_1 \times S_2 = \left\{\left(x,y\right)\ | \ x \in S_1, y \in S_2 \right\}. \\ \end{align*}\]