Problem: Define a relation $ S $ on $ \Bbb N \to \{0,1\} $ as follows:
$ \langle f,g \rangle \in S \iff $ there exists a bijection $ h: \Bbb N \to \Bbb N $ s.t. $ f = g \circ h $.
$ S $ is an equivalence relation on $ \Bbb N \to \{0,1\} $ (no need to prove this). Write a Representative set for the relation $ S $. There's no need to prove that the relation you wrote is indeed a Representative set.
Reminder: Suppose $ T \subseteq X \times X $ is an equivalence relation over $ X $. $~~ A \subseteq X $ will be called a Representative set of $ T $, if it occurs that: $ \forall x \in X. | [x]_T \cap A | =1 $.
Attempt: I don't really know what Representative set to define. It seems to me I'm missing something simple here. I tried to look at the functions: $ f_1(n) = 0 , f_2(n) =1,f_3(n) = \begin{cases} 0 & \text{n=0}\\ 1 &\text{else}\end{cases} $ ,$ f_4(n) = \begin{cases} 0 & n \in \Bbb N_{even} \\ 1 & n \in \Bbb N_{odd} \end{cases} , \forall n \in \Bbb N$ . None of these functions relate through relation $ S $ since there does not exist a bijection between them. I feel lost, do you have any idea what to do? Thanks in advance!
A representative set would be $\{f : \mathbb{N} \to \{0, 1\} | f$ is monotonic$\} \cup \{h\}$, where $h(n)$ is defined s.t. $h(n) \equiv n \mod 2$.
Here, a monotonic function is one which is either monotonically increasing or monotonically decreasing.
Let's prove that this is a representative set.
Consider some function $g : \mathbb{N} \to \{0, 1\}$. Consider $S_i = g^{-1}(i)$ for $i = 0, 1$. Each $S_i$ is either finite or infinite.
If $S_0$ and $S_1$ are both finite, then $\mathbb{N} = S_0 \cup S_1$ is finite. This is contradictory.
If $S_0$ and $S_1$ are both infinite, then they must both be in bijection with $\mathbb{N}$. So we take some bijections $k : \mathbb{N} \to S_0$ and $j : \mathbb{N} \to S_0$. Then consider the bijection $u(n) = k(n / 2)$ if $n$ is even, $u(n) = j((n - 1) / 2)$ if $n$ is odd. Then $u$ is a bijection, and $g \circ u = h$.
Suppose only one is finite: WLOG, take $S_0$ finite and $S_1$ infinite. Then take $m \in \mathbb{N}$ and bijections $k : \{n \in \mathbb{N} | n < m\} \to S_0$ and $j : \mathbb{N} \to S_1$. Define the bijection $u(n) = k(n)$ if $n < m$, $u(n) = k(n - m)$ if $n \geq m$. Then $g \circ u$ is a monotonically increasing function $\mathbb{N} \to \{0, 1\}$.
I'll leave it as an exercise to show that this is the only member of the representative set equivalent to $g$. Hint: if $(k, g) \in S$, then consider $|k^{-1}(\{i\})|$ for $i = 0, 1$.