1
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ This is hard to read. Are you sometimes using $N$ to stand for $\mathbb N$, the natural numbers, and other times using $N$ to stand for some large natural number? $\endgroup$ – lulu Dec 24 '16 at 23:09
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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\}$.)

$\endgroup$

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.