20
$\begingroup$

It's frequently said, informally, that a natural isomorphism is one that doesn't depend on arbitrary choices.

But the phrase "arbitrary choices" lends itself to different interpretations. Consider the following examples, all concerning a finite-dimensional vector space $V$ over a field $k$:

A. The natural isomorphism $V\rightarrow V\otimes_kk$ (by which I mean the obvious natural transformation from the identity functor to the functor $ -\otimes_kk$) is defined by a basis-free formula $v\mapsto v \otimes 1$, and is easily proved to be an isomorphism without ever invoking the existence of a basis.

B. The natural isomorphism $V\rightarrow V^{**}$ is defined by a basis-free formula $v\mapsto \Big(\phi\mapsto \phi(v)\Big)$, but to prove this is an isomorphism, it seems I have to choose a basis. Likewise for the natural isomorphism $V^*\otimes_k V\mapsto Hom_k(V,V)$.

C. The natural isomorphism $Hom_k(V,V)\mapsto V^*\otimes_kV$ cannot, I think, even be defined by any basis-free formula. To define the map, one first chooses a basis and then proves that the definition is independent of that choice.

Is there a more formal way to distinguish such cases? I'm looking for a precise definition of what it means to be "definable by a basis-free formula" or "provably an isomorphism without ever mentioning a basis" --- precise enough so that it's possible to prove (not just suggest, as above) that a given isomorphism satisfies one, the other, both, or neither of these conditions.

(I suppose that the business about "provably an isomorphism without ever mentioning a basis" is perhaps no more interesting than "provably an isomorphism without ever using $X$", where $X$ is some other known property of vector spaces. But the business about being "definable by a basis-free formula" seems to me to be more interesting.)

Edited to add: I appreciate the responses, but I fear the main thing I've learned from them is that I failed to make the question clear. This wasn't intended as a question about vector spaces; the vector spaces were meant to illustrate something more general. I quite understand the reasons why the map $V^{**}\rightarrow V$ can't be constructed without reference to a basis (most notably, this map doesn't exist in the infinite dimensional case, so there's no hope to construct it without using the finite dimensionality, which means referring to a basis). The question is not why this is true but how to state it in a rigorous way. How, formally, and in more general contexts than vector spaces, does one formalize the notion of "not constructible without making some choices that turn out to be irrelevant at the end"?

$\endgroup$
15
  • 10
    $\begingroup$ At C) The natural map goes in the other direction $V^*\otimes_k V\rightarrow Hom_k(V,V), \quad f\otimes v\mapsto f(-)\cdot v$ and has a base free definition. The problem is that for if $V$ is infinite-dimensional, the image of that map consists of all maps in $Hom_k(V,V)$ with finite-dimensional Range. $\endgroup$ Jul 11, 2016 at 23:17
  • 2
    $\begingroup$ @Steven: I think part of what makes your question ambiguous is that much depends on the definition of "finite-dimensional" you use; if it's "has a finite basis" then there's a pretty tautological sense in which you can't make any claim about finite-dimensional vector spaces without referring to a choice of basis. I assume that's not interesting to you. Here is a different example where I don't even know what choices, if any, are required: if $A$ is a topological group then there's a natural map from $A$ to its double Pontryagin dual $[[A, S^1], S^1]$ which, if $A$ is LCH, is an iso. What... $\endgroup$ Jul 12, 2016 at 6:31
  • 1
    $\begingroup$ Maybe what you want here is to consider the free monoidal closed abelian category generated by a single object $X$ and by $\hom(1,1) = k$, and then observe that $X \to X^{**}$ is not an isomorphism? (I'm not sure if there even exists a nonzero map $X^{**} \to X$) $\endgroup$
    – user13113
    Jul 12, 2016 at 6:49
  • 1
    $\begingroup$ It seems like more people want to show off their knowledge of fun facts about vector spaces than want to answer the question... $\endgroup$ Jul 12, 2016 at 12:10
  • 2
    $\begingroup$ Here's a possible approach: I think the ur-example of a problem where you have to make an arbitrary choice is the following: "Let $A$ be non-empty and let $f:A\rightarrow B$. Is $B$ non-empty?". Clearly the only way to proceed is to choose an arbitrary $a\in A$ an consider $f(a)\in B$. Any other problem involving an arbitrary choice reduces to this one. For example we have a function from the set of finite bases of $V$ to the set of inverses to $V\rightarrow V^{**}$, but to show that $V\rightarrow V^{**}$ actually has an inverse we have to actually pick one of these bases. $\endgroup$ Jul 12, 2016 at 14:18

4 Answers 4

21
$\begingroup$

The issue here is that the inverses to $V\rightarrow V^{**}$ and $V^*\otimes V\rightarrow \mathrm{Hom}(V,V)$ don't exist in the infinite dimensional case. So in order to show that they exist one has to assume that $V$ is finite dimensional. Now, if your definition of "finite dimensional" is "has a finite basis", then of course you have to use a basis at some point.

One option is to instead take your definition of "finite dimensional" to be "the natural map $V^*\otimes V\rightarrow \mathrm{Hom}(V,V)$ has an inverse". Then you can prove many facts about finite dimensional vector spaces without using a basis at all, and in particular you can construct an inverse to the map $V\rightarrow V^{**}$.

$\endgroup$
5
  • $\begingroup$ Yes, I quite understand that $V^{**}\rightarrow V$ does not exist in the infinite dimensional case, and this is why one can't hope to construct it without invoking the existence of a finite basis. But this doesn't really answer my question, which is: How, in general, should one rigorously state the condition that the map can't be constructed without reference to a basis? $\endgroup$ Jul 12, 2016 at 1:15
  • $\begingroup$ @Steven: perhaps the issue at stake is the following. More generally, say I have a natural transformation $\eta : F \to G$ between two functors $F, G : C \to D$. I know that there are some $c \in C$ - call them the "nice" c - such that the component $\eta(c) : F(c) \to G(c)$ is an isomorphism. But I can't prove this without choosing a particular way to construct $c$, or something. I would regard "the inverse to $\eta(c)$, when $c$ is nice" as a definition of a map which does not involve making any choices (because inverses, if they exist, are unique). But perhaps you don't? $\endgroup$ Jul 12, 2016 at 6:36
  • $\begingroup$ Finite dimensionality of $V$ is characterized by the fact that $\mathrm{Hom}(V,-)$ commutes with coproducts, so, in principle, you don't need a basis. $\endgroup$
    – Leo Alonso
    Jul 12, 2016 at 8:37
  • 1
    $\begingroup$ @Leo: sure, but at some point you want to prove that some particular vector space you care about is finite-dimensional. How do you prove that it satisfies that condition? Probably by finding a finite generating set, which is not much better than finding a finite basis as far as trying to avoid making choices. $\endgroup$ Jul 12, 2016 at 10:57
  • $\begingroup$ @QiaochuYuan : You write: "I would regard...as a definition of a map which does not involve making any choices...But perhaps you don't?". I have no strong preconceptions about what does or does not count as "making choices", beyond the sort of thing suggested in the post. Mainly, I am curious as to whether others have thought about this much harder than I have and whether they've drawn distinctions subtler than I've considered. $\endgroup$ Jul 12, 2016 at 13:17
10
$\begingroup$

An object $V$ in a symmetric monoidal category is said to be dualizable with dual $V^{\ast}$ if you can find maps

$$\text{ev} : V^{\ast} \otimes V \to 1$$

and

$$\text{coev} : 1 \to V \otimes V^{\ast}$$

such that the zigzag identities hold (the same zigzag identities in the unit-counit definition of an adjunction). It's a formal exercise to show that if $V$ is dualizable with dual $V^{\ast}$ then $V^{\ast}$ is dualizable with dual $V$; moreover, if the ambient symmetric monoidal category is closed, then you can always take $V^{\ast} = [V, 1]$ to be the internal hom of $V$ and the unit, and $\text{ev}$ to be the evaluation map. From here it's not hard to show that

$$V \to [[V, 1], 1] \cong (V^{\ast})^{\ast}$$

is an isomorphism for any dualizable $V$; in other words, dualizable objects are reflexive. It's also true that if $V$ is dualizable then

$$[V, W] \cong V^{\ast} \otimes W$$

for any $W$. None of this requires making any choices and is completely canonical once you show that if duals (together with their evaluation and coevaluation maps) exist then they are unique up to unique isomorphism.

Now, in the case of vector spaces, the dualizable objects are precisely the finite-dimensional ones. Whether you need to exhibit a basis to prove this depends on whether your definition of finite-dimensional is "has a basis." Here it is the coevaluation map which it is troublesome to define without a choice of basis; with a choice of basis $e_i$ it's given by

$$\text{coev} : 1 \ni 1 \mapsto \sum e_i \otimes e_i^{\ast} \in V \otimes V^{\ast}$$

where $e_i^{\ast}$ is the dual basis. But this does not weaken the naturality of anything that's been said here, again because of the important fact that duals (together with their evaluation and coevaluation maps) are unique if they exist.

As in Oscar Cunningham's answer, if your definition of "finite-dimensional" happens to be "the natural map $V \otimes V^{\ast} \to [V, V]$ is an isomorphism" (this map always exists and requires nothing to define) then you can define the coevaluation map to be the inclusion of the identity element into $[V, V]$. At some point you will want to show that something is finite-dimensional, though, and then you might need to pick a basis. But that's okay.

$\endgroup$
1
5
$\begingroup$

How, formally, and in more general contexts than vector spaces, does one formalize the notion of "not constructible without making some choices that turn out to be irrelevant at the end"?

(This is a long comment, rather than an answer.)

The first step seems to be formalizing what "making some choices" means. To some mathematicians, this might simply mean applying the axiom of choice. For instance, in the context of vector spaces one may want to avoid invoking the existence of a basis because the existence of a basis requires the axiom of choice (for a general space).

But even if we throw out the axiom of choice, there are still natural contexts where choice happens. For instance, as the other answers have hinted at, we might define a finite dimensional vector space to be a vector space with a certain type of choice function. If we ever use that choice function, then we have made a choice.

However, your definition of "making some choices" seems to be much broader than even this. It seems to include, for instance, picking an element from a non-empty set. Is that right? Would you consider the fact that "a set with an element is not equal to the empty set" an example of "not constructible without making some choices that turn out to be irrelevant at the end"?

Three further questions. Let's say you define the natural numbers using Peano arithmetic, one of the axioms being "0 is an element of $\mathbb{N}$". Is this axiom (which is a theorem too) constructible? Does it require making choices? If so, is that choice irrelevant at the end?

One possible answer to formalizing "avoidance of choice making" might be working in the context of natural deduction without $\exists$ elimination.

$\endgroup$
6
  • $\begingroup$ The pointer to natural deduction and $\exists$ elimination might be the kind of thing I was looking for. I'll follow up on this. $\endgroup$ Jul 12, 2016 at 15:12
  • 2
    $\begingroup$ $\lor$ elimination also involves a choice. Harrop formulas are those which exclude both $\lor$ and $\exists$. Sometimes it's useful to allow $\lor$ and $\exists$ but only in the negative part (i.e., in hypotheses, but not in the conclusion). The cool thing is that the meaning of such formula is the same in classical logic as it is in intuitionistic logic. wikiwand.com/en/Harrop_formula $\endgroup$ Jul 12, 2016 at 18:03
  • $\begingroup$ It's perhaps useful to add that the independence of the choice is built-in to the $\exists$-elimination rule. That rule says that in order to prove that $\exists x P(x) \to Q$ it suffices to show that $\forall x (P(x) \to Q)$. Since $x$ doesn't appear in the conclusion $Q$, its exactly the same conclusion $Q$ that holds regardless of the choice of $x$. There is a twist, where the conclusion might itself be existential. In that case, the witness for this existential quantifier produced might depend on $x$ but the existential quantifier washes away the distinction between different witnesses. $\endgroup$ Jul 12, 2016 at 21:28
  • $\begingroup$ (continued) In this case, the hypothesis "$V$ is finite dimensional" is existential: "there is a finite basis for $V$". The conclusion is also existential: "there is an inverse to the natural map $V \otimes V^\ast \to \operatorname{Hom}(V,V)$". However, there is at most one inverse to this map, so the same witness is necessarily produced. $\endgroup$ Jul 12, 2016 at 21:32
  • $\begingroup$ (addendum) I just read KConrad's comment on quotient groups and I think it illustrates part of the point. Consider instead the statement "there is a right inverse to the natural map $F(V \times V^\ast) \to \operatorname{Hom}(V,V)$, where $F(V \times V^\ast)$ is the free vector space on $V \times V^\ast$". Then different choices of bases will yield different right inverses. This illustrates the combined $\exists$-elim/intro rule: to prove $\exists x P(x) \to \exists y Q(y)$ it suffices to give construction $f$ such that $\forall x(P(x) \to Q(f(x)))$. $\endgroup$ Jul 12, 2016 at 21:49
3
$\begingroup$

Here are two examples based on sets and one more. Again a long comment.

1) For a set $S$ let $\mathcal{L}$ be the set of linear orders and $\mathcal{P}$ be the set of permutations. There is an easy proof that there is a bijection between these two things, but it depends on choosing an arbitrary but fixed distinguished linear order $\ell$ and composing the obvious bijections $\mathcal{L} \rightarrow \ell \times \mathcal{L} \rightarrow \ell \times \mathcal{P} \rightarrow \mathcal{P}$. This seems unavoidable as there is one, but only one, natural distinguished permutation (once there are three elements) but no distinguished linear order. Alternately, the orbit structure of the natural action of $\operatorname{SYM}_S$ on $\mathcal{L}$ and on $\mathcal{P}$ is not the same.

I stated it that way to highlight the natural bijection between $\mathcal{L} \times \mathcal{L}$ and $\mathcal{L} \times \mathcal{P}$ which is a projection on the first component and, for each fixed first component, a bijection between $\mathcal{L}$ and $\mathcal{P}.$ That seems like a candidate for a proof that the set of bijections is non-empty. Of course it is a little problematic if $S$ might or might not be $\emptyset.$

2) Consider the claim that there is a bijection between the even and odd cardinality finite subsets of a set $S.$ The obvious proof depends on choosing an arbitrary but fixed element $s$ and using it to partition the finite subsets into pairs $\{{A,A \oplus \{{s\}}\}}$. Since the claim is true precisely when $S \ne \emptyset,$ this seems unavoidable.

3) This one I am less sure of. The point is that something like a Hamel basis or an everywhere dense non-measurable set seems needed, but the result feels more discrete and concrete than Vitali Sets.

Call a real triple of the form $T_x=\{{x,x+1,x+\sqrt{2}\}}$ an ell. I want to claim that $\mathbb{R}$ can be partitioned into disjoint ells (call this a $1$-cover). Alternately, but perhaps not equivalently, there is a subset $X \subset \mathbb{R}$ such that $X,X+1$ and $X+\sqrt{2}$ constitutes a partition of $\mathbb{R}$ into three disjoint congruent sets.

The set of all ells is a $3$-fold cover of $\mathbb{R}.$ I will give a natural partition of $\mathbb{R}$ into sets called boards such that there is an explicit and unique set of three $1$-covers for each board. Then a $1$-cover of $\mathbb{R}$ is precisely a selection of one $1$-cover (from the possible three) for each board.

It seems pretty natural that the following are equivalence relations in $\mathbb{R}$.

  • $x \sim y$ when $x-y \in \{{a+b\sqrt{2} \mid a,b \in \mathbb{Z}\}}$
  • $x \approx y$ when $x-y \in \{{a+b\sqrt{2} \mid a,b \in \mathbb{Z} \text{ and }a\equiv b \bmod 3\}}.$

This does not require extending $\{{1,\sqrt{2}\}}$ to an explicit basis of $\mathbb{R}$ over $\mathbb{Z}.$ Note that an equivalence class is everywhere dense. Call an $\sim$-equivalence class a board. Also, consider the equivalence relations on the set of ells defined by $T_x \sim T_y$ and $T_x \approx T_y$ when $x \sim y$ and $x \approx y.$

Each ell lies entirely in one board and its $\approx$-equivalence class is the unique $1$-cover of that board including that ell. A $\sim$-equivalence class constitutes a $3$-cover of its board and it resolves into three $\approx$-equivalence classes which are the only $1$-covers of that board.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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