열거

열거는 컬렉션의 모든 항목을 순서대로 나열한 전체 목록입니다.이 용어는 수학과 컴퓨터 과학에서 집합의 모든 요소의 목록을 참조하기 위해 일반적으로 사용됩니다.열거에 대한 정확한 요구사항(예: 집합이 유한해야 하는지 또는 목록에 반복이 포함되도록 허용되는지 여부)은 연구의 분야와 주어진 문제의 맥락에 따라 달라집니다.

일부 집합은 자연스러운 순서(예: 양의 정수 집합의 경우 1, 2, 3, 4, ...)로 열거할 수 있지만, 다른 경우에는 (아마도 임의) 순서를 부과해야 할 수 있습니다.열거형 조합론과 같은 일부 문맥에서는 열거형이라는 용어가 계산의 의미에 더 많이 사용되며, 이들 요소의 명시적 목록 작성보다는 집합이 포함하는 요소의 수를 결정하는 데 중점을 둔다.

조합

조합론에서 열거는 유한 집합의 정확한 요소 수를 계산하는 것을 의미한다. 즉, 보통 유한 집합의 모든 순열로 구성된 집합의 패밀리와 같이 무한 패밀리로 그룹화된다.이런 의미에서 특수한 종류의 대상을 열거하는 것과 관련된 수학의 많은 분야에는 번창하는 하위 영역이 있다.예를 들어 파티션 열거 및 그래프 열거의 목적은 특정 조건을 충족하는 파티션 또는 그래프를 계산하는 것입니다.

집합론

집합론에서 열거의 개념은 더 넓은 의미를 가지며 열거되는 집합이 유한할 필요가 없다.

리스트

순서부 리스트 컨텍스트에서 열거를 사용하는 경우 인덱스 세트에 일종의 순서부 구조 요건을 부과합니다.일반성을 높이기 위해 주문에 대한 요구사항을 상당히 느슨하게 만들 수 있지만, 가장 자연스럽고 일반적인 전제조건은 인덱스 세트가 잘 정렬되어야 한다는 것입니다.이 특성화에 의해 순서부여는 잘 정렬된 도메인과의 돌출(on-to-relationation)으로 정의된다.이 정의는 인덱스 집합의 순서가 잘 지정되면 부분 열거를 통해 다음 요소를 나열할 수 있는 고유한 방법을 제공한다는 점에서 자연스러운 것입니다.

카운트 가능 대 카운트 불가

집합론에서 열거형의 가장 일반적인 사용은 무한 집합이 셀 수 있는 것과 셀 수 없는 것으로 구분되는 맥락에서 발생합니다.이 경우 열거형은 자연수의 서수인 도메인 ,을 사용한 열거형일 뿐입니다.이 정의는 다음과 같이 기술할 수도 있습니다.

N $\mathbb {N}$ \ $displaystyle \mathbb {N}($ 자연수)에서 S(즉, S의 모든 요소는 적어도 1개의 자연수의 화상)로의 사영 매핑으로 한다.이 정의는 계산 가능성과 기본 집합론의 질문에 특히 적합합니다.

유한 집합을 사용할 때 다르게 정의할 수도 있습니다.이 경우 열거는 다음과 같이 정의할 수 있습니다.

S에서 자연수의 초기 세그먼트에 대한 생물적 매핑.이 정의는 특히 조합 질문 및 유한 집합에 적합합니다. 그러면 초기 세그먼트는 S의 카디널리티인 일부 n에 대해 {1,2,...,n}입니다.

첫 번째 정의에서는 매핑이 사출적이어야 하는지(즉, S의 모든 요소가 정확히 하나의 자연수의 화상이다) 또는/또는 부분적이어야 하는지(즉, 매핑은 일부 자연수에 대해서만 정의된다).일부 응용 프로그램(특히 집합 S의 계산 가능성과 관련된 것)에서 이러한 차이는 거의 중요하지 않다. 왜냐하면 어떤 열거의 존재에만 관심을 가지며, 자유 정의에 따른 열거는 일반적으로 더 엄격한 요건을 충족하는 열거도 존재함을 의미한다.

유한 집합의 열거는 분명히 비주입성 또는 편파성 중 하나를 허용해야 하며, 유한 집합이 나타날 수 있는 상황에서는 이들 중 하나 또는 둘 다 불가피하게 존재한다.

예

자연수는 함수 f(x) = x로 열거할 수 있습니다. 이 $f:\mathbb {N} \to \mathbb {N}$ f : $f:\mathbb {N} \to \mathbb {N}$ $f:\mathbb {N} \to \mathbb {N}$ {\ $displaystyle$ f $:\mathbb {N}$ \ $to \mathbb {N}$ 은 $f:\mathbb {N} \to \mathbb {N}$ 단순히 항등 함수입니다.
$\mathbb {Z}$ $\$ 정수 집합은 다음과 같이 열거할 수 있습니다. $f(x):=param{case}-(x+1)/2,&{\mbox{if}xparammbox{홀수}\x/2,&{\mbox{if}xparambox{짝수}}}xparambox{짝수}}}}.\end {case}$ $f:\mathbb {N} \to \mathbb {Z}$ f $f:\mathbb {N} \to \mathbb {Z}$ : $f:\mathbb {N} \to \mathbb {Z}$ $f:\mathbb {N} \to \mathbb {Z}$ {\ $displaystyle$ f $:\mathbb {N}$ \ $to \mathbb {Z} }$ 는 $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}(여기서 - 는 설정 차이를 나타냅니다).임의의 요소 s' - S'를 선택하고 f(n - 1) = s'를 할당합니다. 세트의 모든 요소에 자연수가 할당될 때까지 이 프로세스를 계속합니다. $f:K\to S$ 다음 $f:K\to S$ f : K $f:K\to S$ {\ $displaystyle$ f $:$ $K\to$ S는 $f:K\to S$ S의 열거형입니다.
칸토어의 대각선 논거와 칸토어의 첫 번째 불가산성 증명에 의해 증명된 것처럼 실수는 셀 수 있는 열거를 가지고 있지 않다.

특성.

집합이 카운트 가능한 경우에만 집합의 열거가 존재합니다(이러한 의미에서는).
집합이 열거될 경우 빈 집합 또는 (정확한 정의에 따라) 하나의 요소가 포함된 집합의 퇴화 경우를 제외하고 셀 수 없을 정도로 다양한 열거를 가집니다.단, 주입할 열거형이 필요하고 f(n)가 정의되면 f(m)가 모든 m < n에 대해 정의되어야 하는 제한된 형태의 편파성만 허용하는 경우 N개의 요소의 유한 집합은 정확히 N! 열거형을 가집니다.
$\mathbb {N}$ 이 $\mathbb {N}$ 인 $\mathbb {N}$ 집합 S의 열거 e는 $\min e^{-1}(s)\leq \min e^{-1}(t)$ e - $\min e^{-1}(s)\leq \min e^{-1}(t)$ 1 ( s $\min e^{-1}(s)\leq \min e^{-1}(t)$ $\min e^{-1}(s)\leq \min e^{-1}(t)$ e - $\min e^{-1}(s)\leq \min e^{-1}(t)$ ( $\min e^{-1}(s)\leq \min e^{-1}(t)$ ){ $display$ style \ $min$ $\mathbb {N}$ e^ { - $1$ ( $s$ )\ $leq \min$ e^ { - $1$ ( t ){ - 1 ( t $\min e^{-1}(s)\leq \min e^{-1}(t)$ 의 경우만 s $\min e^{-1}(s)\leq \min e^{-1}(t)$ t 로 정의되어 있는 집합에서 well-order를 유도합니다.set는 필수입니다.

서수

집합론에서는 열거함수의 도메인이 자연수의 초기 세그먼트여야 하는 특성화보다 열거함수의 도메인이 임의의 서수를 가정할 수 있는 일반적인 개념이 있다.이 정의에서 집합 S의 열거는 순서수 α에서 S로의 돌출이다.앞에서 언급한 열거의 보다 제한적인 버전은 α가 유한 서수 또는 첫 번째 한계 서수 θ인 특수한 경우이다.이 보다 일반화된 버전은 앞서 언급한 정의를 무한 목록을 포함하도록 확장합니다.

이 정의에서는 첫 번째 $\omega _{1}$ ${\$ 1(\ $displaystyle$ $\obega$ _ ${1})$ 을 $\omega _{1}$ $\omega _{1}$ $\omega _{1}$ 의 아이덴티티 함수에 의해 열거할 수 있으므로 이들 두 개념이 일치하지 않습니다.보다 일반적으로, 이 특성화 하에서 잘 정렬된 집합을 열거할 수 있고, 일반화된 목록 열거와 라벨 재지정까지 일치시킬 수 있는 것이 ZF의 정리이다.Axiom of Choice도 가정할 경우, 모든 집합이 열거의 가장 일반적인 형식과 다시 라벨링에 일치하도록 열거될 수 있습니다.

집합 이론가들은 임의로 큰 기수들의 무한한 집합으로 작업하기 때문에, 집합의 열거에 대한 수학자들의 이 그룹들 사이의 기본 정의는 그것의 모든 요소를 정확히 나열하는 임의의 알파 수열인 경향이 있습니다.실제로, 집합 이론가들에게 공통적으로 언급되는 Jech의 책에는 열거가 정확히 이렇게 정의되어 있다.따라서 애매함을 피하기 위해 최종 열거형 또는 제외형이라는 용어를 사용하여 구별되는 계수형 열거형 중 하나를 나타낼 수 있다.

기수 비교

형식적으로 집합 S의 열거에 대한 가장 포괄적인 정의는 임의의 지수 집합 I에서 S로의 돌출이다.이 넓은 맥락에서, 모든 집합 S는 S에서 그 자신으로의 항등함수에 의해 3차적으로 열거될 수 있다.선택 공리 또는 그 변형 중 하나를 가정하지 않는다면, S는 어떠한 순서도 가질 필요가 없다.선택 공리를 가정하더라도, S는 자연적인 정렬을 가질 필요가 없다.

따라서 이 일반적인 정의는 우리가 "어떤 순서로"가 아니라 "몇 개"에 관심이 있는 계산 개념에 적합하다.실제로, 열거의 이 넓은 의미는 종종 다른 집합의 상대적 크기 또는 기수를 비교하기 위해 사용된다.만약 어떤 사람이 선택 공리 없이 체르멜로-프랭켈 집합 이론에서 일한다면, 이 이론에서 I에서 S로의 돌출의 존재가 I로의 주입의 존재를 의미할 필요는 없기 때문에 열거 역시 (반복 없이) 주입되어야 한다는 추가적인 제한을 가할 수 있다.

계산가능성과 복잡성 이론

계산가능성 이론에서는 N $(모든$ 자연수의 집합 $)$ 에서 열거된 집합으로의 매핑이 계산 가능해야 한다는 추가 요건을 가진 계수 가능한 열거를 고려하는 경우가 많다.열거되는 집합은 재귀 열거 가능(또는 현대 언어로는 계산 가능)이라고 불리며, 맵이 계산 가능함을 의미하는 공식화에서 재귀 이론의 사용을 언급한다.

이러한 의미에서 자연수의 서브셋은 계산 가능한 함수의 범위라면 계산 가능하게 열거할 수 있다.이 문맥에서 열거형(Enumerable)은 계산적으로 열거형(enumerable)을 의미하기 위해 사용될 수 있다.단, 도메인 θ를 가진 임의의 함수에 의해 열거될 수 있는 자연수의 서브셋이 셀 수 없을 정도로 많고 계산 가능한 함수는 셀 수 없을 정도로 많기 때문에 이러한 정의는 별개의 클래스를 특징짓습니다.열거형이 있지만 계산 가능한 열거형이 아닌 집합의 구체적인 예는 중지 집합의 보완입니다.

또, 이 특성은, 리스트의 순서가 중요한 장소를 나타내고 있다.정지 세트의 계산 가능한 열거는 존재하지만 요소를 오름차순으로 나열하는 열거는 존재하지 않습니다.만약 하나라도 존재한다면, 정지 집합은 결정될 수 있을 것이고, 이는 명백히 잘못된 것입니다.일반적으로 반복 열거 가능한 것은 결정 가능한 집합보다 약한 조건입니다.

열거의 개념은 열거 알고리즘의 맥락에서 다양한 작업에 대한 계산 복잡도 이론의 관점에서 연구되었다.

「」를 참조해 주세요.

레퍼런스

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

외부 링크

Wiktionary에서 열거에 대한 사전 정의

Search

열거

네임스페이스

더

목차

조합

집합론

리스트

카운트 가능 대 카운트 불가

예

특성.

서수

기수 비교

계산가능성과 복잡성 이론

「」를 참조해 주세요.

레퍼런스

외부 링크

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

Search

열거

조합

집합론

리스트

카운트 가능 대 카운트 불가

예

특성.

서수

기수 비교

계산가능성과 복잡성 이론

「 」를 참조해 주세요.

레퍼런스

외부 링크

「」를 참조해 주세요.