# Inversion of $\cap$ and $\cup$ in set identities

Is there an elementary argument that replacing every $$\cap$$ with $$\cup$$ and $$\cup$$ with $$\cap$$ in a set identity involving only intersections and unions results again in a valid identity?

Strictly speaking, the only facts available at this point are the distributivity identities for $$\cap$$ and $$\cup$$ and $$A\setminus(B \cap C) = (A\setminus B) \cup (A\setminus C)$$ and its dual for arbitrary sets, but complements/universe weren't introduced nor were the De Morgan laws

• The latter is De Morgan's law. Take $A$ to be the universe. – copper.hat Feb 5 at 2:25
• Yeah, I get that. The universe as a concept hasn't been introduced, and you're not supposed to go around taking complements in that sense, is what I'm saying. – user Feb 5 at 2:48
• you can use the DeMorgan laws without the need of an universe, just represent the complement respect to the union of all considered sets – Masacroso Feb 5 at 4:00
• I'm not sure how to make substitution work in that case. If I have an identity, say $A \cap B = B \cap A$, and I can take complements, I get $\overline{A \cap B} = \overline{B \cap A}$, then $\overline{A} \cup \overline{B} = \overline{B} \cup \overline{A}$. Then I can simply substitute the complements of any sets I care about for the variables and get the commutativity of union. But if I use the union of the respective sets, I'll end up needing to factor it into the substitution, and it doesn't simplify to what I need – user Feb 6 at 3:43

Here is a laborious approach that (sort of) sidesteps the universe issue.

Identify a set $$A$$ with its indicator function $$1_A$$ and replace expressions of the form $$A \cap B$$ by $$1_A \land 1_B$$ and similarly $$A \cup B$$ by $$1_A \lor 1_B$$.

Here is the sidestep, note that the indicator of the complement of a set $$A$$ is given by $$1_{A^c} = \lnot 1_A$$.

Suppose we have a set identity of the form $$\alpha_1 = \alpha_2$$, where the $$\alpha_k$$ involve $$\cap,\cup,$$ and the symbols $$A_1,A_2,...$$. Using the above, find the equivalent Boolean expressions $$\omega_1, \omega_1$$, and from the identity we know that $$\omega_1 = \omega_1$$.

(Being a little pedantic, note that strictly speaking one has to apply the above to a specific point say $$x$$, to have a Boolean expression. For example, a set formula $$A \cap B$$ is translated into the function $$x \mapsto 1_A(x) \land 1_B(x)$$, so the get a bona fide Boolean expression it needs to be evaluated at a specific point. However, since two functions are equal iff they are equal when applied to each point of their common domain, we can gloss over this point.)

Given a Boolean expression $$\omega$$ in the variables $$1_{A_k}$$, replace each variable by the corresponding $$1_{A_k^c}$$, replace $$\land$$ by $$\lor$$ and $$\lor$$ by $$\land$$. Call the resulting expression $$\omega^*$$ (the dual).

Show (by induction on the expression depth) that $$\omega^* = \lnot \omega$$. (This is the key result and needs a little work.)

Then since $$\omega_1^* = \lnot \omega_1 = \lnot \omega_2 = \omega_2^*$$, we almost have the desired result.

The catch is that the corresponding expression involves the indicator functions of the complements of sets $$A_k$$, for example the identity $$A \cap B = B \cap A$$ becomes $$1_{A^c} \lor 1_{B^c} = 1_{B^c} \lor 1_{A^c}$$ and for the purposes of this question we are (sort of) avoiding explicit universes (which would give $$A^c \cup B^c = B^c \cup A^c$$).

However, since the identity holds for any indicator functions, we can replace the $$1_{A_k^c}$$ by any other indicator function, in particular we can replace the $$1_{A_k^c}$$ by $$1_{A_k}$$ and the identity remains true and so, in the above example, we end up with $$A \cup B = B \cup A$$.