Enumeration

열거(enumeration)는 모음에 있는 모든 항목의 완전한, 순서화된 목록입니다. 그 용어는 공통적으로 집합(set)의 모든 원소(elements)의 목록화를 참조하기 위한 수학(mathematics)과 컴퓨터 과학(computer science)에서 사용됩니다. 열거에 대한 정확한 요구 사항 (예를 들어, 집합이 유한(finite)해야 하는지 여부, 또는 목록이 반복을 포함하도록 허용하는지 여부)은 연구의 분야와 주어진 문제의 맥락에 따라 다릅니다.

일부 집합은 자연스러운 순서화(natural ordering, 예를 들어, 양의 정수 집합에 대해 1, 2, 3, 4, ...)를 수단으로 열거될 수 있지만, 다른 경우에서 (아마도 임의적인) 순서화를 지정해야 할 수 있습니다. 열거 조합론(enumerative combinatorics)과 같은 일부 맥락에서, 열거(enumeration)라는 용어는 해당 원소의 명시적 목록화의 생성이 아닌 집합이 포함하는 원소의 숫자의 결정에 중점을 두고 세는 것(counting)의 의미로 더 많이 사용됩니다.

Combinatorics

조합론에서, 열거는 세는 것(counting), 즉, 유한 집합의 정확한 원소의 개수를 결정하는 것을 의미하며, 보통 일부 유한 집합의 모든 순열(permutations)로 구성된 집합 각각의 가족과 같이 무한 집합으로 그룹화됩니다. 이러한 의미에서 특별한 종류의 대상을 열거하는 것과 관련된 수학의 많은 가지에서 번창하는 하위-영역이 있습니다. 예를 들어, 분할 열거(partition enumeration) 및 그래프 열거(graph enumeration)에서, 목표는 특정 조건을 충족하는 분할 또는 그래프를 세는 것입니다.

Set theory

집합 이론(set theory)에서, 열거의 개념은 더 넓은 의미를 가지고, 열거되는 집합이 유한할 필요가 없습니다.

Listing

열거가 순서화된 목록(ordered list) 문맥에서 사용될 때, 우리는 인덱스 집합(index set)에 일종의 순서화 구조 요구 사항을 부과합니다. 우리가 일반성을 허용하기 위해 순서화에 대한 요구 사항을 상당히 느슨하게 만들 수 있지만, 가장 자연스럽고 공통적인 전제 조건은 인덱스 집합이 바른-순서화(well-ordered)되어 있어야 한다는 것입니다. 이 특성화에 따르면, 순서화된 열거는 바른-순서화된 도메인과의 전사 (위로의 관계)로 정의됩니다. 이 정의는 인덱스 집합에 대한 주어진 바른-순서화가 부분 열거가 주어진 다음 원소를 나열하기 위한 고유한 방법을 제공한다는 의미에서 자연스럽습니다.

Countable vs. uncountable

별도로 명시하지 않은 한, 열거는 자연수를 수단으로 수행됩니다. 즉, 집합(set) $S$ 의 열거(enumeration)는 자연수 $\mathbb {N}$ 또는 자연수의 초기 분절(initial segment) {1, ..., n}에서 $S$ 까지의 전단사 함수(bijective function)입니다.

집합은 만약 그것이 열거될 수 있으면, 즉, 그것의 열거가 존재하면 셀-수-있는(countable) 것입니다. 그렇지 않으면, 그것은 셀-수-없는(uncountable) 것입니다. 예를 들어, 실수 집합은 셀-수-없는 것입니다.

집합은 만약 그것이 자연수의 적절한 초기 분절 ${1, ..., n}$ 을 수단으로 열거될 수 있으면 유한한(finite) 것이며, 이 경우에서, 그것의 카디널리티(cardinality)는 $n$ 입니다. 빈 집합(empty set)은 유한한 것인데, 왜냐하면 자연수의 빈 초기 분절을 수단으로 열거될 수 있기 때문입니다.

열거-가능 집합(enumerable set)이라는 용어는 때때로 셀-수-있는 집합에 사용됩니다. 어쨌든, 그것은 역시 열거 함수가 알고리듬으로 계산될 수 있는 계산-가능 집합인 계산-가능한 열거-가능 집합(computably enumerable sets)에 대해 종종 사용됩니다.

유한 집합과 셀-수-있는 무한 집합 사이를 구별하는 것을 피하기 위해, 종종 동등한 것인 또 다른 정의를 사용하는 것이 유용합니다: 집합 $S$ 가 셀-수-있는 것과 그것에서 자연수로의 단사 함수(injective function)가 존재하는 것은 필요충분 조건입니다.

Examples

자연수는 함수 f(x) = x에 의해 열거될 수 있습니다. 이 경우에서, $f:\mathbb {N} \to \mathbb {N}$ 은 단순히 항등 함수(identity function)입니다.
$\mathbb {Z}$ , 정수(integers)의 집합은 다음에 의해 열거될 수 있습니다: $f(x):={\begin{cases}-(x+1)/2,&{\mbox{if }}x{\mbox{ is odd}}\\x/2,&{\mbox{if }}x{\mbox{ is even}}.\end{cases}}$ $f:\mathbb {N} \to \mathbb {Z}$ 는 모든 각 자연수가 정확하게 하나의 정수에 대응하기 때문에 전단사입니다. 다음 테이블은 이 열거의 처음 몇 개 값을 제공합니다:

x 0 1 2 3 4 5 6 7 8

f(x) 0 −1 1 −2 2 −3 3 −4 4
모든 (비 빈) 유한 집합은 열거-가능입니다. S를 n > 0 원소를 갖는 유한 집합이라고 놓고 K = {1,2,...,n}이라고 놓습니다. S에서 임의의 원소 s를 선택하고 f(n) = s를 할당합니다. 이제 S' = S − {s}로 설정합니다 (여기서 −는 집합 차이(set difference)를 나타냅니다). 임의의 원소 s' ∈ S'를 선택하고 f(n − 1) = s'를 할당합니다. 집합의 모든 원소에 자연수가 할당될 때까지 이 과정을 계속합니다. 그런-다음 $f:K\to S$ 는 S의 열거입니다.
실수는 칸토어의 대각선 논증(Cantor's diagonal argument)과 칸토어의 첫 번째 셀-수-없음-속성 증명(Cantor's first uncountability proof)에 의해 입증된 것처럼 셀-수-있는 열거를 가지지 않습니다.

Properties

집합에 대해 (이 의미에서) 열거가 존재하는 것과 그 집합이 셀-수-있는(countable) 것은 필요충분 조건입니다.
만약 집합이 열거-가능이면, 그것은 빈 집합 또는 (정확한 정의에 따라) 하나의 원소를 갖는 집합의 퇴화된 경우를 제외하고 다른 열거의 셀-수-없는(uncountable) 무한대를 가질 것입니다. 어쨌든, 만약 열거를 단사가 되도록 요구하고 f(n)이 정의되면 f(m)이 모든 m < n에 대해 정의되어야 함을 만족하는 제한된 형식만 허용하면, N 원소의 유한 집합이 정확히 N! 열거를 가집니다.
도메인 $\mathbb {N}$ 을 갖는 집합 S의 열거 e는 s ≤ t에 의해 정의된 해당 집합 위에 바른-순서(well-order) ≤를 유도하는 것과 $\min e^{-1}(s)\leq \min e^{-1}(t)$ 인 것은 필요충분 조건입니다. 비록 그 순서가 놓여있는 집합과 거의 관련이 없을 수 있지만, 집합의 일부 순서가 필요할 때 유용합니다.

Ordinals

집합 이론(set theory)에서, 열거하는 함수의 도메인이 임의의 순서-숫자(ordinal)를 가정할 수 있는 자연수의 초기 분절(initial segment)이 되도록 목록화 함수의 도메인을 요구하는 특성화보다 열거에 대한 더 일반적인 개념이 있습니다. 이 정의 아래에서, 집합 S의 열거는 순서-숫자 α에서 S위로의 임의의 전사(surjection)입니다. 앞에서 언급된 열거의 보다 제한적인 버전은 α가 유한 순서-숫자이거나 첫 번째 극한 순서-숫자 ω인 특별한 경우입니다. 이러한 보다 일반화된 버전은 앞서 언급된 정의를 초월유한(transfinite) 목록화를 포함하기 위해 확장합니다.

이 정의 아래에서, 첫 번째 셀-수-없는 순서-숫자(first uncountable ordinal) $\omega _{1}$ 은 이들 두 개념이 일치하지 않도록 $\omega _{1}$ 에 대한 항등 함수로 열거될 수 있습니다. 보다 일반적으로, 임의의 바른-순서화된(well-ordered) 집합이 그것이 일반화된 목록화 열거와 다시-레이블링까지 일치하도록 이 특성화 아래에서 열거될 수 있다는 것이 ZF의 정리입니다. 만약 우리가 역시 선택의 공리(Axiom of Choice)를 가정하면, 모든 집합은 그것이 가장 일반적인 열거의 형식으로 다시-레이블링까지 일치하도록 열거될 수 있습니다.

집합 이론가는 임의적으로 큰 카디널리티(cardinalities)의 무한한 집합으로 연구하기 때문에, 집합 열거에 대한 수학자의 이 그룹 중에서 기본 정의는 모든 원소를 정확히 나열하는 임의의 임의적인 α-수열인 경향이 있습니다. 실제로, 집합 이론가들에 대해 공통적으로 참조되는 Jech의 책에서, 열거는 정확히 이것이 되도록 정의됩니다. 그러므로, 모호함을 피하기 위해, 유한하게 열거-가능 또는 번호-매길-수-있는(denumerable)이라는 용어를 사용하여 해당 유형의 구별된 셀-수-있는 열거 중 하나를 나타낼 수 있습니다.

Comparison of cardinalities

형식적으로, 집합 S의 열거에 대한 가장 포괄적인 정의는 임의적인 인덱스 집합(identity function) I에서 S위로의 임의의 전사(surjection)입니다. 이 넓은 맥락에서 모든 각 집합 S는 S에서 자체 위로의 항등 함수(identity function)에 의해 자명하게 열거될 수 있습니다. 만약 우리가 선택의 공리(axiom of choice) 또는 그 변종 중 하나를 가정하지 않으면, S는 임의의 바른-순서화(well-ordering)를 가질 필요가 없습니다. 심지어 우리가 선택의 공리를 가정하더라도, S는 임의의 자연스러운 바른-순서화를 가질 필요가 없습니다.

따라서 이 일반적인 정의는 "어떤 순서에서"가 아니라 "얼마나 많이"에 관심이 있는 세는 개념에 자체로 적합합니다. 실제로, 열거의 이 넓은 의미는 서로 다른 집합의 상대적인 크기 또는 카디널리티(cardinalities)를 비교하기 위해 자주 사용됩니다. 만약 우리가 선택의 공리 없이 체르멜로–프렝켈 집합 이론(Zermelo–Fraenkel set theory)에서 연구하면, 우리는 이 이론에서, I에서 S위로의 전사의 존재는 S에서 I로의 단사(injection)의 존재를 의미할 필요가 없기 때문에, 열거가 역시 (반복 없이) 단사적(injective)이어야 한다는 추가 제한을 부과하기를 원할 수 있습니다.

Computability and complexity theory

계산-가능성 이론(computability theory)에서, 종종 $\mathbb {N}$ (모든 자연수의 집합)에서 열거된 집합으로의 매핑이 계산-가능(computable)이어야 한다는 추가 요구 사항을 갖는 셀-수-있는 열거를 고려합니다. 열거될 집합은 그런-다음 재귀적으로 열거-가능(recursively enumerable, 또는 더 현대적인 언어에서 계산-가능하게 열거-가능)이라고 불리며, 맵이 계산-가능하다는 것이 의미하는 형식화에서 재귀 이론(recursion theory)의 사용을 참조합니다.

이런 의미에서, 자연수의 부분집합은 만약 그것이 계산-가능 함수의 치역이면 계산-가능한 열거-가능(computably enumerable)입니다. 이 문맥에서 열거-가능은 계산-가능한 열거-가능임을 의미하기 위해 사용될 수 있습니다. 어쨌든, 이들 정의는 도메인 ω를 갖는 임의적인 함수와 오직 셀-수-있게 많은 계산-가능 함수에 의해 열거될 수 있는 자연수의 셀-수-없게 많은 부분집합이 있기 때문에 구별되는 클래스를 특징으로 합니다. 열거이지만 계산-가능 열거가 아닌 집합의 구체적인 예제는 정지 집합(halting set)의 여집합입니다.

더욱이, 이 특성화는 목록화의 순서화가 중요한 위치를 보여줍니다. 정지 집합의 계산-가능 열거가 존재하지만, 증가하는 순서화에서 원소를 나열하는 것은 없습니다. 만약 하나가 있다면, 정지 집합은 결정-가능(decidable)일 것이며, 이는 거짓임이 입증됩니다. 일반적으로, 재귀적으로 열거-가능인 것은 결정-가능 집합(decidable set)인 것보다 약한 조건입니다.

열거의 개념은 역시 열거 알고리듬(enumeration algorithms)의 맥락에서 다양한 임무에 대한 계산적 복잡도 이론(computational complexity theory)의 관점에서 연구되어 왔습니다.

References

Jech, Thomas (2002). Set theory, third millennium edition (revised and expanded). Springer. ISBN 3-540-44085-2.

External links

The dictionary definition of enumeration at Wiktionary

x	0	1	2	3	4	5	6	7	8
f(x)	0	−1	1	−2	2	−3	3	−4	4