편집을 취소할 수 있습니다. 이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
최신판 | 당신의 편집 | ||
1번째 줄: | 1번째 줄: | ||
[[분류:집합론]] | {{학술}}[[분류:집합론]] | ||
{{인용문|The Axiom of Choice is necessary to select a set from an infinite number of socks, but not an infinite number of shoes.|Bertrand Russell}} | {{인용문|The Axiom of Choice is necessary to select a set from an infinite number of socks, but not an infinite number of shoes.|Bertrand Russell}} | ||
{{인용문|The axiom gets its name not because mathematicians prefer it to other axioms.|A. K. Dewdney}} | {{인용문|The axiom gets its name not because mathematicians prefer it to other axioms.|A. K. Dewdney}} | ||
7번째 줄: | 7번째 줄: | ||
큰 상자 안에 작은 상자가 여러 개 있고, 그 각각의 작은 상자에 동전이 한 개 이상씩 들어 있는 상황을 생각해 보자. 각각의 상자에서 동전을 '''하나씩''' 골라 주머니 안에 넣을 수 있을까? | 큰 상자 안에 작은 상자가 여러 개 있고, 그 각각의 작은 상자에 동전이 한 개 이상씩 들어 있는 상황을 생각해 보자. 각각의 상자에서 동전을 '''하나씩''' 골라 주머니 안에 넣을 수 있을까? | ||
... 당연하다. 그냥 뽑으면 되지 않는가! 뭐라고 설명해야 할지는 모르겠지만, '''뽑아보면 안다.''' 하지만, 이것은 작은 상자가 ''유한''할 때에만 적용될 수 있는 논리이다. 만약 그 작은 상자가 무한 개(?) 있다면, 우리는 그 동전들을 골라 주머니에 넣을 수 있는가? (사실 현실의 상황으로 생각하는 것은 nonsense이다. 상자가 [[유한론|무한 개 있을 리가 없다!]]) | ... 당연하다. 그냥 뽑으면 되지 않는가! 뭐라고 설명해야 할지는 모르겠지만, '''뽑아보면 안다.''' 하지만, 이것은 작은 상자가 ''유한''할 때에만 적용될 수 있는 논리이다. 만약 그 작은 상자가 무한 개(?) 있다면, 우리는 그 동전들을 골라 주머니에 넣을 수 있는가? (사실 현실의 상황으로 생각하는 것은 nonsense이다. 상자가 [[유한론|무한 개 있을 리가 없다!]] (?)) | ||
==진술== | ==진술== | ||
다음 동치인 명제 중 하나를 '''선택 공리'''('''AC | 다음 동치인 명제 중 하나를 '''선택 공리'''('''AC''')라고 한다: | ||
* <math>\mathcal A</math>를 mutually disjoint한 공이 아닌 집합들의 족이라 하자. 그렇다면 <math>\mathcal A</math>의 각각의 집합으로부터 하나의 원소-씩으로 구성된 집합이 존재한다. | * <math>\mathcal A</math>를 mutually disjoint한 공이 아닌 집합들의 족이라 하자. 그렇다면 <math>\mathcal A</math>의 각각의 집합으로부터 하나의 원소-씩으로 구성된 집합이 존재한다. | ||
* <math>\mathcal A = \{A_i\}_{i\in I}</math>를 index를 가진 집합족이라 하자. <math>I\ne \emptyset</math>이면, <math>\prod_{i \in I} A_i \ne \emptyset</math>이다. | * <math>\mathcal A = \{A_i\}_{i\in I}</math>를 index를 가진 집합족이라 하자. <math>I\ne \emptyset</math>이면, <math>\prod_{i \in I} A_i \ne \emptyset</math>이다. | ||
18번째 줄: | 18번째 줄: | ||
== 선택 공리의 변형 == | == 선택 공리의 변형 == | ||
공통적으로 AC<sub>†</sub>(‡)라고 쓰면 ‡개의 원소를 가진 집합이 †개 모여 있는 집합족에서 선택할 수 있음을 뜻한다고 보면 된다. 이 목록은 <small>{{서적 인용|저자= Herrlich, Horst|제목= Axiom of Choice|출판사= Lecture Notes in Mathematics (영어) 1876. Springer|날짜= 2006|isbn= 3-540-30989-6}}</small>에 실려 있다. | |||
이 목록은 <small>{{서적 인용|저자= Herrlich, Horst|제목= Axiom of Choice|출판사= Lecture Notes in Mathematics (영어) 1876. Springer|날짜= 2006|isbn= 3-540-30989-6}}</small>에 실려 있다. | |||
* CC = AC<sub>ω</sub>: 가산 | * CC = AC<sub>ω</sub>: 가산 선택공리(Axiom of '''C'''ountable '''C'''hoice). 가산 개의 집합족에 대한 선택함수가 존재한다. | ||
* AC(fin): 유한집합들의 임의 족에 대한 선택함수가 존재한다. | * AC(fin): 유한집합들의 임의 족에 대한 선택함수가 존재한다. | ||
* AC(n): 원소 <math>n</math> 개인 집합들의 임의 족에 대한 선택함수가 존재한다. | * AC(n): 원소 <math>n</math> 개인 집합들의 임의 족에 대한 선택함수가 존재한다. | ||
* AMC: | * AMC: '''A'''xiom of '''M'''ultiple '''C'''hoice. 각 집합에서 한 개만 뽑는 거라면 몰라도, 유한 개 정도는 뽑을 수 있다. <math>\{A_i\}_{i\in I}</math>가 집합족일 때, 유한집합들의 족 <math>\{F_i\}_{i\in I}</math>이 존재하여 <math>\forall i \in I \; F_i \subseteq A_i</math> | ||
<!-- | |||
KWKW Kinna–Wagner Selection Principle | |||
{Xi}i∈I{Xi}i∈I가 원소를 적어도 두 개 이상 포함한 집합들의 족일 때 집합족 {Yi}i∈I{Yi}i∈I가 있어 YiYi는 XiXi의 진부분집합이다. | |||
CC(R)CC(R) | |||
실수들로 이뤄진 가산집합들의 족에 대한 선택공리 | |||
CC(Z)CC(Z) | |||
(Xn,≤n)n<ω(Xn,≤n)n<ω가 정수 집합과 순서동형인 순서집합들의 족일 때 그 곱 ∏nXn∏nXn은 nonempty하다. | |||
CC(fin)CC(fin) | |||
유한집합들의 가산 족에 대한 선택함수가 존재한다. | |||
CC(n)CC(n) | |||
원소 nn개인 집합들의 가산 족에 대한 선택함수가 존재한다. | |||
AMCAMC Axiom of Countable Multiple Choice | |||
{An}n<ω{An}n<ω가 가산 집합족일 때, 유한집합들의 족 {Fn}n<ω{Fn}n<ω가 있어 Fn⊂AnFn⊂An for all n<ωn<ω이다. | |||
DCDC Axiom of Dependent Choice | |||
XX가 집합이고 ≺≺이 XX 위의 관계이며 ∀x∃y:x≺y∀x∃y:x≺y이면 XX 위의 수열 (xn)n<ω(xn)n<ω가 있어 xn≺xn+1xn≺xn+1 for all n<ωn<ω이다. | |||
PCC Axiom of Partial Countable Choice | |||
(Xn)n<ω(Xn)n<ω가 공집합이 아닌 집합들의 족일 때 무한집합 M⊂ωM⊂ω가 있어 ∏m∈MXm≠∅이다. (CC와 동치이다.) | |||
FinFin | |||
임의의 무한집합은 데데킨트-무한이다. | |||
Fin(R)Fin(R) | |||
실수 집합의 임의의 무한 부분집합은 데데킨트 무한이다. | |||
Fin(lin)Fin(lin) | |||
임의의 무한 linearly ordered set은 데데킨트 무한이다. | |||
PITPIT Boolean prime ideal theorem | |||
UFTUFT Ultrafilter Theorem | |||
임의의 무한집합 위의 임의의 filter는 ultrafilter로 확장될 수 있다. | |||
UFT(N)UFT(N) | |||
자연수 집합 위의 임의의 filter는 ultrafilter로 확장될 수 있다. | |||
WUFWUF Weak ultrafilter principle | |||
임의의 무한집합은 free ultrafilter를 갖는다. | |||
WUF(N)WUF(N) | |||
자연수 집합은 free ultrafilter를 갖는다. | |||
WUF(?)WUF(?) | |||
free ultrafilter를 갖는 집합이 존재한다. | |||
OPOP Ordering principle | |||
임의의 집합은 선형 순서를 가질 수 있다. | |||
OEPOEP Ordering Extension principle | |||
임의의 partial order는 linear order로 확장될 수 있다. | |||
AH(α)AH(α) Aleph Hypothesis | |||
ℵα+1=2ℵαℵα+1=2ℵα | |||
CUTCUT Countable Union Theorem | |||
기껏가산 집합의 기껏가산 합집합도 기껏가산이다. | |||
--> | |||
==선택 공리의 직관적/반직관적인 결과== | ==선택 공리의 직관적/반직관적인 결과== | ||
76번째 줄: | 118번째 줄: | ||
The first uncountable ordinal \omega_1 can be singular. | The first uncountable ordinal \omega_1 can be singular. | ||
More generally, it can be that every uncountable \aleph_\alpha is singular. Hence, there are no infinite regular uncountable well-ordered cardinals. | More generally, it can be that every uncountable \aleph_\alpha is singular. Hence, there are no infinite regular uncountable well-ordered cardinals. | ||
하지만 선택공리를 가정하게 되면, 실수 <math>\mathbb R</math>의 르벡 비가측인 집합이 생기게 | 하지만 선택공리를 가정하게 되면, 실수 <math>\mathbb R</math>의 르벡 비가측인 집합이 생기게 | ||
83번째 줄: | 126번째 줄: | ||
There can be graphs all of whose cycles have even length and whose chromatic number is greater than two. In fact, let GG be the graph whose vertices are the real numbers, with xx and yy adjacent if |x−y|=2–√+r|x−y|=2+r, where rr is rational. Then GG has only even length cycles. Assuming that every subset of RR is measurable (which is consistent with ZF), then the chromatic number of GG is uncountable. This is a result of Shelah and Soifer. If we assume the Axiom of Choice, then the chromatic number of GG is two. | There can be graphs all of whose cycles have even length and whose chromatic number is greater than two. In fact, let GG be the graph whose vertices are the real numbers, with xx and yy adjacent if |x−y|=2–√+r|x−y|=2+r, where rr is rational. Then GG has only even length cycles. Assuming that every subset of RR is measurable (which is consistent with ZF), then the chromatic number of GG is uncountable. This is a result of Shelah and Soifer. If we assume the Axiom of Choice, then the chromatic number of GG is two. | ||
-----------이하 AC일 때의 문제 | -----------이하 AC일 때의 문제 | ||
98번째 줄: | 143번째 줄: | ||
My feeling about the axiom of choice is pragmatic; it is useful and doesn't seem to get us in trouble so I have no qualms using it (even though I don't believe in it fully). I have also a picture of sets which could be used to justify this contradictory (I am not trying to formalise it so it should not be considered a competing model of mathematics). To me all elements of a set are not on equal footing. Taking my cue from algebraic geometry, there are closed points which are "real" elements but also non-closed points. Hence, the set of embeddings of the pp-adic numbers in CC is under the axiom of choice a non-empty set but in my opinion it does not contain any closed points. (In fact all its elements are probably generic, i.e., their closure is the whole set.) As long as you only deal with "concrete" objects (which should be closed in any set in which they are contained but maybe should be something more) the conclusions about them that are obtained by using the axiom of choice should be OK. | My feeling about the axiom of choice is pragmatic; it is useful and doesn't seem to get us in trouble so I have no qualms using it (even though I don't believe in it fully). I have also a picture of sets which could be used to justify this contradictory (I am not trying to formalise it so it should not be considered a competing model of mathematics). To me all elements of a set are not on equal footing. Taking my cue from algebraic geometry, there are closed points which are "real" elements but also non-closed points. Hence, the set of embeddings of the pp-adic numbers in CC is under the axiom of choice a non-empty set but in my opinion it does not contain any closed points. (In fact all its elements are probably generic, i.e., their closure is the whole set.) As long as you only deal with "concrete" objects (which should be closed in any set in which they are contained but maybe should be something more) the conclusions about them that are obtained by using the axiom of choice should be OK. | ||
The Axiom of Determinacy (AD) fails. | The Axiom of Determinacy (AD) fails. | ||
108번째 줄: | 156번째 줄: | ||
There are apparently many set theorists that agree with this assessment, since they try to rescue AD as relativized to L(R). That the relative consistency strength of this statement is equivalent to that of large cardinals is considered good evidence that those large cardinals are, in fact, consistent. More precisely, ZF + AD is consistent iff ZFC + "there are infinitely many Woodin cardinals" is consistent, and ADL(R) is outright provable in ZFC + "there is a measurable cardinal which is greater than infinitely many Woodin cardinals". | There are apparently many set theorists that agree with this assessment, since they try to rescue AD as relativized to L(R). That the relative consistency strength of this statement is equivalent to that of large cardinals is considered good evidence that those large cardinals are, in fact, consistent. More precisely, ZF + AD is consistent iff ZFC + "there are infinitely many Woodin cardinals" is consistent, and ADL(R) is outright provable in ZFC + "there is a measurable cardinal which is greater than infinitely many Woodin cardinals". | ||
공사중 | 공사중 | ||
118번째 줄: | 168번째 줄: | ||
* [[집합론]] | * [[집합론]] | ||
**[[정렬 원리]]: 모든 집합은 정렬될(well-ordered) 수 있다. | **[[정렬 원리]]: 모든 집합은 정렬될(well-ordered) 수 있다. | ||
**[[타르스키의 선택 정리]]: 임의의 무한집합 <math>A</math>에 대해서, <math>A</math>와 <math>A\times A</math> 사이에 [[전단사]] 함수가 존재한다. 즉 둘은 대등(equipotent)하고, 둘의 [[기수]](cardinality)는 같다. 따라서 다음 명제와 AC가 동치이다: finite <math>\lambda < \kappa := |A|</math>에 대하여, <math>|A| = \kappa = \kappa^\lambda = |A|^\lambda</math>이다. | **[[타르스키의 선택 정리]]: 임의의 무한집합 <math>A</math>에 대해서, <math>A</math>와 <math>A\times A</math> 사이에 [[전단사]] 함수가 존재한다. 즉 둘은 대등(equipotent)하고, 둘의 [[기수]](cardinality)는 같다. 따라서 다음 명제와 AC가 동치이다: finite <math>\lambda < \kappa := |A|</math>에 대하여, <math>|A| = \kappa = \kappa^\lambda = |A|^\lambda</math>이다. | ||
**[[기수]]의 [[삼분성질]]: 기수 사이의 순서 관계는 linear ordering이다. 즉, 임의의 두 집합 <math>A</math>와 <math>B</math>가 있으면, <math>|A| < |B|</math>, <math>|A| = |B|</math>, <math>|A| >|B|</math> 중 하나이다. | **[[기수]]의 [[삼분성질]]: 기수 사이의 순서 관계는 linear ordering이다. 즉, 임의의 두 집합 <math>A</math>와 <math>B</math>가 있으면, <math>|A| < |B|</math>, <math>|A| = |B|</math>, <math>|A| >|B|</math> 중 하나이다. | ||
** 공집합이 아닌 집합들의 카테시언 곱은 공집합이 아니다. (당연해 보이지만 선택 공리와 동치이다!) | |||
** [[쾨니그 정리 (집합론)|쾨니그 정리]]: 작은 것들의 합은 큰 것들의 곱보다 작다. 즉, <math>\kappa_i < \lambda_i</math>이면 <math>\sum_i \kappa_i < \prod_i \lambda_i</math>이다. | ** [[쾨니그 정리 (집합론)|쾨니그 정리]]: 작은 것들의 합은 큰 것들의 곱보다 작다. 즉, <math>\kappa_i < \lambda_i</math>이면 <math>\sum_i \kappa_i < \prod_i \lambda_i</math>이다. | ||
** 모든 전사 함수는 우역원을 가진다. | ** 모든 전사 함수는 우역원을 가진다. | ||
126번째 줄: | 177번째 줄: | ||
**[[초른의 보조정리]]: 모든 사슬(전순서인 부분집합)이 상한을 가지는 poset(반순서집합)은 극대원을 갖는다. | **[[초른의 보조정리]]: 모든 사슬(전순서인 부분집합)이 상한을 가지는 poset(반순서집합)은 극대원을 갖는다. | ||
**[[하우스도르프 극대 원리]]: 모든 poset에 대하여, 극대의 전순서 부분집합이 존재하여 모든 전순서 부분집합이 극대 전순서 부분집합에 포함된다. 극대 전순서 부분집합의 존재성만을 진술한 것은 ZF 위에서 AC와 동치이다. | **[[하우스도르프 극대 원리]]: 모든 poset에 대하여, 극대의 전순서 부분집합이 존재하여 모든 전순서 부분집합이 극대 전순서 부분집합에 포함된다. 극대 전순서 부분집합의 존재성만을 진술한 것은 ZF 위에서 AC와 동치이다. | ||
**[[투키-타이히뮐러 보조정리]](Tukey-Teichmüller lemma, 또는 Tukey's lemma): | **[[투키-타이히뮐러 보조정리]](Tukey-Teichmüller lemma, 또는 Tukey's lemma): <!--Every non-empty collection of finite character has a maximal element with respect to inclusion.--> | ||
**[[반사슬 원리]]: 모든 poset은 극대 반사슬을 갖는다. | **[[반사슬 원리]]: 모든 poset은 극대 반사슬을 갖는다. | ||
*[[대수학]] | *[[대수학]] |