페미위키:포크 프로젝트/리브레 위키/농도 (수학)

정의

농도(Cardinality)는 집합론에서 정의되는 개념이다. 만약 유한집합이라면 "농도는 집합의 원소의 개수입니다!"라고 외치고 싶겠지만 잠시만 참자. 농도를 정의할 때는 다른 개념과 달리 "농도는 ...이다"라고 정의하지 않는다. 아래를 보자.

• 집합 A와 B가 주어졌을 때, 일대일 대응 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle f:A\to B} 가 존재하면 A와 B의 농도는 같다 또는 A와 B는 동등하다(equipotent)고 하고, 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle |A|=|B|} 로 나타낸다.
• 집합 A와 B가 주어졌을 때, 일대일 함수 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle f:A\to B} 가 존재하면 A의 농도는 B의 농도와 같거나 그보다 작다고 하고, 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle |A|\le |B|} 로 나타낸다.
• 집합 A와 B가 주어졌을 때, 일대일 함수 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle f:A\to B} 가 존재하지만 일대일 대응 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle g:A\to B} 가 존재하지 않으면 A의 농도는 B보다 작다고 하고, 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle |A|<|B|} 로 나타낸다.

요약하면, 두 집합에서 원소를 하나씩 빼내서 짝지어 나가는 것이 어떤 식으로든 가능하면,(일대일 대응 함수가 하나 존재하면) 두 집합의 크기는 같다고 정의하는 것이다.

그래서 일대일 대응 함수가 존재한다거나, 혹은 결코 존재할 수 없다는 것을 증명함으로써, 무한 집합 간의 크기를 비교하는 것이 가능하다. 그 한 가지 예는 바로 '임의의 무한 집합 X는 X의 멱집합(Power Set) P(X)보다 크기가 작다.'는 것이다. 멱집합이란, 어떤 집합의 모든 부분집합들을 원소로 가지는 집합을 말하며, 보통 P(X)로 표기한다. 위 명제의 일반적인 증명은 귀류법으로, 일대일 대응 함수구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle f:X\to P(X)} 가 존재한다고 가정할 때, 발생하는 모순을 지적하는 것이다. 해당 모순은 집합 X의 부분 집합 Y={ 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle y\in X | y \require{cancel}\bcancel{∈} f(y)} }와 관련이 있다. 함수 f의 정의에 따라, f(x)=Y를 만족하는 X의 원소 x가 존재한다. 그런데 x가 f(x)의 원소라면, Y의 정의에 따라 x는 Y의 원소가 될 수 없다. 그리고 x가 f(x)의 원소가 아니라면, Y의 정의에 따라 x는 Y의 원소가 된다. f(x)=Y이므로 이는 모순이다. Y가 공집합이든 아니든 이 모순은 반드시 발생한다. 따라서 귀류법에 따라 일대일 대응 함수가 존재하지 않음을 알 수 있다. 그리고 '구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle g:X\to P(X)} such that g(x)={x}'로 정의할 수 있는 함수 g는 일대일 함수이다. 따라서 |X| < |P(X)|임을 알 수 있다.

성질

임의의 집합 A,B,C에 대해

1. 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle |A|=|A|}
2. 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle |A|=|B|} 이면 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle |B|=|A|} 이다.
3. 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle |A|=|B|} 이고 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle |B|=|C|} 이면 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle |A|=|C|} 이다.

이고 임의의 집합 A,B,C에 대해

1. 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle |A|\le |A|}
2. 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle |A|\le |B|} 이고 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle |B|\le |A|} 이면 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle |A|=|B|} 이다. (칸토어-베른슈타인 정리)
3. 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle |A|\le |B|} 이고 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle |B|\le |C|} 이면 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle |A|\le |C|} 이다.

즉, 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle =,\le} 는 각각 동치관계, 반순서관계이다.

유한집합과 무한집합

만약 집합 A가 자연수 n과 동등하다면, A를 유한집합(finite set)이라 한다. 이때 A가 n개의 원소(element)를 가진다고 하고 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle |S|=n} 으로 표기한다.

만약 집합 A와 B가 유한집합이라면, 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle A\cup B} 도 유한집합이며 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle |A\cup B|\le |A|+|B|} 이다. A와 B가 서로소라면, 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle |A\cup B|= |A|+|B|} 이다.

A가 유한집합이 아니라면 무한집합(infinite set)이라고 한다. A가 무한집합이면 임의의 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle n\in \mathbb{N}} 에 대해 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle |A| > n} 이다.