Cardinality

Original article: wikipedia:Cardinality

For other uses, see Cardinality (disambiguation).

The set $S$ of all Platonic solids has 5 elements. Thus the cardinality of $S$ is 5 or, in symbols, $|S|=5$.

수학(mathematics)에서, 집합(set)의 카디널리티(cardinality)는 집합의 "원소(elements)의 숫자"의 측정입니다. 예를 들어, 집합 $A=\{2,4,6\}$은 3개의 원소를 포함하고, 따라서 $A$는 3의 카디널리티를 가집니다. 19세기 후반부 시작에서, 이 개념은 무한 집합(infinite set)으로 일반화되었으며, 이것은 여러 유형의 무한대 사이에 구별과, 그것들에 대한 산술(arithmetic)을 수행하는 것을 허용합니다. 카디널리티에 대한 두 가지 접근법이 있습니다: 하나는 전단사(bijection)와 단사(injection)를 직접 사용하여 집합들을 비교하는 것과 또 다른 하나는 세는-숫자(cardinal number)에 사용하는 것입니다. 집합의 카디널리티는, 크기의 다른 개념과 혼동이 불가능할 때, 그의 크기(size)라고도 불립니다.

집합 $A$의 카디널리티는 보통 양쪽에 수직 막대(vertical bar)를 갖는 $|A|$로 나타냅니다; 이것은 절댓값(absolute value)과 같은 표기법이고, 그 의미는 문맥(context)에 의존합니다. 집합 $A$의 카디널리티는 대안적으로 $n(A)$, $A$, $\operatorname {card} (A)$, 또는 $\#A$로 표시될 수 있습니다.

History

1890년대에, 게오르크 칸토어(Georg Cantor)는 카디널리티(cardinality)의 개념을 무한 집합으로 일반화했으며, 이를 통해 다양한 유형의 무한대를 구별하고 것과 그들에 대한 산술을 수행할 수 있었습니다.

Comparing sets

Bijective function from N to the set E of even numbers. Although E is a proper subset of N, both sets have the same cardinality.

N does not have the same cardinality as its power set P(N): For every function f from N to P(N), the set T = {n∈N: n∉f(n)} disagrees with every set in the range of f, hence f cannot be surjective. The picture shows an example f and the corresponding T; red: n∈f(n)\T, blue:n∈T\f(n).

유한 집합의 카디널리티는 원소의 숫자일 뿐이지만, 개념을 무한 집합으로 확장하는 것은 보통 임의적인 집합 (일부는 무한일 수 있음)의 비교의 개념을 정의하는 것으로 시작합니다.

Definition 1: |A| = |B|

두 집합 A와 B는 A에서 B로의 전단사(bijection) (일명, 일-대-일 대응), 즉, A에서 B로의 단사(injective)와 전사(surjective) 둘 다인 함수(function)가 있으면 같은 카디널리티를 가집니다. 그러한 집합은 equipotent, equipollent, 또는 equinumerous이라고 말합니다. 이 관계는 역시 A ≈ B 또는 A ~ B로 표시될 수 있습니다.

예를 들어, 비-음의 짝수(even number)의 집합 E = {0, 2, 4, 6, ...}는 자연수(natural numbers)의 집합 N = {0, 1, 2, 3, ...}과 같은 카디널리티를 가지는데, 왜냐하면 함수 f(n) = 2n은 N에서 E로의 전단사이기 때문입니다 (그림 참조).

Definition 2: |A| ≤ |B|

A에서 B로의 단사 함수가 존재하면, A는 B의 카디널리티보다 작거나 같은 카디널리티를 가집니다.

Definition 3: |A| < |B|

A에서 B로의 전사 함수가 있지만, 전단사 함수가 없으면, A는 B의 카디널리티보다 엄격하게 작은 카디널리티를 가집니다.

예를 들어, 모든 자연수의 집합 N은 그것의 거듭제곱 집합(power set) P(N)보다 엄격하게 작은 카디널리티를 가지는데, 왜냐하면 g(n) = { n }은 N에서 P(N)로의 단사 함수이고, 그것은 N에서 P(N)로의 어떤 함수도 전단사임을 보일 수 없기 때문입니다 (그림 참조). 비슷한 논증에 의해, N은 모든 실수의 집합(real number) R의 카디널리티보다 엄격하게 작은 카디널리티를 가집니다. 증명에 대해, 칸토어의 대각선 논증(Cantor's diagonal argument) 또는 칸토어의 첫 번째 셀-수-없음-속성 증명(Cantor's first uncountability proof)을 참조하십시오.

만약 |A| ≤ |B| 및 |B| ≤ |A|이면, |A| = |B| (슈뢰더–베른슈타인 정리(Schröder–Bernstein theorem)로 알려진 사실)입니다. 선택의 공리는 모든 각 A, B에 대해 |A| ≤ |B| 또는 |B| ≤ |A|라는 명제와 동등합니다.

Cardinal numbers

Main article: Cardinal number

위의 섹션에서, 집합의 "카디널리티"가 함수형으로 정의되었습니다. 다시 말해서, 그것은 특정 대상 자체로 정의되지 않았습니다. 어쨌든, 그러한 대상은 다음과 같이 정의될 수 있습니다.

같은 카디널리티를 갖는 관계는 숫자-상등성(equinumerosity)이라고 불리고, 이것이 모든 집합의 클래스(class)에 대한 동치 관계(equivalence relation)입니다. 이 관계 아래에서 집합 A의 동치 클래스(equivalence class)는, 그런-다음, A와 같은 카디널리티를 가지는 모든 그들의 집합으로 구성됩니다. "집합의 카디널리티"를 정의하는 두 가지 방법이 있습니다:

1. 집합 A의 카디널리티는 숫자-상등성 아래에서 동치 클래스로 정의됩니다.
2. 대표(representative) 집합이 각 동치 클래스에 대해 지정됩니다. 가장 공통적인 선택은 해당 클래스의 초기 순서-숫자입니다. 이것은 보통 공리적 집합 이론(axiomatic set theory)에서 세는-숫자(cardinal number) 의 정의로 취합니다.

선택의 공리(axiom of choice)를 가정하여, 무한 집합(infinite set)의 카디널리티는 다음으로 표시됩니다:

$\aleph _{0}<\aleph _{1}<\aleph _{2}<\ldots .$

각 순서-숫자(ordinal) $\alpha$에 대해, $\aleph _{\alpha +1}$은 $\aleph _{\alpha }$보다 더 큰 최소 세는 숫자입니다.

자연수(natural number)의 카디널리티는 알레프-영(aleph-null) ($\aleph _{0}$)으로 표시되고, 반면에 실수(real number)의 카디널리티는 "${\mathfrak {c}}$" (소문자 프락투어 스크립트(fraktur script) "c")로 표시되고, 역시 연속체의 카디널리티(cardinality of the continuum)로 참조됩니다. 칸투어는, 대각선 논증(diagonal argument)를 사용하여, ${\mathfrak {c}}>\aleph _{0}$임을 보였습니다. 우리는 ${\mathfrak {c}}=2^{\aleph _{0}}$임을 보일 수 있으며, 이것은 역시 자연수의 모든 부분집합의 집합의 카디널리티입니다.

연속체 가설(continuum hypothesis)은 $\aleph _{1}=2^{\aleph _{0}}$, 즉, $2^{\aleph _{0}}$가 $\aleph _{0}$보다 더 큰 가장 작은 세는 숫자, 즉 그것의 카디널리티가 정수의 카디널리티와 실수의 카디너리티 엄격하게 사이에 있는 집합이 없음을 말합니다. 연속체 가설은 집합 이론의 표준 공리, ZFC와 독립(independent)입니다; 즉, ZFC에서 연속체 가설 또는 그 부정을 증명하는 것은 불가능합니다–ZFC가 일관적이라는 가정 아래에서 그렇습니다. 자세한 내용에 대해, 아래의 § Cardinality of the continuum를 참조하십시오.

Finite, countable and uncountable sets

만약 선택의 공리(axiom of choice)가 유지되면, 삼분법의 법칙(law of trichotomy)은 카디널리티에 대해 유지됩니다. 따라서 우리는 다음 정의를 만들 수 있습니다:

• 자연수(natural number)의 카디널리티보다 작은 카디널리티를 갖는 임의의 집합, 또는 | X | < | N |는 유한 집합(finite set)이라고 말합니다.
• 자연수의 집합과 같은 카디널리티를 가지는 임의의 집합 X, 또는 | X | = | N | = $\aleph _{0}$는 셀-수-있는 무한(countably infinite) 집합이라고 말합니다.
• 자연수의 카디널리티보다 더 큰 카디널리티를 갖는 임의의 집합 X, 또는 | X | > | N |, 예를 들어 | R | = ${\mathfrak {c}}$ > | N |은 셀-수-없는(uncountable) 것이라고 말합니다.

Infinite sets

유한 집합(finite set)에서 얻은 우리의 직관은 무한 집합을 다룰 때 무너집니다. 19세기 후반에서, 게오르크 칸토어(Georg Cantor), 고틀롭 프레게(Gottlob Frege), 리하르트 데데킨트(Richard Dedekind)와 다른 사람들은 전체가 부분과 같은 크기를 가질 수 없다는 견해를 거부했습니다. 이것의 한 예제가 그랜드 호텔의 힐베르트의 역설(Hilbert's paradox of the Grand Hotel)입니다. 실제로, 데데킨트는 무한집합을 엄격한 부분집합과 일대일 대응으로 배치할 수 있는 집합으로 정의했습니다 (즉, 칸토어의 의미에서 같은 크기를 가집니다); 이 무한대의 개념은 데데킨트 무한대(Dedekind infinite)라고 합니다. 칸통어는 세는 숫자를 도입했고, 그의 전단사에 기반한 크기 정의에 따라 일부 무한 집합이 다른 집합보다 더 크다는 것을 보여주었습니다. 가장 작은 무한 카디널리티는 자연수의 카디널리티 ($\aleph _{0}$)입니다.

Cardinality of the continuum

Main article: Cardinality of the continuum

칸토어의 가장 중요한 결과 중 하나는 연속체의 카디널리티(cardinality of the continuum) (${\mathfrak {c}}$)가 자연수의 카디널리티 ($\aleph _{0}$)보다 더 크다는 것입니다; 즉, 자연수 N보다 실수 R이 더 많습니다. 즉, 칸토어는 ${\mathfrak {c}}=2^{\aleph _{0}}=\beth _{1}$가 (Beth one 참조) 다음을 만족시킨다는 것을 보였습니다 (베트 일(Beth one)을 참조하십시오):

$2^{\aleph _{0}}>\aleph _{0}$

(칸토어의 대각선 논증(Cantor's diagonal argument) 또는 칸토어의 첫 번째 셀-수-없음-속성 증명(Cantor's first uncountability proof)을 참조하십시오).

연속체 가설(continuum hypothesis)은 실수의 카디널리티와 자연수의 카디널리티 사이에는 세는 숫자(cardinal number)가 없다는 것입니다. 즉,

$2^{\aleph _{0}}=\aleph _{1}$

어쨌든, 이 가설은 ZFC가 일관적이라면 널리 받아들여지는 ZFC 공리적 집합 이론(axiomatic set theory) 내에서 증명되거나 반증될 수 없습니다.

세는-숫자 산술은 실수 직선(real number line)에 있는 점의 숫자가 해당 직선의 임의의 선분(segment)에 있는 점의 숫자와 같을 뿐만 아니라, 평면, 및 사실, 임의의 유한-자원 공간에 있는 점의 숫자와 같다는 것을 표시하기 위해 사용될 수 있습니다. 이들 결과는 S와 같은 크기를 가지는 무한 집합 S의 적절한 부분집합(proper subset)과 적절한 초월집합(proper superset)이 존재함을 의미하기 때문에 매우 직관적이지 않지만, S는 부분집합에 속하지 않는 원소를 포함하고, S의 초월집합은 그것 내에 포함되지 않는 원소를 포함합니다.

이들 결과 중 첫 번째는 예를 들어 구간(interval) (−½π, ½π)과 R 사이의 일-대-일 대응(one-to-one correspondence)을 제공하는 탄젠트 함수(tangent function)를 고려함으로써 분명합니다 (그랜드 호텔의 힐베르트의 역설(Hilbert's paradox of the Grand Hotel)을 참조하십시오).

두 번째 결과는 1878년에 칸토어에 의해 처음 시연되었지만, 그것은 주세페 페아노(Giuseppe Peano)가 공간-채우는 곡선(space-filling curve), 임의의 정사각형, 또는 정육면체, 또는 초-입방체(hypercube), 유한-차원 공간의 전체를 채울 만큼 충분히 비틀고 회전하는 곡선을 도입한 1890년에 더욱 분명해졌습니다. 또는 유한 차원 공간. 이들 곡선은 직선이 유한 차원 공간과 같은 숫자의 점을 갖는다는 직접적인 증거는 아니지만, 그것들은 그러한 증명을 얻기 위해 사용될 수 있습니다.

칸토어는 역시 카디널리티가 ${\mathfrak {c}}$보다 엄격하게 큰 집합이 존재함을 보여주었습니다 (그의 일반화된 대각선 논증(generalized diagonal argument) 및 정리(theorem)를 참조하십시오). 그것들은, 예를 들어, 다음을 포함합니다:

• R의 모든 부분집합의 집합, 즉, R의 거듭제곱 집합(power set), P(R) 또는 2^R으로 쓰임.
• R에서 R로의 모든 함수의 집합 R^R.

둘 다는 다음 카디널리티를 가집니다:

$2^{\mathfrak {c}}=\beth _{2}>{\mathfrak {c}}$

(배트 이(Beth two)를 참조하십시오).

세는-숫자 상등(cardinal equalities) ${\mathfrak {c}}^{2}={\mathfrak {c}},$ ${\mathfrak {c}}^{\aleph _{0}}={\mathfrak {c}},$, 및 ${\mathfrak {c}}^{\mathfrak {c}}=2^{\mathfrak {c}}$은 세는-숫자 산술(cardinal arithmetic)을 사용하여 시연될 수 있습니다:

${\mathfrak {c}}^{2}=\left(2^{\aleph _{0}}\right)^{2}=2^{2\times {\aleph _{0}}}=2^{\aleph _{0}}={\mathfrak {c}},$

${\mathfrak {c}}^{\aleph _{0}}=\left(2^{\aleph _{0}}\right)^{\aleph _{0}}=2^{{\aleph _{0}}\times {\aleph _{0}}}=2^{\aleph _{0}}={\mathfrak {c}},$

${\mathfrak {c}}^{\mathfrak {c}}=\left(2^{\aleph _{0}}\right)^{\mathfrak {c}}=2^{{\mathfrak {c}}\times \aleph _{0}}=2^{\mathfrak {c}}.$

Examples and properties

• 만약 X = {a, b, c} 및 Y = {apples, oranges, peaches}이면, | X | = | Y |인데 왜냐하면 { (a, apples), (b, oranges), (c, peaches)}는 X와 Y 사이의 전단사이기 때문입니다. X와 Y 각각의 카디널리티는 3입니다.
• 만약 | X | ≤ | Y |이면, | X | = | Z | 및 Z ⊆ Y를 만족하는 Z가 존재합니다.

• 만약 | X | ≤ | Y | 및 | Y | ≤ | X |이면, | X | = | Y |입니다. 이것은 심지어 무한 세는-숫자에 대해 유지되고, 칸토어–베른슈타인–슈뢰더 정리(Cantor–Bernstein–Schroeder theorem)로 알려져 있습니다.
• 연속체의 카디널리티를 갖는 집합(Sets with cardinality of the continuum)은 모든 실수의 집합, 모든 무리수(irrational number)의 집합과 구간 $[0,1]$를 포함합니다.

Union and intersection

만약 A와 B가 서로소 집합(disjoint sets)이면, 다음입니다:

$\left\vert A\cup B\right\vert =\left\vert A\right\vert +\left\vert B\right\vert .$

이것으로부터, 우리는 일반적으로, 합집합(unions)과 교집합(intersections)의 카디널리티는 다음 방정식에 의해 관련되어 있습니다:

$\left\vert C\cup D\right\vert +\left\vert C\cap D\right\vert =\left\vert C\right\vert +\left\vert D\right\vert .$

See also

• Aleph number
• Beth number
• Cantor's paradox
• Cantor's theorem
• Countable set
• Counting
• Ordinality
• Pigeonhole principle