Finding a bijection between two equivalence classes

Question

I am given this equivalence relation:

$$R = \{( f, g ) \in (\mathbb{N} \rightarrow \{0, 1\}) \times (\mathbb{N} \rightarrow \{0, 1\}) \ \vert \ \exists N \in \mathbb{N} \ \forall i \geq N : f (i) = g (i) \}$$

I need to find a bijection between 2 arbitrary equivalence classes. I was trying for a long time without success, any help will be appreciated.

Added: thank you very much for your answers. I now need to find the cardinality of each equivalence class. I think the answer is ℵ but cant seem to find an injective function from N → {0, 1} to [f]. any ideas ?

Answer 1

Let $F:\mathbb{N} \rightarrow \{0,1 \}$ be a function and let $[F]$ be its equivalent class. For $f\in [F]$ we define

$$ l_F(f):= \min\{ N\in \mathbb{N} \ \vert \ \forall i\geq N: f(i)=F(i) \}.$$

Define for $n\in \mathbb{N}$

$$ S_n(F) := \{ f\in [F] \ \vert \ l_F(f)=n \}.$$

Clearly, $(S_n(F))_{n\in \mathbb{N}}$ forms a partition of $[F]$.

Thus, we can reduce the problem of finding a bijection from [F] to [G] to find bijections

$$ \phi_n : S_n(F) \rightarrow S_n(G).$$

One possibility would be to define

$$ \phi_n (f)(i) = \begin{cases} f(i),& 0\leq i \leq n-1; \\ G(i),& i\geq n. \end{cases}$$

Added: Putting all this maps into a single map, this would do the following. It takes a function $f\in [F]$ and doesn't change it, where it differes from F and sends all the values coinciding with F to the respective values of G. The advantage of this procedure is that it immediately generalises to any target.

Answer 2

I am not sure if this works but suppose $\varphi:\mathcal{C}\to \mathcal{C}$ is defined for $C_f\in \mathcal {C}$ in the following way: Consider the sequence $f(1), f(2),\dots$ associate this sequence with the sequence $\{0,1\}\setminus f(1), \{0,1\}\setminus f(2),\dots $. Clearly later is defines a function $g$. So associate the class $C_f$ of $f$ with the class $C_g$ of $g$.You can verify that it is a bijection.

Answer 3

HINT: For $f:\Bbb N\to\{0,1\}$ let $A_f=\{n\in\Bbb N:f(n)=1\}$; $f$ is the indicator (or characteristic) function of $A_f$, i.e., $f=\chi_{A_f}$. Fix $f,g:\Bbb N\to\{0,1\}$, and let $[f]$ and $[g]$ be the $R$-equivalence classes of $f$ and $g$, respectively; we want a bijection between $[f]$ and $[g]$.

Suppose that $h\in[f]$; then $A_h\mathbin{\triangle}A_f$ is a finite subset of $\Bbb N$ (where $\triangle$ is symmetric difference). Conversely, if $F$ is any finite subset of $\Bbb N$, then $\chi_{F\mathbin{\triangle}A_f}\in[f]$. Thus, if $\mathscr{F}$ is the family of finite subsets of $\Bbb N$, the map

$$\varphi:[f]\to\mathscr{F}:h\mapsto A_h\mathbin{\triangle}A_f$$

is a bijection. There is a similar bijection between $[g]$ and $\mathscr{F}$; combine them to get the desired bijection between $[f]$ and $[g]$. (It’s not too hard to describe this bijection directly, using the Boolean function XOR (exclusive OR) on $\{0,1\}$.)