Results 1 to 4 of 4

Thread: set theory

  1. #1
    Junior Member
    Joined
    Dec 2006
    Posts
    48

    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)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    Quote Originally Posted by ruprotein View Post
    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:
    $\displaystyle (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:
    $\displaystyle (x \in A \Rightarrow x \in U) \wedge (x \in B \Rightarrow x \in U) \Rightarrow $$\displaystyle \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)$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,782
    Thanks
    2824
    Awards
    1
    Using DeMorganís laws we have $\displaystyle K\backslash L = K \cap L'.$
    Thus
    $\displaystyle \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}.$
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    848
    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 . . .

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

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

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


    Prove the following DeMorgan's law:

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

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

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

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

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


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

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

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


    Therefore, the two sides are equal . . . QED

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Textbooks on Galois Theory and Algebraic Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: Jul 8th 2011, 06:09 PM
  2. Group Theory - Sylow Theory and simple groups
    Posted in the Advanced Algebra Forum
    Replies: 16
    Last Post: May 16th 2009, 11:10 AM
  3. Problems relating Theory of Automata (Computer Theory)
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: Oct 17th 2007, 09:52 AM
  4. Set theORY
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 25th 2007, 07:01 PM
  5. Set Theory
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 27th 2007, 09:22 AM

Search Tags


/mathhelpforum @mathhelpforum