How is material implication the same as subset?

Question

I've been told and read a number of times that implies, $\implies$, is the same as subset $\subseteq$. For example, in the wikipedia page on iff it states that "P only if Q", "if P then Q", and "P→Q" all mean that P is a subset, either proper or improper, of Q

I'm currently thinking in terms of propositional logic, and I don't understand how it makes sense to say that $P \implies Q$ means that $P$ is a subset of $Q$. To my current understanding, $P$ and $Q$ are both propositions, which means that they are in the set $\{T,F\}$. This set contains only two elements and neither of them are sets, so how can $P$ be a subset of $Q$?

I know that the two element Boolean algebra can be realised using $T = \{\emptyset\}$ and $F = \emptyset$, along with intersection union and complement. Then this would mean that I can represent $\implies$ using $\subseteq$, because $\emptyset \subseteq \{\emptyset\}$ etc. to give the correct truth table, but I don't see how that could relate $P \implies Q$ to $P \subseteq Q$.

I think when I'm told that $P \implies Q$ means that $P \subseteq Q$, this must be somehow taking the space of all propositions (perhaps for some specific set of axioms?) and then $P \subseteq Q$ in that space would mean that $P \implies Q$, is this correct? Can anyone elaborate on how this works and direct me to any related reading?

Answer 1

It's certainly not the case that implication "is" subsethood, since - as you say - that's mixing up types of objects.

However, note that in the wiki page, the relevant claim appears within the section on Euler diagrams: so it's not an absolute statement, but rather a statement about how Euler diagrams interpret sentences. And there's much less here than meets the eye: by definition, an Euler diagram for a collection of sentences is a diagram with regions corresponding to sentences where subsethood matches implication.

That said, there is a nontrivial interpretation of Euler diagrams. Specifically, to a sentence $P$ we can associate the set of "models" of $P$, $Mod(P)$, which you can think of as the ways in which $P$ can be true. Then we do indeed have a match up between impication and subsethood: the sentence "$P\rightarrow Q$" is provable from the laws of logic alone (= is a tautology) iff $Mod(P)\subseteq Mod(Q)$. See also these old answer of mine: 1, 2.

More generally, we have that $P\rightarrow Q$ is provable from some theory $T$ iff $Mod(T\cup\{P\})\subseteq Mod(T\cup\{Q\})$, where for $\Gamma$ a set of sentences we define $$Mod(\Gamma):=\bigcap_{\gamma\in\Gamma}Mod(\gamma)$$ (that is, $Mod(\Gamma)$ is the set of structures which are simultaneously models of all the sentences in $\Gamma$).

Answer 2

Consider this interpretation: $P$ and $Q$ aren't elements of $\{T, F\}$, but rather functions from some sensible domain to $\{T, F\}$. For some simple examples, on the domain of natural numbers, consider

• $A(n)= n\text{ is even}$
• $B(n)=n\text{ is a square}$
• $C(n)= n\text{ is prime}$

In this interpretation, $P\implies Q$ means

(On the implied domain,) $Q(n)$ is true for any $n$ that makes $P(n)$ true

This can be reformulated in terms of $\subseteq$ as $$ \{n\mid P(n)\}\subseteq \{n\mid Q(n)\} $$ This doesn't make $\implies$ into $\subseteq$, but they are quite closely related.

Also, it might be worth noting that the very definition of $X\subseteq Y$ is $$ x\in X\implies x\in Y $$ where the domain is the universe of all sets.

As noted by Noah Schweber, this runs into some issues when you get into the nitty-gritty of formal logic and modern set theory. But for other branches, like number theory, analysis or algebra, this level of rigor is just fine.

Answer 3

Material Implication is a Logical Operation in propositional logic. Whilst taking a subset is a mathematical operation in set theory.

They are not the same.

However, just as we use maths to model physical phenomena we can also use math to model logical phenomena. This was the insight of Boole.

Hence, when we use set theory to model propositional logic it turns out that the implication is modelled by taking subsets. In fact, in early notation of set-theoretic propositional logic the implication was denoted with the subset symbol. However, there is the possibility of confusing the senses and so eventually this was replaced by the usual symbol for implication: the double arrow.

The Material Implication should be distinguished from another sense of this, where it's not a Logical Operation but a Rule of Inference and replaces a conditional statement with a proposition involving 'and' and 'negation'.

Answer 4

As should be clear by now, the $\to$ is of course not the same as the subset relationship, as you yourself and others have noted. The $\to$ is a truth-functional operator, while the $\subseteq$ is a set-theoretic predicate.

But, there is a close relationship between them. Indeed, there is a kind of isomorphism between what is going on in propositional logic and set-theory.

Consider the following axiom defining the set-theoretic operation of intersection:

$\forall x \forall y \forall z (z \in x \cap y \leftrightarrow (z \in x \land z \in y))$

So here we see a close connection between the set-theoretic $\cap$ and the logical $\land$. Of course, the fact that these two symbols look alike is not at all a coincidence! Indeed, we also have a close conections between the logical $\lor$ and the set-theoretic $\cup$

$\forall x \forall y \forall z (z \in x \cup y \leftrightarrow (z \in x \lor z \in y))$

And between the set-theoretic complement and logical negation:

$\forall x \forall z (z \in x^C \leftrightarrow \neg z \in x )$

And here is a connection between $\to$ and $\subseteq$:

$\forall x \forall y (x \subseteq y \leftrightarrow \forall z (z \in x \to z \in y))$