What should be considered a finite size of an infinite dimensional space? [closed]

I've got a map between two infinite dimensional spaces, $f: A\to B$, where $A$ seems "larger" than $B$. For the sake of conversation let's assume that $A$ is the set of smooth maps $\mathbb R^3\to \mathbb R^3$ and $B$ is the set of smooth maps $\mathbb R^2\to \mathbb R^2$. I would like to figure out whether $B$ has a point $p$ such that $|f^{-1}(p)|>1$.

If $A,B$ were finite sets with $|A|>|B|$ the conclusion would follow from the pigeonhole principle.

If $A,B$ were finite dimensional spaces with $\dim(A)>\dim(B)$ the conclusion would follow as well.

The above notions of "size" of finite sets and finite dimensional spaces, the number of elements and the number of elements in the linear basis, are very useful because in part because they are finite and also because one can make "size" based arguments such as pigeonhole principle regarding the corresponding maps.

What could be an appropriate "size" for infinite dimensional spaces such as smooth maps?

closed as unclear what you're asking by Ryan Budney, Stefan Kohl, Ricardo Andrade, Yemon Choi, Willie WongOct 22 '14 at 7:39

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• What do you assume about the map $f$? If you make no assumptions, $f$ can be bijective. This happens also in the finite dimensional case. Your two spaces have the same cardinality, although I agree that one looks bigger than the other. – Joonas Ilmavirta Oct 21 '14 at 16:46
• For instance, let me take the integration map $P: A \to B$ where $A$ is the space of continuous functions $[0,1]\to {\bf R}$ that vanish at $0$, and $B$ is the space of $C^1$-functions $[0,1]\to {\bf R}$ that vanish at $0$. Now should one think $A$ is larger than $B$ or is "just as big" as $B$? – Yemon Choi Oct 21 '14 at 17:01
• @Michael: Even if you want linear maps, this just boils down to the cardinality of the basis of the vector space. The interesting question is if you ask about bounded maps with respect to a norm. Then this is really quite subtle. – Anthony Quas Oct 21 '14 at 17:45
• My naive way of looking at this kind of problems would be to take "natural topologies" on both sets and say one is smaller than the other if one can identify the objects the small space in a natural way with the objects in the larger space and this identification is continuous. So in Yemon's example, $B$ would be indeed smaller than $A$… – Dirk Oct 21 '14 at 18:55
• I mean, isn't this all just Hilbert's hotel? I really think that it would be more fruitful to give the actual problem you're thinking about, and then we can see if there are some finitely generated or finite-dimensional objects lurking in the problem that allow one to employ some kind of size argument – Yemon Choi Oct 21 '14 at 19:22

I don't think you'll find a good notion of dimension to get the pigeonhole principle to work.

Here are two examples of injective maps that are visualizable. I've given formulas for concreteness, which may or may not help in the visualization. They use $C(X,Y)$, the set of continuous maps from $X$ to $Y$.

1) $\ A = C(S^1,R^3), \ B=C(S^1,R^2)$. We want to show that given a curve $a$ in $R^3$, there is a curve in $R^2$ that has all its information. We do this by finding a curve whose first half gives the $x$-coordinate of $a$, and whose second half gives the $y$ and $z$ coordinates.

If $a=(a_x, a_y, a_z)$, let $h = a_y(0)-a_x(0)$, and let $f(a)$ be

$$f(a)(t) = (a_x(2t) + h,\ a_z(0) + (2t-1)th) \text{ if } t \le 1/2$$

$$f(a)(t) = (a_y(2t-1),\ a_z(2t-1) \ \ \ \ \ \ \ \ \ \ \ ) \text{ if } t \ge 1/2$$

Then $f(a)$ is continuous, and $f$ is injective.

2) $\ A' = C(S^2,R^3), \ B=C(S^1,R^2)$. We want to show that given an image of a sphere in $R^3$, there is a curve in $R^2$ that has all its information. We do this by finding a curve that gives us the information meridian by meridian.

Suppose $s$ is in $A'$. For any integer $i$, let $s_i$ be the image under $s$ of the meridian at $i$ radians. Then $s_i$ is in $A$. For any $x\in[0,1]$ and $i\in N$, let $$g(s)(2^{-(i+1)}(1+x)) = (1-2^{-i})\,f(s_i)(0) + 2^{-i}f(s_i)(x)$$ $$g(s)(0) = f(s_0)(0)$$

On each interval $[2^{-(i+1)}, 2^{-i}]$, $g$ reproduces $f(s_i)$, but smaller and faster so as to be continuous. Since $g(s)$ lets us reconstruct $s$ on a dense set of meridians, and since $A'$ had only continuous maps, we can reconstruct $s$ fully. So $g$ is injective.

Thus we have injective maps from $A$ to $B$ and from $A'$ to $B$. If no notion of dimension will yield a pigeonhole principle for examples as nice as these, then probably no notion of dimension will work at all.

To complement the above answer, let me give a purely abstract explanation.

Apparently, I think the notion you are looking for is... the notion of monomorphism --- an object $A$ is no smaller than object $B$ if there is no monomorphism from $A$ to $B$. In such a case if $f \colon A \rightarrow B$ is any morphism then there are "points" $a \neq a' \in A$ that are over a single "point" $b \in B$.

Unfortunately, the relation "is no smaller than" does not behave well in case the Cantor–Bernstein–Schroeder property does not hold (i.e. we say that CBS holds if whenever we have monomorphisms $A \rightarrow B$ and $B \rightarrow A$ then $A \approx B$). There is a nice discussion on the subject in the following question:

When does Cantor-Bernstein hold?

Now, let me elaborate, why I think the notion of a monomorphism is the right notion here.

First of all, one may either use a "positive" or a "negative" definition of your property for $f$. The positive definition says that the collection:

$$\{a \in A \colon f(a) = b\}$$

has more than one element for some $b \in B$; whereas, the negative definition says that it is not the case that all elements from the collection are equal for every $b \in B$. The negative definition has a very natural logical meaning --- the following does not hold:

$$f(a) = f(a') \Rightarrow a = a'$$

Such $f$ satisfying the above are called "monomorphisms" (so the negative definition says: "it is not the case that $f$ is a monomorphism").

However, this is not the end of the story. There are also two choices for your term "point" --- let me call them "external" and "internal" respectively.

In the "external" view, one has to understand the above "formula" with respect to the external logic. That is, $a, a' \in A$ have to be understood as generalized elements of $A$ parametrized by some $X$ --- morphisms $a, a' \colon X \rightarrow A$; and applications $f(a), f(a')$, by Yoneda, have to be understood as compositions $f \circ a, f \circ a'$. Thus the above formula, when interpreted in the external logic, becomes the usual definition of a monomorphism:

$$f \circ a = f \circ a' \Rightarrow a = a'$$

In the "internal" view, one has to choose a sufficiently strong internal logic to give a precise meaning for the formula. If $f$ satisfies the formula in such an internal logic, then we say that $f$ is an "internal monomorphism". Fortunately, in many cases, one may show that the notions of "internal monomorphism" and "external monomorphism" coincide. This is, for example, true in the canonical internal logic of any category (more generally, this is obviously true in any logic with external equality). Therefore, if we do not have any natural premises to chose other notions of monomorphism, perhaps the best choice is the usual notion of (external) monomorphism.

As I have mentioned on MO on an occasion of another MO Question, this kind of dimensional considerations in the context of infinite dimensional space of mathematical analysis were first conducted by Aleksander Pełczyński, and soon aftger and independently by Andrey Kolmogorov and his whole mathematical school. On may check the papers and a relevant monography by Anatoli Georgievich Vitushkin, then there was at least later monograph by another author. Vitushkin related the dimension concept to an aspect of the 13 Hilbert problem. In the case of continuous function a significant progress was achieved by Kolmogorov, and then Vladimir Arnold (at a very young age) provided a full and surprising solution, it was positive--he proved that every continuous function in finitely many variable was a composition of functions in two variables; this surprised Kolmogorov himself, who nevertheless soon made Arnold's solution even more attractive. On the other hand Vituskin was concerned with differentiable maps, and used Kolmogorov's dimension (or Pełczyński-Kolmogorov dimension) to tell different spaces apart, depending on the number of variables and the number of required iterated derivatives. In the similar context Vitushkin also considered computer science questions (informatique); see А. Г. Витушкин. Оценка сложности задачи табулирования. — М.: Гос. изд-во физ-мат. лит-ры, 1959; see also the still more advanced: L. D. Ivanov, Variations of sets and functions, Nauka, Moscow, 1975 (Russian). MR 57:16498.

The key words: metric compact space (or metric totally bounded space), $\ \epsilon$-nets (or $\ \epsilon$-coverings), finite dimensional linear approximations, Hausdorff dimension, ...