Is there a proof to explain why XOR cannot be linearly separable?

Question

Can someone explain to me with a proof or example why you can't linearly separate XOR (and therefore need a neural network, the context I'm looking at it in)?

I understand why it's not linearly separable if you draw it graphically (e.g. here), but I can't seem to find a formal proof somewhere, I wanted to try and understand it with either an equation or example written down. I'm wondering if one exists (I guess it has to do with contradictions?), but I can't seem to find it? I have seen this, but it's more a reason than a proof.

Answer 1

Before proving that XOR cannot be linearly separable, we first need to prove a lemma:

Lemma 1

Lemma: If 3 points are collinear and the middle point has a different label than the other two, then these 3 points cannot be linearly separable.

Proof: Let us label the points as point $A$, $B$, and $C$. $A$ and $C$ have the same label, and $B$ has a different label. They are all collinear with line $\mathcal{L}$.

Assume the contradiction, so a line can linearly separate $A$, $B$, and $C$. This means a line must cross between segment $AB$, and segment $BC$ to linearly separate these three points (by definition of linear separability). Let us label the point where the line crosses segment $AB$ and point $Y$, and the point where the line corsses segment $BC$ and point $Z$.

However, since segments $AB$ and $BC$ are collinear to line $\mathcal{L}$, points $Y$ and $Z$ also falls on line $\mathcal{L}$. Since only one unique line can cross 2 points, it must be that the only line that passes segments $AB$ and $BC$ and (therefore separates points $A$, $B$, and $C$) is line $\mathcal{L}$.

However, line $\mathcal{L}$ cannot linearly separate $A$, $B$, and $C$, since line $\mathcal{L}$ also crosses them. Therefore, no line exists can separate $A$, $B$, and $C$.

Main proof

Consider these 4 points that represent a XOR table. Let us label them clock-wise, so the top-left point as $A$, top-right point as $B$, bottom-right point as $C$, and bottom-left point as $D$. So $A$ and $C$ have the same label, and $B$ and $D$ have the same label. We want to show that points $A, B, C$ and $D$ cannot be linearly separable.

Assume the contradiction, and that there is a line that can separate these 4 points.

Imagine a fifth point that lies in the center, and let us label this as point $E$.

Since $E$ lies in the center, the three points $A, E$ and $C$ are collinear. Similarly, since $E$ lies in the center, the three points $B, E$ and $D$ are collinear.

Because we assume a line can linearly separate $A, B, C$ and $D$, then this line must label point $E$ as some label. If $E$ shares the same label as $A$ and $C$, then the points $B, E$ and $D$ will become "collinear points where the middle point has a different label", which by Lemma 1 cannot be linearly separable. Likewise, if $E$ shares the same label as $B$ and $D$, then the points $A, E$ and $C$ will become "collinear points where the middle point has a different label", which by Lemma 1 cannot be linearly separable.

Therefore it is impossible to give a label to $E$ while satisfying linear separability. As a result, our assumption must be false, and the four points $A, B, C$ and $D$ cannot be linearly separable.

Answer 2

Here is a similar contradiction based answer using basic coordinate geometry.

Is there a proof to explain why $XOR$ cannot be linearly separable?

Let us suppose, if possible, that the $XOR$ function, given by following table, is linearly separable. \begin{array}{|c|c|c|} \hline x& y & x \text{ xor } y\\ \hline 0&0&0\\ \hline 0&1&1\\ \hline 1&0&1\\ \hline 1&1&0\\ \hline \end{array} This ensures the existence of a line $L:ax+by+c=0$ such that the points $(0,0)$ $\&$ $(1,1)$ both lie on the same side of $L$ and the points $(0,1)$ $\&$ $(1,0)$ also lie on same side of $L$ but opposite to that of $(0,0)$ $\&$ $(1,1).$
Also from basic coordinate geometry, we know that if the points $(x_1,y_1)$ $\&$ $(x_2,y_2)$ lie on same side of a line given by $px+qy+r=0$ then, $$(px_1+qy_1+r)\cdot(px_2+qy_2+r)>0$$ and if they are on opposite sides of the line then, $$(px_1+qy_1+r)\cdot(px_2+qy_2+r)<0$$ Since $(0,0)$ and $(1,1)$ lie on same side of $L$, so \begin{equation} c\cdot(a+b+c)>0 \tag{1} \end{equation} And, as $(1,0)$ and $(1,1)$ lie on different sides of $L$, so \begin{equation} (a+c)\cdot(a+b+c)<0. \tag{2} \end{equation} Similarly as $(0,1)$ and $(1,1)$ lie on different sides of $L$, \begin{equation} (b+c)\cdot(a+b+c)<0 \tag{3} \end{equation} On adding equations $(2)$ and $(3)$ we get, $$(a+b+2c)\cdot(a+b+c)<0$$ $$\implies (a+b+c)\cdot(a+b+c)+c\cdot(a+b+c)<0$$ $$\implies (a+b+c)^2+c\cdot(a+b+c)<0$$ Since $(a+b+c)^2\geq0$ for any choice of numbers $a,b,c,$ so $$c\cdot(a+b+c)<-(a+b+c)^2\leq0$$ $$c\cdot(a+b+c)<0$$ which is a contradiction of equation $(1)$, proving the non-existence any such line $L.$

The $XOR$ function is not linearly separable.