가산 집합

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

1. 개요
2. 정의
3. 역사
4. 예시
5. 성질
6. 전순서
- 6.1. 정렬 순서
- 6.2. 정렬 순서가 아님
7. 최소 표준 모형
참조

1. 개요

가산 집합은 그 기수가 알레프-0(ℵ₀, 자연수 집합의 기수)보다 작거나 같은 집합을 의미한다. 이는 집합에서 자연수로의 단사 함수가 존재하거나, 자연수에서 집합으로의 전사 함수가 존재하거나, 집합과 자연수의 부분 집합 사이에 전단사 매핑이 존재하는 경우와 동치이다. 가산 집합은 유한하거나 가산 무한 집합일 수 있으며, 정수, 유리수, 대수적 수의 집합 등이 가산 집합에 속한다. 가산 집합의 유한 합집합과 가산 개의 가산 집합의 합집합 역시 가산 집합이며, 칸토어의 정리에 따라 멱집합은 비가산 집합이다. 가산 집합은 전순서화될 수 있으며, 정렬 순서와 그렇지 않은 순서가 존재한다. ZFC 집합론의 최소 표준 모형은 가산 집합이다.

더 읽어볼만한 페이지

집합론 - 퍼지 집합
퍼지 집합은 각 원소가 0과 1 사이의 소속도를 가지며, 소속 함수를 통해 정의되고, 여집합, 합집합, 교집합 등의 연산을 수행하며, 퍼지 논리, 퍼지 수, 엔트로피 등의 개념과 L-퍼지 집합, 직관적 퍼지 집합 등으로 확장된다.
집합론 - 무한 집합
무한 집합은 유한 집합이 아니며, 자연수보다 큰 크기를 가지고 자신의 진부분집합과 일대일 대응을 가지며, 가산 무한 집합과 비가산 무한 집합으로 나뉜다.

가산 집합
정의
가산 집합	자연수 집합과 대응시킬 수 있는 집합
영어	Countable set
종류
가산 집합 종류	유한집합 가산 무한 집합
설명	가산 무한 집합은 자연수 전체의 집합과 대등하다.
성질
가산 집합의 성질	가산 집합의 부분집합은 가산 집합이다. 가산 집합들의 가산 합집합은 가산 집합이다. 유한 집합들의 가산 곱집합은 가산 집합이다. 정수 집합, 유리수 집합은 가산 집합이다. 대수적 수의 집합은 가산 집합이다.
비가산 집합
비가산 집합 종류	실수 집합 복소수 집합 무리수 집합 초월수 집합 칸토어 집합
설명	이들은 모두 연속체의 크기를 갖는다.

2. 정의

집합 $S$ 가 가산 집합이라는 것은 다음 조건 중 하나와 동치이다.

기수 $|S|$ 가 ℵ₀ (알레프-0, 자연수 집합 $\N$ 의 기수)보다 작거나 같다.^[15]
$S$ 에서 $\N$ 으로의 단사 함수가 존재한다.^[9]^[10]
$S$ 가 비어 있거나 $\N$ 에서 $S$ 로의 전사 함수가 존재한다.^[10]
$S$ 와 $\N$ 의 부분 집합 간에 전단사 매핑이 존재한다.^[11]
$S$ 는 유한 ( $|S|<\aleph_0$ )하거나 가산 무한이다.^[5]

게오르크 칸토어의 연구 이전에는, 무한 집합은 모두 같은 크기를 갖는다고 생각했다. 예를 들어 무한히 많은 홀수, 짝수, 정수가 존재하는데, 모든 정수에 대해 고유한 짝수를 대응시킬 수 있기 때문이다. 하지만 칸토어는 모든 무한 집합이 가산 무한은 아니라는 것을 보였다.

2. 1. 가산 집합

자연수, 정수, 유리수의 집합은 가산 집합이다.^[1]

집합

S

는 다음과 같은 경우에 ''가산 집합''이다.

그 기수 $|S|$ 가 ℵ₀ (알레프-0, 자연수 집합 $\N$ 의 기수)보다 작거나 같다.^[15]
$S$ 에서 $\N$ 으로의 단사 함수가 존재한다.^[9]^[10]
$S$ 가 비어 있거나 $\N$ 에서 $S$ 로의 전사 함수가 존재한다.^[10]
$S$ 와 $\N$ 의 부분 집합 간에 전단사 매핑이 존재한다.^[11]
$S$ 는 유한 ( $|S|<\aleph_0$ )하거나 가산 무한이다.^[5]

이 모든 정의는 동치이다.

정의에 따르면, 집합

S

와 자연수

\N=\{0,1,2,\dots\}

의 부분 집합 사이에 전단사 함수가 존재하면

S

는 ''가산 집합''이다. 예를 들어,

S=\{a,b,c\}

이고,

a \leftrightarrow 1,\ b \leftrightarrow 2,\ c \leftrightarrow 3

으로 대응하면,

S

의 모든 원소가

\{1,2,3\}

의 원소와 정확히 일대일 대응되므로, 이는 전단사 함수를 정의하며

S

가 가산 집합임을 보여준다. 마찬가지로 모든 유한 집합은 가산 집합이다.

무한 집합의 경우, 집합

S

와

\N

전체 사이에 전단사 함수가 존재하면 집합

S

는 가산 무한 집합이다. 예를 들어, 양의 정수 집합

A=\{1,2,3,\dots\}

와 짝수 정수의 집합

B=\{0,2,4,6,\dots\}

은

n \leftrightarrow n+1

및

n \leftrightarrow 2n

으로 각각 자연수와 전단사 함수를 만들수 있으므로, 가산 무한 집합이다.

모든 가산 무한 집합은 가산 집합이고, 모든 무한 가산 집합은 가산 무한 집합이다. 또한, 자연수의 모든 부분 집합은 가산 집합이다.

모든 순서쌍의 자연수 집합(두 개의 자연수 집합의 데카르트 곱,

\N\times\N

)은 가산 무한 집합이며, 위 그림과 같이 확인할 수 있다. 이 사상은 다음과 같다.

0 \leftrightarrow (0, 0), 1 \leftrightarrow (1, 0), 2 \leftrightarrow (0, 1), 3 \leftrightarrow (2, 0), 4 \leftrightarrow (1, 1), 5 \leftrightarrow (0, 2), 6 \leftrightarrow (3, 0), \ldots

이러한 형태의 삼각 사상은

n

-튜플의 자연수(

(a_1,a_2,a_3,\dots,a_n)

, 여기서

a_i

와

n

은 자연수)로 일반화될 수 있다. 예를 들어

(0, 2, 3)

은

((0, 2), 3)

으로 쓸 수 있고,

(0, 2)

는 5로 사상되므로,

((0, 2), 3)

은

(5, 3)

으로, 다시

(5,3)

은 39로 사상된다. 서로 다른 튜플은 다른 자연수로 사상되므로,

n

-튜플의 집합에서 자연수 집합

\N

으로의 단사 함수가 증명된다.

모든 정수 집합

\Z

과 모든 유리수 집합

\Q

는 직관적으로

\N

보다 훨씬 더 커 보일 수 있지만, 겉보기와는 다를 수 있다. 분수

a/b

(

a

와

b\neq 0

는 정수)에 대해 분자

a

와 분모

b

를 순서쌍으로 생각하면, 모든 양의 분수는 고유한 자연수에 대응시킬 수 있다. 모든 자연수

n

은 분수

n/1

로 표현가능하므로, 양의 유리수의 수는 양의 정수의 수와 정확히 같다.

비슷한 방식으로, 대수적 수의 집합은 가산 집합이다.^[23]

집합

A

가 가산 집합임을 보이기 위해,

A

를 다른 집합

B

에 일대일 사상(단사)한 다음,

B

를 자연수 집합에 일대일 사상하는 방법을 쓸 수 있다. 예를 들어, 양의 유리수 집합은

p/q

를

(p,q)

로 사상하여 자연수 쌍의 집합에 일대일 사상할 수 있고, 자연수 쌍의 집합은 자연수 집합과 일대일 대응되므로 양의 유리수 집합은 가산 집합이다.

가산 집합

\textbf{a},\textbf{b},\textbf{c},\dots

가 주어지면, 각 집합의 각 요소에 튜플을 할당한 다음, 삼각 열거를 사용하여 각 튜플에 인덱스를 할당한다.

\begin{array}{ c|c|c }\text{Index} & \text{Tuple} & \text {Element} \\ \hline0 & (0,0) & \textbf{a}_0 \\1 & (0,1) & \textbf{a}_1 \\2 & (1,0) & \textbf{b}_0 \\3 & (0,2) & \textbf{a}_2 \\4 & (1,1) & \textbf{b}_1 \\5 & (2,0) & \textbf{c}_0 \\6 & (0,3) & \textbf{a}_3 \\7 & (1,2) & \textbf{b}_2 \\8 & (2,1) & \textbf{c}_1 \\9 & (3,0) & \textbf{d}_0 \\10 & (0,4) & \textbf{a}_4 \\\vdots & &\end{array}

''모든'' 집합

\textbf{a},\textbf{b},\textbf{c},\dots

에 동시에 인덱스를 부여하려면 가산 선택 공리가 필요하다.

길이가 유한한 자연수 수열의 집합은 길이 1, 2, 3, ... 인 수열들의 합집합이고, 각 길이에 대한 수열의 집합은 가산 집합(유한 데카르트 곱)이므로, 가산 집합의 가산 합집합이 되어 가산 집합이다.

모든 유한 부분 집합의 요소는 유한 수열로 정렬할 수 있고, 유한 수열은 가산 개이므로, 유한 부분 집합도 가산 개이다.

함수

f:S\to T

가 단사 함수이고

T

가 가산 집합이면

S

는 가산 집합이다. 함수

g:S\to T

가 전사 함수이고

S

가 가산 집합이면

T

는 가산 집합이다.

'''칸토어의 정리'''는

A

가 집합이고

\mathcal{P}(A)

가

A

의 모든 부분 집합의 집합인 멱집합일 때,

A

에서

\mathcal{P}(A)

로의 전사 함수는 없다고 주장한다.

2. 2. 가산 무한 집합

그 기수 $|S|$ 가 정확히 $\aleph_0$ 이다.^[15]
$S$ 와 자연수 집합 $\N$ 사이에는 단사 함수이면서 전사 함수(전단사 함수)인 매핑이 존재한다.
$S$ 는 $\N$ 과 일대일 대응을 이룬다.^[12]
$S$ 의 원소는 $a_0, a_1, a_2, \ldots$ 와 같은 무한 수열로 배열할 수 있으며, 여기서 $i\neq j$ 일 때 $a_i$ 는 $a_j$ 와 다르고, $S$ 의 모든 원소가 나열된다.^[13]^[14]

예를 들어, 모든 정수에 대해 고유한 짝수가 존재하도록 배열할 수 있다.

\ldots \, -\! 2\! \rightarrow \! - \! 4, \, -\! 1\! \rightarrow \! - \! 2, \, 0\! \rightarrow \! 0, \, 1\! \rightarrow \! 2, \, 2\! \rightarrow \! 4 \, \cdots

일반적으로,

n \rightarrow 2n

과 같이 나타낼 수 있다(위 그림 참조). 여기서 정수와 짝수를 ''일대일 대응'' (''전단사 함수'')으로 배열하였다. 이는 두 집합 사이에서 각 집합의 원소가 다른 집합의 단일 원소에 대응하도록 하는 함수이다. "크기"에 대한 이러한 수학적 개념, 즉 기수는 두 집합 사이에 전단사 함수가 존재할 경우에만 두 집합이 같은 크기를 갖는다는 것이다. 정수와 일대일 대응을 이루는 모든 집합을 ''가산 무한''이라고 부르며, 이 기수를

\aleph_0

이라고 한다.

2. 3. 비가산 집합

가산적이지 않은 집합, 즉 그 기수가 ℵ₀|알레프-0^한국어보다 큰 집합을 비가산 집합이라고 한다.^[15] 실수의 집합, 자연수의 멱집합, 무리수의 집합은 비가산 집합이며 비가부번 집합이다. 이것은 대각선 논법이나 범주정리, 실수의 연속성 등으로 증명할 수 있다.

3. 역사

1874년, 칸토어는 자신의 첫 번째 집합론 논문에서 실수의 집합이 가산 집합이 아님을 증명하여, 모든 무한 집합이 가산 집합은 아니라는 것을 보였다.^[16] 1878년에는 일대일 대응을 사용하여 기수를 정의하고 비교했다.^[17] 1883년에는 무한 서수로 자연수를 확장하고, 서수의 집합을 사용하여 서로 다른 무한 기수를 가진 무한 개의 집합을 만들었다.^[18]

4. 예시

자연수, 정수, 유리수의 집합은 가산 집합이다.^[19] 실수의 집합, 자연수의 멱집합, 무리수의 집합은 비가산 집합이며, 대각선 논법, 범주정리, 실수의 연속성 등으로 증명할 수 있다.^[19]

집합 $S$ 와 자연수 $\N=\{0,1,2,\dots\}$ 의 부분 집합 사이에 전단사 함수가 존재하면 $S$ 는 가산 집합이다. 예를 들어, $S=\{a,b,c\}$ 의 모든 원소가 $\{1,2,3\}$ 의 정확히 하나의 원소에 대응되고 그 반대도 성립하는 대응( $a \leftrightarrow 1,\ b \leftrightarrow 2,\ c \leftrightarrow 3$ )은 전단사 함수를 정의하며, $S$ 가 가산 집합임을 보여준다. 모든 유한 집합은 가산 집합이다.

무한 집합의 경우, 집합 $S$ 와 $\N$ 전체 사이에 전단사 함수가 존재하면 $S$ 는 가산 무한 집합이다. 예를 들어, 양의 정수 집합 $A=\{1,2,3,\dots\}$ 와 짝수 정수의 집합 $B=\{0,2,4,6,\dots\}$ 은 $n \leftrightarrow n+1$ 및 $n \leftrightarrow 2n$ 할당을 통해 전단사 함수를 제시하여 가산 무한 집합임을 보일 수 있다.

$\begin{matrix}0 \leftrightarrow 1, & 1 \leftrightarrow 2, & 2 \leftrightarrow 3, & 3 \leftrightarrow 4, & 4 \leftrightarrow 5, & \ldots \\[6pt]0 \leftrightarrow 0, & 1 \leftrightarrow 2, & 2 \leftrightarrow 4, & 3 \leftrightarrow 6, & 4 \leftrightarrow 8, & \ldots\end{matrix}$

모든 가산 무한 집합은 가산 집합이고, 모든 무한 가산 집합은 가산 무한 집합이다. 자연수의 모든 부분 집합은 가산 집합이다.

모든 순서쌍의 자연수 집합( $\N\times\N$ )은 가산 무한 집합이며, 위 그림과 같은 경로를 따라 확인할 수 있다. 결과적인 사상은 다음과 같다.

$0 \leftrightarrow (0, 0), 1 \leftrightarrow (1, 0), 2 \leftrightarrow (0, 1), 3 \leftrightarrow (2, 0), 4 \leftrightarrow (1, 1), 5 \leftrightarrow (0, 2), 6 \leftrightarrow (3, 0), \ldots$

모든 정수 집합 $\Z$ 과 모든 유리수 집합 $\Q$ 는 직관적으로 $\N$ 보다 훨씬 커 보일 수 있지만, 겉보기와는 다를 수 있다.

대수적 수의 집합은 가산 집합이다.^[23]

'''칸토어의 정리'''는 $A$ 가 집합이고 $\mathcal{P}(A)$ 가 $A$ 의 모든 부분 집합의 집합인 멱집합인 경우, $A$ 에서 $\mathcal{P}(A)$ 로의 전사 함수는 없다고 주장한다.

실수의 집합은 비가산 집합이고, 자연수의 모든 무한 수열의 집합도 비가산 집합이다.

5. 성질

가산 집합의 합집합은 가산 집합이다. (이 명제는 가산 선택 공리를 가정해야 참이다.)^[26] 가산 집합의 부분 집합은 가산 집합이다.^[20] 유한 개의 가산 집합의 데카르트 곱은 가산 집합이다.^[21] 가산 집합의 모든 유한 합집합은 가산 집합이다.^[24]^[25] 자연수의 모든 유한 길이 수열의 집합은 가산 집합이다. 자연수의 모든 유한 부분 집합의 집합은 가산 집합이다.

함수 $f:S\to T$ 가 단사 함수이고 $T$ 가 가산 집합이면 $S$ 는 가산 집합이다. 함수 $g:S\to T$ 가 전사 함수이고 $S$ 가 가산 집합이면 $T$ 는 가산 집합이다.

칸토어의 정리에 따르면, 집합 $A$ 의 멱집합 $\mathcal{P}(A)$ 는 $A$ 에서 $\mathcal{P}(A)$ 로의 전사 함수가 존재하지 않으므로 항상 $A$ 보다 크다. 따라서 $\mathcal{P}(\N)$ 은 비가산 집합이다.

6. 전순서

가산 집합은 여러 가지 방법으로 전순서화될 수 있다. 정렬 순서인 경우와 정렬 순서가 아닌 경우가 있으며, 전순서가 정렬 순서인지 판별하는 핵심은 모든 부분 집합이 '최소 원소'를 가지는지 확인하는 것이다.

6. 1. 정렬 순서

정렬 순서는 다음과 같다.

자연수의 일반적인 순서: (0, 1, 2, 3, 4, 5, ...)
정수의 순서: (0, 1, 2, 3, ...; −1, −2, −3, ...)

6. 2. 정렬 순서가 아님

정렬 순서가 아닌 경우:

정수의 일반적인 순서 (..., −3, −2, −1, 0, 1, 2, 3, ...)
유리수의 일반적인 순서 (정렬된 목록으로 명시적으로 작성할 수 없음)

정렬 순서의 두 예시에서는 모든 부분 집합이 '최소 원소'를 가지지만, 정렬 순서가 아닌 위의 두 예시에서는 일부 부분 집합이 '최소 원소'를 갖지 않는다.^[1] 이것은 전순서가 정렬 순서이기도 한지 여부를 결정하는 핵심 정의이다.^[1]

7. 최소 표준 모형

ZFC 집합론의 표준 모형(내부 모형)이 있다면, 최소 표준 모형(구성적 우주)이 존재한다. 뢰벤하임-스콜렘 정리를 사용하여 이 최소 모형이 가산임을 보일 수 있다. 이 모형에서도 "비가산성" 개념이 성립한다는 사실, 특히 이 모형 ''M''이 다음 요소를 포함한다는 사실은 집합론 초창기에 역설적인 것으로 여겨졌다.

''M''의 부분 집합이므로 가산,
하지만 ''M''의 관점에서는 비가산,

더 자세한 내용은 스콜렘의 역설을 참고하라.

최소 표준 모형은 모든 대수적 수와 모든 효과적으로 계산 가능한 초월수뿐만 아니라 다른 많은 종류의 수도 포함한다.

참조

_[1] 서적 Topology https://books.google[...] Springer 2015-06-19
_[2] 간행물
_[3] 간행물
_[4] 간행물
_[5] 간행물
_[6] 간행물
_[7] 서적 Handbook of Mathematics https://books.google[...] BoD - Books on Demand 2017-04-04
_[8] 서적 First Course in Real Analysis https://books.google[...] Academic Publishers 2009-01-01
_[9] 서적 Introduction to Topology https://books.google[...] Springer 2019-05-17
_[10] 서적 An Illustrative Introduction to Modern Analysis https://books.google[...] CRC Press 2018-01-02
_[11] 간행물
_[12] 간행물
_[13] 서적 Invitation To Algebra: A Resource Compendium For Teachers, Advanced Undergraduate Students And Graduate Students In Mathematics https://books.google[...] World Scientific 2020-06-09
_[14] 간행물
_[15] 서적 An Introduction to Metalogic https://books.google[...] Broadview Press 2014-10-24
_[16] citation Roads to Infinity: The Mathematics of Truth and Proof https://books.google[...] CRC Press
_[17] 간행물
_[18] 간행물
_[19] 웹사이트 What Are Sets and Roster Form? https://www.expii.co[...] 2021-05-09
_[20] 간행물
_[21] 간행물
_[22] 간행물
_[23] 간행물
_[24] 간행물
_[25] 간행물
_[26] 서적 Introduction to Set Theory, Third Edition, Revised and Expanded https://books.google[...] CRC Press 1999-06-22

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

문의하기 : help@durumis.com