Consider a perceptron $F(x) = \phi(x \* w - b), \ x \in \mathbb{R}^n,$ (with Heaviside activation function $\phi$) and a dataset consisting of a finite subset $\Omega \subseteq \mathbb{R}^n$ with labels $y: \Omega \rightarrow \{0, 1\}$. Clearly, $F$ can fit the dataset exactly (in the sense that there are $w$ and $b$ such that $F(x) = y(x)$ for each $x \in \Omega$) if and only if the sets $y^{-1}(0)$ and $y^{-1}(1)$ can be separated by an affine hyperplane. 


The question is: if we consider a multilayer perceptron with $2$ layers instead: 
$$F(x)= \phi(a\*w -b), \ a\_i= \phi(w\_i\*x - b\_i)$$
can it fit exactly an arbitrary labeled dataset $y: \Omega \rightarrow \{0,1\}$ (for an appropriate choice of $w$, $w\_i$'s, $b$, $b\_i$'s)? 


The question is related (but quite different) to the Universal Approximation Theorem: we know that a 2-layer perceptron with continuous activation can approximate any continuous function. In our setting we have discontinuous activation and we want to fit exactly (not just aproximate) a function defined on a finite subset. 


Thank you very much for your help. 



Can a Multilayer Perceptron fit any binary function?
Denote the points in $\Omega$ as $\omega\_i$, $1\leq i \leq m$. 


As every finite point set has an extreme point, it is possible to arrange the points in an order such that $\omega\_i$ is separable from $\omega\_{i+1},\omega\_{i+2},...,\omega\_{m}$ by a hyperplane. 


In other words, there exists $a\_i=ϕ(w\_i∗x−b\_i)$ for $1\leq i \leq m$ where $a\_i(\omega\_i)=1$ and $a\_i(\omega\_k)=0$ for $k>i$.


Assign weights $\epsilon\_i2^{m-i}$ to $a\_i$ where $\epsilon\_i=-1$ or $1$ according to the label $y\_i=1$ or $0$, respectively. 


Let $b=0$.


It is easy to check the construction works: the output depends on the first $i$ such that $a\_i\neq0$, and the values of $a\_k$ for $k>i$ does mot matter. 


