Countable & Uncountable

Presentation on theme: "Countable & Uncountable"— Presentation transcript:

1 Countable & Uncountable
조선해양공학과 조지훈

2 Countable & Uncountable

3 Countable 하지만 가산집합 이라고 합니다.
가산집합 이라고 합니다.  단순하게 생각해보면 말 그대로 '셀 수 있는', 즉 원소가 유한개 있는 집합은 가산집합이고 원소가 무한 개 있어서 셀 수 없는 집합은 비가산집합일 것 같습니다. 즉 다음과 같이 생각할 수 있겠죠. 셀 수 있는 집합(가산집합) = 유한집합 셀 수 없는 집합(비가산집합) = 무한집합 하지만 가산집합 = 유한집합 비가산집합 = 무한집합 은 아니다. 모든 유한집합은 가산집합 인건 맞지만 모든 무한집합은 비가산집합이 아니다. 여기서  ＂세다＂라는 행위는 여러분이 일반적으로 생각하는 ＂하나, 둘, 셋, 넷, …, 열다섯 끝!＂ 이런 개념이 아닙니다. 끝까지 세지 못해도 센다는 행위 자체가 가능하면 가산집합으로 생각합니다.

4 임의의 집합이 자연수의 부분집합과 일대일 대응 관계가 성립할 때 그 집합은 가산집합이다
임의의 집합이 자연수의 부분집합과 일대일 대응 관계가 성립할 때 그 집합은 가산집합이다.  자연수 집합 자체도 자연수 집합의 부분집합 입니다. 예를 들어 집합 {-1, -2, -3, -4, -5}는 자연수의 부분집합 {1, 2, 3, 4, 5}와 일대일 대응시킬 수 있으므로 가산집합입니다. 임의의 두 집합이 서로 일대일대응 관계가 성립할 때, 두 집합의 크기는 같다고 정의합시다. 즉, 두 집합 {-1, -2, -3, -4, -5}와 {1, 2, 3, 4, 5}의 집합의 크기는 같습니다

5 다음과 같이 좌표평면의 모든 격자점이 고유한 자연수에 대응되므로 격자점과 자연수 집합의 크기는 같습니다.
<순서쌍의 집합과 자연수의 집합>  그렇다면 자연수 두 개의 쌍으로 이루어진, 순서쌍의 집합은 가산집합일까요? 즉 A = {(1, 1), (1, 2), (1, 3), ... , (2, 1), (2, 2), ... , (100, 273), ...}    = {(x, y) | x∈N, y∈N} 이런 자연수 2개의 쌍으로 이루어진 집합 A는 자연수의 집합의 크기와 같을까요? 순서쌍을 격자점의 형태로 좌표평면 위에 나타내 보겠습니다. (격자점: x좌표와 y좌표가 둘 다 정수인 점) 다음과 같이 좌표평면의 모든 격자점이 고유한 자연수에 대응되므로 격자점과 자연수 집합의 크기는 같습니다. 따라서 격자점의 집합도 가산집합입니다.

6 Uncountable 무한한 집합으로서 원소가 너무 많아서 다 셀 수 없는 집합을 말한다
Uncountable 무한한 집합으로서 원소가 너무 많아서 다 셀 수 없는 집합을 말한다. 또한 이런 셀 수 없음은 기수(cardinal number)와도 관련이 있다. 만약 기수(cardinal number)가 자연수보다 크다면 셀 수 없는 집합이다.

7 <실수 집합과 자연수 집합의 크기> 
실수 집합이 자연수 집합보다 크기가 더 크다는 것을 보이기 위해, 실수 집합과 자연수 집합의 크기가 같다고 가정한 후, 모순을 보이도록 하면. 그게 바로 귀류법 입니다.

8 단 여기서 은 0부터 9까지의 자연수입니다.   은

9 칸토어의 대각선 논법 새로 만든 실수에서, 숫자 '1'은 '0'으로 바꾸고 숫자 '1' 이외의 수는 '1'로 바꾸겠습니다
칸토어의 대각선 논법 새로 만든 실수에서, 숫자 '1'은 '0'으로 바꾸고 숫자 '1' 이외의 수는 '1'로 바꾸겠습니다. 그러면 은  이 되겠죠. 이렇게 만들어진 수 은 기존의 어떤 n번째 수와 비교하든 소수점 n번째 자릿수가 다릅니다. 이는 모든 자연수와 실수를 대응시켰다는 가정에 모순입니다. 따라서 실수의 집합은 알레프 제로보다 크며 비가산집합 입니다.

10 1. Countable Set 이란? 가산 집합(countable set)은 자연수의 집합으로의 단사 함수가 존재하는 집합을 말한다. 가산집합이 아닌 집합을 비가산 집합(uncountable set)이라 한다. 자연수, 정수, 유리수의 집합은 가산집합이고, 실수의 집합은 비가산집합이다. 어떤 집합이 가산 집합인 경우, 그 집합을 셀 수 있다 혹은 가산 개의 원소가 있다고 정의한다. 일반적으로 가산 집합에는 유한 집합이 포함되지만, 유한 집합을 제외하고 셀 수 있는 무한 집합만을 가리키는 경우도 있다. 앞의 경우는 가산 이하(at most countable)라는 표현을, 뒤의 의미에 대해 가산 무한(countable infinite)이나 가부번 집합(denumerable set)이라고 표현한다. 엄밀히는 유한 집합(가산 이하)은 자연수 집합으로 단사 함수가 존재하나 원소의 개수가 유한한 집합을 말하며, 가부번 집합은 자연수 집합으로 전단사 함수가 존재하는 집합을 말한다.

11 실수가 가산집합이 아닌이유 대각선 논법 : 실수가 비가산 집합임을 보이는 수학적 증명 게오르크 칸토어가 고안하였다.

12 3. Countable Set의 성질 집합 A와 집합 B가 가산집합이면 와 는 가산집합이다.
가산 집합에서 농도가 유한인 부분 집합들의 집합도 가산 집합이다. 는 가산합(countable union) 이라고도 한다. 예를 들면, A1={0}, A2={1}, A3={-1}, A4={2}, ... 일 때, 이런 집합들의 합집합 {0}∪{1}∪{-1}∪{2}∪{-2}∪{3}∪{-3}... 은 주어진 집합들의 가산합이다. 따라서, A1={a11, a12, a13,... }, A2={a21, a22, a23, a24,...}, A3={a31, a32, a33, a34,... } .... 일 때, A1∪A2∪A3∪A4∪...= {a11, a12, a21, a13, a22, a31, a14, a23, a32, ….. }은 가산집합이다.

13 4. Q & A

14 5. 출처 http://blog.naver.com/pupleshiner/100018917946

15