# Connection between logic and set theory?

I just noticed there is a similarity between logic operations on propositions and the operations of set theory. It seems:

$$\begin{array}{llll} \textrm{disjunction} & (-)\vee (-)& \textrm{corresponds to union}& (-)\cup (-)\\ \textrm{conjunction} & (-) \wedge (-)& \textrm{correspons to intersection} & (-)\cap (-)\\ \textrm{negation} & \sim (-) & \textrm{correspons to taking complements} & c(-), \end{array}$$ and I conjecture:

$$\begin{array}{lll} \textrm{conditional} & (-)\rightarrow (-) & \textrm{corresponds to inclusion} & \subset\\ \textrm{biconditional} & (-)\leftrightarrow (-) & \textrm{corresponds to equality} & = \end{array}$$

How far does it go? I believe there is some kind of functor between some category whose objects are propositions and the category of sets, is that right?

Thanks

• The category of sets deals with functions from one set to another. What will be the arrows in your proposed category where the objects are propositions? Summary: Yes, there is a parallel here, but you should not bring in categories. – GEdgar Mar 21 '19 at 12:57
• For conenctio, see Boolean algebra as well as The Mathematics of Boolean Algebra. – Mauro ALLEGRANZA Mar 21 '19 at 13:11
• See also The Algebra of Logic Tradition for historical development. – Mauro ALLEGRANZA Mar 21 '19 at 13:12
• The parallel between $\to$ and $\subseteq$ is not quite direct. Note that $\to$ combines two propositions into a proposition that you can use with further logical symbols, whereas $\subseteq$ combines two set expressions into a proposition. So whereas you can say $A\land(B\to C)$ in logic, you cannot meaningfully say $A\cap(B\subseteq C)$ in set algebra. (Similarly for $\leftrightarrow$ versus $=$). – hmakholm left over Monica Mar 21 '19 at 15:54
• The simplest connection is to identify each set $S$ with the proposition $a\in S$ for some constant $a$, or each proposition $p$ with the set of conditions under which it's true. There's also another natural concept for analysing propositions. – J.G. Mar 21 '19 at 15:55

## 3 Answers

"How far does it go ?" : as far as it can get !

Here's a general idea about how set theory is a semantics for classical propositional logic (note that if we change the formal system we're looking at without changing our assumptions on sets, for instance if we're studying intuitionistic logic from a classical point of view, then we have to take another semantics, in this specific case, topological spaces can be appropriate) :

Suppose you have a set of propositional variables $$V$$, a "global" set $$E$$, and a function $$[-] :V\to \mathcal{P}(E)$$. Then you can build a function that goes from the set $$\mathrm{Form}$$ of formulas to $$\mathcal{P}(E)$$ by expanding $$[-]$$ according to the rules you displayed : if $$\varphi, \psi$$ are formulas and you already defined $$[\varphi]$$ and $$[\psi]$$, then define $$[\varphi \land \psi] = [\varphi]\cap [\psi]$$, similarly for $$\lor, \neg$$, and define $$[\varphi\implies \psi]$$ as $$\{x\in E\mid x\in [\varphi]\implies x\in[\psi]\}$$.

These rules allow you to define $$[\varphi]$$ for any formula $$\varphi$$ by induction, going from the variables and gaining complexity.

Then you can prove the following things : if $$\varphi$$ is a theorem of classical logic, then $$[\varphi] = E$$, which tells you that the set-operations behave according to the logical ones, but also you can prove : if for any $$E$$ and any $$[-] :V\to \mathcal{P}(E)$$, $$[\varphi] = E$$, then $$\varphi$$ is a theorem of classical logic ! This tells you that actually the logical operations behave just like set-theoretic operations as well.

There's actually a lot more you can say about this sort of thing (for instance : what happens if you add quantifiers ? Or in another direction what happens if we replace $$\mathcal{P}(E)$$ by some other type of object ? If we completely change the type of object, what kind of logic do we get ? etc. etc.)

If you absolutely want to use the words "functor" and "category" you can, but at this level they're not the most relevant thing.

Yes, there is an abstract isomorphism here and the likeness of the symbols $$\lor$$ and $$\cup$$, as well as that of $$\land$$ and $$\cap$$ is of course no accident!

Also, if you use the formal definition of the set operators, we see the connection there as well:

Union:

$$\forall A \ \forall B \ \forall x \ (x \in A \color{red}\cup B \leftrightarrow (x \in A \color{red}\lor x \in B))$$

Intersection:

$$\forall A \ \forall B \ \forall x \ (x \in A \color{red}\cap B \leftrightarrow (x \in A \color{red}\land x \in B))$$

Complement:

$$\forall A \ \forall B \ \forall x \ (x \in A\color{red}' \leftrightarrow \color{red}\neg x \in A)$$

And your conjecture is right in that we also have:

Inclusion:

$$\forall A \ \forall B \ (A\color{red} \subseteq B \leftrightarrow \forall x (x \in A \color{red} \rightarrow x \in B))$$

Equality:

$$\forall A \ \forall B \ (A\color{red} = B \leftrightarrow \forall x (x \in A \color{red} \leftrightarrow x \in B))$$

The connection is math is a logical science. It's built on a foundation of axioms and definitions, from which ideally, all statements can be proven, or disproven ( though some are undecideable sadly). You can have logical properties with set operations, Sets equipped with operations, having certain properties applied on the set, are the basis for: magmas, monoids, loops, semigroups, quasigroups, groups, abelian groups, rings, commutative rings, and fields, just to name a few buzzwords. Mathematical logic, can be defined in terms of other more basic logics.