집합의 크기
집합론에서, 집합의 크기(영어: cardinality) 또는 농도(濃度)는 집합의 "원소 개수"에 대한 척도이다. 유한 집합의 크기의 표현은 자연수로 충분하다. 임의의 집합의 크기는 단사 함수 및 전단사 함수를 통해 비교할 수 있으며, 기수로서 대상화할 수도 있다. 집합 A의 크기는 |A| 또는 n(A), A, card(A), # A로 표기한다.
정의
편집두 집합 와 사이에 만약 전단사 함수 가 존재한다면, 라고 하고, 두 집합이 서로 대등(對等, 영어: equinumerous)하다고 한다.
두 집합 와 사이에 만약 단사 함수 가 존재한다면, 라고 하고, 의 크기가 의 크기보다 작거나 같다고 한다.
두 집합 와 사이에 만약 단사 함수 가 존재하나, 전단사 함수 가 존재하지 않는다면, 라고 하고, 의 크기가 의 크기보다 작다고 한다.
성질
편집집합의 대등 은 집합들에 대한 "동치 관계"이다. 은 집합들에 대한 "반사 관계"이자 "추이 관계"이다.
칸토어-베른슈타인 정리에 따르면, 만약 이며 이면, 이다.
임의의 두 집합에 대하여 이거나 이다. 이는 선택 공리와 동치이다.
만약 전사 함수 가 존재한다면, 이다. 이는 선택 공리 가정 하에 성립한다.
집합의 크기 비교는 기수의 비교와 일치한다. 예를 들어 두 집합이 대등할 필요 충분 조건은 두 집합의 기수가 같다는 것이다.
정리하면, 집합의 크기 비교는 집합들에 대한 "원전순서"이며, 이에 대응하는 "동치 관계"는 집합의 대등, 이에 대응하는 "전순서"는 기수의 비교이다.
예
편집유한 집합의 크기는 단순히 그 원소 개수이다. 예를 들어, 이다. 무한 집합의 크기는 자연수로 표현할 수 없다.
자연수 집합과 대등한 집합을 가산 무한 집합이라고 한다. 정수 집합이나 유리수 집합은 모두 가산 무한 집합이다. 즉, 이들은 모두 자연수와 일대일 대응한다.
자연수 집합과 대등하지 않은 무한 집합을 비가산 집합이라고 한다. 실수 집합은 비가산 집합이다. 즉, 이는 자연수와 일대일 대응할 수 없다.