14
$\begingroup$

I noticed that the exponentiation identity $$\exp(r + s) = \exp(r) \cdot \exp(s)~,$$ which is of course completely standard for real or complex numbers also holds in a Boolean setting.

That is, when I associate

  • addition ($+$) with disjunction ($\vee$) (as is standard),

  • multiplication ($\:\cdot\:$) with conjunction ($\wedge$) (as is also standard),

  • and exponentiation ( $\exp(\,-\,)$ ) with negation ( $\neg$ ),

then the exponentiation identity becomes De'Morgans law: $$\neg(r \vee s) \equiv \neg r \wedge \neg s$$

I'm pretty sure this holds in Heyting algebras as well. Is this very well known? Is there something deeper behind this analogy? Or is it completely obvious? Is negation the exponentiation of logic? Or is the above a mere coincidence with no deeper meaning?

$\endgroup$
7
  • 8
    $\begingroup$ Well the fact that the other De Morgan's law says $\neg$ also changes $\wedge$ to $\vee$ makes me suspicious there is anything too useful to this analogy... $\endgroup$ Commented May 28 at 22:39
  • $\begingroup$ I thought about that too. Intuitively, it would render logarithm and exponentiation both to be the negation, which is of course strange. But I was wondering whether one could use the analogy to define a "negation" of sorts in more general complete lattices. $\endgroup$
    – blk
    Commented May 28 at 22:54
  • 5
    $\begingroup$ De Morgan's laws express the logical duality of $\wedge$ and $\vee$, with much of the power coming from the fact that the double-dual brings you back. But that's not true for this exponential duality. So it isn't really a duality I think. $\endgroup$ Commented May 28 at 22:59
  • $\begingroup$ I see your point. I want to raise one more defense argument: It could be that I don't really need double negation but negation and some conegation to come back? And in the Boolean case negation and conegation happen to coincide. Also: For Heyting, double negation does not bring me back. Yet, De Morgan holds. $\endgroup$
    – blk
    Commented May 28 at 23:06
  • 8
    $\begingroup$ You can do more generally binary exponential: interpreting $a^b$ in propositional logic as $b\to a$, you have the identity $a^{b+c}=a^ba^c$ as well as $a^0=1$, $a^1=a$, and $a^{bc}=(a^b)^c$. These hold in Heyting algebras as well. In fact, they hold in all residuated lattices, except that each then holds for a different conjunction (we have $(b\lor c)\to a=(b\to a)\land(c\to a)$, but $(b\cdot c)\to a=b\to(c\to a)$). (If $\cdot$ is not commutative, then my notation is probably off.) $(b\cdot c)\to a=b\to(c\to a)$ is indeed the defining property of residuation. $\endgroup$ Commented May 29 at 6:03

3 Answers 3

14
$\begingroup$

Is there something deeper behind this analogy?

If you have a bijection $\beta\colon X\to Y$, then to every operation on $X$ there is a ($\beta$-)conjugate operation on $Y$. Namely, if $f\colon X^k\to X$ is an operation on $X$, then ${}^{\beta}f:=\beta\circ f\circ \beta^{-1}$ is the conjugate operation on $Y$. If $\mathbb X=\langle X; f_1,f_2,\ldots\rangle$ is an algebraic structure and $\mathbb Y=\langle Y; f_1,f_2,\ldots\rangle$ is the structure of the same signature where the operations are interpreted so that $f_i^{\mathbb Y} = {}^{\beta}(f_i^{\mathbb X})$, then $\beta\colon \mathbb X\to \mathbb Y$ is an isomorphism. Every isomorphism $\beta\colon \mathbb X\to \mathbb Y$ can be viewed as a statement that the interpretation of the operations on the codomain structure are the $\beta$-conjugates of the interpretations of the operations on the domain structure.

The identity $\textit{exp}(x+y)=\textit{exp}(x)\cdot \textit{exp}(y)$ communicates that the bijection $\textit{exp}\colon \mathbb R\to \mathbb R^+$ is an isomorphism from the structure $\langle \mathbb R; +\rangle$ to the structure $\langle \mathbb R^+;\cdot\rangle$. This bijection realizes multiplication on $\mathbb R^+$ as the operation that is ($\textit{exp}$-)conjugate to addition on $\mathbb R$. Similarly, the negation operation on a Boolean algebra $B$ is a bijection $\neg\colon B\to B$ that realizes meet as the conjugate of join, join as the conjugate of meet, negation as its own conjugate, etc.

I would say that your observation is this: bijections lead to relations expressing conjugacy. That is, the assertion that ''$\textit{exp}\colon \mathbb R\to \mathbb R^+$ is a bijection and $\textit{exp}(x+y)=\textit{exp}(x)\cdot \textit{exp}(y)$ holds'' contains the same information as the statement that ''$\textit{exp}\colon \mathbb R\to \mathbb R^+$ is a bijection and multiplication on $\mathbb R^+$ is the $\textit{exp}$-conjugate of addition on $\mathbb R$''. Both of these are saying only that ''$\textit{exp}\colon \langle \mathbb R; +\rangle\to\langle \mathbb R^+;\cdot\rangle$ is an isomorphism''.

$\endgroup$
5
  • $\begingroup$ Is there a reason why you use \textit{exp} instead of \exp? $\endgroup$ Commented May 30 at 20:03
  • $\begingroup$ With 3\exp4 you see $3\exp4,$ with some space between $\exp$ and the two numerals, and with 3\exp(4) you see $3\exp(4),$ with a smaller amount of space to the right of $\exp,$ and with 3\textit{exp}4 you see $3\textit{exp}4,$ without proper horizontal spacing. $\endgroup$ Commented May 30 at 20:06
  • $\begingroup$ @MichaelHardy: I write \textit{exp} because I want the letters e-x-p written in italic font with text spacing in math mode. I would never write 3\textit{exp}4 when I could write 3 \textit{exp}(4), which displays as $3 \textit{exp}(4)$. $\endgroup$ Commented May 30 at 22:46
  • $\begingroup$ If you write 3\textit{exp}(4), which displays as $3\textit{exp}(4)$, then it looks different from $3\operatorname{\textit{exp}}(4),$ which is coded as 3\operatorname{\textit{exp}}(4). It has proper horizontal spacing. In full-fledged LaTeX, you could put a suitable command above the \begin{document} line so that wherever you type \e within the body of the document, that's what you would get. $\endgroup$ Commented May 31 at 19:13
  • $\begingroup$ @MichaelHardy, re, in MathJax too you can, say, \DeclareMathOperator\e{\textit{exp}} (inside $ $, of course) to get the desired macro (although I agree that at least \mathit would be better). $\endgroup$
    – LSpice
    Commented Jun 1 at 23:10
13
$\begingroup$

Yes, $(r \lor s) \implies x$ and $(r \implies x) \land (s \implies x)$ are the same truth value for any truth value $x$. Thus $\implies x$ is kind of like an exponential function. The DeMorgan law you gave is the special case $x = \bot$.

They are equal because they are logically equivalent in intuitionistic logic. The fact that the second value implies the first value is known as proof by cases.

$\endgroup$
7
$\begingroup$

A way to formalize what you are noticing is the following:

So let $Q$ be a group with a single generator. Let $X$ be some set of your choice. We can then define a "blk structure" as follows:

A blk structure is a set $X$ and group $Q$ along with a set of binary associative operators $B_q: X^2 \rightarrow X $ indexed by the elements $Q$ with a transition map $T$ s.t. $T(B_q(u,v)) = B_{q+1}(T(u),T(v))$

Over the reals we have $X=\mathbb{R}$, $Q=\mathbb{Z}$, $B_q(x,y) = \text{exp}^{q}(\text{exp}^{-q}(x) + \text{exp}^{-q}(y))$, $T=\text{exp}$ (Note here $\text{exp}^q$ means the $q^{\text{th}}$ iterate of exponentiation).

To clarify then we have the following: $$\begin{array}{l} \vdots \\ B_{-1}(x,y) = \ln(e^{x}+e^{y}) \\ B_0(x,y) = x+y \\ B_1(x,y) = xy \\ B_2(x,y) = e^{\ln(x)\ln(y)} \\ \vdots \end{array} $$

And it's clear that $e^{B_q(x,y)} = B_{q+1}(e^x, e^y)$.

In formal logic we have $X = \lbrace0, 1 \rbrace $, $Q=\mathbb{Z}_2$, $B_0 = \vee, B_1 = \wedge$, and $T=\neg$. Spelled out we then have

$$ \begin{array}{l} B_0(x,y) = x \vee y \\ B_1(x,y) x \wedge y \end{array} $$

And similarly $\neg B_a(x,y) = B_{a + 1} (\neg x, \neg y)$

I'm not sure about this next part but I would hope that just like we can quotient the integers by the evens to get $\mathbb{Z}/2\mathbb{Z} = \mathbb{Z}_2$ that there might exist generally a "natural" way to quotient the $\mathbb{R}$-blk structure by some suitable relation to get the $\lbrace 0, 1 \rbrace$-blk structure of formal logic. And if you can find that construction and its "natural" you would have substantially clarified the matter.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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