Nico Patterson

Answered

2022-11-11

Representative Set for Relation S on $\mathbb{N}\to \{0,1\}$ s.t. $\u27e8f,g\u27e9\in S\phantom{\rule{thickmathspace}{0ex}}\u27fa\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 \{0,1\}$ as follows:$\u27e8f,g\u27e9\in S\phantom{\rule{thickmathspace}{0ex}}\u27fa\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 \{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. $\text{}\text{}A\subseteq X$ will be called a Representative set of T, if it occurs that: $\mathrm{\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{array}{ll}0& \text{n=0}\\ 1& \text{else}\end{array}$, ${f}_{4}(n)=\{\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?

Problem: Define a relation S on $\mathbb{N}\to \{0,1\}$ as follows:$\u27e8f,g\u27e9\in S\phantom{\rule{thickmathspace}{0ex}}\u27fa\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 \{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. $\text{}\text{}A\subseteq X$ will be called a Representative set of T, if it occurs that: $\mathrm{\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{array}{ll}0& \text{n=0}\\ 1& \text{else}\end{array}$, ${f}_{4}(n)=\{\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?

Answer & Explanation

lelestalis80d

Expert

2022-11-12Added 23 answers

Step 1

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\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 \{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 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$.

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:\{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\ge 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$.

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\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 \{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 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$.

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:\{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\ge 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$.

Most Popular Questions