Objects which can't be defined without making choices but which end up independent of the choice

It happens a lot of times that when one defines a new object (ring, module, space, group, algebra, morphism, whatever) out of given data one first chooses some additional structure. And sometimes (often?) the constructed object a posteriori happens to be independent of the choice.

Examples which come to mind are the following:
1. The trace of an endomorphism, defined by choosing a basis
2. Derived functors like $Ext$, $Tor$, defined by choosing projective/injective resolutions

Now I have the feeling, that "natural" objects that are not dependent on choices should exist independently of that choices. So they should still exist in an universe where there's no way to choose and so I would expect that existence to be provable there. So I would expect there to be some way to avoid choosing anything in the first place in order to define such objects.
For instance, one can define the trace as the composite map: $End_k(V)\cong V^*\otimes V \to k$ where $V^ *\otimes V\to k$ is evaluation and $V^ *\otimes V \to End_k(V)$ is given by $f\otimes v\mapsto (w\mapsto f(w)v)$.

So my questions are the following:

1. Do you know examples of things which are natural in some sense but which can't be defined without choosing something first?
2. Are $Ext$, $Tor$, etc. examples? i.e. is there a way to define derived functors without choosing resolutions?
3. If such things to exist, is there some way to make the statement precise that they can't be defined without choosing anything? Can such results be proven?
4. Assuming again something like this exists. Where exactly does the above informal "philosophical" argument fail? What is the deeper reason for the existence (or nonexistence) of such objects?

-
1.) The dimension of a vector space is natural in some sense but can't be uniquely defined without a choice (depending of what this means, of course). –  Dietrich Burde May 20 '13 at 18:38
really? can't one just say $dim_k(V)$ is the smallest integer $n$ such that the set {$(v_1,\ldots,v_n)\in V^n\mid \langle v_1,\ldots, v_n\rangle=V$} is nonempty? –  Toink May 20 '13 at 18:44
The smallest cardinal, really. (Assuming AC, of course. Otherwise there may not be such a cardinal.) –  Goldstern May 20 '13 at 20:22
This should probably be Community Wiki. –  Dan Petersen May 21 '13 at 3:08
@Sam Hopkins: Torsion part of the cokernel of the signed adjacency matrix. Admittedly, proving this is isomorphic to other definitions isn't trivial, but it's true and doesn't use a sink. –  David Speyer May 21 '13 at 15:33

I think that the fundamental group of a path-connected space is an archetype of the phenomenon which you are describing. Its construction and definition requires a choice of basepoint ("Give me a place to stand, and I will move the world", as Archemedes said, quoted by Pappus), but it is independent of that choice up to automorphism (and it's only ever considered up to automorphism).

The "choiceless" object is the fundamental groupoid, but because groupoids are more complicated less familiar algebraic objects than groups, fundamental groups are much more commonly used... and they can't be defined without an arbitrary choice which they are independent of. We just need "a place to stand", that's all!

Philosophically, I think that the reason that we see examples of this phenomenon so often in topology (choice of basepoint, triangulation, smooth structure, lift, cell decomposition, Morse function, etc. where everything is independent of these choices) is that, by definition, manifolds (and, in a weaker sense, other commonly-studied classes of spaces such as CW complexes) "look the same" around any point. So in order to "nail down" a mathematical statement, sometimes we need to "stand somewhere", "introduce coordinates", "fix an arbitrary construction of the space"... and then we can translate our problem to a tractable and/or familiar algebraic category such as "groups", "modules", "symmetric monoidal something", or whatever. These "translations" are the subject of algebraic topology.

-
The fundamental group can be recovered from the category of covering spaces; it's the unique group $G$ such that the category of covering spaces is equivalent to $G\text{-Set}$. In that sense it doesn't depend on a choice of basepoint. –  Qiaochu Yuan May 21 '13 at 4:05
Can the fundamental group (not groupoid) be a functor from unbased, path-connected spaces to groups? If not it seems to me that the fundamental group must be viewed to depend on the basepoint. This is in contrast to the case of homology which as the example of singular homology shows is manifestly functorial. –  Jeremy Hahn May 21 '13 at 4:46
@Daniel: 'but because groupoids are more complicated algebraic objects than groups' They are no more complicated algebraically, since their algebraic theory is the theory of groups but with a certain graph theoretic side to it. Many group theoretic theorems are much easier to prove using groupoids as covering groupoids are so neat to use. @Jeremy: perhaps that suggests that the fundamental group is less fundamental than the fundamental groupoid! Compare Grothendieck's SGA definition of $\pi_1$. Groups are just better known and so are more convenient a lot of the time –  Tim Porter May 21 '13 at 5:50
@Qiaochu, Don't you need a choice of basepoint for the fibre functor? And then, the group is up to automorphism independent of this choice of fibre functor. –  jmc May 21 '13 at 7:04
The fundamental group DOES depend on the base point. If you choose a different point, you get an isomorphic group, but there is no good choice of an isomorphism if the groups are nonabelian. The groups are different objects. Ignoring this distinction leads to error and confusion. –  anon May 21 '13 at 16:10

The simple groups appearing in a composition series of a finite group are independent of the choice of composition series by the Jordan–Hölder theorem, but I'm not aware of a way to define these groups that doesn't involve a choice of composition series.

-
"Simple subquotients"? ... tolerating vagueness? Dunno. –  paul garrett May 20 '13 at 22:11
@paul garrett: it doesn't seem like you can naturally describe the multiplicities of the groups which occur in such a way. –  Dan Petersen May 21 '13 at 3:08
@paul garret: Is there a definition of subquotient according to which a subgroup is not a subquotient? Because $mathbb{Z}/p$ is a simple subgroup of $S_p$ but you don't want it to be a Jordan-Holder quotient for $p \geq 5$. –  David Speyer May 21 '13 at 15:35
@paulgarrett It's not that simple. Running through the construction of a composition series in my head, the best precise statement I can come up with is "if simple, then the whole group; else, a composition factor of a normal subgroup or a quotient". The problem is that normality is not transitive. This also obstructs the otherwise appealing definition "a normal simple subgroup or a composition factor of the quotient by the normal subgroup (the socle) generated by all normal simple subgroups". –  Ryan Reich May 21 '13 at 18:37
Here's one possibility: consider the Grothendieck group of the category of finite groups, where $[A] = [B] + [C]$ whenever there is a short exact sequence $0 \to B \to A \to C \to 0$. Then the Grothendieck group should be free abelian on the finite simple groups, and the image of a finite group in the Grothendieck group should be precisely the simple groups in a composition series, with appropriate multiplicities. –  Qiaochu Yuan May 21 '13 at 20:40

I think your question can be unasked (in the sense of Gödel-Escher-Bach): The answer depends on what you consider to be a definition - you can define a mathematical object by its properties ~ or give an explicit description.

As an example consider the real numbers. An explicit description would be to take the rationals and show the Dedekind cuts to be a field. Then call it $\mathbb{R}$ and continue to investigate it using the explicit description.

On the other side you can prove the following theorem:

There is an ordered field $\mathbb R$ such that every subset with a lower bound has an infimum. Every other ordered field $\mathbb R'$ with this property is uniquely isomorphic to $\mathbb R$.

Now the theorem consists of two parts: First a description of the desired properties (ordered, infima) and the uniqueness and second a statement about the existence. In order to show the existence one has to give an explicit description of an object with the desired properties. In our example take the Dedekind cuts.

For the uniqueness part one should be able to work without an explicit description, using only the properties. In our case the argument goes as follows: ordered fields have characteristic 0 so we can embed $\mathbb Q$ into both $\mathbb R$ and $\mathbb R'$. Now use the existence of infima of subsets with a lower bound to construct the mapping. There is no need to refer to the Dedekind cuts in this part of the proof.

Back to your question: The crucial distinction is between description and implementation. For example there are several algorithms to sort a list: They are all implemenations of the same function - "same" in the sense of extensionality. Likewise there are different ways to build the real numbers - yet they all result in the same object; "same" in the sense specified above.

If one constructs an object explicitely making some choices and later on shows that it is "independent" of these choices one has to say what "independent" means in this context. This can only be done by listing properties of the object that characterise it up to some notion of equivalence.

I personally prefer definitions via descriptions: For me $\mathrm{Ext}$ "is" the derived $\mathrm{Hom}$-functor.

PS: I guess the uniqueness of an object up to [some notion of equivalence] can be seen as some sort of extensional equality (in the sense of the yoneda lemma?). I guess Homotopy Type Theory deals with this question but I don't know enough about it to say more in this direction.

-
Yes, a "characterization", rather than "proof of existence by construction" (making the construction the "definition") is very often more useful, in any case. If not a "category-theoretic", at least a bit "post-set-theoretic", perhaps. –  paul garrett May 20 '13 at 22:12
"This can only be done by listing properties of the object that characterise it up to some notion of equivalence." <-- I realised this to be not true - example: The fundamental group. Then again; in all the cases I can think of there is also a description via universal properties. Maybe this can be turned into an actual theorem? –  Garlef Wegart May 21 '13 at 18:51

You can define $\mathrm{Ext}^n$ as the set of isomorphism classes of $n$-step extensions, equipped with the Baer sum. This eliminates choices from the definition of $\mathrm{Ext}$ in exactly the same spirit as your original post eliminates choices from the definition of the trace.

-
Nice. Is there a construction of this sort for $Tor$? –  Toink May 20 '13 at 22:42
Toink: I'm pretty sure there's not. –  Steven Landsburg May 20 '13 at 22:44
It seems like now you need to argue that the collection of isomorphism classes of n-step extensions actually forms a set, though. –  zeb May 21 '13 at 2:45
@zeb Does it count as making choices if you do so by constructing $\operatorname{Ext}^n$ the usual way and showing it's isomorphic to Steven's definition? After all, it's not the definition that contains the choices, but simply a proof that the definition has a certain property. –  Ryan Reich May 21 '13 at 18:42
Tor using torsion products as described in Mac Lane's book "Homology" does not use resolutions at all, and does not make choices. It's just a bit impractical to work with it. –  Jason Polak Jun 5 '13 at 13:56

I think homology theory is a good example of this phenomenon. Namely, to construct the simplicial homology groups it is necessary to first choose a triangulation of the space. In the end, it turns out that the groups are independent of the choice of triangulation, but this is not obvious from first principles.

A posteriori, the better (choiceless) object that one should work with are the singular homology groups.

-
Then I don't feel this example fits the thread. This thread is about objects that can't be defined without making choices. The existence of singular cohomology shows that it can be defined without making choices. –  David Corwin May 21 '13 at 2:38
I'm with you David. –  Liviu Nicolaescu May 21 '13 at 10:06
I am with @Tony :-). This is an excellent example. The singular homology does not affect it since it's a priori not constructive. (I thought about this and other "big" examples but every other time I hesitate and choose discretion). The above "Question" is somewhat fractional, it represents a grand theme at the root of advanced mathematics. –  Włodzimierz Holsztyński May 21 '13 at 22:34
@David: Well, the thread is about object that "can't be defined without making choices so far" and before inventing singular homology, it was so for the simplicial one. –  Filippo Alberto Edoardo Jun 5 '13 at 3:30

The growth rate of a group, and in particular the notions of polynomial/subexponential growth, are defined in terms of (the Cayley graph corresponding to) a symmetric generating set, but are independent of the symmetric generating set chosen.

-
Though I think you can play the same trick that Steven Landsburg uses in a comment on another answer: let $r(S)$ be the growth rate for a symmetric generating set $S$, and define the growth rate of the group to be the supremum of $r(S)$ over all symmetric generating sets $S$. –  Nate Eldredge Sep 8 '14 at 14:32

The Seiberg-Witten invariant of an oriented compact manifold $4$-manifold needs at least a metric and often an additional $2$-form to be defined. Ultimately it is independent of the choice of metric and form

-

To my knowledge, the "pushforward with compact supports" along $f \colon X \to Y$ for étale cohomology is such a thing. For topological spaces it is easy to define

$$f_!\mathcal{F}(U) = \{ s \in \mathcal{F}(f^{-1}U) \mid f|_{\operatorname{supp}(s)} \text{ is proper}\}$$

(you know, as the name says) but this relies on $U$ actually being a subset of $Y$, so for étale sheaves one simply chooses a factorization of $f$ as a composition $p \circ j$, where $p$ is proper and $j$ is an open immersion; for $p$, we define $p_! = p_*$, while for $j$ we take $j_!$ to be "extension by zero" which does work even in the étale topology; then $f_! = p_! j_!$.

There are many such factorizations (that is, many compactifications of $f$); that one even exists in general, under some finiteness hypotheses, is a theorem of Nagata, but as for vector space bases, there is no canonical one. And unlike for bases, there is also no "maximal object" in the class of functors obtained from these choices; they are all simply canonically isomorphic to each other.

-

A possible example of what you're looking for, though of a somewhat different character from the examples given so far, is [the] "algebraic closure of $\mathbb Q$." Läuchli (Auswahlaxiom in der Algebra, Comment. Math. Helv. 37 (1962), 1–18) showed that ZF does not prove the uniqueness of the algebraic closure of $\mathbb Q$. However, it is very easy to construct an algebraic closure of $\mathbb Q$ in ZF. So in some sense there is provably no way to define "the" algebraic closure of $\mathbb Q$ unless we give ourselves the power of making arbitrary choices, via the axiom of choice. This example is a little peculiar, though, since what the ability to make arbitrary choices is needed for is not to construct an instance of the object, but rather to prove the equivalence of different constructions.

Of a similar flavor is the construction of "the" hyperreals as an ultrapower, which is unique up to isomorphism if you assume the continuum hypothesis.

-
...easy to construct an algebraic closure... you mean as a subset of the complex numbers? –  Gerald Edgar May 21 '13 at 17:45
Isn't it true that the theorem "every field has an algebraic closure" is somewhere between plain ZF and ZFC? That is, you seem to need to make some arbitrary choices (of representatives of each isomorphism class of algebraic extensions) to form a general algebraic closure, even though it's unique. –  Ryan Reich May 21 '13 at 18:44
@Ryan: Yes, this statement follows from the Boolean Prime Ideal theorem (equivalently, the ultrafilter lemma), which is strictly weaker than AC. The exact strength of "every field has an algebraic closure" as well "every field has a unique algebraic closure up to isomorphism" (which also follows from the above) are unknown. –  Asaf Karagila May 21 '13 at 20:26
@Gerald: It's simpler than that. Just enumerate all polynomials with integer coefficients and adjoin their roots. –  Timothy Chow May 22 '13 at 2:30

Well-ordering of the real numbers, or just any arbitrary set. Although this is somewhat inaccurate. So we can require a slightly more explicit requirement, well-ordering of a minimal order type.

The minimal order type, if any exists, is unique. But in order to have one to begin with, we need to make plenty of choices.

One more for the road, which is not entirely up to the requirements here, but deserves a mention after all, is a Vitali set. We have to make quite a few of choices in order to prove that one exists. And although in a good sense many are non-isomorphic (they can have outer measure as large and as small as we want it to be), the one property we are interested in is independent of that choice -- all Vitali sets are non-measurable.

-
If you're thinking of the classical Vitali set, one is taking a section of $\mathbb{R} \to \mathbb{R}/\mathbb{Q}$ over the image of $[0,1]$. All such sections have isomorphic images as sets, but perhaps you were thinking of other Vitali sets. –  David Roberts May 21 '13 at 1:03
David, yes. one takes a section over the image of $[0,1]$. But if the section accidentally ended up equal to the section taken over the image of $[0,\ln2]$? It could be equal to the section of $[3/\pi,1]$ too. These are sections which are isomorphic as sets, but we can still arrange for those sections to have different outer measure. So it all comes down to what sort of structure you care about preserving. –  Asaf Karagila May 21 '13 at 2:03

I doubt that you can define addition and multiplication on the real numbers (defined as equivalence classes of Cauchy sequences) without making choices.

[Edited to add: As Toink points out in comments, it's actually quite easy to define addition and multiplication without making choices. So let me modify the above by replacing "addition and multiplication on the real numbers" with "the square root function on the positive real numbers".]

In general, when an infinite set (or, say, an infinitely generated group, etc) is defined via an equivalence relation, as often happens in mathematics, there's no avoiding the fact that functions on that set have to be defined by choosing representatives (unless, of course, you first prove that your definition is equivalent to some other definition --- e.g. the reals can also be defined by Dedekind cuts --- but that only pushes the making of choices back a step, into the proof that the definitions are equivalent).

(One class of exceptions: If you're defining a function into an ordered set, you can avoid making choices by defining the value of your function to be its maximum over all possible choices --- this works for, say, the dimension of a vector space. But if the function's codomain has no extra structure, it seems clear that choices are unavoidable. Edited to add: Again, per Toink's comment, another class of exceptions occurs when the structure on the quotient is inherited from above.)

-
Let $A$ and $B$ be equivalence classes of Cauchy sequences. Define $C$ as the set of all Cauchy sequences $(z_n)$ such that for all $(x_n)\in A$, all $(y_n) \in B$, the sequence $(x_n+y_n-z_n)$ converges to $0$. Isn't then $C$ the sum of $A$ and $B$? –  Goldstern May 20 '13 at 20:19
Goldstern: This is very clever and I briefly agreed with it. But to make it work, you need to prove there's at least one such sequence $z_n$, and I don't know how to do that without first choosing elements of $A$ and $B$. Am I missing something? –  Steven Landsburg May 20 '13 at 20:47
Goldstern: Likewise I can define $Ext(A,B)$ as the module that arises when I take arbitrary resolutions of $A$ and $B$ and then etc etc. This definition requires no choices, but proving it makes sense requires a choice. Your example isn't exactly the same, because you need a choice to prove existence whereas in the Ext case I need a choice to prove uniqueness. But (unless I'm missing something, and I might be) it seems that if we allow "definitions" without first proving they make sense, then we can use this trick to eliminate all dependence on choices everywhere. –  Steven Landsburg May 20 '13 at 20:55
@Steven. actually in your example of Cauchy sequences there is no need to choose anything to define the sum of $A$ and $B$. You can just define the function $f\colon A\times B \to V$ defined by $f((x_n),(y_n))=(x_n+y_n)$. Then $A+B = Im(f)$ is nonempty if $A\times B$ is. –  Toink May 20 '13 at 21:56
Toink is right - to state it differently: The set of Cauchy sequences inherits the addition from $\mathbb Q$. The addition is compatible with the equivalence relation at hand and thus carries over to the quotient $\mathbb R$. –  Garlef Wegart May 20 '13 at 22:21

I don't know of a way to completely formalize your question, but here is something with the same flavor that may hint at how to proceed. Blass and Gurevich defined a complexity class—or more accurately, a logic—that they called "Choiceless Polynomial Time with Counting" or $\tilde CPT+Card$. The exact definition is somewhat technical (their paper is easily findable with Google) but roughly speaking, the idea is that the properties of unlabeled graphs that are expressible in $\tilde CPT + Card$ are precisely those that are computable in polynomial time without choosing a labeling of the graph. I believe that it is still an open question whether every polynomial-time computable property of unlabeled graphs, including those that proceed by labeling the graph and then computing some property that ends up being independent of the labeling, is expressible in $\tilde CPT+Card$. I think most people expect the answer to be no, but it's not easy to come up with a candidate to separate the two classes. This question is closely related to the question of whether graph isomorphism is solvable in polynomial time.

Of course, what you're interested in doesn't involve any computational limitations. However, the above discussion suggests that if you wanted to formally prove that some particular property of an object requires an arbitrary choice, then you should:

1. define two classes of objects, one "labeled" and the other "unlabeled," where "unlabeled" basically means a class of labeled objects equivalent up to some notion of automorphism;

2. write down a logic that allows you to express properties of labeled objects, and another "choiceless logic" that allows you to express properties of the unlabeled objects "without choosing a labeling";

3. show that there is some property of labeled objects that is invariant under automorphism but that is inexpressible in your "choiceless logic."

-
I suppose that you mean this paper: math.lsa.umich.edu/~ablass/149.pdf ? –  Asaf Karagila May 21 '13 at 3:49
Actually, I was thinking of reference [4] in that paper (which I now see has Shelah as a co-author; I think this was because Shelah proved one of the more interesting theorems, but the basic idea of choiceless polynomial time is due to Blass and Gurevich). –  Timothy Chow May 21 '13 at 15:05
Actually, the first version of choiceless polynomial time was proposed by Shelah and was (not surprisingly) fairly complicated. The "official" definition resulted from my and Yuri's effort to understand (and write up) Saharon's original proposal. I confess that I've forgotten all details about the original version, but I believe that Saharon continued to use it, for example in reference [15] of the paper that Asaf linked to. Note that the linked paper began as Yuri's and my effort to simplify and explain [15]. –  Andreas Blass May 21 '13 at 16:04

Daniel Moskovich's notion of "support point" to anchor definitions on manifolds is interesting. I suggest a radically non-geometric example: MATROIDS.

A finite matroid is a finite set with a family of subsets satisfying a list of properties. There are different lists of properties. The subsets could be independent sets, bases, circuits, flats, etc.

Given a matroid defined by independent sets (say) there is a canonical way to find a family of subsets that form a basis (say). So the cool thing about this example is that to define a matroid you need a choice of definition.

-
Eh, this applies to a lot of things. Topological spaces, for instance. –  Harry Altman May 21 '13 at 17:40

In topology, many maps are only characerized by homotopy properties. Proving that a certain homotopy class exists often requires the construction of an actual element in it, and this element is typically not uniquely determined. Aa advanced jargon phrase is that a ''construction depends on a contractible space of choices''. Here are two examples.

If $P \to X$ is a $G$-principal bundle, a ''classifying map'' $f: X \to BG$ is characterized by the property that $f^{\ast} EG \cong BG$, and this is unique up to homotopy. What one does is to prove that the space of $G$-equivariant maps $g:P \to EG$ is contractible (if $X$ is paracompact). Any such $g$ descends to a classifying map $X \to BG$ (and any classfying map is covered by such a $g$). Therefore, $f$ depends on a contractible space of choices and is therefore unique up to homotopy in the strongest possible sense. The concrete construction depends on data such as local trivializations of the bundle and partitions of unity and is therefore not unique or ''natural'' or ''canonical''.

The other example I want to mention is the Pontrjagin-Thom isomorphism, both of whose direction depend on choices. It states a bijection of the set of bordism classes of framed $n$-manifolds in $R^{m+n}$ and homotopy classes of maps $S^{m+n} \to S^m$.

Only after descending to discrete invariants (homotopy and bordism groups), the construction is well-defined. Passing from a bordism class to a homotopy class requires choosing an embedding of the manifold into a euclidean space and the choice of a tubular neighborhood and the choice of a concrete framing. In the reverse direction, you need a representative of the homotopy class by a smooth map and a regular value.

-

The dimension of a vector space is defined to be the size of a basis.

The canonical divisor is defined to be the divisor of a top-degree form.

-
In the same vein: an element of $\mathbb{Z}/n\mathbb{Z}$ is defined to be the class of an element of $\mathbb{Z}$. –  Matthieu Romagny May 20 '13 at 19:09
The dimension of a vector space is not, I think, a good example, because instead of making choices you can define it as the <b>maximum</b> cardinality of any basis. –  Steven Landsburg May 20 '13 at 19:12
Your example of the canonical divisor doesn't quite fit the bill, at least as written: the divisor you get does depend on the choice of form. (Its linear equivalence class doesn't, but that's not quite the same thing.) –  user5117 May 20 '13 at 21:55
On the other hand, the axiom of choice is needed to show that the dimension of a vector space is well-defined: Without choice, we could have spaces without bases, or with bases of different sizes. –  Andres Caicedo May 21 '13 at 5:28