Results 1 to 4 of 4

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

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1
    Using DeMorganís laws we have K\backslash L = K \cap L'.
    Thus
    \begin{array}{rcl}<br />
 U\backslash \left( {A \cup B} \right) & = & U \cap \left( {A \cup B} \right)' \\ <br />
  & = & U \cap \left( {A' \cap B'} \right) \\ <br />
  & = & \left( {U \cap A'} \right) \cap \left( {U \cap B'} \right) \\ <br />
  & = & \left( {U\backslash A} \right) \cap \left( {U\backslash B} \right) \\ <br />
 \end{array}.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,707
    Thanks
    627
    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.


    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

    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: July 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: October 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: February 27th 2007, 09:22 AM

Search Tags


/mathhelpforum @mathhelpforum