Propositional tautologies whose analogues for sets are false

Question

Are there tautologies of propositional logic whose analogues for sets are false? I believe I have found such a tautology. For example, $((p \rightarrow q) \vee (q \rightarrow p))$ is a tautology, but the analogue for sets $((A \subseteq B) \vee (B \subseteq A))$ is not always true, for there are sets which are not subsets of each other. But maybe I am just misunderstanding something. My real question is, can someone clarify my misunderstanding, if indeed I am misunderstanding something?

Answer 1

I think you should set the analogy you refer to more precisely.

Basic operations on sets are indeed defined in terms of logical connectives in a one-to-one way. Intersection $\cap$ corresponds to conjunction $\land$ in that $x \in A \cap B$ if and only if $x \in A \land x \in B$. Similarly for other basic operations on sets such as union, complementation, symmetric difference, etc.

According to that, you can establish a nice analogy from some tautologies in propositional logic and basic laws in set theory. For instance, the commutative law for intersection $A \cap B = B \cap A$ corresponds to the tautology conjunction $(p \land q) \leftrightarrow (q \land p)$. This analogy can be made more precise if you look at the Boolean algebra of sets, see here for a very gentle introduction

But $\subseteq$ is not an operation on sets ($A \subseteq B$ is not a set), it is a binary relation on sets, as well as $=$. So, $A \subseteq B$ is a statement that can be true or false, not a set. It doesn't make sense to write something like $(A \subseteq B) \cap C$.

Thus, what you can do with your analogy is to see basic operations on sets as logical connectives, and the relations on sets $=$ and $\subseteq$ as the connectives $\leftrightarrow$ and $\to$. Hence, you can interpret any tautology in classical logic that fulfils the two conditions below:

1. there is only one occurrence of the connectives $\leftrightarrow$ and $\to$, and
2. this occurrence is the main connective of the tautology,

as a set theory law. The formula $(p \to q) \lor (q \to p)$ doesn't fulfill the two conditions above, this is the reason why you can't get the corresponding set theory law from it.

Answer 2

To get a precise analogy between propositional logic and the basic set theory operations, use the following correspondence $\sim$, where the variables $p$ and $q$ name propositions, the variables $P$ and $Q$ name subsets of some given set $U$ (the universe) and the notation $P^c$ means complementation with respect to the universe: $P^c = U \setminus P$.

\begin{align*} \lnot p &\sim P^c\\ p \lor q &\sim P \cup Q\\ p \land q &\sim P \cap Q\\ p \to q &\sim P^c \cup Q \end{align*}

Under this correspondence a propositional tautology $t$ corresponds to a set expression $T$ which is equal to $U$ for any assignment of subsets of $U$ to the variables occurring in $T$. For example, the propositional tautology $p \lor \lnot p$ corresponds to the set expression $P \cup P^c$, which is equal to $U$ for any subset $P$ of $U$.

Under this correspondence, your example works properly: $(p \to q) \lor (q \to p)$ corresponds to $(P^c \cup Q) \cup (Q^c \cup P)$, which is equal to $U$ for any choice of subsets $P$ and $Q$ of $U$.

This correspondence is essentially the semantics of propositional logic, in which we think of a proposition as denoting some set of situations in which that proposition holds (under some assignment of propositional variables to sets of situations). A tautology is a proposition which holds under all assignments.