유한 집합

수학, 특히 집합론에서, 유한 집합은 유한한 수의 요소들을 가진 집합이다.비공식적으로 유한 집합은 원칙적으로 카운트하고 종료할 수 있는 집합입니다.예를들면,

$(\displaystyle\{2,4,6,8,10\})$

5개의 요소를 가진 유한 집합입니다.유한 집합의 요소 수는 자연수(아마도 0)이며 집합의 카디널리티(또는 기수)라고 불립니다.유한 집합이 아닌 집합을 무한 집합이라고 합니다.예를 들어, 모든 양의 정수 집합은 무한합니다.

$(\displaystyle\{1,2,3,\ldots\}).}$

유한 집합은 계수 수학인 조합론에서 특히 중요하다.유한 집합을 포함하는 많은 논거는 비둘기구멍 원리에 의존하는데, 비둘기구멍 원리는 더 큰 유한 집합에서 더 작은 유한 집합으로의 주입 함수는 존재할 수 없다는 것이다.

정의와 용어

형식적으로, 집합 S는 만약 분사가 존재한다면 유한하다고 불린다.

$(\displaystyle f\colon S\to\{1,\ldots,n\})$

자연수 n에 대해서요숫자 n은 집합의 카디널리티로 S로 표시됩니다.빈 집합 { } 또는 is은 유한으로 간주되며 카디널리티는 ^[1][2][3][4]0입니다.

집합이 유한한 경우, 그 요소는 여러 가지 방법으로 순차적으로 작성될 수 있습니다.

$\displaystyle x_{1},x_{2},\ldots,x_{n}\quad(x_{i}\in S,\leq i\leq n).}$

조합론에서, n개의 원소가 있는 유한 집합을 n-집합이라고 부르기도 하고 k개의 원소가 있는 부분 집합을 k-집합이라고 부르기도 한다.예를 들어, 집합 {5,6,7}은 3개의 요소로 이루어진 유한 집합인 3개의 집합이고 {6,7}은 2개의 집합입니다.

(일명 von Neumann 구조라고 불리는 집합론에서 자연수의 정의에 익숙한 사람들은 동등한 bijection${\displaystyle }f{\displaystyle }$ : ${\displaystyle S}$ ${\displaystyle \to }$ \ $displaystyle f\to$n의 존재를 선호할 수 있다.)

기본 속성

유한 집합 S의 임의의 적절한 부분 집합은 유한하며, S 자체보다 적은 수의 요소를 가진다.그 결과, 유한 집합 S와 S의 적절한 부분 집합 사이에 바이젝션이 존재할 수 없다.이 속성을 가진 집합을 Dedekind-finite라고 합니다.집합론에 표준 ZFC 공리를 사용하면, 모든 데데킨드 유한 집합은 유한하지만, 이 함의는 선택 공리가 없는 ZF(Zermelo-Fraenkel 공리)만으로는 증명할 수 없다.선택 공리의 약한 버전인 계산 가능한 선택의 공리는 이 동등성을 증명하기에 충분하다.

같은 카디널리티의 2개의 유한 집합 사이의 모든 주입 함수도 사출 함수(사출 함수)입니다.마찬가지로, 동일한 카디널리티의 두 유한 집합 사이의 돌출도 주입입니다.

두 유한 집합의 결합은 유한하다.

$\displaystyle S\cup T \leq S + T . }$

실제로 포함-배제 원칙에 따라 다음과 같이 처리한다.

$(\displaystyle S\cup T = S + T - S \ cap T )$

보다 일반적으로 유한 집합의 유한한 수의 합집합은 유한하다.유한 집합의 데카르트 곱 또한 유한하다.

${\displaystyle S\times T = S \times T }$

마찬가지로, 유한 집합의 데카르트 곱은 유한하다.n개의 요소가 있는 유한 집합에는 2개의 서로 다른 서브셋이 있습니다ⁿ.즉, 유한 집합 S의 멱집합 P(S)는 유한하고 카디널리티는 ^S 2이다.

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

모든 유한 집합이 계수 가능하지만 계수 가능 집합이 유한한 것은 아닙니다.(단, 일부 저자는 "countable"을 "countable infinite"라는 의미로 사용하므로 유한 집합을 계산 가능한 집합으로 간주하지 마십시오.)

유한 집합에 대한 자유 반격차는 빈 서브셋이 아닌 집합 집합이며 결합 연산은 집합 연합에 의해 제공됩니다.

최종성을 위한 필요충분조건

선택 공리(ZF)가 없는 체르멜로-프랭켈 집합론에서는 다음 조건이 모두 ^{[citation needed]}동일하다.

1. S는 유한 집합이다.즉, S는 특정 자연수보다 작은 자연수 집합과 일대일 대응 관계에 놓일 수 있다.
2. (카지미에즈 쿠라토프스키) S는 빈 집합에서 시작하여 새로운 원소를 한 번에 1개씩 더함으로써 증명할 수 있는 모든 성질을 가지고 있다.(Kuratowski 미세도의 집합 이론 공식은 아래를 참조하십시오.)
3. (Paul Stéckel) S는 전방과 후방 모두 순서가 좋은 총 순서를 지정할 수 있다.즉, S가 비어 있지 않은 모든 부분 집합은 부분 집합에서 가장 작은 요소와 가장 큰 요소를 모두 가집니다.
4. P(P(S)에서 그 자체에 이르는 모든 일대일 함수는 에 있습니다.즉, S의 거듭제곱 집합의 멱집합은 데데킨드 유한이다(아래 ^[5]참조).
5. P(P(S)에서 그 자체에 이르는 모든 투영 함수는 일대일입니다.
6. (Alfred Tarski) S의 모든 비빈 부분 집합 패밀리는 ^[6]포함에 관해 최소한의 요소를 가진다(동등하게, S의 비빈 부분 집합 패밀리는 포함에 관해 최대 요소를 가진다).
7. S는 잘 정렬될 수 있으며 그 위에 있는 두 개의 잘 정렬된 순서는 모두 동형입니다.즉, S의 Well-ording은 정확히 하나의 주문 유형을 가집니다.

선택 공리도 가정할 경우(계산 가능한 선택 공리만으로 충분^{[7][citation needed]}), 다음 조건은 모두 동일합니다.

1. S는 유한 집합이다.
2. (Richard Dedekind) S에서 그 자체에 이르는 모든 1대1 함수는 그 위에 있습니다.
3. S에서 그 자체로 이어지는 모든 투영 함수는 일대일입니다.
4. S가 비어 있거나 S의 모든 부분 순서가 최대 요소를 포함합니다.

근본적인 문제

게오르크 칸토르는 무한 집합의 수학적 처리를 제공하기 위해 집합 이론을 시작했다.따라서 유한과 무한의 구별은 집합론의 핵심에 있다.엄밀한 피니티스트인 특정 기초론자들은 무한 집합의 존재를 거부하고 따라서 유한 집합만을 기초로 한 수학을 추천한다.주류 수학자들은 엄격한 피니티즘을 너무 제한적이라고 생각하지만, 상대적인 일관성을 인정한다: 유전적으로 유한한 집합의 우주는 무한의 공리가 부정으로 대체되는 체르멜로-프랭켈 집합론의 모델을 구성한다.

심지어 무한 집합을 수용하는 대부분의 수학자들에게도, 특정한 중요한 맥락에서, 유한과 무한 사이의 공식적인 구별은 미묘한 문제로 남을 수 있습니다.그 어려움은 괴델의 불완전성 이론에서 비롯된다.페아노 산술에서 유전적으로 유한한 집합의 이론을 해석할 수 있기 때문에 페아노 산술의 이론의 불완전성은 유전적으로 유한한 집합의 이론을 암시한다.특히, 두 이론 모두 소위 말하는 비표준 모델이 너무 많이 존재한다.유전적으로 유한 집합의 이론에는 무한 집합을 포함하는 비표준 모델이 있지만, 이러한 무한 집합은 모형 내에서 유한해 보입니다.(이는 모델에 이러한 집합의 무한성을 확인하는 데 필요한 집합이나 함수가 없을 때 발생할 수 있습니다.)불완전성 이론 때문에, 어떤 1차 술어도 심지어 1차 술어의 어떤 재귀적 체계도 그러한 모든 모델의 표준 부분을 특징지을 수 없다.따라서, 적어도 1차 논리의 관점에서 보면, 최종성을 대략적으로 묘사할 수 있을 것이다.

보다 일반적으로 집합, 특히 유한 집합과 같은 비공식적 개념은 공리학과 논리 기구에 따라 다양한 공식 시스템 범위에 걸쳐 해석을 받을 수 있다.가장 잘 알려진 공리 집합론에는 체르멜로-프렝켈 집합론(ZF), 선택 공리를 사용한 체르멜로-프렝켈 집합론(ZFC), 폰 노이만-베르네이스 등이 있다.괴델 집합론(NBG), 근거가 없는 집합론, 버트런드 러셀의 유형 이론과 그들의 다양한 모델의 모든 이론.고전적인 1차 논리, 다양한 고차 논리 및 직관적 논리 중에서 선택할 수도 있다.

형식주의자는 시스템마다 집합의 의미가^{[citation needed]} 다르다는 것을 알 수 있습니다.어떤 종류의 플라톤주의자들은 특정한 형식적인 시스템을 근저에 있는 현실에 가깝다고 볼 수 있다.

미세성의 집합론적 정의

만약 S는 형태{x=<>n}{\displaystyle\와 같이{x\, \,x<, n\}의 자연수의 일부를 bijection을 인정하는 자연적인 숫자의 개념 논리적으로 전 세트의 개념으로 앉아 있어 맥락에서 보면, 유한으로}. 수학자들 대체적으로 집합론에서 숫자의 유래된 개념에, 예를 들어 그들이 선택한 집합 S규정할 수 있습니다. 아마.순서가 잘 지정된 유한 집합의 순서 유형으로 자연수를 모형화합니다.그러한 접근방식은 자연수에 의존하지 않는 미세성의 구조적 정의를 요구한다.

ZFC 이론의 모든 집합 중에서 유한 집합을 골라내는 다양한 특성은 ZF나 직관적인 집합 이론과 같은 약한 시스템에서 논리적으로 불평등하게 나타난다.두 가지 정의는 문헌에서 두드러지게 나타나는데, 하나는 리처드 데데킨트, 다른 하나는 카지미에르츠 쿠라토스키에 의한 것이다. (쿠라토스키의 정의는 위에서 사용된 정의이다.)

집합 S를 데데킨트 무한(Dedekind infinite)이라고 하는데, 이는 주입식 $비사사{\displaystyle }$ ${\displaystyle \mathrm{함수}}$f: ${\displaystyle S}$ $→$ S(\$displaystyle$ f$:$$S\right$ 화살표 S$.$ $이러한$ 함수는 S와 S의 적절한 부분 집합, 즉 f의 이미지 사이에 분사를 나타낸다.Dedekind 무한 집합 S, 함수 f 및 f의 이미지에 없는 요소 x가 주어지면, $우리$는 x${\displaystyle ,}$ ${\displaystyle f(x),f(x),}$ f$($x${\displaystyle ),}$ ${\displaystyle ...,}$ .\$displaystyle x,$ f($x),$ ...\$displaystyle$ x, f$(x),$ $...\}$의 개별 $요소{\displaystyle {}_{}}$x ${\displaystyle {}_{}}$로 이루어진 시퀀스를 형성할 수 있다.$${\$displaystyle x_{1$},$x_{2},x_{3$ $시퀀스{\displaystyle }$f(${\displaystyle {xi}_{}}$ ${\displaystyle =}$ ${\displaystyle {xi}_{}}$ ${\displaystyle {+}_{}}$ $(\$ f$(x_{i})$의 요소에 대해 함수 f를 정의할 수 있습니다$.$=$x_{i+$1$$}} 및 f는 그렇지 않으면 ID 함수처럼 작동합니다$.$따라서 Dedekind 무한 집합에는 자연수와 생물적으로 일치하는 부분 집합이 포함됩니다.Dedekind 유한한 것은 당연히 모든 주입형 자기 맵이 또한 주관적이라는 것을 의미합니다.

쿠라토프스키 미세도는 다음과 같이 정의된다.임의의 집합 S가 주어졌을 때, 합집합 2진수 연산은 멱집합 P(S)를 반격자 구조로 한다.빈 집합과 싱글톤에 의해 생성된 서브 반격자에 대해 K(S)를 쓰고, S가 K(S)^[8]에 속하는 경우, 콜 집합 S Kuratowski는 유한하다.직관적으로, K(S)는 S의 유한 부분 집합으로 구성되어 있다. 결정적으로, 빈 집합과 단일톤을 포함하는 모든 반격자의 교집합을 취함으로써 K(S)를 얻을 수 있기 때문에 생성되는 자연수의 정의를 정의할 필요가 없다.

반문제와 추상대수의 다른 개념에 익숙하지 않은 독자들은 완전히 기초적인 공식을 선호할 수 있다.쿠라토프스키 유한평균 S는 다음과 같이 구성된 집합 K(S)에 존재한다.P(S)의 모든 서브셋 X의 세트에 대해 다음과 같이 M을 쓴다.

• X에는 빈 세트가 포함됩니다.
• P(S)의 모든 집합 T에 대해 X가 T를 포함하면 X는 T와 싱글톤의 결합도 포함합니다.

그러면 K(S)는 M의 교집합으로 정의할 수 있다.

ZF에서 Kuratowski 유한은 Dedekind 유한함을 의미하지만 그 반대는 아니다.인기 있는 교육학적 공식의 용어로 표현하면, 선택의 공리가 잘못되면, 한 쌍의 양말을 선택할 방법이 없는 무한한 양말 가족을 가질 수 있다.그것은 그러한 양말 세트를 유한하게 만들 것이다: 그러한 양말의 무한한 시퀀스는 있을 수 없다. 왜냐하면 그러한 시퀀스는 시퀀스의 첫 번째 양말을 선택함으로써 무한히 많은 쌍에 대해 하나의 양말을 선택할 수 있기 때문이다.그러나 쿠라토프스키의 세트는 같은 양말 세트에 실패한다.

기타 미세성의 개념

선택 공리가 없는 ZF 집합론에서, 집합 S에 대한 다음과 같은 미세도 개념은 구별된다.이들은 엄격히 강도의 감소 순서로 배열된다. 즉, 세트 S가 목록의 기준을 충족하면 다음과 같은 기준을 모두 충족한다.선택의 원리의 부족하여, 반대 의미를 모든지만, 만약 선택의 원리 가정한다 그 다음에 모든 이 개념들의 능력과 동일한 것이 실증할 수 없는 있다.[9]( 이러한 정의 중 누구도 한정된 순서 번호 첫번째 정의될의 집단이 필요합니다;평등 및 회원 레의 관점에서 그들은 모두 순수한"set-theoretic"정의습니다.lations, )는 포함되지 않습니다.)

• I-finite.S의 서브셋이 비어 있지 않은 모든 집합은 θ-최대 요소를 가진다.(이것은 θ-최소 요소의 존재에 상당한다.)이는 또한 최종성의 표준 수치 개념과도 동일합니다.)
• Ia-finite.S를 두 집합으로 분할할 때마다 두 집합 중 적어도 하나는 I-유한이다.
• II-finite.S의 서브셋이 비어 있지 않은 모든 γ-모노톤 세트는 γ-최대 요소를 가진다.
• III-한정멱집합 P(S)는 Dedekind 유한이다.
• 링거 유한S는 Dedekind 유한이다.
• V-finite.'S' = 0 또는2 'S' > 'S'
• VI-finite.'S' = 0 또는 'S' = 1 또는 'S'² > 'S'
• VII-무한S는 I-finite이거나 순서가 적절하지 않습니다.

앞으로 (강력에서 약함)의 의미는 ZF 내의 정리이다.요소와 함께 ZF에서 (약함에서 강함) 역의 의미에 대한 반례는 모델 ^[10]이론을 사용하여 찾을 수 있다.

이러한 미세성 정의와 그 이름은 Howard & Rubin 1998, 페이지 278에 의해 Tarski 1954에 기인한다.그러나 정의 I, II, III, IV 및 V는 전방 함의에 대한 증거(또는 증거에 대한 참조)와 함께 Tarski 1924, 페이지 49, 93에 제시되었다.당시 모델 이론은 반례를 찾을 만큼 충분히 발전하지 못했다.

각각의 특성 I-유한 스루 IV-유한은 그러한 성질을 가진 집합의 모든 부분집합이 그 성질을 가질 것이라는 점에서 작은 것의 개념이다.V-무한 ~ VII-무한 부분 집합은 셀 수 있을 만큼 무한할 수 있기 때문에 이는 사실이 아니다.

「 」를 참조해 주세요.

• 핀셋
• 서수
• 페아노 산술

메모들

레퍼런스

• Apostol, Tom M. (1974), Mathematical Analysis (2nd ed.), Menlo Park: Addison-Wesley, LCCN 72011473
• Cohn, Paul Moritz, F.R.S. (1981), Universal Algebra, Dordrecht: D. Reidel, ISBN 90-277-1254-9, LCCN 80-29568
• Dedekind, Richard (2012), Was sind und was sollen die Zahlen?, Cambridge Library Collection (Paperback ed.), Cambridge, UK: Cambridge University Press, ISBN 978-1-108-05038-8
• Dedekind, Richard (1963), Essays on the Theory of Numbers, Dover Books on Mathematics, Beman, Wooster Woodruff (Paperback ed.), Dover Publications Inc., ISBN 0-486-21010-3
• Herrlich, Horst (2006), Axiom of Choice, Lecture Notes in Math. 1876, Berlin: Springer-Verlag, ISBN 3-540-30989-6
• Howard, Paul; Rubin, Jean E. (1998). Consequences of the axiom of choice. Providence, Rhode Island: American Mathematical Society. ISBN 9780821809778.
• Kuratowski, Kazimierz (1920), "Sur la notion d'ensemble fini" (PDF), Fundamenta Mathematicae, 1: 129–131, doi:10.4064/fm-1-1-129-131
• Labarre, Jr., Anthony E. (1968), Intermediate Mathematical Analysis, New York: Holt, Rinehart and Winston, LCCN 68019130
• Lévy, Azriel (1958). "The independence of various definitions of finiteness" (PDF). Fundamenta Mathematicae. 46: 1–13. doi:10.4064/fm-46-1-1-13.
• Rudin, Walter (1976), Principles Of Mathematical Analysis (3rd ed.), New York: McGraw-Hill, ISBN 0-07-054235-X
• Suppes, Patrick (1972) [1960], Axiomatic Set Theory, Dover Books on Mathematics (Paperback ed.), Dover Publications Inc., ISBN 0-486-61630-4
• Tarski, Alfred (1924). "Sur les ensembles finis" (PDF). Fundamenta Mathematicae. 6: 45–95. doi:10.4064/fm-6-1-45-95.
• Tarski, Alfred (1954). "Theorems on the existence of successors of cardinals, and the axiom of choice". Nederl. Akad. Wetensch. Proc. Ser. A., Indagationes Math. 16: 26–32. doi:10.1016/S1385-7258(54)50005-3. MR 0060555.
• Whitehead, Alfred North; Russell, Bertrand (February 2009) [1912]. Principia Mathematica. Vol. Two. Merchant Books. ISBN 978-1-60386-183-0.

외부 링크

• Barile, Margherita. "Finite Set". MathWorld.