# Vector dimension of a set of functions

Let $F$ be a field and $S$ an infinite set. Set $V=\{f:S \rightarrow F\}$ endowed with the vector space structure that results from the pointwise operations of $F$.

It is easy to prove that $|S| \leq \dim V$, since the functions $\delta_s$ defined by $\delta_s(s)=1$ and $\delta_s(t)=0$ for all $t \neq s$ are linearly independent.

Is it true that $|S| < \dim V$? If so how could it be proved? I tried some kind of Cantor-like diagonal argument, but nothing worked so far.

-

Case 1 when $|F|\leq\aleph_0$: Let $W$ be the set of functions $S\to F$ with finite support. Then $W$ is clearly a vector space with $\dim W=|S|$. We also have $|W|=|S|$, because there are $|F|\times|S|=|S|$ scalar multiples of base vectors and the number of finite sums of such vectors is $\sum_{i<\omega}|S|^i = \sum_{i<\omega}|S| = \aleph_0\times|S|=|S|$. On the other hand $V$ contains at least $2^{|S|}$ elements. Since $W$ and $V$ have different cardinality, they cannot be isomorphic. In particular, $V$ must have dimension $>|S|$.

Case 2 for arbitrary $F$: Let $K$ be the smallest subfield of $F$, that is, $\mathbb{Q}$ if $F$ has characteristic $0$ and $\mathbb{F}_p$ for characteristic $p > 0$. In either case, $K$ is small enough to match the condition in case 1.

Let $\mathfrak{B}$ be a basis for $\{f:S\to K\}$. By case 1, $|\mathfrak{B}|>|S|$. But each member of $\mathfrak{B}$ is also a member of $V$, and $\mathfrak{B}$ is still linearly independent over $F$. Namely, suppose that $f_1\mathbf{b}_1+\cdots+f_n\mathbf{b}_n$ is an $F$-linear relation among vectors $\mathbf{b}\in\mathfrak{B}$. Then the $f_i$'s are a solution to a homogenous system of $|S|$ linear equations with coefficients in $K$, and this system has only the trivial solution in $K^n$. Then $n$ of the equations must be linearly independent over $K$, which means that their determinant is nonzero whether evaluated in $K$ or in $F$. Therefore the $f_i$'s must all be zero, too.

So the dimension of $V$ is at least $|\mathfrak{B}|>|S|$.

-

If $\kappa=|S|$ is a regular cardinal, $\dim V>\kappa$.

For $A\subseteq S$ let $$f_A:S\to F:s\mapsto\begin{cases}1,&\text{if }s\in A\\0,&\text{if }s\notin A\;.\end{cases}$$

Suppose that $\mathscr{A}$ be a collection of subsets of $S$, each of cardinality $\kappa$, such that $|A_0\cap A_1|<\kappa$ whenever $A_0,A_1\in\mathscr{A}$ and $A_0\ne A_1$; I’ll call such a family almost disjoint. I claim that $\{f_A:A\in\mathscr{A}\,\}$ is linearly independent.

Suppose that $A_0,\dots,A_n$ are distinct members of $\mathscr{A}$ and that $c_0f_{A_0}+\cdots+c_nf_{A_n}=0$, where $c_0,\dots,c_n\in F$ are not all $0$. Without loss of generality assume that $c_0\ne 0$. Since $|A_0|=\kappa$, but $|A_0\cap A_k|<\kappa$ for $k=1,\dots,n$, $|A_0\setminus (A_1\cup\dots\cup A_n)|=\kappa$. In particular, $A_0\setminus (A_1\cup\dots\cup A_n)\ne\varnothing$, so we can choose $s\in A_0\setminus (A_1\cup\dots\cup A_n)$. Then $$c_0f_{A_0}(s)+c_1f_{A_1}(s)+\cdots+c_nf_{A_n}(s)=c_0\ne 0\;;$$ this gives us the desired contradiction, showing that $\{f_A:A\in\mathscr{A}\,\}$ is indeed linearly independent.

Thus, to show that $\dim V>\kappa$, it suffices to show that the almost disjoint family $\mathscr{A}$ can be chosen so that $|\mathscr{A}\,|>\kappa$. Clearly $\mathscr{A}$ can be chosen to have cardinality at least $\kappa$, since $S$ can be partitioned into $\kappa$ subsets of cardinality $\kappa$. Let $\mathscr{A}_0$ be such a family. Suppose that $\alpha<\kappa$, and for every $\beta<\alpha$ we’ve constructed an almost disjoint family $\mathscr{A}_\beta$ in such a way that $\mathscr{A}_\beta\subseteq\mathscr{A}_\gamma$ whenever $\beta<\gamma<\alpha$. Let $\mathscr{A}_\alpha^*=\bigcup_{\beta<\alpha}\mathscr{A}_\beta$; clearly $|\mathscr{A}_\alpha^*|=\kappa$, so let $\mathscr{A}_\alpha^*=\{A_\xi:\xi<\kappa\}$. Suppose that $\eta<\kappa$. For each $\xi<\eta$ we have $|A_\eta\cap A_\xi|<\kappa$, and $\kappa$ is regular, so $$\left|\bigcup_{\xi<\eta}(A_\eta\cap A_\xi)\right|<\kappa\;,$$ and we can choose $$s_\eta\in A_\eta\setminus\bigcup_{\xi<\eta}A_\xi\;.$$ Now let $A=\{s_\eta:\eta<\kappa\}$; clearly $|A_\eta|=\kappa$. Moreover, $A\cap A_\eta\subseteq\{s_\xi:\xi\le\eta\}$ for each $\eta<\kappa$, so $|A\cap A_\eta|<\kappa$ for each $\eta<\kappa$, and $\mathscr{A}_\alpha^*\cup\{A\}$ is almost disjoint. Thus, we may set $\mathscr{A}_\alpha=\mathscr{A}_\alpha^*\cup\{A\}$, and the construction goes through to $\kappa^+$. Finally, let $$\mathscr{A}=\bigcup_{\alpha<\kappa^+}\mathscr{A}_\alpha\;;$$ clearly $|\mathscr{A}|=\kappa^+>\kappa$, and $\mathscr{A}$ is almost disjoint since any two members of it already belong to one of the almost disjoint families $\mathscr{A}_\alpha$ with $\alpha<\kappa^+$.

-

Here's my two cents. The space $F^{\oplus S}$ of the set of all functions $S\to F$ with finite support in $S$ is a vector space of dimension $\#(S)$. So, if $F^S$ had dimension $\#(S)$ then it would be in bijective correspondence with $F^S$. In most tame cases this is impossible. For example, if $F$ is countable then $F^{\oplus S}$ is equipotent with $S$ while $F^S$ is certainly larger, cardinal wise, $S$ since $2^S$ naturally (set wise) embeds into $F^S$ (note $F$ must have at least two elements) and so Cantor's theorem applies.

EDIT: Of course, for the general case you could just reduce to the prime subfield.

EDIT EDIT:I see Henning just said this.

EDIT EDIT EDIT: Of course, this is is how one generally proves that for infinitey dimensional spaces the dual space is strictly larger, in dimension, than the original space! Indeed, if $F[S]$ is some infinite dimensional vector space, then $\text{Hom}_F(F[S],F)\cong F^S$ whereas $F[S]\cong F^{\oplus S}$.

-
Indeed, the dimension of the dual space was the original context for the text I reused in my answer. –  Henning Makholm Dec 29 '11 at 22:12

Indeed, the vector space $\mathbf R^\mathbf N$ has no countable Hamel basis. Fix any countable set of sequences $\{ a_i \}$ where $a_i \in \mathbf R^\mathbf N$. Our goal is to produce an element of sequence $b$ not in the span of this set, using a Cantor-style diagonalisation argument.

Let $\mathcal U$ be the set of finite subsets of $\mathbf N$. Since $\mathcal U$ is countable, we enumerate the members of $\mathcal U$ as $\{ U_1, U_2, \ldots, U_n, \ldots \}$. For each $U_n$, let $I_n$ be a set of $|U_n|+1$ “private” coordinates (so that all $I_n$'s are disjoint). Now, for each $i \in U_n$, the vector $(a_{i,j})_{j \in I_n}$ is of length $|U_n|+1$. Since $|U_n|$ vectors cannot span the whole of $\mathbf R^{|U_n|+1}$, there exists a vector $x_n$ in $\mathbf R^{|U_n|+1}$ that is not in the span of the vectors $$\left\{ (a_{i,j})_{j \in I_n} \ : \ i \in U_n \right\}.$$ Finally define $b$ so that $b|_{I_n}$ is equal $x_n$ above.

Now to complete the argument, just note that the construction ensures that for each finite $U \subseteq \mathbf N$, $b$ is not in the span of the vectors $\{ a_i \}_{i \in U}$. That is, $b$ is not in the span of $\{ a_i \}$.

-
I do not address the question in full generality; moreover, Henning's answer seems to subsume this. But I will just leave the answer as it is just in case any one is interested. :-) –  Srivatsan Dec 29 '11 at 22:08