# Showing countability of $V:=\{f\in F^{\mathbb{N}}:\operatorname{supp}(f)$ is finite $\}$ and uncountability of $V'$

Let $F:={\mathbb{Z_2}}$ be the field with two elements and let $F^{\mathbb{N}}:=\{f:\mathbb{N}\to\mathbb{Z_2}:$ with usual pointwise addition and multiplication by scalers $\}$

Then define

$V:=\{f\in F^{\mathbb{N}}:\operatorname{supp}(f)$ is finite $\}$ where $\operatorname{supp}(f)=\{n\in \mathbb{N}:f(n)=1\}$

Now we can think about the elements of V as seqeunces alternating between $0$ and $1$.

We define the dual space $V'$ as

$V'=\{\phi:V\to \mathbb{Z_2}:$ $\phi$ is a linear functional $\}$

So far I have shown that if we define for $S\subset \mathbb{N}$, $\phi_S(f):= \sum_{n\in S}^{}f(n)$ then $V'=\{\phi_S: S\subset \mathbb{N}\}$

Would anyone be able to help me show that $V$ is countable and $V'$ is uncountable. I am hoping what I have shown already can help show $V'$ is uncountable, if I am correct in that there are an uncountable number of subsets of $\mathbb{N}$ then we have already shown $V'$ is uncountable.

EDIT: As the set $\{S:S\subset \mathbb{N}\}$ is uncountable so is $V'$

EDIT#2: How about $\forall f \in V$, $|\operatorname{supp}(f)|=n\in \mathbb{N}$

So let us call $V=\{f:|\operatorname{supp}(f)|=1\}\cup\{f:|\operatorname{supp}(f)|=2\}\cup\cdots\cup\{f:|\operatorname{supp}(f)|=n\}\cup\cdots$ this forms a countable number of subsets of $V$

So by considering $\{f:|\operatorname{supp}(f)|=n\}$, the set of functions with have $n$ such values such that $f(x)=1$, if we can find a way to make the ways $n$ values can by arranged over $\mathbb{N}$ countable then $V$ must also be countable?

EDIT#3: Could we do this inductively? Take n=1 and define,

$g:\mathbb{N} \to \{f:|\operatorname{supp}(f)|=1\}$ where $g(n)=f(x)$ where $f(x)=1$ for $x=n$ and $f(x)=0$ for $x\neq n$

Therefore countable for $n=1$ assume countable for $n$.

Define $S_i:=\{f:|\operatorname{supp}(f)|=i\}$

By assumption $\exists g:\mathbb{N} \to S_n$ then $\forall f \in S_{n+1}$ we can write

$f=f_n+f_1$ for some $f_n \in S_n$ and $f_1 \in S_1$ as $S_1$ is countable and by assumption $S_n$ is countable so is $S_{n+1}$, therefore $S_n$ is countable for $n\in \mathbb{N}$. Therefore as the set $\{S_1,S_2,\dots\}$ is countable so is $V$?

-
Your idea works, though its presentation could be a bit more polished. In particular, things like $\mathrm{supp}(f)=2$ is strictly speaking nonsense, $\mathrm{supp}(f)$ is a set of integers and cannot equal one particular integer. You mean the the size of this set is 2, which is notated $\#\mathrm{supp}(f)=2$ or $|\mathrm{supp}(f)|=2$. – Henning Makholm Sep 24 '11 at 14:57
You are looking at sequences of $0$'s and $1$'s that are eventually $0$. Any such sequence can be identified with a terminating base $2$ expansion. The numbers with such an expansion form a subset of the rationals, and there are only countably many rationals. – André Nicolas Sep 24 '11 at 14:58
@HenningMakholm: Yes, that was a rookie error. Thanks for pointing it out!! – Freeman Sep 24 '11 at 15:07
@AndréNicolas: Awesome! I like that method a lot. – Freeman Sep 24 '11 at 15:07
@André, or you could expand the sequence to the left of the decimal (um, binary) point instead, and get integers directly. – Henning Makholm Sep 24 '11 at 15:11

Hint for part (1): Give a bijection between $V$ and the collection of finite subsets of $\mathbb N$.

If you prefer sequences, you can alternatively give a bijection between $V$ and the collection of finite length $0$-$1$ sequences. You were right in thinking of the elements of $V$ as zero-one sequences, but missed the crucial length restriction.

Part (2): The subspace $V$ obviously contains the elements $\{ e_i \}$, where $e_i \in F^{\mathbb N}$ is such that $$e_i(x) = \begin{cases} 1, &x=i, \\ 0, &x \neq i. \end{cases}$$ Show that the set $B = \{ e_i \,:\, i \in \mathbb N\}$ forms a (Hamel) basis for $V$. So to describe a linear functional, you may arbitrarily specify its action on $B$, and the functional is uniquely specified, thanks to linearity.

Now the big hint: what is the cardinality of the set $\{ \psi : B \to \mathbb Z_2 \}$?

I think you were on these lines (that $B$ is a basis for $V$) when you wrote:

So far I have shown that if we define for $S \subset N$, $\phi_S(f):= \sum_{n \in S} f(n)$, then $V'= \{ \phi_S : S\subset N \}$.

I think this approach is fine, but you will need to make it a bit more rigorous. In particular, you will need to justify the following:

1. In the definition of $\phi_S(f)$, the sum could be potentially infinite and infinite sums do not make sense over $\mathbb Z_2$. But this particular sum does make sense if $f \in V$, even if $S$ is infinite. In my opinion, if you justify this properly, this will also be a very good motivation behind the definition of $V$. (The uncountability of $V'$ essentially stems from the fact that $S$ is an unrestricted subset of $\mathbb N$.)

2. Related to previous point, I think you should explicitly write $\left. \phi_S \right|_V$ to signal that $f$ must come from $V$. Then $V' = \{ \left. \phi_S \right|_V \,:\, S \subset \mathbb N \} .$

3. You haven't actually proved (in this post) that $V'=\{\phi_S \,:\, S \subseteq \mathbb N \}$; you should definitely do so. Moreover, if $S \neq S'$, then $\left. \phi_S \right|_V \neq \left. \phi_{S'} \right|_V$. This one-one-ness is important just to prevent double-counting the elements of $V'$.

-
Still digesting your answer (looks very good! :) ) but in response to part 2 point 3, I had previously proved it, I just chose not to include my proof to it in my question – Freeman Sep 24 '11 at 15:02
@LHS I polished my answer a bit. Hope that's not inconvenient. (And I added a bit saying that you haven't included a proof in this post :)) – Srivatsan Sep 24 '11 at 15:10
No no, that's good! you have given me much food for thought – Freeman Sep 24 '11 at 15:20

It is easy to see that there is bijection between $V$ and a subset of $\mathbb{N}^+ = \bigcup_{n=0}^\infty \mathbb{N}^n$ where $\mathbb{N}^n = \{ (a_1, \dots, a_n) \mid a_i \in \mathbb{N} \text{ for all } i \}$; represent any function $f \in V$ with $|\mathrm{supp}(f)| = n$ by the $n$-tuple that contains all values from $f^{-1}(1)$ in a sorted fashion.

Suffice to show that $\mathbb{N}^+$ is countable (as any subset of a countable set is itself countable). First, note that $\mathbb{N}^n$ is countable for any $n$; use a generalisation of Cantor's pairing function. So $\mathbb{N}^+$ is a subset of countably many countable sets, and therefore countable itself.

-
Hmmm.. I have not encountered $\mathbb{N^n}$ before, sorry for my lack of knowledge, but if what you're saying along the lines of my edit? – Freeman Sep 24 '11 at 14:18
@LHS, the very useful general principle Raphael is pointing to is that if you have a set, and every element in the set can be uniquely described by a finite sequence of integers, then the set is at most countable. This "description" can work in any odd way as long as you're sure that every element has a description and two different elements do not share a description. – Henning Makholm Sep 24 '11 at 15:01
@LHS, in this particular case there is, however, a more direct way to write down a bijection between V and $\mathbb N$, namely $\phi(f) = \sum\{2^n\mid f(n)=1\}$. – Henning Makholm Sep 24 '11 at 15:03
@Raphael When you "$V$ is isomorphic to a subset of $\mathbb N^+$", I suppose you only mean a bijection. Is my understanding correct? – Srivatsan Sep 24 '11 at 15:15
@Hen Perhaps Raphael is referring to Cantor's pairing function. – Srivatsan Sep 24 '11 at 15:17