Isomorphism of logic, arithmetic, and set theory

[Eric2]

Has anybody ever heard of this? I learned about it in a discrete math class in grad school, and I've never heard of it anywhere else !?

For example, logical disjunction (OR) and set-theoretic UNION are isomorphic in this sense:

0 OR 0 = 0.
{0} UNION {0} = {0}.

Similarly, logical AND & set theoretic INTERSECTION are isomorphs:
0 AND 0 = 0.
{0} INTERSECTION {0} = {0}.

Anyway,, has anybody ever heard of this? I'm trying to figure out how the isomorphism comprises arithmetic also, whereby in a computer's hardware,
arithmetic is computed on logic circuitry
and equivalently
logic is computed on arithmetic circuitry.

Thanks.

 

[Olinguito]

Hi Eric.

Well, we have
$$x\in A\cup B\ \iff\ (x\in A)\vee(x\in B) \\ x\in A\cap B\ \iff\ (x\in A)\wedge(x\in B)$$
don’t we? If you define “$x\in A$” as having the value $1$ and “$x\notin A$” as having the value $0$, then you have the same tables for $A\cup B$ and $A\cap B$ as the truth tables for the logical propositions $p\vee q$ and $p\wedge q$:
$$\begin{array}{|c|c|c|c|c|c|}\hline A & A\cup B & B &{}& p & p\vee q & q \\ \hline 0\,(\notin) & 0\,(\notin) & 0\,(\notin) &{}& 0\,(\rm F) & 0\,(\rm F) & 0\,(\rm F) \\ \hline 0\,(\notin) & 1\,(\in) & 1\,(\in) &{}& 0\,(\rm F) & 1\,(\rm T) & 1\,(\rm T) \\ \hline 1\,(\in) & 1\,(\in) & 0\,(\notin) &{}& 1\,(\rm T) & 1\,(\rm T) & 0\,(\rm F) \\ \hline 1\,(\in) & 1\,(\in) & 1\,(\in) &{}& 1\,(\rm T) & 1\,(\rm T) & 1\,(\rm T) \\ \hline\end{array}$$
$$\begin{array}{|c|c|c|c|c|c|}\hline A & A\cap B & B &{}& p & p\wedge q & q \\ \hline 0\,(\notin) & 0\,(\notin) & 0\,(\notin) &{}& 0\,(\rm F) & 0\,(\rm F) & 0\,(\rm F) \\ \hline 0\,(\notin) & 0\,(\notin) & 1\,(\in) &{}& 0\,(\rm F) & 0\,(\rm F) & 1\,(\rm T) \\ \hline 1\,(\in) & 0\,(\notin) & 0\,(\notin) &{}& 1\,(\rm T) & 0\,(\rm F) & 0\,(\rm F) \\ \hline 1\,(\in) & 1\,(\in) & 1\,(\in) &{}& 1\,(\rm T) & 1\,(\rm T) & 1\,(\rm T) \\ \hline\end{array}$$
Certainly union/intersection of sets and disjunction/conjunction of logical propositions have a number of parallel properties. For example, each is distributive over the other:
$$\begin{array}{ccc} A\cap(B\cup C) = (A\cap B)\cup(B\cap C) &;& p\wedge(q\vee r) = (p\wedge q)\vee(q\wedge r) \\ A\cup(B\cap C) = (A\cup B)\cap(B\cup C) &;& p\vee(q\wedge r) = (p\vee q)\wedge(q\vee r)\end{array}$$
(which is not the same as for $+$ and $\times$, where the latter is distributive over the former but not the other way round).

They also obey De Morgan’s laws:
$$\begin{array}{ccc} \overline{A\cup B}=\overline A\cap\overline B &;&\neg(p\vee q) = (\neg p)\wedge(\neg q) \\ \overline{A\cap B}=\overline A\cup\overline B &;& \neg(p\wedge q) = (\neg p)\vee(\neg q)\end{array}$$
where the overline denotes set complement.

I suppose you just need to define the isomorphism precisely. I suspect we are into category theory here, the isomorphism being between the category of sets and the category of logical propositions.

 

[Eric2]

That was very helpful.

Basically, what I'm trying to do is refute a published position that logical disjunction and conjunction are computationally interchangeable, with the only meaningful distinction arising from subjective observer interpretation.

I believe this is wrong and strongly suspect that they are referring to the computational equivalence/isomorphism of logic and arithmetic -- since in a computer's ALU, arithmetic operations are performed on logic gates, which is the same as logic operations being performed on arithmetic gates.

Here's the catch. In formulating isomorphism between logic and arithmetic, I've been able to do so for conjunction/multilplication and (I think) for negation/unary-minus. But not for disjunction/addition !

Here's why. For all four instances of diadic boolean disjunction, I get a normal result. But for binary addition, I get a normal, single-bit result for all cases EXCEPT 1 + 1, which yields the two-bit result 10 (i.e., binary 2).

I can't seem to make this fit the larger pattern. Taking only the low-order bit of the sum yields 0 for 1 + 1, which doesn't correspond to disjunction of 1 OR 1, which is 1.

High-order bit doesn't work either -- just a logical AND.

All I can think of is a "notches-on-a-stick" data structure for addition, which does yield the correct answer in the low-order notch.

I am confused and hope I explained it clearly.

Thanks for your help with this.