# How to prove that linear functions cannot represent binary functions

Yesterday, I thought about representing boolean algebra as linear functions:

For some vector space $V$ and for some $A, B \subset V$ such that $A \ne \emptyset \,\wedge\, B \ne \emptyset \,\wedge\, A \cap B = \emptyset$, can a linear map $f: V \times V \rightarrow V$ exist which satisfies all of the following?

• $\forall x \in A\, \forall y \in A,\, f(x, y) \in B$
• $\forall x \in A\, \forall y \in B,\, f(x, y) \in A$
• $\forall x \in B\, \forall y \in A,\, f(x, y) \in A$
• $\forall x \in B\, \forall y \in B,\, f(x, y) \in A$

So this function basically imitates NOR (or NAND) function, and since every boolean functions can be represented by combinations of NORs, so if this function exists for some $V$, $A$ and $B$, all boolean functions can represented by a linear map (there is a "true set" $A$, "false set" $B$, and a linear map $f$ like above). (And trivially the converse holds.)

Of course I highly doubt that boolean algebra can be represented by a linear map, but how can I prove that it is impossible?

I think "NAND is not linear" is not enough; since even though NOT($\neg$) is not a linear map ($\neg 0 = 1$), this question

For some vector space $V$ and for some $A, B \subset V$ such that $A \ne \emptyset \,\wedge\, B \ne \emptyset \,\wedge\, A \cap B = \emptyset$, can a linear map $f: V \rightarrow V$ exist which satisfies all of the following?

• $\forall x \in A,\, f(x) \in B$
• $\forall x \in B,\, f(x) \in A$

does have a solution $V = \mathbb{R}^1$, $A = (1, \infty)$, $B = (-\infty, 1)$, and $f:x \mapsto -x$. (Of course any $A \subseteq (0, \infty)$ and $B = -A$ will work.)

If you allow for infinite-dimensional spaces, there is a simple "enveloping" solution (I mean it in analogy with Lie algebra theory) as I explain below.

The really interesting question is of course whether there is a finite- dimensional solution.

Lemma Let ${\cal N}=\lbrace 1,2,3, \ldots, \rbrace$. Then there is a bijection $g:{\cal N}^2 \to {\cal N} \setminus \lbrace 1 \rbrace$ satisfying $g(x,y)>{\sf max}(x,y)$ for any $x,y$.

Proof of lemma You can take, for example Cantor’s bijection

$$g(x,y)=\left\lbrace\begin{array}{lcl} x+(y-1)^2+1 & \rm if & x < y, \\ x^2-x+y+1 & \rm if & x \geq y. \end{array}\right.$$

Once we have a $g$ as in the lemma, it is straightforward to see by induction that there is a unique "truth map" $t:{\cal N} \to \lbrace {\sf True},{\sf False} \rbrace$ such that $t(1)={\sf True}$ and $t(g(x,y))=NAND(t(x),t(y))$ for any $x,y\in{\cal N}$.

Then, if $V$ is a vector space with countable basis $(v_{k})_{k\in{\cal N}}$, you can put $A=\lbrace v_k \ \big| \ t(k)={\sf True}\rbrace$, $B=\lbrace v_k\ \big| \ t(k)={\sf False}\rbrace$, and $f$ defined by $f(v_x \otimes v_y)=v_{g(x,y)}$.