How do you mathematically prove that boosting cannot have zero error in training set arranged in a square with the corners labeled plus and minus? I have the following data:

Say we want to perfectly separate those points using only an ensemble of horizontal and vertical decision stumps. Maybe using Boosting or Adaboost, but the main point is any ensemble with coordinate wise weighted stumps.
It seems intuitively "obvious" that this particular data set cannot be separated using only stumps. However, I cannot convince myself with a mathematically rigors proof of this. How would one go about proving rigorously such a claim?
I was wondering, if there was also a generalization of the number of points we require to have until ensemble of stumps start to fail to separate the data perfectly. When does this happen and what its proof?
 A: On this dataset, there are four nontrivial things that a stump could do:


*

*$s_1$ classifies the left two points as positive;

*$s_2$ classifies the right two points as positive;

*$s_3$ classifies the top two points as positive;

*$s_4$ classifies the bottom two points as positive.


So the function you end up learning could be anything of the form $$\hat y(x) = \sum_{i=1}^n f_i(x),$$ where each $f$ is one of the $s_j$.
Now, note that each copy of $s_1$ in that sum cancels out a copy of $s_2$, because they're opposite, and similarly for $s_3$ and $s_4$. So $\hat y$ is really an integer combination $\hat y(x) = a\,s_1(x) + b\,s_3(x)$.
But the first half of that expression doesn't change when you move from top to bottom, and the second half always changes by the same amount ($b$). So we know that the output of $\hat y$ must either always increase as the datapoint moves from top to bottom (if $b < 0$), or always decrease (if $b > 0$).


*

*If it always increases when moving from top to bottom, then it can't get both the top-left and bottom-left points correct (because the top one is greater than 0 and the bottom one is less than 0).

*If it always decreases, then similarly it can't get both the top-right and bottom-right points correct.
Therefore, no possible sum of boosted stumps can classify the dataset perfectly, QED.
(EDIT: I made the proof more understandable. The previous one was true, but didn't provide much intuition, and I figured out a way to do the intuitive thing without too much case analysis.)
