집합

• 정의
  • 집합(sets)
  • 집합의 같음
  • 부분집합(subset), 진 부분집합(proper subset)
  • 멱집합(poser set)
  • 데카르트 곱(cartesian products)
  • 연산
    • 합집합(union)
    • 교집합(intersection)
      • 서로 소(disjoint)
    • 차집합(difference)
    • 여집합(complement)
• 집합의 항등
• datatype 과 집합
• 집합의 크기
  • 셀 수 있는 집합
    • 슈뢰더-베른슈타인 정리
    • 모든 정수의 집합은 셀 수 있는가?
    • 모든 양의 유리수의 집합은 셀 수 있는가?
  • 셀 수 없는 집합
    • 칸토어의 대각선 논법
  • 계산 가능, 계산 불가
• 용어 정리
  • 조건 제시법의 예
  • 구간(interval) 표기법
• 참고문헌
• Links

정의

집합(sets)

A set is an unordered collection of objects, called elements or members of the set. A set is said to contain its elements. We write $a ∈ A$ to denote that a is an element of the set A. The notation $a \notin A$ denotes that a is not an element of the set A.

• 집합은 순서 없는 객체들의 컬렉션이다.

집합의 같음

Two sets are equal if and only if they have the same elements. Therefore, if A and B are sets, then A and B are equal if and only if $∀x(x ∈ A ↔ x ∈ B)$. We write $A=B$ if A and B are equal sets.

• 두 집합이 같은 원소를 갖고 있다면 두 집합은 같다.
• $A \subseteq B$ 이고, $B \subseteq A$ 이면 $A=B$.

부분집합(subset), 진 부분집합(proper subset)

The set A is a subset of B if and only if every element of A is also an element of B. We use the notation $A ⊆ B$ to indicate that A is a subset of the set B.

• 집합 A의 모든 원소가 집합 B의 원소이면 A는 B의 부분집합이다.
• $A \subset B$ : 진 부분집합(proper subset)
  • $A \subseteq B$ 이고, $A \ne B$ 이면 A는 B의 진 부분집합.

멱집합(poser set)

Given a set S, the power set of S is the set of all subsets of the set S. The power set of S is denoted by $P(S)$.

• 집합 S의 멱집합(power set)은 집합 S의 모든 부분집합의 집합을 말한다.
• $P(S)$로 표기한다.

데카르트 곱(cartesian products)

Let A and B be sets. The Cartesian product of A and B, denoted by $A × B$, is the set of all ordered pairs $(a, b)$, where $a ∈ A$ and $b ∈ B$. Hence, $A × B = \{(a, b) \vert a ∈ A ∧ b ∈ B \}$

• A와 B의 데카르트 곱 $A × B$는 $a ∈ A$ 이고 $b ∈ B$인 모든 순서쌍의 집합이다.
• $A_1 × A_2 × ... × A_n = \{(a_1, a_2, ..., a_n) \vert a_i ∈ A_i \ for \ i = 1, 2, ..., n \}$  
• $A × B$의 부분집합 $R$을 집합 A 로부터 집합 B로의 관계(relation)라고 한다.

연산

합집합(union)

Let A and B be sets. The union of the sets A and B, denoted by $A ∪ B$, is the set that contains those elements that are either in A or in B, or in both.

• $$A ∪ B = \{ x \vert x ∈ A ∨ x ∈ B \}$$
• 여러 집합의 합집합은 적어도 하나의 집합에 있는 원소들의 집합이다.

교집합(intersection)

Let A and B be sets. The intersection of the sets A and B, denoted by $A ∩ B$, is the set containing those elements in both A and B.

• $$A ∩ B = \{ x \vert x ∈ A ∧ x ∈ B \}$$
• 여러 집합의 교집합은 여러 집합 모두에 나타나는 원소들의 집합이다.

서로 소(disjoint)

Two sets are called disjoint if their intersection is the empty set.

• 두 집합의 교집합이 공집합인 경우를 서로 소라 한다.

차집합(difference)

Let A and B be sets. The difference of A and B, denoted by $A − B$, is the set containing those elements that are in A but not in B. The difference of A and B is also called the complement of B with respect to A.

• A에 대한 B의 여집합(complement of B with respect to A) 이라고도 부른다.
• $$A-B = \{ x \vert x ∈ A ∧ x ∉ B \}$$

여집합(complement)

Let U be the universal set. The complement of the set A, denoted by $\bar{A}$, is the complement of A with respect to U . Therefore, the complement of the set A is $U − A$.

• 여집합은 $U - A$이고, $\bar{A}$로 표기한다.
• $$\bar{A} = \{ x ∈ U \vert x ∉ A \}$$

집합의 항등

datatype 과 집합

컴퓨터과학에서 이야기하는 "데이터형"이라고 하는 개념은 집합의 개념 위에 정의된다는 것에 주목하라. 특히 datatype, type이란 집합과 그 집합을 구성하고 있는 개체에 적용할 수 있는 연산자들의 집합을 말한다. 예를 들어 boolean 이란 집합 $\{ 0, 1 \}$과, 그 원소인 0과 1을 피연산자로 하여 연산을 수행하는 AND, OR, NOT과 같은 연산자들을 함께 지칭하는 것이다.

집합의 크기

Cardinality of Sets

Let S be a set. If there are exactly n distinct elements in S where n is a nonnegative integer, we say that S is a finite set and that n is the cardinality of S. The cardinality of S is denoted by $\vert S \vert$.

• 0 이상의 정수 $n$에 대하여, 집합 $S$에 $n$ 개의 서로 다른 원소가 존재하면
  • $S$는 유한집합(finite set)이다.
  • $n$은 집합 $S$의 크기(cardinality)이다.
• 유한 집합(finite set) $S$의 크기는 $\vert S \vert$로 표기한다.

The sets A and B have the same cardinality if and only if there is a one-to-one correspondence from A to B. When A and B have the same cardinality, we write $|A| = |B|$.

• 집합 A와 B가 같은 크기(same cardinality)이면
  • A로부터 B로의 전단사 함수가 존재한다.
  • 두 집합의 크기가 같을 때 $\vert A \vert = \vert B \vert$로 표기한다.

If there is a one-to-one function from A to B, the cardinality of A is less than or the same as the cardinality of B and we write $\abs{A} ≤ \abs{B}$. Moreover, when $\abs{A} ≤ \abs{B}$ and A and B have different cardinality, we say that the cardinality of A is less than the cardinality of B and we write $\abs{A} < \abs{B}$.

• A로부터 B로의 단사 함수가 있다면
  • A의 크기는 B보다 작거나 같다. $\abs{A} \le \abs{B}$.
• $\abs{A} \le \abs{B}$이고, $\abs{A} \ne \abs{B}$이면
  • A의 크기는 B보다 작다. $\abs{A} < \abs{B}$.

셀 수 있는 집합

Countable Sets

A set that is either finite or has the same cardinality as the set of positive integers is called countable. A set that is not countable is called uncountable. When an infinite set S is countable, we denote the cardinality of S by $\aleph_0$ (where $\aleph$ is aleph, the first letter of the Hebrew alphabet). We write $\abs{S} = \aleph_0$ and say that S has cardinality "aleph null".

• uncountable(셀 수 없는) 집합
• countable(셀 수 있는) 집합
  • 원소의 수가 유한한 집합.
  • 원소의 수가 무한한 집합 중, 원소의 수가 양의 정수의 집합과 같은 크기를 갖는 집합.
    • 무한집합 S가 셀 수 있을 경우 S의 크기를 $\aleph_0$ 라고 표기한다. $\abs{S} = \aleph_0$.
    • $\aleph_0$는 "알레프 널(aleph null)"이라 읽는다.
• 무한 집합을 셀 수 있다는 말은 좀 이상하게 들릴 수 있다.
  • 양의 정수의 집합으로부터 어떤 집합 S로의 일대일 대응이 가능하다면(전단사 함수) 셀 수 있다고 생각하자.

If A and B are countable sets, then $A ∪ B$ is also countable.

• 집합 A와 집합 B와 셀 수 있는 집합이면, $A ∪ B$도 셀 수 있는 집합이다.

슈뢰더-베른슈타인 정리

Schröder–Bernstein theorem

If A and B are sets with $\abs{A} ≤ \abs{B}$ and $\abs{B} ≤ \abs{A}$, then $\abs{A} = \abs{B}$. In other words, if there are one-to-one functions $f$ from A to B and $g$ from B to A, then there is a one-to-one correspondence between A and B.

• A, B 가 $\abs{A} ≤ \abs{B}$ 이고 $\abs{B} ≤ \abs{A}$, 이면 $\abs{A} = \abs{B}$ 이다.
• 즉 A 에서 B 로의 단사 함수 $f$ 가 존재하고, B 로부터 A 로의 단사 함수 $g$ 가 존재하면 A와 B는 전단사 함수 관계이다.

예제: $\abs{ (0,1) } = \abs{ (0,1] }$ 인가?

• 슈뢰더 베른슈타인 정리를 사용하자.
  • $(0,1) \subset (0,1]$ 이다. 그러므로, $(0,1)$에서 $(0,1]$ 으로의 단사 함수가 존재한다.
    • $f(x) = x$ 가 그러한 단사 함수의 하나에 해당한다.
  • $(0,1]$ 에서 $(0,1)$ 로의 단사 함수를 찾아보자.
    • $g(x) = \frac{x}{2}$ 는 $(0,1]$의 모든 원소를 $(0, \frac{1}{2}]$로 대응시키는 단사 함수다.
  • 따라서 $\abs{ (0,1) } = \abs{ (0,1] }$ 는 참이다.

모든 정수의 집합은 셀 수 있는가?

• 모든 정수는 다음과 같이 나열할 수 있을 것이다. 인덱스를 매기기 애매하다.

• 나열하는 방법을 바꿔서, 다음과 같이 나열해 보자.

이렇게 하면 양의 정수로 인덱스를 매길 수 있다. 전단사 함수 관계가 성립하는 것이다.

따라서 모든 정수의 집합은 셀 수 있다.

모든 양의 유리수의 집합은 셀 수 있는가?

다음과 같이 배열하면 순서대로 셀 수 있다.

따라서 양의 유리수의 집합은 셀 수 있다.

셀 수 없는 집합

An Uncountable Set

칸토어의 대각선 논법

Cantor diagonalization argument: 실수는 비가산 집합이다.

• 귀류법을 사용하자.
  • 실수의 집합이 셀 수 있다고 가정하자.
  • 셀 수 있는 집합의 부분 집합은 셀 수 있으므로, 실수의 부분집합도 셀 수 있을 것이다.
  • 적당히 (0, 1) 범위($0 \lt r \lt 1$)의 수들의 집합을 잡는다.
    • 이 집합이 셀 수 없는 집합임을 보이면 된다.

0 과 1 사이의 실수를 모두 나열한다면 다음과 같을 것이다.

• 여기에서 $d_{ij}$는
  • $r_i$ 의 소수점 아래 $j$ 번째 숫자를 말하며,
  • $d_{ij} \in \{ 0,1,2,3,4,5,6,7,8,9 \}$ 이다.

그런데 $d_{ij}$가 다닥다닥 붙어있으니 알아보기가 어렵다.

네모칸을 나누어, 한 글자가 한 칸에 들어가도록 하면 눈이 편할 것 같다.

예를 들어 $r_n = 0.1415$ 를 이렇게 표기해 보자.

이제 0 과 1 사이의 모든 실수를 다음과 같이 나열했다고 하자.

• 위에서 실수의 집합이 셀 수 있는 집합이라 가정했으므로,
  • 이렇게 나열한 집합도 셀 수 있는 집합이어야 한다.

그런데 $r_1$ 부터 $r_n$까지의 모든 수와 각 자리값이 하나씩만 다른 수를 만들어 보자.

이 수를 만들 수 있다면 0과 1 사이의 실수들 중 나열하지 못한 수가 존재한다는 의미이다.

따라서 모순이 발생하며, 그러므로 0과 1 사이의 실수는 셀 수 없는 집합이 된다.

그 수 $x$는 다음과 같이 만든다. (그러므로 실수의 집합은 셀 수 없는 집합이다.)

1. i 값을 1로 한다.
2. 실수 $r_i$의 소수점 아래 $i$ 번째 수를 확인한다.
   • if 그 수가 4 이면 $x$의 소수점 아래 $i$번째 수를 5 로 한다.
   • else $x$의 소수점 아래 $i$번째 수를 4 로 한다.
3. i 에 1을 더한다.
4. $r_i$ 가 마지막 숫자인가?
   • if 맞다면 작업을 끝낸다.
   • else GOTO 2

예를 들어 $r_1$ 부터 $r_5$ 이 다음과 같다고 하자.

$x$ 는 다음과 같을 것이다.

4와 5로만 구성된 수이지만, $r_1$ ~ $r_5$ 중 어느 숫자와도 같을 수 없다. 적어도 한 자리는 다른 숫자가 되기 때문이다.

계산 가능, 계산 불가

coumputable, uncomputable

We say that a function is computable if there is a computer program in some programming language that finds the values of this function. If a function is not computable we say it is uncomputable.

• 계산 가능
  • 어떤 프로그래밍 언어로 어떤 컴퓨터 프로그램을 짰을 때, 그 프로그램이 어떤 함수의 값을 계산해 낼 수 있다면, 그 함수는 계산가능하다고 한다.
• 계산 불가능
  • 어떤 프로그래밍 언어로 어떤 컴퓨터 프로그램을 짰을 때, 그 프로그램이 어떤 함수의 값을 계산해 낼 수 없다면, 그 함수는 계산불가능하다고 한다.

용어 정리

조건 제시법의 예

구간(interval) 표기법

• [a, b] : 닫힌 구간(closed interval)
• (a, b) : 열린 구간(open interval)

참고문헌

• Rosen의 이산수학 / Kenneth H. Rosen 저 / 공은배 등저 / 한국맥그로힐(McGraw-Hill KOREA) / 2017년 01월 06일

Links

• 대각선 논법(위키백과)