# How to prove that the XOR problem for dimension d is not lineary seperable

The 2 dimensions xor problem can be converted to 4 equations which is possible to prove that are not possible to solve

  x1       x2     output
0         0         0
0         1         1
1         0         1
1         1         0

w1*0 + w2*0 <= 0
w1*0 + w2*1 > 0
w1*1 + w2*0 > 0
w1*1 + w2*1 <= 0


How can I prove that the XOR problem for dimension d is not lineary seperable? How to relate to an even d and an odd d?

I thought of the following answer: Lets observe all of the equations of the form:

0*w1 + .. + 1*wi + .. + 0*wd > 0, for each i=1..d


These equations obligate wi > 0, for each i.

Now lets take the last equation.

1*w1 + 1*w2 + ... + 1*wd <= 0 (only when d is even)


This equation force wi<=0 for all i.

So:

wi > 0, for each i.
wi<=0 for all i.


Cannot be solved because. On the odd - d case, we'll have to consider the all of the equations with 1 zero (d equations), and it will get to the same contradiction.

But - i'm not sure it's the good-practice way.

Thanks

Your answer for 2 dimensions can be true even for $$d>2$$.

Consider the vectors:
$$(1, 0, 0, ..., 0)$$
$$(0, 1, 0, ..., 0)$$
$$(1, 1, 0, ..., 0)$$

You can't have $$w1, w2$$ s.t.
$$w_1>0, w_2 >0$$
$$w_1 + w_2 \leq 0$$

edit:
this is for the equations that you posted for when $$b=0$$,
for $$b \neq 0$$, see Arthur's answer

If $$XOR_d(x_1,x_2,\ldots,x_d)$$ is the (linear) XOR function on $$d$$ variables (defined as 1 iff an odd number of the inputs are 1), then define the two functions $$f(x_1)=XOR_d(x_1,0,0,\ldots,0)=w_1x_1+a\\ g(x_1)=XOR_d(x_1,0,0,\ldots,0,1)=w_1x_1+b$$ But $$f$$ is (strictly) increasing and $$g$$ is (strictly) decreasing, which is impossible.

• I didn't understad your proof, what do you mean by first item of x1? where are the equations? Thanks – JohnSnowTheDeveloper Nov 3 '18 at 8:17