가산 집합(Countable set)
자연수(natural number)와 일대일로 짝지을 수 있는(하나씩 번호를 붙여 나열할 수 있는) 무한집합. 유리수(rational number) 전체도 가산이다.
무한집합에 "첫째, 둘째, 셋째, …"로 빠짐없이 번호를 붙일 수 있으면 가산 집합입니다. 자연수와 크기가 같다는 뜻입니다. (유한집합까지 넣어 '가산'이라 부르는 책도 있습니다. 이 글에서는 무한인 경우만 말합니다.) 분수는 어떨까요? 0과 1 사이에만도 무한히 많고, 어떤 두 분수 사이에도 또 분수가 있으니 자연수보다 훨씬 많아 보입니다.
분수
이 걸음을 끝없이 이어 가면, 목록에는 모든 양의 유리수가 정확히 한 번씩 나옵니다.
반대로 실수(real number)는 가산이 아닙니다. 어떤 목록을 만들어도 빠진 실수를 만들 수 있습니다(대각선 논법(diagonal argument)). 유리수는 가산이니, 실수에서 유리수를 빼고 남은 무리수(irrational number)는 셀 수 없이 많습니다. 길이로 재도 마찬가지입니다. 0과 1 사이에서 고르게 고른 수가 유리수일 확률(probability)은 0입니다(이유는 바로 다음 문단에 있습니다). 다만 확률 0이 불가능을 뜻하지는 않습니다.
수직선 위의 가산 집합은 길이의 합이 얼마든지 작은 구간들로 덮을 수 있습니다(측도 0, measure zero).
0이 아닌 정수(integer) 계수 다항식(polynomial)의 근, 곧 대수적 수(algebraic number)도 목록으로 늘어놓을 수 있습니다. 차수와 계수 절댓값(absolute value)들을 모두 더한 값이
문법이나 프로그램은 유한한 글자 모음(알파벳)으로 쓴 유한한 글자열이라 가산 개뿐입니다. 그런데 계산 이론(theory of computation)에서는 글자열들의 집합(예: "a가 짝수 개인 모든 글자열")을 언어라 부릅니다. 글자열 전체는 가산 무한(countably infinite)이고 언어는 그 부분집합(subset)이니, 언어 전체는 자연수의 멱집합(power set)처럼 셀 수 없이 많습니다. 문법은 셀 수 있을 만큼뿐이고 언어는 셀 수 없이 많으니, 어떤 문법이나 프로그램으로도 적을 수 없는 언어가 반드시 있습니다(촘스키 위계(Chomsky hierarchy), 튜링 기계(Turing machine)).
이 개념이 나오는 긴 글
이 개념 위에 세워진 것
이 개념을 언급하는 페이지
- 확률
… 고를 때, 그 수가 유리수일 확률은 0입니다. 유리수는 하나, 둘, 셋 하고 번호를 붙일 수 있어서(가산 집합) 첫째 유리수를 길이 ε/2인 구간으로, 둘째를 ε/4, 셋째를 ε/8인 구간으로 덮어 가면 모든 …
- 집합의 크기
… 0, 1, −1, 2, −2, …로 번갈아 부르면 자연수와 짝이 맞습니다. 자연수와 짝지을 수 있는 집합을가산 집합이라 합니다. 분수 전체도 가산입니다. 그렇다면 모든 무한은 같은 크기일까요? 아닙니다. 실수 전체는 …
- 칸토어의 대각선 논법
… 이 논법은 특정한 목록 하나가 아니라 '어떤 목록이든'에 대한 것이라, 고친 목록에도 똑같이 적용됩니다.가산 집합이라면 모든 원소를 담은 목록이 있어야 하니, 이진 수열의 집합은 가산이 아닙니다. 실수로 옮기려면 한 …
- 동치관계와 분할
… " ad = bc 이면 a/b \sim c/d "( b, d \ne 0 )로 묶인 분수들의 덩어리이고,유리수를 셀 때약분되는 칸을 건너뛴 것이 바로 덩어리마다 대표를 하나만 고른 일입니다. 거꾸로, 어떤 함수든 "같은 …
- 연분수
… 수⟧입니다. 유리수는 계수가 유한하고, 무리수는 무한합니다. 유한한 정수 목록은 셀 수 있으니 유리수가가산이라는 사실도 여기서 한 번 더 보입니다.
- 무리수
… 여기서 '셀 수 있다'는 1번, 2번, 3번, …으로 빠짐없이 번호를 붙일 수 있다는 뜻입니다. 유리수는셀 수 있지만실수는 대각선 논법에 따라 셀 수 없습니다. 셀 수 있는 유리수를 실수에서 빼도, 남는 무리수는 여전히 …
- 연속체 가설
… …은 n과 2n을 짝지으면 양쪽 모두 남는 것이 없으니 크기가 같습니다. 자연수 전체의 크기, 다시 말해가산 집합의 크기를 \aleph_0 (알레프 0)라 적습니다. \aleph 는 히브리 문자입니다. 이것이 가장 작은 …
- 대수적 수와 초월수
… 1, 2, 3, … 순서로 근을 늘어놓으면 모든 대수적 수가 언젠가 목록에 오릅니다. 대수적 수 전체는가산입니다. 높이 h = 까지 모았습니다. 다항식 , 근 , 그중 서로 다른 수는 입니다. 높이 h 이하인 …
- 측도 0
… 합니다. '길이가 0'을 정확히 말하는 방법입니다. 0과 1 사이의 유리수를 덮어 봅시다. 유리수는가산이라 0, 1, 1/2, 1/3, 2/3, 1/4, 3/4, …처럼 번호를 붙일 수 있습니다. i 번째 …
- 튜링 기계
… 방식과 같은 생각이 이 기계에 이미 들어 있습니다. 또 기계는 모두 유한한 기호열로 적히니 기계 전체는가산개뿐이고, 자릿수를 계산해 낼 수 있는 실수도 가산개뿐입니다. 그런데 실수는 셀 수 없이 많으므로(⟦대각선 …
- 정지 문제
… 기댑니다. 증명은 표 한 장입니다. 프로그램은 유한한 기호열이니 번호를 붙여 모두 늘어놓을 수 있습니다(가산). 행은 프로그램, 열은 입력으로 준 프로그램의 코드 \langle P_j \rangle 이고, 칸에는 …
- 처치–튜링 논제
… 말은 "그것을 하는 튜링 기계는 없다"는 뜻으로 쓰이고, 정지 문제가 대표적인 예입니다. 기계는가산개뿐인데 자연수에서 자연수로 가는 함수는 셀 수 없이 많으니, 계산할 수 없는 함수가 계산할 수 있는 …
- 촘스키 위계
… 보조정리가 있습니다. 가장 바깥 층 너머에도 언어가 있습니다. 문법은 유한한 글자로 적히니 모두 합쳐도가산개입니다. 반면 언어는 Σ*(Σ의 글자로 만들 수 있는 모든 유한 문자열의 집합)의 부분집합이라 …
- 수학적 귀납법
… 가장 작은 것에서 출발해 한 걸음씩 쌓아 올린 구조라면 어디서나 씁니다. 원소를 하나씩 셀 수 있다(가산)는 것만으로는 부족합니다. 유리수는 셀 수 있지만, 크기 순서로 보면 0보다 큰 유리수 전체처럼 가장 …
- 램지 이론
… 어떻게 칠해도 서로 모두 같은 색으로 이어진 무한히 많은 점들이 반드시 있습니다(무한 램지 정리). 이것은가산 집합에 관한 정리로, 여섯 명 논법을 끝없이 되풀이해 증명합니다. 한 점을 고르면 그 점에서 나가는 무한히 …
- 콜모고로프 복잡도
… 이 모든 논증의 바탕은 짧은 프로그램이 몇 개 안 된다는 셈입니다. 같은 까닭으로 프로그램은 모두 합쳐가산개뿐이어서, 대부분의 실수는 어떤 프로그램으로도 적을 수 없습니다. 이어지는 곳. π의 이진 전개나 …
- 수 체계: 자연수에서 실수까지
… − 2가 1에서 음수, 2에서 양수여도 그 사이에서 0이 되는 점이 없습니다. ℕ ⊂ ℤ ⊂ ℚ는 모두셀 수 있는무한이지만 ℝ는 대각선 논법에 따라 셀 수 없습니다. 구멍을 메운 수가 원래 있던 수보다 훨씬 많은 …
- 르베그 적분과 측도
… 집합론⟧의 보렐 집합). 측도가 0인 집합이 특히 중요합니다. 점 하나, 셀 수 있는 점들, 예컨대유리수 전체는 측도가 0이고, 셀 수 없이 많은 점을 가진 칸토어 집합도 측도가 0입니다(측도 0). 어떤 …
- 기술 집합론
… 칸토어가 무한 집합을 연구하기 시작한 것도 삼각급수가 함수를 하나로 정하는지를 묻다가였습니다(가산 집합, 대각선 논법). 측도에 대해서는 르베그 적분과 측도와 측도 0을, 그 무대였던 세미나에 …
- 게임의 결정성
… 번갈아 점점 작은 구간을 고르는 게임을 다루었습니다. 공통 부분이 집합 E와 만나면 I이 이깁니다. E가셀 수 있는집합이면 II는 E의 원소를 하나씩 차례로 비켜 가서 이기는데, 이것이 1874년 칸토어가 실수가 셀 …