사용자:CrMT/연습장/0

“	No one will drive us from the paradise which Cantor created for us.	“
— David Hilbert (1926)

선택 공리((the) Axiom of Choice, AC)는 임의의 집합족의 각 집합에서 원소를 하나씩 선택하여 모아 만든 새로운 집합을 구성할 수 있음을 주장하는 공리이다. 수학의 전 분야, 특히 집합론과 해석학에서 그 형식화에 많은 도움을 주는 공리이다. 임의의 집합의 기수의 존재성, 임의의 벡터공간의 기저의 존재성 등 여러 분야에서 쓰이는 개념을 잘 정의할 수 있게 해준다. 물론 이보다 약한 가산 선택 공리나 의존 선택 공리와 같은 것만을 이용하여 증명할 수 있는 것들도 일부 있지만, AC가 꼭 필요한 명제들도 있기에 집합론과 해석학에서는 보통 선택 공리를 인정하는 편이다. 하지만 이를 가정하는 데에 조심스러운 수학자가 많다.

직관

큰 상자 안에 작은 상자가 여러 개 있고, 그 각각의 작은 상자에 동전이 한 개 이상씩 들어 있는 상황을 생각해 보자. 각각의 상자에서 동전을 하나씩 골라 주머니 안에 넣을 수 있을까?

... 당연하다. 그냥 뽑으면 되지 않는가! 뭐라고 설명해야 할지는 모르겠지만, 뽑아보면 안다. 하지만, 이것은 작은 상자가 유한할 때에만 적용될 수 있는 논리이다. 만약 그 작은 상자가 무한 개(?) 있다면, 우리는 그 동전들을 골라 주머니에 넣을 수 있는가? (사실 현실의 상황으로 생각하는 것은 nonsense이다. 상자가 무한 개 있을 리가 없다! (?))

진술

다음 동치인 명제 중 하나를 선택 공리(AC)라고 한다:

• [math]\displaystyle{ \mathcal A }[/math]를 mutually disjoint한 공이 아닌 집합들의 족이라 하자. 그렇다면 [math]\displaystyle{ \mathcal A }[/math]의 각각의 집합으로부터 하나의 원소-씩으로 구성된 집합이 존재한다.
• [math]\displaystyle{ \mathcal A = \{A_i\}_{i\in I} }[/math]를 index를 가진 집합족이라 하자. [math]\displaystyle{ I\ne \emptyset }[/math]이면, [math]\displaystyle{ \prod_{i \in I} A_i \ne \emptyset }[/math]이다.
• [math]\displaystyle{ \mathcal A = \{A_i\}_{i\in I} }[/math]를 index를 가진 집합족이라 하자. [math]\displaystyle{ I\ne \emptyset }[/math]이면, 어떤 집합 [math]\displaystyle{ C }[/math]가 존재하여 [math]\displaystyle{ \forall i \in I [C \cap A_i \text{ is a singleton}] }[/math]이다.
• 선택함수(choice function)가 존재한다. 더욱 명시적으로, 주어진 집합 [math]\displaystyle{ A }[/math]에 대하여, 함수 [math]\displaystyle{ F:\mathcal P(A) \to A }[/math]가 존재하여 [math]\displaystyle{ \forall X \subseteq A[X\ne \emptyset \Rightarrow F(X) \in X] }[/math]이다.
• 선택함수가 존재한다. 임의의 집합족 [math]\displaystyle{ \mathcal A }[/math]에 대하여, [math]\displaystyle{ \emptyset \notin \mathcal A\implies \exists f\colon \mathcal A\rightarrow \bigcup \mathcal A\left[\forall X\in \mathcal A\,(f(X)\in X)\right] }[/math]이다.

선택 공리의 직관적/반직관적인 결과

“	The Axiom of Choice is obviously true; the Well Ordering principle is obviously false; and who can tell about Zorn’s lemma?	“
— Jerry Lloyd Bona.

AC 없이 생길 수 있는 일>>

There can be a nonempty tree T, with no leaves, but which has no infinite path. That is, every finite path in the tree can be extended one more step, but there is no path that goes forever. A real number can be in the closure of a set X\subset\mathbb{R}, but not the limit of any sequence from X. A function f:\mathbb{R}\to\mathbb{R} can be continuous in the sense that x_n\to x\Rightarrow f(x_n)\to f(x), but not in the \epsilon\ \delta sense. A set can be infinite, but have no countably infinite subset. Thus, it can be incorrect to say that \aleph_0 is the smallest infinite cardinality, since there can be infinite sets of incomparable size with \aleph_0. (see this MO answer.) There can be an equivalence relation on \mathbb{R}, such that the number of equivalence classes is strictly greater than the size of \mathbb{R}. (See François's excellent answer.) This is a consequence of AD, and thus relatively consistent with DC and countable AC. There can be a field with no algebraic closure. The rational field \mathbb{Q} can have different nonisomorphic algebraic closures (due to Läuchli, see Timothy Chow's comment below). Indeed, \mathbb{Q} can have an uncountable algebraic closure, as well as a countable one. There can be a vector space with no basis. There can be a vector space with bases of different cardinalities. The reals can be a countable union of countable sets. Consequently, the theory of Lebesgue measure can fail totally. 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.

하지만 선택공리를 가정하게 되면, 실수 [math]\displaystyle{ \mathbb R }[/math]의 르벡 비가측인 집합이 생기게

The fact that there exist non-measurable sets is highly counter-intuitive; the reason we don't find it so is that we've all been conditioned from day 1 to do measure theory very carefully, and define Borel sets, measurable sets, etc, so we all know that non-measurable sets exist because what would be the point of doing it all so carefully otherwise. At high school we were all taught that the probability of an event occurring was "do it a million times, count how often it happened, divide by a million, and now let a million tend to infinity". And no-one thought to ask "what if this process doesn't tend to a limit?". I bet if anyone asked their teacher they'd say "well it always tends to a limit, that's intuitively clear". But am I right in thinking the following: if we take a subset XX of [0,1] with inner measure 0 and outer measure 1, and we keep choosing random reals uniformly in [0,1] and asking whether they land in XX, and keep a careful table of the result, then the number of times we land in XX divided by the number of times we tried just oscillates around between 0 and 1 without converging? That is fundamentally counterintuitive and in some sense completely goes against the informal (non-rigorous) training that we all got in probability at high school. [if I've got this right!]

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일 때의 문제

Banach Tarski paradox

There are of course reasons to care about the axiom of choice because there are categories in which epimorphisms do not split. However if one sticks to the category of sets my position could be (provocatively) described as follows: The axiom of choice is obviously false but that doesn't stop me from using it.

Before I go on to explain why I think it is false let me make a general remark. Set theory is a mathematical model for mathematics it isn't mathematics itself. We all know that all models usually manage to model some part of what they model but they almost never correctly model everything. Things are a little bit more complicated in the case of set theory but it is also supposed to be the common language of mathematics. However, it really works as such only as a protocol for conflict resolution; in case we disagree over a proof we are supposed to work our way down to formal set theory where there couldn't possibly be any conflicts. However, most mathematicians would rather, I believe, voluntarily submit to extended flagellation than actually work with formal set theory. Luckily, in practice all disagreements are resolved long before one reaches that level. Furthermore, most working mathematicians show a cavalier towards set theory. It is quite common to speak of the free group on isomorphism classes of objects in some large category which is not possible in formal set theory as the the isomorphism classes are themselves proper classes and hence can not be members of some class. Of course, when pressed a mathematician using such a phrase would probably modify it by speaking of skeleta but I have once been criticised when using a slightly different formulation that avoided the problem without speaking of skeleta as being wrong for set-theoretic reasons. (This is not meant as a criticism of the person in question, a working mathematician should have the right to ignore the horny parts of set theory, at their own peril of course.)

Now, the reason why I believe that the axiom of choice is obviously false is that gives us an embedding of the field of pp-adic numbers into CC which seems fishy as they are constructed in such different ways. In fact if you try to pin down such an embedding by asking for it to fulfil more conditions then it doesn't exist. This is true if you ask that it be measurable or take definable numbers to definable numbers and so on. My own feeling is that its existence is so counter-intuitive that it couldn't possibly existst. On the other hand such an embedding is used over and over again in say the theory of ℓℓ-adic cohomology. It is true that in that case at least it can be avoided (Deligne seems to share some of my disbelief as in his second paper on the Weil conjecture he starts with a short discussion on how to avoid it but still uses it as it cuts down on uninteresting arguments).

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.

선택 공리와 동치인 유명한 명제들

누가 뭐래도, 제일 중요한 것은 Zorn's Lemma와 정렬 원리이다. 이와 함께, 다음과 같은 동치인 명제들이 알려져 있다.

• 집합론
  • 정렬 원리: 모든 집합은 정렬될(well-ordered) 수 있다.
  • 타르스키의 선택 정리: 임의의 무한집합 [math]\displaystyle{ A }[/math]에 대해서, [math]\displaystyle{ A }[/math]와 [math]\displaystyle{ A\times A }[/math] 사이에 전단사 함수가 존재한다. 즉 둘은 대등(equipotent)하고, 둘의 기수(cardinality)는 같다. 따라서 다음 명제와 AC가 동치이다: finite [math]\displaystyle{ \lambda \lt \kappa := |A| }[/math]에 대하여, [math]\displaystyle{ |A| = \kappa = \kappa^\lambda = |A|^\lambda }[/math]이다.
  • 기수의 삼분성질: 기수 사이의 순서 관계는 linear ordering이다. 즉, 임의의 두 집합 [math]\displaystyle{ A }[/math]와 [math]\displaystyle{ B }[/math]가 있으면, [math]\displaystyle{ |A| \lt |B| }[/math], [math]\displaystyle{ |A| = |B| }[/math], [math]\displaystyle{ |A| \gt |B| }[/math] 중 하나이다.
  • 공집합이 아닌 집합들의 카테시언 곱은 공집합이 아니다. (당연해 보이지만 선택 공리와 동치이다!)
  • 쾨니그 정리: 작은 것들의 합은 큰 것들의 곱보다 작다. 즉, [math]\displaystyle{ \kappa_i \lt \lambda_i }[/math]이면 [math]\displaystyle{ \sum_i \kappa_i \lt \prod_i \lambda_i }[/math]이다.
  • 모든 전사 함수는 우역원을 가진다.
• 순서론
  • 초른의 보조정리: Every non-empty partially ordered set in which every chain (i.e. totally ordered subset) has an upper bound contains at least one maximal element.
  • 하우스도르프 극대 원리: In any partially ordered set, every totally ordered subset is contained in a maximal totally ordered subset. The restricted principle "Every partially ordered set has a maximal totally ordered subset" is also equivalent to AC over ZF.
  • 투키-타이히뮐러 보조정리(Tukey-Teichmüller lemma, 또는 Tukey's lemma): Every non-empty collection of finite character has a maximal element with respect to inclusion.
  • 반사슬 원리 모든 poset(반순서집합)은 극대 반사슬을 갖는다.
• 대수학
  • 모든 벡터공간은 기저를 갖는다. (초른의 보조정리의 직접적인 응용)
  • 모든 nontrivial r[math]\displaystyle{ i }[/math]ng은 극대 이데알을 가진다.
  • 공이 아닌 집합 [math]\displaystyle{ S }[/math]에 대하여 [math]\displaystyle{ S }[/math]를 군이 되게 하는 이항연산이 존재한다.
• 함수해석

The closed unit ball of the dual of a normed vector space over the reals has an extreme point. Point-set topology Tychonoff's theorem: Every product of compact topological spaces is compact. In the product topology, the closure of a product of subsets is equal to the product of the closures. Mathematical logic If S is a set of sentences of first-order logic and B is a consistent subset of S, then B is included in a set that is maximal among consistent subsets of S. The special case where S is the set of all first-order sentences in a given signature is weaker, equivalent to the Boolean prime ideal theorem; see the section "Weaker forms" below. Graph theory Every connected graph has a spanning tree.[17]