Skip to main content
added 127 characters in body
Source Link
Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114

Do there exist "nice" (maybe analytic?) functions $f_0,f_1:\mathbb R \to \mathbb R$ such that

$\forall n\in\mathbb N,\forall \sigma\in\{0,1\}^n,\exists x\in\mathbb R, \forall \tau\in\{0,1\}^n, (\tau\ne \sigma \to (f_\sigma(x)>f_\tau(x))$ ?

Here, for $\sigma,\tau\in\{0,1\}^*$, concatenation is composition: $f_{\sigma \tau}=f_\sigma\circ f_\tau$.

For example, if $f_0(x)=ax+b$ and $f_1(x)=cx+d$ then $$f_{01}(x)=a(cx+d)+b=acx + (ad+b)$$ $$f_{10}(x)=c(ax+b)+d=acx + (bc+d)$$ $$f_{00}(x)=a(ax+b)+b=a^2 x + (ab+b)$$ $$f_{11}(x)=c(cx+d)+d=c^2 x + (cd+d)$$ For $\sigma=01$ we would need $ad+b>bc+d$ and an $x$ with $$acx + ad > a^2 x + ab,$$ $$acx + (ad+b) > c^2 x + (cd+d).$$ Such $a,b,c,d$ could surely be found for this $\sigma$For example, $d=0$, $a=c<0$, $b>0$ suffices. On On the other hand, surely no $a,b,c,d$ work for all $\sigma$.

But what if $f_0,f_1$ can be rather arbitrary functions?

Do there exist "nice" (maybe analytic?) functions $f_0,f_1:\mathbb R \to \mathbb R$ such that

$\forall n\in\mathbb N,\forall \sigma\in\{0,1\}^n,\exists x\in\mathbb R, \forall \tau\in\{0,1\}^n, (\tau\ne \sigma \to (f_\sigma(x)>f_\tau(x))$ ?

Here, for $\sigma,\tau\in\{0,1\}^*$, concatenation is composition: $f_{\sigma \tau}=f_\sigma\circ f_\tau$.

For example, if $f_0(x)=ax+b$ and $f_1(x)=cx+d$ then $$f_{01}(x)=a(cx+d)+b=acx + (ad+b)$$ $$f_{10}(x)=c(ax+b)+d=acx + (bc+d)$$ $$f_{00}(x)=a(ax+b)+b=a^2 x + (ab+b)$$ $$f_{11}(x)=c(cx+d)+d=c^2 x + (cd+d)$$ For $\sigma=01$ we would need $ad+b>bc+d$ and an $x$ with $$acx + ad > a^2 x + ab,$$ $$acx + (ad+b) > c^2 x + (cd+d).$$ Such $a,b,c,d$ could surely be found for this $\sigma$. On the other hand, surely no $a,b,c,d$ work for all $\sigma$.

But what if $f_0,f_1$ can be rather arbitrary functions?

Do there exist "nice" (maybe analytic?) functions $f_0,f_1:\mathbb R \to \mathbb R$ such that

$\forall n\in\mathbb N,\forall \sigma\in\{0,1\}^n,\exists x\in\mathbb R, \forall \tau\in\{0,1\}^n, (\tau\ne \sigma \to (f_\sigma(x)>f_\tau(x))$ ?

Here, for $\sigma,\tau\in\{0,1\}^*$, concatenation is composition: $f_{\sigma \tau}=f_\sigma\circ f_\tau$.

For example, if $f_0(x)=ax+b$ and $f_1(x)=cx+d$ then $$f_{01}(x)=a(cx+d)+b=acx + (ad+b)$$ $$f_{10}(x)=c(ax+b)+d=acx + (bc+d)$$ $$f_{00}(x)=a(ax+b)+b=a^2 x + (ab+b)$$ $$f_{11}(x)=c(cx+d)+d=c^2 x + (cd+d)$$ For $\sigma=01$ we would need $ad+b>bc+d$ and an $x$ with $$acx + ad > a^2 x + ab,$$ $$acx + (ad+b) > c^2 x + (cd+d).$$ For example, $d=0$, $a=c<0$, $b>0$ suffices. On the other hand, surely no $a,b,c,d$ work for all $\sigma$.

But what if $f_0,f_1$ can be rather arbitrary functions?

edited tags
Link
Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114
Source Link
Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114

Functions representing all strings somewhere

Do there exist "nice" (maybe analytic?) functions $f_0,f_1:\mathbb R \to \mathbb R$ such that

$\forall n\in\mathbb N,\forall \sigma\in\{0,1\}^n,\exists x\in\mathbb R, \forall \tau\in\{0,1\}^n, (\tau\ne \sigma \to (f_\sigma(x)>f_\tau(x))$ ?

Here, for $\sigma,\tau\in\{0,1\}^*$, concatenation is composition: $f_{\sigma \tau}=f_\sigma\circ f_\tau$.

For example, if $f_0(x)=ax+b$ and $f_1(x)=cx+d$ then $$f_{01}(x)=a(cx+d)+b=acx + (ad+b)$$ $$f_{10}(x)=c(ax+b)+d=acx + (bc+d)$$ $$f_{00}(x)=a(ax+b)+b=a^2 x + (ab+b)$$ $$f_{11}(x)=c(cx+d)+d=c^2 x + (cd+d)$$ For $\sigma=01$ we would need $ad+b>bc+d$ and an $x$ with $$acx + ad > a^2 x + ab,$$ $$acx + (ad+b) > c^2 x + (cd+d).$$ Such $a,b,c,d$ could surely be found for this $\sigma$. On the other hand, surely no $a,b,c,d$ work for all $\sigma$.

But what if $f_0,f_1$ can be rather arbitrary functions?