2
$\begingroup$

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.)

$\endgroup$
3
$\begingroup$

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)}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.