Vtyjkyuk

Suppose $f$ is an arbitrary binary function and it is given to us:
$$
f: mathbbR^d rightarrow 0, 1
$$
Prove that it is always possible to write this function, as a composition of two functions:

1. A continuous function: $g: mathbbR^d rightarrow (0, 1) $


2. A thresholding function: $h: (0, 1) rightarrow 0, 1$, e.g. $h(x) = 0.5 + 0.5 sgn(x - 0.5)$

such that: $ forall X in mathbbR^d : ; ; ; f(x) = h(g(x))$.

If there is any requirement needed to have such decomposition, please state it.

Let's say the threshold is $t$, and that $h(x)=1$ when $x> t$ and $h(x)=0$ when $xle t$. The other possibility is to have $h(x)=1$ for $xge t$ instead, I will deal with this at the end.

If $f=hcirc g$, then $f^-1(1)=g^-1(h^-1(1))=g^-1((t,1))$. Since $g$ is continuous and $(t,1)$ is open, this implies $f^-1(1)$ is an open set. This gives a necessary condition for the decomposition to exist; $f^-1(1)$ must be open.

This condition is also sufficient. If $f^-1(1)$ is open, then $C:= f^-1(0)$ is closed. Let $d:mathbb R^nto mathbb R$ be defined by
$$
d(x)= textdist(x,C)=inf_cin C|x-c|
$$
Since $C$ is closed, it follows $d(x)=0$ if and only if $xin C$. Therefore, letting $$g(x)=frac12 + frac12cdot fracd(x)1+d(x),$$
then $g(x)=frac12$ when $xin C$, while $g(x)>frac12$ when $xnotin C$. This means that letting $h(x)=1$ when $x>frac12$ and $h(x)=0$ when $xle frac12$, then $f=hcirc g$.

If you use the other type of threshold function, where $h(x)=1$ for $xge t$, then you instead get the necessary condition that $f^-1(1)$ must be closed, but otherwise the same logic works. That is, the condition you need is that $f^-1(1)$ is either open or closed.