set theory

Printable View

January 3rd 2007, 01:51 PM
ruprotein

set theory

Prove the following demorgans law: if A, B, U are sets such that A is a subset of U and B is a subset of U, then U - (A union B) = (U-A) intersection (U-B)
January 3rd 2007, 03:35 PM
OReilly

Quote:

Originally Posted by ruprotein

Prove the following demorgans law: if A, B, U are sets such that A is a subset of U and B is a subset of U, then U - (A union B) = (U-A) intersection (U-B)

You want to prove this:
$(A \subset U) \wedge (B \subset U) \Rightarrow \left( {U\backslash (A \cup B) \Leftrightarrow (U\backslash A) \cap (U\backslash B)} \right)$

It can be proved using tautology:
$(x \in A \Rightarrow x \in U) \wedge (x \in B \Rightarrow x \in U) \Rightarrow$ $\left( {x \in U \wedge (x \notin A \vee x \notin B) \Leftrightarrow (x \in U \wedge x \notin A) \wedge (x \in U \wedge x \notin B)} \right)$
January 3rd 2007, 03:51 PM
Plato

Using DeMorgan’s laws we have $K\backslash L = K \cap L'.$
Thus
$\begin{array}{rcl} U\backslash \left( {A \cup B} \right) & = & U \cap \left( {A \cup B} \right)' \\ & = & U \cap \left( {A' \cap B'} \right) \\ & = & \left( {U \cap A'} \right) \cap \left( {U \cap B'} \right) \\ & = & \left( {U\backslash A} \right) \cap \left( {U\backslash B} \right) \\ \end{array}.$
January 4th 2007, 12:27 PM
Soroban

Hello, ruprotein!

It is difficult to provide a proof if we don't know what axioms and theorems you are allowed.

I will assume you are familiar with these rules . . .

. . $[1]\;\;P - Q \:=\: P \cup\overline{Q}$ . . . definition of set subtraction

. . $[2]\;\;\overline{(P \cup Q)} \:=\:\overline{P} \cap \overline{Q}$ . . . one of DeMorgan's Laws.

. . $[3]\;\;U \cap P \:=\:P$ . . . the intersection of $U$ and a set $P$ is the set $P$ .

Quote:

Prove the following DeMorgan's law:

If $A,\,B,\,U$ are sets such that: $A \subset U,\:B \subset U,$ then:
. . $U - (A \cup B) \;= \;(U - A) \cap (U - B)$

The left side is: . $U - (A \cup B)$

. . . . . . . . . . $=\:U \cap \overline{(A \cup B)}$ . . . from [1]

. . . . . . . . . . $= \:U \cap (\overline{A} \cap \overline{B})$ . . . from [2]

. . . . . . . . . . $= \:\overline{A} \cap \overline{B}$ . . . from [3]

The right side is: . $(U - A) \cap (U - B)$

. . . . . . . . . . . $= \:(U \cap \overline{A}) \cap (U \cap \overline{B})$ . . . from [1]

. . . . . . . . . . . $= \:\overline{A} \cap \overline{B}$ . . . from [3]

Therefore, the two sides are equal . . . QED