열거

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 조합론
- 2.1. 예시
3. 집합론
4. 계산 가능성 및 복잡도 이론
참조

1. 개요

열거는 수학, 특히 조합론, 집합론, 계산 가능성 이론에서 사용되는 개념으로, 유한 또는 무한 집합의 원소를 순서대로 나열하는 것을 의미한다. 조합론에서는 유한 집합의 원소 개수를 세는 것을 의미하며, 집합론에서는 집합의 원소를 순서대로 나열하는 것을 의미한다. 집합이 열거될 수 있으면 가산 집합, 그렇지 않으면 비가산 집합으로 분류된다. 계산 가능성 이론에서는 계산 가능한 함수를 사용하여 집합을 열거하며, 열거된 집합은 재귀적 가산이라고 불린다.

더 읽어볼만한 페이지

순서 - 필순
한자 획순은 글자를 쓰는 순서에 대한 규칙으로, 경제적인 획 사용을 통해 필기 속도, 정확성, 가독성을 높이고 학습과 기억에 도움을 주며, 시대, 지역, 서체에 따라 차이가 있을 수 있지만 여러 국가에서 표준화된 획순을 교육한다.
순서 - 의전서열
의전서열은 공식 행사나 사회 관계에서 개인이나 집단의 상대적 중요성이나 지위를 나타내는 체계로, 사회 질서 유지, 존중 문화 조성, 조직 운영 및 국제 관계에서 중요한 역할을 하지만, 사회적 불평등 심화 및 권위주의 문화 고착화에 대한 비판과 개선 방안이 존재하며, 각국은 고유한 역사, 문화, 정치 체제에 따라 독특한 의전 서열을 가진다.
열거조합론 - 카탈랑 수
카탈랑 수는 조합론에서 여러 개수 세기 문제의 해답으로 나타나는 수열로, 괄호 구조, 이진 트리, 다각형 분할 등 다양한 조합론적 대상의 개수를 나타내며 여러 분야에 응용된다.
열거조합론 - 오일러 수 (조합론)
오일러 수는 조합론에서 집합의 순열 중 특정 조건을 만족하는 순열의 개수를 나타내는 수로, 주로 집합 $\{1,2,\ldots,n\}$ 의 순열에서 $a_i>a_{i+1}$ 인 $i$ 가 정확히 $m$ 개 있는 순열의 개수를 나타내며, 오일러 다항식 및 관련 성질과 함께 1755년 레온하르트 오일러에 의해 소개되었다.
수리논리학 - NAND 게이트
NAND 게이트는 모든 입력이 1일 때 0을 출력하고 그 외에는 1을 출력하는 논리 게이트로서, 다양한 기호로 표현되며, AND 연산의 결과를 부정하는 연산을 수행하고, 여러 방식으로 구현될 수 있으며, 기능적으로 완전하여 디지털 회로 설계에 필수적이다.
수리논리학 - 셈
셈은 대상의 개수를 파악하는 기본적인 행위로, 수학에서는 집합의 원소 개수를 파악하는 과정으로 정의되며, 셈의 방식에 따라 결과가 달라질 수 있고, 셈을 배우는 과정은 아동의 교육 및 발달에 중요한 역할을 한다.

열거

2. 조합론

조합론에서 열거는 셈을 의미하며, 이는 유한 집합의 원소 개수를 정확히 결정하는 것을 의미한다. 일반적으로 각 집합이 어떤 유한 집합의 모든 순열로 구성된 집합의 집합과 같이 무한 패밀리로 그룹화된다.

2. 1. 예시

조합론에서 열거는 셈을 의미하며, 이는 유한 집합의 정확한 원소 개수를 결정하는 것을 의미한다. 일반적으로 각 집합이 어떤 유한 집합의 모든 순열로 구성된 집합의 집합과 같이 무한 패밀리로 그룹화된다. 이러한 의미에서 특별한 종류의 객체를 열거하는 것과 관련된 많은 수학 분야에 번성하는 하위 영역이 있다. 예를 들어, ''정수 분할 열거'' 및 ''그래프 열거''에서 목표는 특정 조건을 충족하는 분할 또는 그래프를 세는 것이다.

3. 집합론

집합론에서 열거는 집합의 원소를 순서대로 나열하는 것을 의미하며, 유한 집합뿐만 아니라 무한 집합에도 적용된다.

어떤 집합을 자연수를 사용하여 열거할 수 있으면 가산 집합이라고 한다. 즉, 어떤 집합의 열거가 존재하면 가산 집합이다. 그렇지 않으면 비가산 집합이다. 예를 들어, 실수의 집합은 칸토어의 대각선 논법 및 칸토어의 첫 번째 비가산 증명에 의해 증명된 바와 같이 가산적인 열거가 불가능한 비가산 집합이다.

집합이 자연수의 초기 부분집합으로 열거될 수 있으면 유한 집합이며, 이 경우 해당 기수는 그 부분집합의 원소 개수이다. 공집합은 자연수의 빈 초기 부분집합으로 열거될 수 있으므로 유한 집합이다.

유한 집합과 가산 무한 집합을 구별하지 않기 위해, 집합에서 자연수로의 단사 함수가 존재하는 경우에만 가산 집합이라고 정의하기도 한다. 유한하면 반드시 가산이지만, 가산이라고 해서 유한한 것은 아니다(예: 자연수 전체 집합). 세어 올릴 수 있지만 무한 개의 요소를 가진 집합을 가산 무한 집합이라고 한다. 실제로는 "가산"이라고 말할 때 가산 무한을 가리키는 경우가 많으며, 가산 무한 또는 유한임을 명시할 때는 기껏해야 가산이라는 표현을 사용한다.

3. 1. 정렬된 목록

열거가 정렬된 목록 컨텍스트에서 사용될 때, 인덱스 집합에 어떤 종류의 정렬 구조를 요구한다. 정렬에 대한 요구 사항을 완화할 수 있지만, 가장 자연스럽고 일반적인 전제 조건은 인덱스 집합이 전순서 집합이어야 한다는 것이다. 이 특성에 따르면, 정렬된 열거는 전순서 집합을 정의역으로 하는 전사 함수(onto 관계)로 정의된다. 이 정의는 부분 열거를 고려할 때 인덱스 집합에 대한 주어진 전순서가 다음 요소를 나열하는 고유한 방법을 제공한다는 점에서 자연스럽다.

3. 2. 가산 집합과 비가산 집합

어떤 집합을 자연수를 사용하여 열거할 수 있으면 가산 집합이라고 한다. 즉, 어떤 집합의 열거가 존재하면 가산 집합이다. 그렇지 않으면 비가산 집합이다. 예를 들어, 실수의 집합은 비가산 집합이다.

집합이 자연수의 초기 부분집합으로 열거될 수 있으면 유한 집합이며, 이 경우 해당 기수는 그 부분집합의 원소 개수이다. 공집합은 자연수의 빈 초기 부분집합으로 열거될 수 있으므로 유한 집합이다.

유한 집합과 가산 무한 집합을 구별하지 않기 위해, 집합에서 자연수로의 단사 함수가 존재하는 경우에만 가산 집합이라고 정의하기도 한다. 유한하면 반드시 가산이지만, 가산이라고 해서 유한한 것은 아니다(예: 자연수 전체 집합). 세어 올릴 수 있지만 무한 개의 요소를 가진 집합을 가산 무한 집합이라고 한다.

실제로는 "가산"이라고 말할 때 가산 무한을 가리키는 경우가 많으며, 가산 무한 또는 유한임을 명시할 때는 기껏해야 가산이라는 표현을 사용한다.

가산이 아닌 것, 즉 비가산은 세어 올리는 것이 불가능한 무한을 의미한다(예: 실수 전체 집합).

3. 2. 1. 예시

자연수는 함수 ''f''(''x'') = ''x''에 의해 열거 가능하다. 이 경우 $f\colon\mathbb{N} \to \mathbb{N}$ 은 단순히 항등 함수이다.
정수 집합( $\mathbb{Z}$ )은 다음과 같이 열거 가능하다.

:

f(x):=\frac {1-(-1)^x\,(2\,x+1)} 4

:

f\colon\mathbb{N}_0 \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$ 는 ''S''의 열거이다.
실수는 칸토어의 대각선 논법 및 칸토어의 첫 번째 비가산 증명에 의해 증명된 바와 같이 가산적인 열거가 없다.

3. 2. 2. 성질

어떤 집합이 가산 집합일 경우에만 열거될 수 있다.
집합이 열거 가능하다면, 공집합 또는 (정확한 정의에 따라) 한 개의 원소를 가진 집합의 퇴화된 경우를 제외하고, 서로 다른 무한히 많은 열거가 존재한다. 그러나 열거가 주입적이어야 하며, ''f''(''n'')이 정의되면 모든 ''m'' < ''n''에 대해 ''f''(''m'')도 정의되어야 하는 제한된 형태의 부분성만 허용하는 경우, ''N''개의 원소를 가진 유한 집합은 정확히 ''N''!개의 열거를 갖는다.
도메인이 $\mathbb{N}$ 인 집합 ''S''의 열거 ''e''는 $\min e^{-1}(s) \leq \min e^{-1}(t)$ 일 경우에만 ''s'' ≤ ''t''로 정의되는 해당 집합에 대한 정렬 순서 ≤를 유도한다. 순서가 기본 집합과 거의 관련이 없을 수 있지만, 집합의 일부 순서가 필요할 때 유용하다.

3. 3. 서수

집합론에서는 정의역이 서수인 열거 함수도 정의할 수 있다. 이 정의에 따르면, 집합 ''S''의 열거는 서수 α에서 ''S''로의 모든 전사 함수이다. 이는 α가 유한 서수이거나 첫 번째 극한 서수 ω인 특수한 경우로, 초한 귀납법적 나열을 포함하도록 확장된다.

이 정의에 따르면,

\omega_1

은

\omega_1

에 대한 항등 함수에 의해 나열될 수 있으므로, 일반적인 열거와는 '''일치하지 않는다'''. 더 일반적으로, 모든 정렬 집합은 이 특성에 따라 나열될 수 있으며, 이는 일반화된 열거와 재라벨링을 통해 일치한다는 ZF의 정리이다. 또한 선택 공리를 가정하면 모든 집합을 나열할 수 있어 가장 일반적인 형태의 열거와 재라벨링을 통해 일치한다.

집합론자들은 임의로 큰 기수의 무한 집합으로 작업하므로, 집합의 나열에 대한 기본 정의는 모든 요소를 나열하는 임의의 α-수열이 되는 경향이 있다. 실제로, 집합론자들이 흔히 참고하는 Jech의 책에서는 나열을 바로 이것으로 정의한다. 따라서 모호성을 피하기 위해, 해당 유형의 구별되는 가산 나열 중 하나를 나타내기 위해 유한 나열 가능 또는 가산이라는 용어를 사용할 수 있다.

4. 계산 가능성 및 복잡도 이론

계산 가능성 이론에서, 종종 $\mathbb{N}$ (모든 자연수의 집합)에서 열거된 집합으로의 매핑이 계산 가능한 함수여야 한다는 추가 요구 사항과 함께 가산 열거를 고려한다. 열거된 집합은 해당 매핑이 계산 가능하다는 의미를 공식화하는 데 재귀 이론을 사용하는 것과 관련하여 재귀적 가산(또는 보다 현대적인 언어로는 계산 가능하게 가산)이라고 한다.

이러한 의미에서, 자연수의 부분 집합은 계산 가능한 함수의 범위인 경우 계산 가능하게 가산이다. 이 맥락에서, 열거는 계산 가능하게 열거를 의미하는 데 사용될 수 있다. 그러나 이러한 정의는 서로 다른 클래스를 특징짓는데, 그 이유는 ω를 도메인으로 하는 임의의 함수에 의해 열거될 수 있는 자연수의 부분 집합이 무한히 많고 계산 가능한 함수는 가산적으로만 존재하기 때문이다. 열거는 있지만 계산 가능한 열거가 없는 집합의 구체적인 예는 정지 문제의 여집합이다.

또한 이 특징은 목록의 순서가 중요한 위치를 보여준다. 정지 집합의 계산 가능한 열거가 존재하지만, 원소를 증가하는 순서로 나열하는 것은 '''아니다'''. 만약 그런 것이 있다면, 정지 집합은 결정 가능 언어가 될 것이고, 이는 증명에 의해 거짓이다. 일반적으로 재귀적으로 가산인 것은 결정 가능한 집합인 것보다 약한 조건이다.

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

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com