집합의 크기
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
집합의 크기는 두 집합의 원소 개수를 비교하는 개념으로, 전단사 함수, 단사 함수 등을 활용하여 정의된다. 두 집합 A, B 사이에 전단사 함수가 존재하면 두 집합은 대등하며, |A| = |B|로 표기한다. 단사 함수만 존재하면 |A| ≤ |B|로, 단사 함수는 존재하나 전단사 함수는 존재하지 않으면 |A| < |B|로 표기한다. 칸토어-베른슈타인 정리에 의해 |A| ≤ |B|이고 |B| ≤ |A|이면 |A| = |B|가 성립하며, 선택 공리를 가정하면 임의의 두 집합에 대해 크기 비교가 가능하다. 집합의 크기를 나타내는 수는 기수이며, 유한 집합은 원소의 개수로, 무한 집합은 알레프 수를 사용하여 나타낸다. 가산 집합, 비가산 집합 등 다양한 집합의 크기를 비교하며, 폰 노이만과 스코트의 정의를 통해 집합론적으로 엄밀하게 정의할 수 있다.
유한 집합의 크기는 단순히 그 원소의 수를 세어 비교할 수 있다. 하지만 무한 집합을 포함한 일반적인 집합들의 크기를 비교하기 위해서는 다른 접근 방식이 필요하다.
집합의 대등 관계 는 동치 관계의 성질(반사성, 대칭성, 추이성)을 만족한다. 집합의 크기 비교 관계 는 모든 집합 A에 대해 가 성립하는 반사 관계이며, 이고 이면 가 성립하는 추이 관계이다.
집합의 크기를 비교하는 기본적인 개념, 즉 어떤 사물이나 사건의 모임이 다른 모임보다 더 많거나, 적거나, 같은 수의 구성원을 가지는지 인식하는 능력은 여러 동물 종에서도 관찰되며, 이는 수백만 년 전으로 거슬러 올라갈 수 있다.[4] 인간이 집합의 크기를 표현한 증거는 약 40,000년 전의 유물에서도 찾아볼 수 있는데, 기록된 눈금 표시나 막대기, 조개껍질 같은 물체를 사용하여 집단의 크기를 나타냈다.[5] 집합의 크기를 추상적인 숫자로 다루기 시작한 것은 기원전 3000년경 수메르의 수학에서 명확해지는데, 이때부터 특정 대상과 관계없이 숫자를 조작하기 시작했다.[6]
2. 정의
두 집합의 크기가 같은지 혹은 다른지, 다르다면 어느 쪽이 더 큰지를 판단하는 기본적인 방법은 두 집합 사이에 특별한 종류의 함수가 존재하는지 확인하는 것이다. 특히, 두 집합 사이에 원소를 하나씩 빠짐없이 짝지을 수 있는 전단사 함수(일대일 대응)가 존재한다면, 두 집합은 같은 크기를 가진다고 정의한다. 이를 두 집합이 서로 '''대등'''(equinumerous영어)하다고 말하며, 같은 기수를 가진다고 표현한다.
만약 한 집합에서 다른 집합으로 가는 단사 함수만 존재하고 전단사 함수는 존재하지 않는다면, 첫 번째 집합의 크기가 두 번째 집합의 크기보다 작다고 정의한다. 이러한 비교 방식을 통해 유한 집합뿐만 아니라 무한 집합들의 크기까지 비교하고 분류할 수 있다.
2. 1. 대등
두 집합 ''A''와 ''B'' 사이에 전단사 함수 ''f'': ''A'' → ''B''가 존재하면, |''A''| = |''B''|라고 표기하며, 두 집합은 서로 '''대등'''(對等, equinumerous영어)하다고 한다. 이는 두 집합의 크기가 같다는 것을 의미한다.
두 집합 ''A''와 ''B'' 사이에 단사 함수 ''f'': ''A'' → ''B''가 존재하면, |''A''| ≤ |''B''|라고 표기하며, ''A''의 크기가 ''B''의 크기보다 작거나 같다고 한다.
두 집합 ''A''와 ''B'' 사이에 단사 함수 ''A'' → ''B''는 존재하지만, 전단사 함수 ''A'' → ''B''가 존재하지 않는다면, |''A''| < |''B''|라고 표기하며, ''A''의 크기가 ''B''의 크기보다 작다고 한다.
유한 집합의 크기는 단순히 그 원소의 수를 세어 비교할 수 있지만, 무한 집합의 크기를 비교하기 위해서는 집합 간의 대응 관계를 이용한다. 어떤 집합 ''A''의 크기가 다른 집합 ''B''의 크기보다 작거나 같다는 것(|''A''| ≤ |''B''|)은, ''A''에서 ''B''로 가는 단사 함수가 존재한다는 의미이다.
만약 |''A''| ≤ |''B''|이고 |''B''| ≤ |''A''|이면, |''A''| = |''B''|이다. 즉, ''A''에서 ''B''로 가는 단사 함수와 ''B''에서 ''A''로 가는 단사 함수가 모두 존재하면 두 집합의 크기는 같다. 이 정리는 칸토어-베른슈타인-슈뢰더 정리로 알려져 있다. 선택 공리는 임의의 두 집합 ''A''와 ''B''에 대해 항상 |''A''| ≤ |''B''| 또는 |''B''| ≤ |''A''| 둘 중 하나가 성립한다는 명제와 동치이다.[11][12]
집합의 크기, 즉 농도를 비교하는 다른 표기법은 다음과 같다.
칸토어-베른슈타인-슈뢰더 정리에 의해, ''X'' ≺ ''Y''이고 ''Y'' ≺ ''X''이면, ''X'' ≈ ''Y''가 성립한다. 또한, 선택 공리를 가정하면, 임의의 집합 ''X''와 ''Y''에 대해, ''X'' ≺ ''Y'' 또는 ''Y'' ≺ ''X''가 성립한다.
집합의 농도, 즉 크기를 나타내는 수학적 대상을 기수라고 한다. |''X''| = |''Y''|라는 표기는 ''X'' ≈ ''Y''와 같은 의미이며, 집합 ''X''의 기수는 card(''X''), #''X'' 등으로도 표기한다.
2. 2. 크기 비교
두 집합 와 사이에 전단사 함수 가 존재한다면, 라고 쓰고, 두 집합이 서로 대등(對等, equinumerous영어)하다고 한다. 이는 두 집합의 원소를 일대일로 대응시킬 수 있음을 의미한다.
두 집합 와 사이에 단사 함수 가 존재한다면, 라고 쓰고, 의 크기가 의 크기보다 작거나 같다고 한다. 이는 집합 의 모든 원소를 집합 의 서로 다른 원소에 대응시킬 수 있음을 의미한다.
두 집합 와 사이에 단사 함수 가 존재하지만, 전단사 함수 가 존재하지 않는다면, 라고 쓰고, 의 크기가 의 크기보다 작다고 한다. 이는 의 원소를 의 원소에 일대일로 대응시키되, 에는 의 어떤 원소와도 대응되지 않는 원소가 남아 있음을 의미한다.
유한 집합의 크기는 단순히 그 원소의 개수를 세어 비교할 수 있다. 그러나 무한 집합의 크기를 비교하기 위해서는 위에서 정의한 함수(단사 함수, 전단사 함수)의 존재 여부를 이용한다.
예를 들어, 모든 자연수의 집합 의 크기는 그 멱집합 (의 모든 부분집합들의 집합)의 크기보다 엄격하게 작다. 즉, 이다. 왜냐하면 함수 는 에서 로 가는 단사 함수이지만, 칸토어의 대각선 논법을 이용하면 에서 로 가는 전단사 함수는 존재할 수 없음을 보일 수 있기 때문이다 (위 그림 참조). 비슷한 논증으로, 자연수 집합 의 크기는 모든 실수의 집합 의 크기보다 엄격하게 작다(). 자세한 증명은 칸토어의 대각선 논법이나 칸토어의 첫 번째 비가산성 증명을 참조할 수 있다.
집합의 크기 비교는 농도(cardinality) 개념을 사용하여 다음과 같이 표기하기도 한다.
칸토어-베른슈타인-슈뢰더 정리에 따르면, 만약 이고 이면, 가 성립한다. 즉, 각 집합에서 다른 집합으로 가는 단사 함수가 각각 존재하면 두 집합 사이에는 전단사 함수도 존재하여 크기가 같다는 것이다. 또한, 선택 공리를 가정하면, 임의의 두 집합 와 에 대해 또는 둘 중 하나는 반드시 성립한다. 즉, 임의의 두 집합은 항상 크기를 비교할 수 있다는 것이다.
집합의 크기를 나타내는 수학적 대상을 기수라고 하며, 집합 의 기수는 , , 등으로 표기한다. 따라서 는 와 동치이다.
3. 성질
칸토어-베른슈타인 정리에 따르면, 두 집합 A, B에 대해 각각 단사 함수 와 가 모두 존재한다면(즉, 이고 이면), 두 집합의 크기는 같다(). 이는 두 집합 사이에 전단사 함수가 존재함을 의미한다.
임의의 두 집합 A, B에 대해 항상 이거나 둘 중 하나가 성립한다는 성질(비교 가능성)은 선택 공리와 동치이다.[11][12] 즉, 선택 공리를 가정하면 임의의 두 집합의 크기를 비교할 수 있다.
선택 공리를 가정할 경우, 만약 집합 B에서 집합 A로 가는 전사 함수 가 존재한다면, A의 크기는 B의 크기보다 작거나 같다().
집합의 크기를 비교하는 것은 각 집합에 대응하는 기수를 비교하는 것과 같다. 두 집합 A, B가 대등하다는 것()은 두 집합의 기수가 같다는 것과 필요 충분 조건이다. 마찬가지로, 라는 것은 A의 기수가 B의 기수보다 작거나 같다는 것을 의미하며, 이는 A에서 B로 가는 단사 함수가 존재한다는 뜻이다.
요약하면, 집합의 크기 비교 관계()는 집합 전체에 대한 원전순서(preorder)를 이룬다. 이 원전순서에 따른 동치 관계는 집합의 대등()이며, 이 동치류들의 모임인 기수들 사이의 순서는 선택 공리를 가정할 때 전순서(total order)가 된다.
4. 역사
무한 집합의 크기에 대한 생각은 기원전 6세기경 고대 그리스 철학자들의 글에서 나타나기 시작했다. 그들은 무한을 1을 계속 더하는 것과 같이 끝없는 과정으로 이해했지만, 무한 집합 자체를 하나의 대상으로 보고 그 크기를 생각하지는 않았다.[7] 고대 그리스에서는 사물을 끝없이 작은 부분으로 나누는 개념도 다루었다. 유클리드의 ''원론''에서는 두 선분 ''a''와 ''b''의 길이를 비율로 비교하는 공약성 개념을 설명했다. 이는 두 선분 모두를 정확히 측정할 수 있는 공통 단위(아무리 작더라도)가 존재할 때 가능했다. 그러나 무리수가 발견되면서, 모든 유리수의 무한 집합만으로는 모든 가능한 선분의 길이를 나타내기에 충분하지 않다는 사실이 밝혀졌다.[8] 그럼에도 불구하고, 여전히 무한 집합을 크기를 가진 하나의 대상으로 여기는 개념은 없었다.
무한 집합을 체계적으로 이해하고 그 크기를 다루는 개념은 19세기 말 게오르크 칸토어에 의해 정립되었다.[9] 칸토어 이전까지 무한은 주로 끝없는 과정으로 여겨졌으나, 칸토어는 무한 집합 자체를 하나의 대상으로 간주하고 집합들 간의 크기를 비교하는 방법을 제시하며 현대 집합론의 기초를 마련했다. 그는 일대일 대응 개념을 사용하여 무한 집합의 크기를 비교하였고, 모든 무한 집합이 같은 크기를 갖는 것이 아님을 증명했다.[9]
4. 1. 칸토어의 업적
집합론의 창시자인 게오르크 칸토어는 1880년경 집합 크기의 개념을 명확히 정립하였다. 그는 두 집합의 원소 사이에 일대일 대응 관계, 즉 전단사가 존재하는지를 기준으로 두 집합의 크기가 같은지를 판단하는 방법을 연구했다.[9]
1891년, 칸토어는 칸토어의 대각선 논법을 발표하며 중요한 증명을 제시했다. 이 논법을 통해 그는 자연수의 집합과 일대일 대응을 만들 수 없는 수의 집합, 즉 비가산 집합이 존재함을 보였다. 이는 자연수의 무한 집합보다 더 많은 원소를 가지는, 즉 더 '큰' 무한 집합이 존재한다는 것을 의미한다.[9]
칸토어의 이론에 따르면, 집합 의 크기가 집합 의 크기보다 엄격하게 작다는 것은, 에서 로 가는 단사 함수는 존재하지만, 와 사이에 전단사 함수는 존재하지 않는다는 것을 의미한다.
예를 들어, 모든 자연수의 집합 = {1, 2, 3, ...}의 크기는 그 멱집합 (의 모든 부분집합들의 집합)의 크기보다 엄격하게 작다. 이는 함수 가 에서 로 가는 단사 함수이지만, 어떤 함수도 에서 로 가는 전단사 함수가 될 수 없기 때문이다. 비슷한 논리로, 자연수 집합 의 크기는 모든 실수의 집합 의 크기보다 엄격하게 작다는 것을 증명할 수 있다. 이 증명은 칸토어의 대각선 논법이나 칸토어의 첫 번째 비가산성 증명을 통해 이루어진다.
칸토어의 이러한 발견은 유한 집합에 익숙한 우리의 직관과 상충되는 면이 있다. 특히 "전체는 항상 부분보다 크다"는 직관은 무한 집합에서는 성립하지 않는다. 19세기 후반 게오르크 칸토어, 고틀로프 프레게, 리하르트 데데킨트 등은 무한 집합의 경우 전체가 자신의 진부분집합과 크기가 같을 수 있다는 점을 받아들였다.[16] 대표적인 예시로 힐베르트의 호텔 역설이 있다.
리하르트 데데킨트는 무한 집합을 자신의 진부분집합과 일대일 대응이 가능한 집합, 즉 칸토어의 의미에서 크기가 같은 집합으로 정의하기도 했다. 이러한 무한의 정의를 데데킨트 무한이라고 부른다. 칸토어는 더 나아가 기수라는 개념을 도입하여 무한 집합들의 크기를 비교하고 분류했다. 그의 정의에 따르면 서로 다른 크기를 가지는 무한 집합들이 존재하며, 가장 작은 무한 기수는 자연수의 집합의 기수인 (알레프 널)이다.
5. 기수
집합의 "크기"를 나타내는 수를 기수라고 한다. 두 집합의 크기가 같다는 것은 두 집합 사이에 일대일 대응 관계를 설정할 수 있다는 의미이며, 이러한 관계를 동등성이라고 한다. 동등성은 집합 전체에 대한 동치 관계이다. 어떤 집합 ''A''와 동치 관계에 있는 모든 집합의 모임, 즉 ''A''와 크기가 같은 모든 집합의 모임을 ''A''의 동치류라고 한다.
집합의 크기, 즉 기수를 정의하는 방법에는 두 가지가 있다.
# 집합 ''A''의 크기를 동등성 관계에 따른 동치류 자체로 정의하는 방법.
# 각 동치류마다 대표하는 특정 집합을 하나씩 지정하는 방법. 가장 일반적인 선택은 해당 동치류에 속하는 서수 중에서 가장 작은 서수, 즉 초기 서수를 대표로 삼는 것이다. 이 방법이 공리적 집합론에서 기수를 정의할 때 주로 사용된다.
선택 공리를 가정하면, 무한 집합의 기수는 알레프 수를 사용하여 표현할 수 있다. 알레프 수는 다음과 같이 순서대로 나열된다.
:
여기서 각 서수 에 대해, 은 보다 큰 기수 중에서 가장 작은 기수를 나타낸다.
자연수 전체의 집합의 크기는 알레프-영()으로 표기한다. 실수 전체의 집합의 크기는 "" (소문자 프락투어 스크립트 "c")로 표기하며, 이를 연속체의 크기라고 부른다. 게오르크 칸토어는 칸토어의 대각선 논법을 사용하여 실수의 크기가 자연수의 크기보다 엄격하게 크다는 것, 즉 임을 증명했다. 또한 칸토어는 임을 보였는데, 이는 자연수 집합의 모든 부분 집합으로 이루어진 멱집합의 크기와 같다.
연속체 가설은 라고 주장한다. 이는 보다 크면서 보다 작은 기수는 존재하지 않는다는 의미이다. 즉, 자연수의 크기와 실수의 크기 사이에는 다른 크기의 무한 집합이 없다는 것이다. 연속체 가설은 집합론의 표준 공리 체계인 ZFC와 독립적이다. 이는 ZFC 공리계가 일관성이 있다면, ZFC 내에서는 연속체 가설을 증명할 수도 없고 그 부정을 증명할 수도 없다는 것을 의미한다.[13][14][15]
두 집합 ''X''와 ''Y''의 크기를 비교할 때, ''X''에서 ''Y''로 가는 단사 함수가 존재하면 라고 표기한다. 만약 이고 이면, 칸토어-베른슈타인-슈뢰더 정리에 의해 가 성립한다. 즉, 두 집합 사이에 각각 단사 함수가 존재하면, 두 집합 사이에 전단사 함수(일대일 대응)도 반드시 존재하여 크기가 같다는 것이다.
6. 다양한 집합의 농도
집합의 크기, 즉 기수는 서로 다를 수 있다. 두 집합 사이에 전단사 함수가 존재하면 두 집합의 기수는 같다. 예를 들어, 집합 ''X'' = {''a'', ''b'', ''c''}와 집합 ''Y'' = {사과, 오렌지, 복숭아}가 있고, ''a'', ''b'', ''c''가 서로 다르다면, {(''a'', 사과), (''b'', 오렌지), (''c'', 복숭아)}는 전단사 함수이므로 | ''X'' | = | ''Y'' | = 3이다.
집합의 기수는 비교할 수 있다. 만약 집합 ''X''의 기수가 집합 ''Y''의 기수보다 작거나 같다면(| ''X'' | ≤ | ''Y'' |), ''Y''의 부분집합 ''Z'' 중에서 ''X''와 기수가 같은 집합(| ''X'' | = | ''Z'' |)이 반드시 존재한다. 또한, 두 집합 ''X'', ''Y''에 대해 | ''X'' | ≤ | ''Y'' |이고 | ''Y'' | ≤ | ''X'' |이면, 두 집합의 기수는 같다(| ''X'' | = | ''Y'' |). 이는 무한 집합의 기수에도 적용되며, 칸토어-베른슈타인-슈뢰더 정리로 알려져 있다.
집합의 크기는 유한 집합일 수도 있고, 가산 집합일 수도 있으며, 비가산 집합일 수도 있다. 예를 들어, 실수 전체의 집합, 모든 무리수의 집합, 그리고 구간 등은 연속체의 기수를 가지는 대표적인 비가산 집합이다. 각 종류의 집합과 그 농도에 대한 자세한 내용은 아래 하위 섹션에서 다룬다.
6. 1. 유한 집합
유한 집합의 크기는 그 집합에 속한 원소의 개수를 세어 나타낸다. 예를 들어, 집합 는 원소가 5개 있으므로 크기는 5이다. 이를 와 같이 표기한다. 이와 달리 무한 집합의 크기는 자연수로 표현할 수 없다.기수 개념을 이용하면 유한 집합을 더 수학적으로 정의할 수 있다. 어떤 집합 ''X''의 기수가 자연수 집합 '''N'''의 기수보다 작을 때, 즉 |''X''| < |'''N'''|일 때, 이 집합 ''X''를 유한 집합이라고 한다.
유한 집합의 농도(크기)는 이처럼 자연수로 나타낼 수 있으며, 농도가 자연수 ''n''인 유한 집합을 ''n'' 점 집합이라고 부르기도 한다.
6. 2. 가산 집합
자연수 집합과 일대일 대응 관계를 가지는 집합을 '''가산 무한 집합'''이라고 한다.[10] 즉, 어떤 집합 ''X''의 기수가 자연수 전체의 집합 '''N'''의 기수와 같을 때, | ''X'' | = | '''N''' | = 일 때, 그 집합 ''X''를 가산 무한 집합이라고 부른다.자연수 전체로 이루어진 집합의 농도를 '''가산 무한 농도''' 또는 단순히 '''가산 농도'''라고 하며, 과거에는 '''가부번 농도'''라고도 불렸다.[18] 이 농도는 보통 (알레프-0) 또는 로 표기한다. 여기서 는 히브리 문자의 첫 글자인 '알레프'이다. 농도가 가산 무한인 집합을 '''가산 무한 집합''' 또는 단순히 '''가산 집합'''(영어: countable set)이라고 한다.[21] 예를 들어, 정수 전체의 집합이나 유리수 전체의 집합은 모두 가산 무한 집합이다.[22] 이는 정수나 유리수도 자연수처럼 하나씩 세어 나갈 수 있음을 의미한다.
유한 집합이거나 가산 무한 집합인 경우, 즉 그 농도가 가산 무한 이하인 경우를 통틀어 '''기껏해야 가산''' 농도 또는 단순히 '''가산 농도'''라고 하기도 한다.[21]
가산 무한 농도 는 다음과 같은 중요한 성질을 가진다.
- 는 가장 작은 무한 농도이다. 즉, 어떤 농도 가 보다 작다면, 는 반드시 유한 농도(즉, 자연수)이다.
- 선택 공리를 가정하면, 는 모든 무한 농도 중에서 가장 작다. 즉, 어떤 무한 농도 에 대해서도 항상 가 성립한다.
반면, 자연수 집합과 일대일 대응이 불가능한 무한 집합, 즉 자연수보다 '더 많은' 원소를 가진 집합을 비가산 집합이라고 한다. 예를 들어 실수 전체의 집합은 대표적인 비가산 집합이다.
6. 3. 비가산 집합
자연수 집합과 일대일 대응이 불가능한 무한 집합을 '''비가산 집합'''이라고 한다. 선택 공리를 가정하면, 어떤 집합 의 기수 ||가 자연수 집합 '''N'''의 기수 알레프-영 보다 큰 경우() 그 집합을 비가산 집합이라고 정의할 수 있다.[10]대표적인 비가산 집합으로는 실수 집합 과 자연수 집합의 멱집합 이 있다. 칸토어는 칸토어의 대각선 논법을 이용하여 실수가 자연수와 일대일 대응될 수 없음을 보였다.
6. 3. 1. 연속체 농도
실수 집합의 농도를 '''연속체 농도'''라고 한다. 이는 (소문자 프락투어 문자 'c') 또는 베스 수 로 표기된다.칸토어는 칸토어의 대각선 논법을 사용하여 연속체 농도 가 자연수의 농도인 알레프-영 ()보다 크다는 것, 즉 임을 증명했다. 이는 실수의 개수가 자연수의 개수보다 많다는 의미이다. 또한 칸토어는 임을 보였다. 이는 가 자연수 집합의 모든 부분집합의 집합, 즉 멱집합의 농도와 같다는 것을 의미한다.
연속체 가설은 와 사이에 다른 기수가 존재하지 않는다는 주장, 즉 이라는 명제이다. 이 가설은 집합론의 표준 공리계인 ZFC로부터 독립적이다. 즉, ZFC 공리계 내에서는 연속체 가설을 증명할 수도, 반증할 수도 없다.[13][14][15]
실수선 위의 점들의 집합뿐만 아니라, 실수선의 어떤 선분 위의 점들의 집합, 평면 위의 점들의 집합, 더 나아가 임의의 유한 차원 유클리드 공간 위의 점들의 집합도 연속체 농도 를 갖는다. 유클리드 공간 위의 연속 함수 전체의 집합이나 가분 힐베르트 공간 전체의 집합도 같은 농도를 가진다.
이는 직관에 반하는 결과를 낳기도 한다. 예를 들어, 무한 집합의 진부분집합이 원래 집합과 같은 크기를 가질 수 있다. 탄젠트 함수는 유한한 길이의 열린 구간 (−π/2, π/2)과 무한한 길이의 실수선 '''R''' 사이에 일대일 대응을 제공하여 두 집합의 크기가 같음을 보여준다. 또한, 공간 채움 곡선의 존재는 1차원 선분이 2차원 정사각형이나 더 높은 차원의 공간과 같은 수의 점을 가질 수 있음을 보여준다.
칸토어는 또한 칸토어의 정리를 통해 보다 더 큰 농도가 존재함을 보였다. 예를 들어, 실수 집합 '''R'''의 모든 부분집합의 집합(멱집합 )이나, '''R'''에서 '''R'''로 가는 모든 함수들의 집합()은 의 농도를 가지며, 이는 보다 크다 ().
기수 산술을 통해 다음과 같은 등식들이 성립함을 보일 수 있다.
7. 집합 연산과 농도
기수들 사이에는 다음과 같은 연산이 정의된다. 집합 ''X'', ''Y''의 농도를 각각 , 라고 할 때,
- 합: 두 집합의 분리 합집합의 농도로 정의된다. . 만약 ''X''와 ''Y''가 서로소 집합 ()이라면, 이는 단순히 와 같다.
- 곱: 두 집합의 곱집합의 농도로 정의된다.
- 거듭제곱: 한 집합에서 다른 집합으로 가는 모든 함수들의 집합의 농도로 정의된다.