distribution of disjunction and conjunction over each other in intuitionistic logic

Question

I can't find any references as to whether or not the usual properties of disjunction and conjunction distributing over each other hold in intuitionistic logic. Consider:

$$(1) \ \ (p \vee (q \& r)) \rightarrow ((p \vee q) \& (p \vee r))$$ $$(2) \ \ ((p \& q) \vee (p \& r)) \rightarrow (p \& (q \vee r))$$ $$(3) \ \ ((p \vee q) \& (p \vee r)) \rightarrow (p \vee (q \& r))$$ $$(4) \ \ (p \& (q \vee r)) \rightarrow ((p \& q) \vee (p \& r))$$

I can easily prove (1) and (2) in intuitionistic logic. But (3) and (4) do not seem provable. Are they intuitionistically valid?

Answer 1

Here are proofs in a fairly standard natural deduction system for intuitionistic logic.

For (3), assume $(p\lor q)\&(p\lor r)$. In particular, we have $p\lor q$, so we can consider separately two cases.

Case 1: $p$. Then the desired conclusion $p\lor(q\&r)$ follows immediately.

Case 2: $q$. In this case, we go back to the initial assumption to obtain $p\lor r$. So we can consider two subcases.

Subcase 2a: $p$. Again the desired conclusion follows immediately.

Subcase 2b: $r$. Combine this with $q$, which we have because we're in Case 2, to get $q\&r$ and thus the desired conclusion $p\lor(q\&r)$.

We got the desired conclusion in all cases and subcases, so the proof is complete.

For (4), assume $p\&(q\lor r)$. So we know $p$ and we know $q\lor r$. The latter lets us consider two cases separately.

Case 1: $q$. So we have $p\&q$, and therefore $(p\&q)\lor(p\&r)$, as required.

Case 2: $r$. So we have $p\&r$, and therefore $(p\&q)\lor(p\&r)$, as required.

Answer 2

The familiar properties distributive properties for $\land$ and $\lor$ do indeed hold.

The easiest way to see this is with the topological semantics for IPC.

As far as I know, there are two common ways to present the topological semantics:

1. Using the proper class of all topologies as your semantics.
2. Picking a representative topology (usually $\mathbb{R}$) in such a way that the sentences that are true of that topology are the same as in (1).

I'm going with (2) because it is, in my opinion, more concrete.

It suffices to look at a single topology, the standard topology on the reals (which I'll write $\tau^R$) where the whole real line $\mathbb{R}$ is the sole designated truth value. A designated truth value is a value that's treated as "true" for the purposes of determining tautologies and our notion of logical consequence.

Suppose $\varphi$ is a well-formed formula; $[\varphi]$ would then denote its interpretation.

$ [a \land b] $ is equivalent to $[a] \cap [b]$.
$ [a \lor b]$ is equivalent to $[a] \cup [b]$.
$ [\bot] $ is equivalent to $\varnothing$.
$ [\top] $ is equivalent to $\mathbb{R}$.
$ [a \to b]$ is equivalent to $([a]^c \cup [b])^o$ where $^c$ is the complement and $^o$ is the interior.

Using these semantics we can see that, for example, the interpretation of $a \land (b \lor c)$ is equal to the interpretation of $(a \lor b) \land (a \lor c)$. From this it follows that $(a \land (b \lor c)) \to (a \lor b) \land (a \lor c)$ and its converse are intuitionistic tautologies.