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

  • $\begingroup$ The latter is De Morgan's law. Take $A$ to be the universe. $\endgroup$ – copper.hat Feb 5 at 2:25
  • $\begingroup$ 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. $\endgroup$ – user Feb 5 at 2:48
  • $\begingroup$ you can use the DeMorgan laws without the need of an universe, just represent the complement respect to the union of all considered sets $\endgroup$ – Masacroso Feb 5 at 4:00
  • $\begingroup$ 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 $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.