농도 (수학) 편집하기


== 정의 ==
'''농도(Cardinality)'''는 [[집합론]]에서 [[정의]]되는 [[개념]]이다. 만약 유한집합이라면 "농도는 집합의 원소의 개수입니다!"라고 외치고 싶겠지만 잠시만 참자. 농도를 정의할 때는 다른 개념과 달리 "농도는 ...이다"라고 정의하지 않는다. 아래를 보자.
* [[집합 (수학)|집합]] ''A''와 ''B''가 주어졌을 때, 일대일 대응 <math>f:A\to B</math>가 존재하면 '''''A''와 ''B''의 농도는 같다''' 또는 '''''A''와 ''B''는 동등하다(equipotent)'''고 하고, <math>|A|=|B|</math>로 나타낸다.
* 집합 ''A''와 ''B''가 주어졌을 때, 일대일 함수 <math>f:A\to B</math>가 존재하면 '''''A''의 농도는 ''B''의 농도와 같거나 그보다 작다'''고 하고, <math>|A|\le |B|</math>로 나타낸다.
* 집합 ''A''와 ''B''가 주어졌을 때, 일대일 함수 <math>f:A\to B</math>가 존재하지만 일대일 대응 <math>g:A\to B</math>가 존재하지 않으면 '''''A''의 농도는 ''B''보다 작다'''고 하고, <math>|A|<|B|</math>로 나타낸다.

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

그래서 일대일 대응 함수가 존재한다거나, 혹은 결코 존재할 수 없다는 것을 증명함으로써, 무한 집합 간의 크기를 비교하는 것이 가능하다.
그 한 가지 예는 바로 '임의의 무한 집합 X는 X의 [[멱집합]](Power Set) P(X)보다 크기가 작다.'는 것이다. 멱집합이란, 어떤 집합의 모든 부분집합들을 원소로 가지는 집합을 말하며, 보통 P(X)로 표기한다.<ref>예: 집합 A={1,2}의 부분집합은 각각 공집합(ø), {1}, {2}, {1,2}이다. 따라서 P(A)={ø, {1}, {2}, {1,2}}이다.</ref> 위 명제의 일반적인 증명은 귀류법으로, 일대일 대응 함수<math>f:X\to P(X)</math>가 존재한다고 가정할 때, 발생하는 모순을 지적하는 것이다. 해당 모순은 집합 X의 부분 집합 Y={ <math>y\in X | y \require{cancel}\bcancel{∈} f(y)</math> }와 관련이 있다. 함수 f의 정의에 따라, f(x)=Y를 만족하는 X의 원소 x가 존재한다. 그런데 x가 f(x)의 원소라면, Y의 정의에 따라 x는 Y의 원소가 될 수 없다. 그리고 x가 f(x)의 원소가 아니라면, Y의 정의에 따라 x는 Y의 원소가 된다. f(x)=Y이므로 이는 모순이다. Y가 공집합이든 아니든 이 모순은 반드시 발생한다. 따라서 귀류법에 따라 일대일 대응 함수가 존재하지 않음을 알 수 있다. 그리고 '<math>g:X\to P(X)</math> such that g(x)={x}'로 정의할 수 있는 함수 g는 일대일 함수이다. 따라서 |X| < |P(X)|임을 알 수 있다.

== 성질 ==
임의의 집합 ''A,B,C''에 대해
# <math>|A|=|A|</math>
# <math>|A|=|B|</math>이면 <math>|B|=|A|</math>이다.
# <math>|A|=|B|</math>이고 <math>|B|=|C|</math>이면 <math>|A|=|C|</math>이다.
이고 임의의 집합 ''A,B,C''에 대해
# <math>|A|\le |A|</math>
# <math>|A|\le |B|</math>이고 <math>|B|\le |A|</math>이면 <math>|A|=|B|</math>이다. (칸토어-베른슈타인 정리)
# <math>|A|\le |B|</math>이고 <math>|B|\le |C|</math>이면 <math>|A|\le |C|</math>이다.
즉, <math>=,\le</math>는 각각 [[동치관계]], [[반순서관계]]이다.

== 유한집합과 무한집합 ==
만약 집합 ''A''가 자연수 ''n''과 동등하다면, ''A''를 유한집합(finite set)이라 한다. 이때 ''A''가 ''n''개의 원소(element)를 가진다고 하고 <math>|S|=n</math>으로 표기한다.

만약 집합 ''A''와 ''B''가 유한집합이라면, <math>A\cup B</math>도 유한집합이며 <math>|A\cup B|\le |A|+|B|</math>이다. ''A''와 ''B''가 서로소라면, <math>|A\cup B|= |A|+|B|</math>이다.

''A''가 유한집합이 아니라면 무한집합(infinite set)이라고 한다. ''A''가 무한집합이면 임의의 <math>n\in \mathbb{N}</math>에 대해 <math>|A| > n</math>이다.

{{각주}}
[[분류:집합론]]