 Nico Patterson

2022-11-11

Representative Set for Relation S on $\mathbb{N}\to \left\{0,1\right\}$ s.t. $⟨f,g⟩\in S\phantom{\rule{thickmathspace}{0ex}}⟺\phantom{\rule{thickmathspace}{0ex}}\mathrm{\exists }$ bijection $h:\mathbb{N}\to \mathbb{N}$ s.t.$f=g\circ h$
Problem: Define a relation S on $\mathbb{N}\to \left\{0,1\right\}$ as follows:$⟨f,g⟩\in S\phantom{\rule{thickmathspace}{0ex}}⟺\phantom{\rule{thickmathspace}{0ex}}$ there exists a bijection $h:\mathbb{N}\to \mathbb{N}$ s.t. $f=g\circ h$.
S is an equivalence relation on $\mathbb{N}\to \left\{0,1\right\}$ (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×X$ is an equivalence relation over X. will be called a Representative set of T, if it occurs that: $\mathrm{\forall }x\in X.|\left[x{\right]}_{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}\left(n\right)=0,{f}_{2}\left(n\right)=1,{f}_{3}\left(n\right)=\left\{\begin{array}{ll}0& \text{n=0}\\ 1& \text{else}\end{array}$, ${f}_{4}\left(n\right)=\left\{\begin{array}{ll}0& n\in {\mathbb{N}}_{even}\\ 1& n\in {\mathbb{N}}_{odd}\end{array},\mathrm{\forall }n\in \mathbb{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? lelestalis80d

Expert

Step 1
A representative set would be $\left\{f:\mathbb{N}\to \left\{0,1\right\}|f$ is monotonic $\right\}\cup \left\{h\right\}$, where h(n) is defined s.t. $h\left(n\right)\equiv n\phantom{\rule{0.667em}{0ex}}\mathrm{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}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 \left\{0,1\right\}$. Consider ${S}_{i}={g}^{-1}\left(i\right)$ 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 N. So we take some bijections $k:\mathbb{N}\to {S}_{0}$ and $j:\mathbb{N}\to {S}_{0}$. Then consider the bijection $u\left(n\right)=k\left(n/2\right)$ if n is even, $u\left(n\right)=j\left(\left(n-1\right)/2\right)$ if n is odd. Then u is a bijection, and $g\circ u=h$.
Step 2
Suppose only one is finite: WLOG, take ${S}_{0}$ finite and ${S}_{1}$ infinite. Then take $m\in \mathbb{N}$ and bijections $k:\left\{n\in \mathbb{N}|n and $j:\mathbb{N}\to {S}_{1}$. Define the bijection $u\left(n\right)=k\left(n\right)$ if $n, $u\left(n\right)=k\left(n-m\right)$ if $n\ge m$. Then $g\circ u$ is a monotonically increasing function $\mathbb{N}\to \left\{0,1\right\}$.
I'll leave it as an exercise to show that this is the only member of the representative set equivalent to g. Hint: if $\left(k,g\right)\in S$, then consider $|{k}^{-1}\left(\left\{i\right\}\right)|$ for $i=0,1$.

Do you have a similar question?