Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
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
show 1 more comment

2 Answers

up vote 2 down vote accepted

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'$.

share|improve this answer
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
add comment

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.

share|improve this answer
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
show 3 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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