i have the following question: let $A=${0,1}$^\mathbb{N}$. we define $v\in A$ ,$v_i$ is the i'th coordinate of the infinite vector, and $$R =\{ (u,v)|\{i|u_i\neq v_i\}is\space finite\}$$ Determine if $[v_0]_R$ is finite/infinite and countable/uncountable, and prove it, where $v_0$ is the infinite all zeros vector. Now it's pretty obvious that this group is uncountable and i'm trying to prove that with cantor's diagonalization, but i'm having trouble because every attempt to differ myself from the other vectors results one way or the other with a vector with infinite 1's. Can anyone help?


Let $R_0$ be the subset of elements $u = (u_0, u_1 \dotsc) \in \{ 0, 1 \}^\mathbb{N}$ such that $u_i = 1$ for finitely many values of $i$. Let $\mathscr{F} ( \mathbb{N} )$ be the set of finite subsets of $\mathbb{N}$. Then \begin{align*} \varphi : R_0 &\to \mathscr{F} ( \mathbb{N} ) \\ u &\mapsto \{ i \in \mathbb{N} \mid u_i = 1 \} \end{align*} is an injective function: if $u, v \in R_0$ are such that $u \neq v$, then there exists $j \in \mathbb{N}$ such that $u_j \neq v_j$, and such a $j$ is either an element of $\varphi ( u )$, or an element of $\varphi ( v )$. Therefore $\varphi ( u ) \neq \varphi ( v )$.

For all $p \in \mathbb{N}$, the set of subsets of $\mathbb{N}$ with cardinal $p$, $N_p$, is countable: let \begin{align*} \psi : N_p &\to \mathbb{N} \\ A &\mapsto \sum_{k \in \mathbb{N}} \alpha_k 2^k \quad\text{with }\alpha_k =\begin{cases} 1 &\text{if } k \in A \\ 0 &\text{otherwise} \end{cases} \end{align*} Since $A$ has only $p$ elements, there are only $p$ nonzero terms in the sum, and $\psi$ is well-defined. If $A, B \in N_p$ are such that $A \neq B$, then at least one of them is nonempty; swapping the roles of $A$ and $B$ as necessary, we can suppose that $A \neq \varnothing$. Since both are also finite, there exists a largest element $m \in A - B$. Then $\psi ( A ) \geq 2^m > \psi ( B )$, and $\psi$ is injective.

From this we deduce that $\mathscr{F} ( \mathbb{N} ) = \cup_{p \in \mathbb{N}} \,N_p$, as a countable union of countable sets, is countable; and finally, that $R_0$ is also countable.

  • $\begingroup$ Thanks man, but we haven't learned what a cardinal is so i can't understand what you did there. I see that you've reached the conclusion that $R_0$ is countable, so i guess i should find an injection from $\mathbb{N}$ to $[v_0]_R$. $\endgroup$ – CodeHoarder May 16 '17 at 9:02
  • $\begingroup$ For a finite set, its cardinal is the number of elements that are in it. It is safe to replace "the set of subsets of $\mathbb{N}$ with cardinal $p$" with "the set of subsets of $\mathbb{N}$ with $p$ elements". $\endgroup$ – Nicolas Pelletier May 16 '17 at 9:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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