[Math] Set Theory – Negation of the Union and Intersection operators

discrete mathematicselementary-set-theoryproof-writing

I have recently started getting into Set Theory, and, I have recently started learning DeMorgan's laws in depth.

Recently, when I tried to solve a question involving some of the laws, I stumbled upon a proof that I have tried tackling, but I am not sure if it's the right approach to take.

Here is the question:

Given the fact that $¬(P∧Q)$ is logically equivalent to $(¬P)∨(¬Q)$,
prove that $A-(B∩C) = (A-B)∪(A-C).$

I have tried to prove it using set conjunction which worked out, but now that I try to prove it using the given fact, I find it a little more tricky since there's the negation part to the proof.

So, here is what I have tried doing so far:

Let $¬(P∧Q)$ = $¬(A-B)$, $(¬P) = ¬(A-B)$ ,$(¬Q) = ¬(A-C)$.

Let L.H.S = $¬(A-B) ∨ ¬(A-C)$

=> $¬(x∈A$ and $x∉B)$ ∨ $¬(x∈A$ and $x∉C)$

=> $x∉A$ ∨ $x∈B$ ∨ $x∉A$ ∨ $x∈C)$

=> $x∉A$ ∨ $(x∈B$ and $x∈C)$

=> $(B ∩ C) ∩ A$

Let R.H.S = $¬((A-B) ∩ C)$

=> $¬(x∈A$ and $(x∉B$ ∨ $x∉C))$

=> $x∉A$ ∨ $(x∈B$ and $x∈C)$

=> $(B ∩ C) ∩ A$

I am not sure if this is a valid and sufficient proof for this kind of question. So, could anybody please help me get on track if I'm missing something?

Best Answer

First some comments on your proof.

The statement "$x\in X$" is a proposition, since it has a truth value, whereas the set "$X$" itself does not have a truth value. Hence it makes sense to say $\lnot (x\in X)$, usually written as $(x\notin X)$, whereas it does not make sense to say $\lnot X$ or talk about the negaton of $A-(B\cap C)$, etc...

Ignoring this technical (but important) point, your proof seems to be of the form:

  • If $x\in \text{LHS}$, then $x\in \text{[new expression]}$
  • If $x\in \text{RHS}$, then $x\in \text{[new expression]}$
  • Therefore $\text{LHS}=\text{RHS}$

Your new expression was $(B\cap C)\cap A$. However, note that something important is missing, namely the following two directions:

  • If $x\in \text{[new expression]}$, then $x\in \text{LHS}$
  • If $x\in \text{[new expression]}$, then $x\in \text{RHS}$

Without these, your proof fails. It has the same structure as "If I'm blue, then I'm not an apple", "If I'm purple, then I'm not an apple", therefore "I'm blue if and only if I'm purple".

The thing we want to show is that $x\in A-(B\cap C)$ if and only if $x\in (A-B)\cup (A-C)$.

So we start by assuming that the first is true, and then the rest follows from the definitions of $-$, $\cap$ and $\cup$ and propositional logic:

\begin{align} &\quad x\in A-(B\cap C)\\ \Leftrightarrow&\quad x\in A\land \lnot(x\in B\cap C)&&\text{Definition of $-$}\\ \Leftrightarrow&\quad x\in A\land \lnot(x\in B\land x\in C)&&\text{Definition of $\cap$}\\ \Leftrightarrow&\quad x\in A\land (\lnot(x\in B)\lor \lnot(x\in C))&&\text{DeMorgan's law}\\ \Leftrightarrow&\quad (x\in A\land\lnot(x\in B))\lor (x\in A\land\lnot(x\in C))&&\text{Distributive law}\\ \Leftrightarrow&\quad (x\in A-B)\lor (x\in A-C)&&\text{Definition of $-$, twice}\\ \Leftrightarrow&\quad x\in (A-B)\cup (A-C)&&\text{Definition of $\cup$}\\ \end{align}

It is no coincidence that these propositional rules are also true for the set theoretic operators. This is because the subsets of some set $A$ form a Boolean algebra under the set theoretic operators, just as the set of propositional formulas form a Boolean algebra under the logical operators.

Related Question