2
$\begingroup$

In this video on category theory (Curry-Howard-Lambek Isomorphism), the tutor states that there is a 1 to 1 correspondence with boolean logic.

My question, then, is how would the NOT function be represented in the category of sets?

From my understanding, there could be no morphism between the two sets as no element used in A is used in ¬A. Is it as simple as ignoring the set contents, or do you need a function to the local universal set U, followed by a contra-variant (co) function to the opposite set ¬A?

Thanks in advance.

EDIT:

To clarify, I am after the category theory representation of the complement (NOT) function from set theory.

Apologies for any misunderstanding.

$\endgroup$
13
  • $\begingroup$ Not $A$ would correspond to the compliment of $A$ $\endgroup$
    – Doug M
    Jul 12, 2017 at 20:34
  • $\begingroup$ @DougM Are you saying that to perform the function NOT from a category theory perspective, I would forget about the contents of all of the sets and just consider their names? If so, then I am somewhat confused as to when this forgetfulness should occur. Thanks for your quick reply. $\endgroup$ Jul 12, 2017 at 20:36
  • $\begingroup$ $A\subset X, A' = X-A, A\cap A' = \emptyset, A\cup A' = X.$ $\endgroup$
    – Doug M
    Jul 12, 2017 at 20:40
  • $\begingroup$ $\operatorname{Not}A$ is equivalent to $A\Rightarrow \bot$. So in the category of Sets, $\operatorname{Not}A$ is represented by the set of maps $A\rightarrow\emptyset$. $\endgroup$
    – Roland
    Jul 12, 2017 at 21:46
  • $\begingroup$ @Roland I'm not sure what the symbol ⊥ means, could you clarify? So you're saying there is no direct morphism between A and ¬A in the category of sets? Rather, a constant morphism maps A to the initial object , followed by a dual morphism over to the set ¬A? Or am I still missing something? $\endgroup$ Jul 12, 2017 at 22:09

3 Answers 3

3
$\begingroup$

So my comments start to be a little long, here is a summary of what I said.

The video is about the Curry-Howard-Lambek isomorphism. From what I read in your comments, there seems to be a confusion on the context of this isomorphism.

Indeed, while learning elementary set theory, students meet a first correspondence between sets and propositions. This is not what is called the Curry-Howard-Lambek isomorphism. This correspondence is based on the following : if $\mathcal{P}(x)$ is a proposition with a free variable $x$ which can take value in a universe $U$, you can form the set $A=\{x\in U, \mathcal{P}(x)\}$ of all elements $x$ of the universe which satisfies the property $\mathcal{P}(x)$. Every logical operators (AND, OR, IMPLIES, NOT...) have a counterpart with the corresponding sets.

I insist : this is not the topic of the linked video. The Curry-Howard-Lambek isomorphism is more about proofs. The point is that the basic rule of logical deductions are very closed the basic construction of morphism in a category. From this perspective, one can say that sets are propositions and elements of sets are "proof" of the corresponding proposition.

For instance, we have the following tautology : $A\wedge B\Rightarrow A$. I will use the same letter to write the corresponding sets. The $\wedge$ (AND) operator corresponds to the cartesian product $\times$ and the $\Rightarrow$ operator corresponds to taking the mapping set. Thus, the tautology corresponds to the set $Map(A\times B,A)$. It always has an element : the first projection. This element is "the proof" of the tautology.

Similarly, the canonical inclusion $A\rightarrow A\sqcup B$ is an element of $Map(A,A\sqcup B)$, so this is a "proof" of the tautology $A\Rightarrow A\vee B$.

You can check that the categorical constructions satisfies the same deduction rules as in logic. So for example, if you have a "proof" of $A$ and a "proof" of $B$, that is, if you have $a\in A$ and $b\in B$, well you have $(a,b)\in A\times B$ : you have a proof of $A\wedge B$.

Here is the modus ponens : if you have a proof of $A$ and a proof of $A\Rightarrow B$, you should have a proof of $B$. But a proof of $A$ is an element $a\in A$, a proof of $A\Rightarrow B$ is an element $f\in Map(A,B)$. Well the element $f(a)$ is then a proof of $B$.


Finally the question was about the categorical interpretation of NOT. In fact $\operatorname{Not}A$ is logically equivalent to $A\Rightarrow \bot$ (False). The categorical interpretation of $\bot$ is the initial object $\emptyset$. So the categorical interpretation of $\operatorname{Not}A$ is simply $Map(A,\emptyset)$.

Note that if you have a proof of $A$ (ie $a\in A$), you cannot have a map $f:A\rightarrow\emptyset$ because what can be $f(a)$ ? So $Map(A,\emptyset)$ is empty, in other words if you have a proof of $A$, then $\operatorname{Not}A$ is false.

Conversely, if $A$ is false, that is if $A=\emptyset$, then $Map(A,\emptyset)$ contains the identity. So you have a proof of $\operatorname{Not}A$. This is all good.

$\endgroup$
1
  • $\begingroup$ Perfect explanation! This makes a lot more sense now, thank you =) $\endgroup$ Jul 14, 2017 at 13:35
0
$\begingroup$

The set operator that corresponds to a logical "not" is the complement. A set A's complement is AC = U - A.

Although I'm not quite sure I understand your question, it might help to think of it this way:

A = { x ∈ U | x ∈ A }

AC = { x ∈ U | ¬(x ∈ A) }

$\endgroup$
2
  • $\begingroup$ Are you saying that to perform the function NOT from a category theory perspective, I would forget about the contents of all of the sets and just consider their names? If so, then I am somewhat confused as to when this forgetfulness should occur. Thanks for your quick reply. $\endgroup$ Jul 12, 2017 at 20:36
  • $\begingroup$ I'm new to both set and category theory, so apologies if this is obvious. The notation you're using looks like set theory. I understand how the not function works in set theory. I am unsure of how to represent this function in category theory though. Thanks again. $\endgroup$ Jul 12, 2017 at 20:43
0
$\begingroup$

Maybe this will help.

We have the set $X = \{a,b,c,d,e,f,g,h\}$

$A = \{a,b,c,h\}$

And $A\subset X$

All of the elements in the algebra are members of the power set of $X$

If we could write this $A$ as $(11100001)$ with a 1 in the first spot if $a\in A$ and a zero, otherwise.

if $B = \{c,d,f,h\} \cong (00110101)$

$A\cup B = \{a,b,c,d,f,h\} \cong (11110101) = A\lor B\\ A\cap B = \{c,h\} \cong (00100001) = A\land B$

What about $\neg A?$

$A' = X - A = \{d,e,f,g\} \cong (00011110) = \neg A$

$A\cup A' = X \cong (11111111)\\ A\cap A' = \emptyset \cong (00000000)$

After re-reading your question, you are looking for the relation of Boolean algebra to Category theory, not set theory...

My knowledge of category theory is sparse. Sorry.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .