유한 집합

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

1. 개요

유한 집합은 선택 공리를 가정한 체르멜로-프렝켈 집합론에서 다음 조건들을 만족하는 집합으로 정의된다. 집합 S가 하나 이하의 원소를 갖거나, S와 S^2 사이에 전단사 함수가 존재하지 않는 경우, S와 부분 집합 T⊂S 사이에 전단사 함수가 존재한다면 S=T인 경우, 모든 단사 함수 S→S는 전단사 함수인 경우, 모든 전사 함수 S→S는 전단사 함수인 경우, 단사 함수 ℕ→S가 존재하지 않는 경우, 전사 함수 S→ℕ이 존재하지 않는 경우, 집합의 크기가 자연수인 경우, 멱집합 격자가 오름 사슬 조건을 만족하는 경우, 멱집합 격자가 내림 사슬 조건을 만족하는 경우이다. 선택 공리를 가정하지 않으면 이 조건들 중 일부는 동치가 아닐 수 있다. 또한, 형식적으로는 어떤 자연수 n에 대해 전단사 함수 f: S→n가 존재하면 유한하다고 부른다. 유한 집합의 기본 성질은 모든 진부분집합은 유한하며, S 자체보다 더 적은 원소를 가지며, 유한 집합과 진부분집합 사이에는 전단사 함수가 존재할 수 없다는 것이다. 두 유한 집합의 합집합, 유한 개수의 유한 집합의 합집합, 유한 집합의 데카르트 곱, 유한 개의 유한 집합의 데카르트 곱 또한 유한하다. 선택 공리를 가정하지 않은 ZF 집합론에서는 유한 집합에 대한 여러 동치 조건이 존재하며, 선택 공리를 가정하면 데데킨트 유한 집합으로 정의된다. 선택 공리가 없는 ZF 집합론에서는 여러 유한성 개념이 존재하며, 선택 공리를 가정하면 이들은 모두 동일해진다. 유한 집합과 무한 집합의 구별은 집합론에서 중요하며, 유한주의자들은 유한 집합에만 기초한 수학을 주장하기도 한다. 괴델의 불완전성 정리는 유한 집합의 형식적 구별에 대한 미묘한 문제를 야기하며, 다양한 형식 체계에서 "집합"과 "유한 집합"이 해석된다.

유한 집합

기본 정보

정의	원소의 개수가 유한한 집합
다른 용어	유한 집단
반대 개념	무한 집합
포함 관계	집합론 조합론

예시

예시 1	{2, 4, 6, 8, 10}
예시 2	{1, 2, 3, ...}

📚 더 읽어볼만한 페이지

기수 - 초한수
초한수는 게오르크 칸토어가 도입한 무한 개념을 확장한 수로, 집합의 크기를 나타내는 기수와 정렬된 집합 내의 위치를 나타내는 서수로 나뉘며, 무한에도 여러 종류가 있음을 밝혀 현대 수학의 기초를 다졌다.
기수 - 칸토어의 정리
칸토어의 정리는 집합 X의 멱집합의 크기가 X의 크기보다 항상 크다는 것을 나타내며, 임의의 기수 κ에 대해 2<sup>κ</sup> > κ가 성립한다는 내용으로, 칸토어의 대각선 논법으로 증명되고 집합론의 역설과 관련되어 전체 집합의 존재를 가정할 때 칸토어의 역설을 유발한다.
집합론의 기본 개념 - 치역
치역은 함수에서 정의역의 모든 원소에 대한 함숫값들의 집합으로, 공역의 부분집합이며, 함수의 상을 의미하거나 공역 전체를 의미하기도 한다.
집합론의 기본 개념 - 항등 함수
항등 함수는 집합 X의 각 원소를 자기 자신에게 대응시키는 함수로서, 정의역과 공역이 같은 집합 X에서 단사 함수이자 전사 함수이며, 함수 합성에서 항등원의 역할을 수행하는 중요한 개념이다.

1. 개요
2. 정의
- 2.1. 동치 조건
3. 성질
- 3.1. 기본 성질
- 3.2. 구성
4. 유한성의 필요충분조건
- 4.1. ZF 집합론에서의 동치 조건
- 4.2. 선택 공리를 가정한 경우의 동치 조건
5. 여러 유한성 개념 (선택 공리 없는 경우)
6. 기초付け 문제

2. 정의

선택 공리를 추가한 체르멜로-프렝켈 집합론에서는 집합 $S$ 에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 집합을 유한 집합이라고 한다.

형식적으로, 집합 $S$ 는 어떤 자연수 $n$ 에 대해 전단사 함수
: $\displaystyle f\colon S\to n$
가 존재하면 유한이라고 부른다. (자연수는 체르멜로-프렝켈 집합론에서 집합으로 정의된다.) 수 $n$ 은 집합의 기수이며, $|S|$ 로 표기한다.

집합이 유한하면, 그 원소는 여러 가지 방법으로 수열로 나타낼 수 있다.
: $\displaystyle x_1,x_2,\ldots,x_n \quad (x_i \in S, \ 1 \le i \le n).$
조합론에서 $n$ 개의 원소를 가진 유한 집합을 때때로 $n$ -집합이라고 부르며, $k$ 개의 원소를 가진 부분 집합을 $k$ -부분집합이라고 부른다. 예를 들어, 집합 $\{5,6,7\}$ 은 3-집합, 즉 세 개의 원소를 가진 유한 집합이고, $\{6,7\}$ 은 이 집합의 2-부분집합이다.

2.1. 동치 조건

3. 성질

공집합은 유한 집합이다. 모든 자연수는 (폰 노이만 정의에 따르면) 유한 집합이다.

* x, y가 어떤 원소이든 {}, {x}, {x, y}와 같은 집합은 유한 집합이다.
* 유한 집합을 정의역으로 하는 함수의 치역은 유한하다.
* 유한 집합의 임의의 부분 집합은 유한하다.

3.1. 기본 성질

유한 집합 $S$ 의 모든 진부분집합은 유한하며, S 자체보다 더 적은 원소를 갖는다. 따라서 유한 집합 S와 S의 진부분집합 사이에는 전단사 함수가 존재할 수 없다. 같은 기수를 가진 두 유한 집합 사이의 모든 단사 함수는 전사 함수이기도 하다. 마찬가지로, 같은 기수를 가진 두 유한 집합 사이의 모든 전사 함수는 단사 함수이기도 하다.

두 유한 집합의 합집합은 유한하며, 다음이 성립한다.

: $\displaystyle |S \cup T| \le |S| + |T|.$

포함-배제 원리에 의해 다음이 성립한다.

: $\displaystyle |S \cup T| = |S| + |T| - |S\cap T|.$

일반적으로, 유한 개의 유한 집합의 합집합은 유한하다. 유한 집합의 데카르트 곱 또한 유한하며, 다음이 성립한다.

: $\displaystyle |S \times T| = |S|\times|T|.$

마찬가지로, 유한 개의 유한 집합의 데카르트 곱은 유한하다. $n$ 개의 원소를 가진 유한 집합은 $2^n$ 개의 서로 다른 부분 집합을 갖는다. 즉, 유한 집합 S의 멱집합은 유한하며, 기수는 $2^$

👆

좌우로 밀어서 보기

이다.

유한 집합의 모든 부분 집합은 유한하다. 유한 집합의 원소에 적용될 때 함수의 값의 집합은 유한하다.

모든 유한 집합은 가산 집합이지만, 모든 가산 집합이 유한한 것은 아니다.

3.2. 구성

* x, y가 어떤 원소이든 {}, {x}, {x, y}와 같은 집합은 유한 집합이다.
* 유한 개수의 유한 집합들의 합집합은 다시 유한 집합이 된다.
* 유한 집합의 멱집합은 역시 유한 집합이다.
* 유한 집합의 임의의 부분 집합은 유한이다.
* 유한 집합을 정의역으로 하는 함수의 치역은 유한하다.
* 유한 개수의 유한 집합들로 이루어진 직접곱은 또한 유한하다.

두 유한 집합의 합집합은 유한하며, 다음이 성립한다.
: |S ∪ T| ≤ |S| + |T|

포함-배제 원리에 따르면, 다음이 성립한다.
: |S ∪ T| = |S| + |T| - |S ∩ T|

유한 집합의 데카르트 곱 또한 유한하며, 다음이 성립한다.
: |S × T| = |S| × |T|

마찬가지로, 유한 개의 유한 집합의 데카르트 곱은 유한하다. n개의 원소를 가진 유한 집합은 2ⁿ개의 서로 다른 부분 집합을 갖는다. 즉, 유한 집합 S의 멱집합 𝒫(S)는 유한하며, 기수는 2^|S|이다.

4. 유한성의 필요충분조건

선택 공리 유무에 따라 체르멜로-프렝켈 집합론(ZF)에서 유한 집합에 대한 여러 동치 조건들이 존재한다.

선택 공리가 없는 ZF에서는 다음 조건들이 모두 동치이다.

* $S$ 는 유한 집합이다.
* (카지미에시 쿠라토프스키) $S$ 는 공집합에서 시작하여 한 번에 하나의 새로운 원소를 추가하여 수학적 귀납법으로 증명할 수 있는 모든 속성을 갖는다.
* (파울 슈테켈) $S$ 는 앞뒤로 모두 전순서화된 정렬 순서를 가질 수 있다.
* $\wp\bigl(\wp(S)\bigr)$ 에서 자기 자신으로의 모든 일대일 함수는 전사이다.
* $\wp\bigl(\wp(S)\bigr)$ 에서 자기 자신으로의 모든 전사 함수는 일대일이다.
* (알프레트 타르스키) $S$ 의 공집합이 아닌 모든 부분 집합의 집합은 포함 관계에 대해 최소 원소를 갖는다.
* $S$ 는 정렬될 수 있으며, 이에 대한 모든 두 개의 정렬은 순서 동형이다.

선택 공리를 가정하는 경우(가산 선택 공리로 충분하다), 다음 조건들이 모두 동치이다.

* $S$ 는 유한 집합이다.
* (리하르트 데데킨트) $S$ 에서 자기 자신으로의 모든 일대일 함수는 전사이다.
* $S$ 에서 자기 자신으로의 모든 전사 함수는 일대일이다.
* $S$ 는 비어 있거나 $S$ 의 모든 부분 순서는 최대 원소를 포함한다.

4.1. ZF 집합론에서의 동치 조건

선택 공리를 추가한 체르멜로-프렝켈 집합론에서는 집합 $S$ 에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 집합을 유한 집합이라고 한다.

* $S$ 는 하나 이하의 원소를 갖거나, 아니면 $S$ 와 $S^2$ 사이에 전단사 함수가 존재하지 않는다.
* $S$ 와 부분 집합 $T\subset S$ 사이에 전단사 함수가 존재한다면, $S=T$ 이다.
* 모든 단사 함수 $S\to S$ 는 전단사 함수이다.
* 모든 전사 함수 $S\to S$ 는 전단사 함수이다.
* 단사 함수 $\mathbb N\to S$ 가 존재하지 않는다.
* 전사 함수 $S\to\mathbb N$ 이 존재하지 않는다.
* $S$ 의 집합의 크기가 자연수이다. 즉, $|S|\in\mathbb N=\{0,1,2,3,\dots\}$ 이다.
* $S$ 의 멱집합 격자 $(\mathcal P(S),\subseteq)$ 는 오름 사슬 조건을 만족시킨다.
* $S$ 의 멱집합 격자 $(\mathcal P(S),\subseteq)$ 는 내림 사슬 조건을 만족시킨다.

만약 선택 공리를 가정하지 않으면, 이 조건들 가운데 일부는 동치이지 않을 수 있다.

선택 공리가 없는 체르멜로-프렝켈 집합론(ZF)에서 다음 조건은 모두 동치이다.

* $S$ 는 유한 집합이다. 즉, $S$ 는 특정 자연수보다 작은 자연수 집합과 일대일 대응을 이룰 수 있다.
* (카지미에시 쿠라토프스키) $S$ 는 공집합에서 시작하여 한 번에 하나의 새로운 원소를 추가하여 수학적 귀납법으로 증명할 수 있는 모든 속성을 갖는다.
* (파울 슈테켈) $S$ 는 앞뒤로 모두 전순서화된 정렬 순서를 가질 수 있다. 즉, $S$ 의 모든 공집합이 아닌 부분 집합은 해당 부분 집합에서 최소 원소와 최대 원소를 모두 갖는다.
* $\wp\bigl(\wp(S)\bigr)$ 에서 자기 자신으로의 모든 일대일 함수는 전사이다. 즉, $S$ 의 거듭제곱의 멱집합은 데데킨트 유한이다.
* $\wp\bigl(\wp(S)\bigr)$ 에서 자기 자신으로의 모든 전사 함수는 일대일이다.
* (알프레트 타르스키) $S$ 의 공집합이 아닌 모든 부분 집합의 집합은 포함 관계에 대해 최소 원소를 갖는다. (동등하게, $S$ 의 공집합이 아닌 모든 부분 집합의 집합은 포함 관계에 대해 최대 원소를 갖는다.)
* $S$ 는 정렬될 수 있으며, 이에 대한 모든 두 개의 정렬은 순서 동형이다. 즉, $S$ 에 대한 정렬은 정확히 하나의 순서 타입을 갖는다.

선택 공리도 가정하는 경우(가산 선택 공리로 충분하다), 다음 조건은 모두 동치이다.

* $S$ 는 유한 집합이다.
* (리하르트 데데킨트) $S$ 에서 자기 자신으로의 모든 일대일 함수는 전사이다. 이 속성을 가진 집합을 데데킨트 유한이라고 한다.
* $S$ 에서 자기 자신으로의 모든 전사 함수는 일대일이다.
* $S$ 는 비어 있거나 $S$ 의 모든 부분 순서는 최대 원소를 포함한다.

4.2. 선택 공리를 가정한 경우의 동치 조건

선택 공리를 추가한 체르멜로-프렝켈 집합론에서는 집합 $S$ 에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 집합을 유한 집합이라고 한다.

* $S$ 는 하나 이하의 원소를 갖거나, $S$ 와 $S^2$ 사이에 전단사 함수가 존재하지 않는다.
* $S$ 와 부분 집합 $T\subset S$ 사이에 전단사 함수가 존재한다면, $S=T$ 이다.
* 모든 단사 함수 $S\to S$ 는 전단사 함수이다.
* 모든 전사 함수 $S\to S$ 는 전단사 함수이다.
* 단사 함수 $\mathbb N\to S$ 가 존재하지 않는다.
* 전사 함수 $S\to\mathbb N$ 이 존재하지 않는다.
* $S$ 의 집합의 크기가 자연수이다. 즉, $|S|\in\mathbb N=\{0,1,2,3,\dots\}$ 이다.
* $S$ 의 멱집합 격자 $(\mathcal P(S),\subseteq)$ 는 오름 사슬 조건을 만족시킨다.
* $S$ 의 멱집합 격자 $(\mathcal P(S),\subseteq)$ 는 내림 사슬 조건을 만족시킨다.

만약 선택 공리를 가정하지 않으면, 이 조건들 가운데 일부는 동치이지 않을 수 있다.

선택 공리가 없는 체르멜로-프렝켈 집합론(ZF)에서 다음 조건은 모두 동치이다.

* $S$ 는 유한 집합이다. 즉, $S$ 는 특정 자연수보다 작은 자연수 집합과 일대일 대응을 이룰 수 있다.
* (카지미에시 쿠라토프스키) $S$ 는 공집합에서 시작하여 한 번에 하나의 새로운 원소를 추가하여 수학적 귀납법으로 증명할 수 있는 모든 속성을 갖는다.
* (파울 슈테켈) $S$ 는 앞뒤로 모두 전순서화된 정렬 순서를 가질 수 있다. 즉, $S$ 의 모든 공집합이 아닌 부분 집합은 해당 부분 집합에서 최소 원소와 최대 원소를 모두 갖는다.
* $\wp\bigl(\wp(S)\bigr)$ 에서 자기 자신으로의 모든 일대일 함수는 전사이다. 즉, $S$ 의 거듭제곱의 멱집합은 데데킨트 유한이다.
* $\wp\bigl(\wp(S)\bigr)$ 에서 자기 자신으로의 모든 전사 함수는 일대일이다.
* (알프레트 타르스키) $S$ 의 공집합이 아닌 모든 부분 집합의 집합은 포함 관계에 대해 최소 원소를 갖는다. (동등하게, $S$ 의 공집합이 아닌 모든 부분 집합의 집합은 포함 관계에 대해 최대 원소를 갖는다.)
* $S$ 는 정렬될 수 있으며, 이에 대한 모든 두 개의 정렬은 순서 동형이다. 즉, $S$ 에 대한 정렬은 정확히 하나의 순서 타입을 갖는다.

선택 공리도 가정하는 경우(가산 선택 공리로 충분하다), 다음 조건은 모두 동치이다.

* $S$ 는 유한 집합이다.
* (리하르트 데데킨트) $S$ 에서 자기 자신으로의 모든 일대일 함수는 전사이다. 이 속성을 가진 집합을 데데킨트 유한이라고 한다.
* $S$ 에서 자기 자신으로의 모든 전사 함수는 일대일이다.
* $S$ 는 비어 있거나 $S$ 의 모든 부분 순서는 최대 원소를 포함한다.

5. 여러 유한성 개념 (선택 공리 없는 경우)

체르멜로-프렝켈 집합론(ZF 집합론)에서는 선택 공리가 없는 경우, 집합 $S$ 에 대한 여러 유한성 개념들이 서로 다를 수 있다. 이 개념들은 강도가 엄격하게 감소하는 순서로 정렬되어 있으며, 집합 $S$ 가 목록의 특정 기준을 충족하면 그 뒤에 나오는 모든 기준도 충족한다. 선택 공리가 없는 경우 역방향 함의는 모두 증명할 수 없지만, 선택 공리를 가정하면 이러한 모든 개념은 동일하다.

* I-유한: $S$ 의 부분 집합으로 구성된 모든 공집합이 아닌 집합은 $\subseteq$ -최대 원소를 갖는다. (이는 $\subseteq$ -최소 원소의 존재를 요구하는 것과 같으며, 표준적인 수적 유한성 개념과도 같다.)
* Ia-유한: $S$ 를 두 집합으로 분할하는 모든 경우, 두 집합 중 적어도 하나는 I-유한이다. (이러한 속성을 갖지만 I-유한이 아닌 집합을 비정형 집합이라고 한다.)
* II-유한: $S$ 의 부분 집합으로 구성된 모든 공집합이 아닌 $\subseteq$ -단조 집합은 $\subseteq$ -최대 원소를 갖는다.
* III-유한: 멱집합 $\wp(S)$ 는 데데킨트 유한이다.
* IV-유한: $S$ 는 데데킨트 유한이다.
* V-유한: $|S|=0$ 또는 $2\cdot|S|>|S|$ .
* VI-유한: $|S|=0$ 또는 $|S|=1$ 또는 $|S|^2>|S|$ .
* VII-유한: $S$ 는 I-유한이거나 정렬 가능하지 않다.

(강한 것에서 약한 것으로의) 정방향 함의는 ZF 내의 정리이다. ZF에 기초 집합이 있는 역방향 함의 (약한 것에서 강한 것으로)에 대한 반례는 모형 이론을 사용하여 찾아진다.

I-유한에서 IV-유한까지의 각 속성은 그러한 속성을 가진 집합의 모든 부분 집합도 해당 속성을 갖는다는 의미에서 작음의 개념이다. 이는 V-유한에서 VII-유한까지는 해당 속성이 무한히 가산 가능한 부분 집합을 가질 수 있기 때문에 해당되지 않는다.

6. 기초付け 문제

게오르크 칸토어는 무한 집합을 수학적으로 다루기 위해 집합론을 구축했으며, 이에 따라 유한 집합과 무한 집합을 구별하는 것이 중요해졌다. 유한주의자들은 무한 집합의 존재를 부정하고 유한 집합에만 기초한 수학을 주장했지만, 대부분의 수학자들은 유전적 유한 집합의 영역이 체르멜로-프렝켈 집합론의 모델을 구성한다는 점을 인정하며 상대적인 일관성을 인정했다.

그러나 괴델의 불완전성 정리로 인해 유한 집합과 무한 집합의 형식적 구별은 미묘한 문제로 남았다. 유전적 유한 집합은 페아노 공리로 해석 가능하며, 페아노 산술의 불완전성은 유전적 유한 집합 이론에도 존재함을 의미한다. 이는 비표준 모델의 존재로 이어져, 겉보기에는 유한하지만 실제로는 무한 집합을 포함하는 모델이 나타날 수 있다. 일계 술어 논리로는 이러한 모델의 표준 부분을 특정할 수 없어, 유한성을 정확하게 정의하는 데 어려움이 있다.

"집합"과 "유한 집합"의 개념은 체르멜로-프렝켈 집합론(ZF), 선택 공리를 추가한 체르멜로-프렝켈 집합론(ZFC), NBG 집합론, 비기초적 집합론 등 다양한 형식 체계에서 다르게 해석된다. 형식주의 관점에서는 집합의 의미가 체계에 따라 달라지며, 플라톤주의 관점에서는 특정 형식 체계를 현실의 근사로 간주한다.

자연수 개념이 집합보다 먼저 정의된 경우, 유한 집합은 특정 자연수 집합과의 전단사로 정의될 수 있다. 그러나 수학에서는 보통 집합론을 통해 수를 정의하므로, 자연수에 의존하지 않는 유한성에 대한 구조적 정의가 필요하다.

ZFC에서는 유한 집합을 정의하는 여러 조건들이 동치이지만, ZF나 직관 논리에서는 그렇지 않다. 대표적인 유한성 정의로는 리하르트 데데킨트의 정의와 카지미에시 쿠라토프스키의 정의가 있다.

데데킨트 무한 집합은 단사이지만 전사가 아닌 함수 f: S → S가 존재하는 집합이다. 이러한 함수는 집합과 그 진부분집합 사이에 전단사를 나타낸다. 데데킨트 유한 집합은 모든 단사 자기 사상이 전사인 경우를 의미한다.

쿠라토프스키 유한 집합은 멱집합 P(S)에 합집합 연산으로 생성되는 반격자 K(S)에 속하는 집합이다. 이는 자연수에 의존하지 않고 정의된다. ZF에서는 쿠라토프스키 유한이 데데킨트 유한을 포함하지만, 그 역은 성립하지 않는다.

정의	원소의 개수가 유한한 집합
다른 용어	유한 집단
반대 개념	무한 집합
포함 관계	집합론 조합론

예시

예시 1	{2, 4, 6, 8, 10}
예시 2	{1, 2, 3, ...}