1
$\begingroup$

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

  • 0
    Then you should like the "backwards" suggestion of @Henning Makholm much better. I was stuck in the reading from left to right world. Still get countability, but reading right to left is a lot more direct.2011-09-24

2 Answers 2

2

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

  • 0
    No no, that's good! you have given me much food for thought2011-09-24
3

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.

  • 0
    Hennin$g$, lost in translation, thanks. Editing it. Srivatstan yes, indeed, on both counts.2011-09-24