MHB Isomorphism of logic, arithmetic, and set theory

Eric2
Messages
2
Reaction score
0
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.
 
Physics news on Phys.org
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.
 
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.
 
Hi all, I've been a roulette player for more than 10 years (although I took time off here and there) and it's only now that I'm trying to understand the physics of the game. Basically my strategy in roulette is to divide the wheel roughly into two halves (let's call them A and B). My theory is that in roulette there will invariably be variance. In other words, if A comes up 5 times in a row, B will be due to come up soon. However I have been proven wrong many times, and I have seen some...
Thread 'Detail of Diagonalization Lemma'
The following is more or less taken from page 6 of C. Smorynski's "Self-Reference and Modal Logic". (Springer, 1985) (I couldn't get raised brackets to indicate codification (Gödel numbering), so I use a box. The overline is assigning a name. The detail I would like clarification on is in the second step in the last line, where we have an m-overlined, and we substitute the expression for m. Are we saying that the name of a coded term is the same as the coded term? Thanks in advance.
Back
Top