Chapter 0. Sets and Relations

현대대수학은 집합 내용부터 짚고 시작한다! 집합, relation, function, cardinality, partition 등의 개념에 대해 아래에서 설명한다.

---

목차

• Set
• Subset
• cartesian product
• 숫자와 관련된 집합
• Relation
• function
• one-to-one, onto, one-to-one correspondence
• Cardinality
• Paritions
• Equivalence relation

---

집합$($Set$)$

집합은 다음 4가지 정도로 간단하게 요약할 수 있다.

1. 집합$($Set$)$ $S$는 원소들$($elements$)$로 이루어져 있으며, $a$가 이 원소들 중 하나라면 다음과 같이 표기 할 수 있다.
   $$a\in S$$
2. 원소가 전혀 없는 집합이 있다. 이 집합을 공집합$($empty set$)$이라고 부르며 $\varnothing $ 기호를 사용하여 표기한다.
   
   
3. 집합을 표현하는 표준적인 방법은 원소 나열법과 조건 제시법이 있다. 원소 나열법은 $\{1, 2, 15\}$와 같이 원소, 쉼표, 괄호를 통해 원소들을 나열하여 표기하는 방식이다. 조건 제시법은 $\{x | P(x)\}$와 같이 표기하며 "$x$에 관한 statement $P(x)$가 참이 되는 모든 $x$들의 집합"이라는 뜻이다.
   $$\{2,\, 4,\, 6,\, 8\} = \{x\, |\, x는\, 8\, 이하의\, 양의\, 짝수\} = \{2x\, |\, x\, =\, 1,\, 2,\, 3,\, 4\}$$
   $\{x\, |\, P(x)\}$ 표기는 "set-builder notation"이라고 불린다.
   
   
4. 집합은 well defined 되어야 한다! 즉 그 원소들을 명확하게 알 수 있어야한다. 예를 들어 "키가 큰 사람들"은 집합이 될 수 없다. 몇 cm부터 키가 크다고 느끼는지는 사람마다 다르기 때문이다. "키가 2m 이상인 사람들"은 well defined 되어 있다.

부분집합$($Subset$)$

집합$B$가 집합$A$의 부분집합일 때, $B\subseteq A$ 또는 $A\supseteq B$ 로 표기한다. $B$의 모든 원소는 $A$의 원소이기도 하다는 뜻이다. $B \subset A$ 또는 $A \supset B$는 $B$가 $A$의 진부분집합$($proper subset$)$이라는 것을 표기하는 것이다. $B \subset A$은 $B\subseteq A$ 중에서 $B \neq A$인 경우를 의미한다.

Cartesian product

집합 $A$와 집합 $B$가 있다고 하자. 집합 $A \times B = \{(a,b)\, |\, a \in A\; and\; b \in B \}$ 을 $A$와 $B$의 Cartesian product 라고 한다.

예시$)$ $A = \{1,\, 2,\, 3\}$ 그리고 $B = \{3,\, 4\}$  일 때, 두 집합의 Cartesian product는 다음과 같다.

$$A \times B = \{(1,\, 3),\, (1,\, 4),\, (2,\, 3),\, (2,\, 4),\, (3,\, 3),\, (3,\, 4)\}$$

숫자와 관련된 집합

• $\mathbb{Z}$ 는 모든 정수(integers)의 집합
• $\mathbb{Q}$ 는 모든 유리수(rational numbers)의 집합
• $\mathbb{R}$ 는 모든 실수(real numbers)의 집합
• $\mathbb{C}$ 는 모든 복소수(complex numbers)의 집합
• $\mathbb{Z}^{+}$, $\mathbb{Q}^{+}$, $\mathbb{R}^{+}$는 각각 $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$의 원소들 중에서 양수만 원소로 가지는 집합이다.
• $\mathbb{Z}^{*}$, $\mathbb{Q}^{*}$, $\mathbb{R}^{*}$, $\mathbb{C}^{*}$는 각각 $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$의 원소들 중에서 0이 아닌 원소들만 포함하는 집합이다.

Relation

집합 $A$와 $B$의 relation $R$은 $A \times B$의 부분집합이다. $(a, b) \in R$을 "$a$ is related to $b$"라고 읽고 $a\; R\; b$로 쓴다.

어떠한 집합 $S$가 자기 자신과 relation을 이룰 때 relation on $S$ 라고 부른다.

함수$($Function$)$

함수는 무엇인지 다들 잘 알 것이라고 생각하여 설명을 생략합니다.

one-to-one$($injection$)$, onto$($surjection$)$, one-to-one correspondence$($bijection$)$

함수 $f\, : \, X \rightarrow Y$에 대하여 $f(x_{1}) = f(x_{2})$ 이면 $x_{1} = x_{2}$ 일 때, 함수 $f$를 one-to-one function이다. 함수 $f$에 대하여 $f$의 치역이 $Y$일 때 $($즉, 공역과 치역이 같을 때$)$ 함수 $f$를 onto function이라고 한다.
one-to-one function이면서 동시에 onto function인 경우, one-to-one correspondence 이라고 하며, one-to-one correspondence는 inverse function이 존재한다.

Cardinality

집합 $X$안에 있는 원소들의 개수를 집합 $X$의 cardinality라고 부른다. $|X|$와 같이 표기한다.

ex)    $|\{2,\, 3,\, 5\}| = 3$

 

두 집합 $X$와 $Y$사이에 one-to-one correspondence가 존재할 때, 두 집합 $X$와 $Y$는 같은 cardinality를 갖는다고 말한다. 이 개념은 무한 집합의 크기를 비교할 때 사용한다.

신기하게도 정수의 집합과 유리수의 집합 사이에는 one-to-one correspondence가 존재하기 때문에 $|\mathbb{Z}| = |\mathbb{Q}|$ 이다.

Partitions

• 집합은 서로 공통된 원소를 갖고 있지 않을 때 disjoint 라고 말한다.
• 집합 $S$의 partition 은 집합 $S$의 모든 원소가 정확히 하나의 부분집합 안에 있도록하는 공집합이 아닌 부분집합들의 collection을 지칭한다. 이 때 partition의 각각의 부분집합을 cell이라고 부른다.
• $\bar{x}$는 집합 $S$의 partition이 있을 때 원소 $x$가 포함된 cell을 의미한다.

Equivalence relation

Relation on a set $S$인 $R$에 대해 모든 $x,\, y,\, z \in S$이 다음 3가지 조건을 만족하는 경우 $R$을 equivalence relation 이라고 부른다.

1. $($Reflexibe$)$ $x\, R\, x$
2. $($Symmetric$)$ If $x\, R\, y$, then $y\, R\, x$.
3. $($Transitive$)$ If $x\, R\, y$ and $y\, R\, z$ then $x\, R\, z$.

이를 만족하는 예시를 보자.

$S = \{1,\, 2,\, 3\}$에 대하여 다음의 Relation on a set $S$인 $R = \{(1,1), (1,2), (2,1),(2,2),(3,3)\}$ 이 있다고 하자.

1. $($Reflexible$)$ $(1,\, 1),\, (2,\,2),\,(3,\,3)$이 $R$의 원소로 있다. $S$에 있는 모든 원소 $x$에 대해 $(x,\,x)$꼴을 원소로 갖고 있기 때문에 Reflexible 성질을 만족한다.
2. Symmetric과 Transitive 성질도 보이기 쉽다.