Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The axiom of choice states that arbitrary products of nonempty sets are nonempty. Clearly, we only need the axiom of choice to show the non-emptiness of the product if there are infinitely many choice functions. If we use a choice function to construct a mathematical object, the object will often depend on the specific choice function being used. So constructions that require the axiom of choice often do not provide the existence of a unique object with certain properties. In some cases they do, however. The existence of a cardinal number for every set (ordinal that can be mapped bijectively onto the set) is such an example.

What are natural examples outside of set theory where the existence of a unique mathematical object with certain properties can only be proven with the axiom of choice and where the uniqueness itself can be proven in ZFC (I don't want the uniqueness to depend on a specific model of ZFC)?

The next question is a bit more vague, but I would be interested in some kind of birds-eye view on the issue.

Are there some general guidelines to understand in which cases the axiom of choice can be used to construct a provably unique object with certain properties?

This question is motivated by a discussion of uniqueness-properties of certain measure theoretic constructions in mathematical economics that make heavy use of non-standard analysis.

Edit: Examples so far can be classified in three categories:

Cardinal Invariants: One uses the axiom of choice to construct a representation by some ordinal. Since ordinals are canonically well ordered, this gives us a unique, definable object with the wanted properties. Example: One takes the dimension (as a cardianl) of a vector space and constructs the vector space as functions on finite subsets of the cardinal (François G. Dorais).

AC Properties: One constructs the object canonically "by hand" and then uses the axiom of choice to show that it has a certain property. Trivial example: $2^\mathbb{R}$ as the family of well-orderable sets of reals.

Employing all choice functions: Here one gets uniqueness by requiring the object to contain in some sense all objects of a certain kind that can be obtained by AC. Examples: The Stone-Čech compactification as the set of all ultrafilters on it (Juris Steprans), or the dual space of a vector space, the space of all linear functionals. (Martin Brandenburg) The AC is used to show that these spaces are rich enough. Formally, these examples might be categorized in the second category, but they seem to have a different flavor.

share|improve this question
7  
If there are infinitely many choice functions, we already know that the product is nonempty (and infinite). We only need the axiom of choice to show the nonemptiness of the product if it is conceivable that there are no choice functions. –  Emil Jeřábek Nov 16 '11 at 15:59
1  
Maybe what I wrote was not clear enough. The only cases in which we need the axiom of choice are the ones where the axiom of choice automatically provides the existence of not one, but infinitely many choice functions. –  Michael Greinecker Nov 16 '11 at 16:21
3  
ZF alone proves that there is a vector space over $\mathbb{Q}$ of size continuum. But you need AC to prove that there is a unique such thing (up to isomorphism). –  Ramiro de la Vega Nov 16 '11 at 20:42
2  
Looking at your comments below, I don't see how the cardinality example satisfies your criteria for uniqueness since you don't seem to allow uniqueness up to isomorphism. The cardinality of a set is unique, but the bijection between the set and its cardinality is far from unique and the cardinality by itself, without the bijection, is rather useless... –  François G. Dorais Nov 16 '11 at 21:12
5  
So what you want has not much to do with choice. Just use ordinals to build canonical anything. For the canonical real vector space with dimension $\kappa$, take all finitely supported functions $v:\kappa\to\mathbb{R}$; every real vector space is isomorphic to just one of those. Same for algebraically closed fields of characteristic 0, ranked by transcendence degree; free abelian groups by rank; etc. –  François G. Dorais Nov 16 '11 at 23:33

6 Answers 6

This came up yesterday in my Real Analysis course. I´m not sure if it is the sort of thing you are looking for and I´m also not sure if the use of $AC$ is essential, but...

Suppose $X$ is a complete metric space and $\{E_n:n\in \omega\}$ is a nested sequence of non-empty closed subsets of $X$ such that $\lim_{n \to \infty} diam (E_n)=0$. Then there is a point $p$ that belongs to every $E_n$.

The only proof I know of this uses countable choice to get a sequence $\{ x_n\}$ with $x_n \in E_n$; then this sequence is a Cauchy sequence, etc.

But then the object whose existence you are trying to prove (i.e. $p$) is unique, by the condition on the diameters.

share|improve this answer
4  
What's really going on here is that you need countable choice to show that the naïve definition of a complete metric space (one in which every Cauchy sequence converges) implies to the definition as a complete uniform or Cauchy space (one in which every Cauchy net or Cauchy filter converges). If a space meets the latter definition, then we may construct p (uniquely) without any choice. –  Toby Bartels Mar 15 '12 at 4:56
    
@Toby: That´s interesting, thanks! –  Ramiro de la Vega Mar 15 '12 at 11:53

If you are satisified with your example of the cardinals as unique objects defined using choice then there is an easy answer to your question. Note that there is not a unique ordinal which is in bijective correspondence with each set; there are many, but there is always a least one which we call a cardinal. So the uniqueness comes from the well ordering of the ordinals. Given the axiom of choice you can always well order the domain of objects in which you are interested and then choose the least one. This will of course, be unique, but I doubt this is what you had in mind. But I think it does show that a better example than the cardinals is needed for uniqueness.

One can construct saturated models by transfinite induction and then show that, under certain circumstances, these are unique. One also has $\beta \mathbb{N}\setminus \mathbb{N}$ which needs choice to be non-empty, and it is also unique --- but probably also not what you had in mind.

share|improve this answer
1  
The first example doesn't give you really uniqueness, since there are many well-orderings you could choose. In the example with the cardnials, you use the well-ordering of the ordinals and that is canonical. The Stone–Čech compactification is actually a good example of what I'm interested. There the uniqueness comes from having a space that contains "everything constructable" by the axiom of choice. –  Michael Greinecker Nov 16 '11 at 19:42
2  
If you assume a bit of extra set theory (V=L for example, but much less will work too) there are canonical well ordering of the universe that will give the same uniqueness as for the cardinals. –  Juris Steprans Nov 16 '11 at 21:15

I use the following - hopefully correct - interpretation of the question: We look for examples where AC enables us to construct an object, but AC also proves that this object is unique (up to unique isomorphism if this object is structured).

What about the dimension function $\dim$ which associates to every vector space over $k$ a cardinal number? It is uniquely determined by $\dim(k)=1$ and $\dim(\oplus_i V_i) = \sum_i \dim(V_i)$. Remark that the notion of a cardinal number also makes sense in absence of AC; as well as their sum and therefore this function $\dim$. But existence and uniqueness require AC.

Similarily, the transcendence degree $\mathrm{tr.deg}_k$ associates to every field extension of $k$ a cardinal number. If we vary $k$, these are characterized by (1) $\mathrm{tr.deg}_k(k[t])=1$, (2) $\mathrm{tr.deg}_k(E) = \mathrm{tr.deg}_F(E) \cdot \mathrm{tr.deg}_k(F)$ for $k \subseteq E \subseteq F$, (3) $\mathrm{tr.deg}_k(E)=0$ if $E/k$ is algebraic, (4) $\mathrm{tr.deg}_k(\mathrm{Q}(\bigotimes_i R_i)) = \sum_i \mathrm{tr.deg}_k(\mathrm{Q}(R_i))$ if $R_i/k$ are polynomial rings.

To go into a slightly different and probably more interesting direction: Often AC is needed to show that some object has a certain property, although this object can be defined and understood a priori without AC. There are tons of examples in commutative algebra and algebraic geometry, for example:

Let $k$ be an algebraically closed field, for example $\mathbb{C}$. If $X,Y$ are integral $k$-schemes, then $X \times_k Y$ is again integral. The affine case is: If $A,B$ are $k$-algebras without zero divisors, then the same is true for $A \otimes_k B$. The only proofs I know for this use AC. So in this case, AC also proves the existence of the quotient field of $A \otimes_k B$, which wouldn't make sense if $A \otimes_k B$ wasn't a integral domain.

In linear algebra, you can write down the natural map $i : V \to V^{**}$. It's image $W$ consists precisely of the functionals $V^\* \to k$ which are continuous with respect to the weak-*-topology, see here. You have to use AC to show that $i$ is injective and therefore construct the inverse map $W \to V$.

I'm not fully satisfied with these examples. I hope someone else finds more natural examples.

share|improve this answer
    
I am not 100% certain that the dimension is a good example. Mostly because infinite sums are not so well defined in the absence of choice. –  Asaf Karagila Nov 17 '11 at 16:29
    
What about a cardinal number as an index set? –  Martin Brandenburg Nov 17 '11 at 17:00
    
@Martin: Even if the index set is well ordered, the countable union of sets of cardinality 2 need not be countable. Of course this is an extreme case, but it is an example. –  Asaf Karagila Nov 17 '11 at 17:02
    
My above comment can be translated as "We can construct a vector space with an infinite basis, and we can write the vector space as a countable direct sum of subspaces of dimension 2, but the sum is not countable, thus not well defined (as it can be countable as well). –  Asaf Karagila Nov 17 '11 at 17:11

When you say "unique," how strictly do you mean it? For instance, would you be happy to see examples of algebraic objects that are shown to exist with the axiom of choice, and are unique up to isomorphism?

A possible example that comes to mind is the construction of the injective hull of a module $M$ over a ring. The argument that I know to embed a module into an injective requires Baer's criterion, which seems to require the axiom of choice. After embedding $M$ into an injective, one must then cut down to a minimal injective submodule containing $M$, and this also seems to use choice.

However, if an injective hull exists then it seems to me that it's unique up to isomorphism without requiring the axiom of choice.

(Notice, this is one case where the object is unique up to isomorphism, but not unique up to unique isomorphism. A similar example is the algebraic closure of a field $K$. I almost quoted this as an example of the phenomenon above, but I realized that the proof of the uniqueness of $\overline{K}$ in Lang's Algebra, for instance, uses choice.)

share|improve this answer
    
I think allowing for uniqueness-up-to-isomorphism might make life too easy. A basis of a vector space seems to me extremely non-canonical, yet they are all unique up to isomorphism. Up to unique-isomorphism seems to me more interesting. Well-orders would be set theoretic example of something that is unique up to isomorphism yet exists only with AC. If isomorphisms are unique, one can probably replace the objects in question by some kind of quotient-object. –  Michael Greinecker Nov 16 '11 at 20:56
    
OK, so it sounds like for you an algebraic example would probably need to be a universal construction, in the category-theoretic sense. I have a much harder time thinking of such an object that requires AC to prove existence! (They typically are unique for trivial reasons, though.) –  Manny Reyes Nov 16 '11 at 20:59
    
Michael: Well orders exist just fine without the axiom of choice. The ordinals have nothing to do with the axiom of choice to begin with, in particular the uniqueness of the order isomorphism. The axiom of choice just say that the ordinals exhaust the possible cardinalities of sets in the universe. –  Asaf Karagila Nov 16 '11 at 21:06
    
Yes, what I meant is that for every set, all well-orderings of the set are order-isomorphic under a unique order isomorphism. That there are well orderings for every set, requires AC. –  Michael Greinecker Nov 16 '11 at 21:55
1  
Michael: your statement "all well-orderings of the set are order-isomorphic under a unique order isomorphism" is true only for finite sets. –  Ramiro de la Vega Nov 17 '11 at 11:29

With respect to your second question (I understand the uniqueness requirement in your questions as "being instatiatiated by abstraction terms" ):

Suppose that $A$ is equivalent (in $ZF$) to a sentence of the form $\forall z\exists y B$, for $B$ (provably in $ZF$) absolute for transitive models of $ZF$, and that $ZFC\vdash A$.

In this case, $ZFC\vdash\forall x A^{\textbf{L}(x)}$ (where $x$ is the first variable that does not occur in $A$) if and only if (omitting the quantifier $\forall x$),

$ZFC\vdash (\forall z\exists y B)^{\textbf{L}(x)}$,

that is, if and only if

$ZFC\vdash (\forall z\in \textbf{L}(x))(\exists y\in \textbf{L}(x)) B$,

because $B$ is absolute. If this holds, then

$ZFC\vdash (x\in \textbf{L}(x))\rightarrow(\exists y\in \textbf{L}(x)) B'$

for $B'$, the formula obtained replacing the free occurrences of $z$ in $B$ by $x$. But then

$ZFC\vdash (\exists y\in \textbf{L}(x)) B'$

and, replacing back $x$ by $z$,

$ZFC\vdash (\exists y\in \textbf{L}(z)) B$.

This means that if $A$ is a theorem of $ZFC$ of the form explained above and such that $ZFC\vdash\forall x A^{\textbf{L}(x)}$, then $ZFC$ proves that given a set $z$ there exists a set $y$ in $\textbf{L}(z)$ such that $B$. Therefore, there is a composition of Godel operations applied to some elements in the transitive closure of $z$ that gives you a witness for that existence. So, even in this simple case you don't have instantiation by an abstraction term with parameter $z$, but you do have something close to it, that is a term with paramenters in the transitive closure of $z$. I think that there is no way to substantially improve this.

The so-called existence axioms of set theory are classified according to this condition of being instantiated by an abstraction term or not. The axiom of choice is the example of existence axiom that is not instantiated by an abstraction term. I think that this is an inadequate condition for classifying the axioms and these and other related questions are the subject of my paper "on existence in set theory", (to appear in notre dame journal of formal logic).

share|improve this answer
    
It seems like you explained why one cannot get unique existence in general, not what makes the cases when one can work. –  Michael Greinecker Nov 17 '11 at 13:04
    
In case you know that the sentence you want to prove is of the form described and that it is valid in $\textbf{L}(x)$ then, if you prove it in $ZFC$ you can instantiate it by a term with paramenters in the transitive closure of $z$. If the sentence is proved without the axiom of choice then it is valid in $\textbf{L}(x)$ and that hypothesis becomes superflous. In fact, one cannot expect too much: there are existential theorems from logic that are not instantiated by any abstraction term in $ZFC$. (Of course, in $ZFL$ every existential theorem is instantiated by an abstraction term). –  Rodrigo Freire Nov 17 '11 at 13:44

Ulm's Theorem comes to mind: http://en.wikipedia.org/wiki/Height_(abelian_group)#Ulm.27s_theorem

This states that any two countable abelian $p$-groups without divisible subgroups have the same Ulm invariants if and only if they are isomorphic. This can, I believe, be proved in ZFC, and relies on choice (though possibly only countable choice). This gives unique (only up to isomorphism) abelian groups and ends up classifying countable abelian torsion groups (to isomorphism).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.