Week 2 - Sets B

Lesson 1.2 Set representation and manipulation

1.201 The representation of a set using Venn diagrams

  • Universal Set
    • A set containing everything.
    • Represented by letter UU.
  • Complement
    • Represented as: Aˉ\bar{A}
    • All the elements in the universal set UU but not in AA: Aˉ=UA\bar{A} = U - A
    • The union of a set and its compliment, is equal to universal set: AˉA=U\bar{A} \cup A = U
  • Venn Diagram

    • Used to visualise the possible relations among a collection of sets.
    • In this example, the red area represents the union of A and B:

      Venn Diagram example

    • In this example, the red area represents the intersection of A and B:

      Venn Intersection

    • In this example, the set difference:

      Venn Set Difference

    • In this example, it shows the symmetric difference between A and B

      Venn Symmetric Difference

    • Can use a Venn Diagram to show that each sets are equivalent. Venn Show Sets Same

1.203 De Morgan's laws

  • De Morgan's Laws
    • By Augustus De Morgan (1806 - 1871), a British mathematician.
    • Describe how statements and concepts are related through opposites.
    • Example from set theory:
      • De Morgan's laws relate to the Intersection and Union of sets through their complements.
    • The structure of De Morgan's laws, whether applied to sets, propositions or logic gates is always the same.
    • Law #1: Compliment of the union of 2 sets, AA and BB is equal to intersection of complements:
      • AB=AˉBˉ\overline{A \cup B} = \bar{A} \cap \bar{B}
        • A={a,b},B={b,c,d}A = \{a, b\}, B = \{b ,c, d\}
        • AB\overline{A \cup B} = {a,b,c,d}\overline{\{a, b, c, d}\} = {}\{\}
        • A={c,d}\overline{A} = \{c, d\}, B={a}\overline{B} = \{a\},
          • AB={}\overline{A} \cap \overline{B} = \{\},
    • Law #2: Complement of the intersection of 2 sets A and B, is equal to union of their complements.
      • AB=AˉBˉ\overline{A \cap B} = \bar{A} \cup \bar{B}
        • A={a,b},B={b,c,d}A = \{a, b\}, B = \{b, c, d\}
        • AB={a,c,d}\overline{A \cap B} = \{a, c, d\}
        • AˉBˉ={a,c,d}\bar{A} \cup \bar{B} = \{a, c, d\}

1.205 Laws of sets: Commutative, associative and distributives

  • Commutative Operation
    • An operation where order does not affect the results.
      • Additional is commutative: 2+3=3+22 + 3 = 3 + 2
      • Multiplication is commutative: 2x3=3x22 x 3 = 3 x 2
      • Subtraction is not commutative: 23322 - 3 \neq 3 - 2
    • Set union is commutative:
      • AB=BAA \cup B = B \cup A
    • Set intersection is commutative:
      • AB=BAA \cap B = B \cap A
    • Symmetric difference is commutative:
      • AB=BAA \oplus B = B \oplus A
    • Set difference is not commutative:
      • ABBAA - B \neq B - A
  • Associativity Operation
    • Concerns grouping of elements in an operation.
      • An example from algebra, the additional of numbers is associative:
        • (a+b)+c=a+(b+c)(a + b) + c = a + (b + c)
    • The grouping of elements does not affect the results for union, set intersection or symmetric difference.
    • Set union is associative:
      • (AB)C=A(BC)(A \cup B) \cup C = A \cup (B \cup C)
    • Set intersection is associative:
      • (AB)C=A(BC)(A \cap B) \cap C = A \cap (B \cap C)
    • Symmetric difference is associative:
      • (AB)C=A(BC)(A \oplus B) \oplus C = A \oplus (B \oplus C)
    • Set difference is not associate:
      • (AB)CA(BC)(A - B) - C \ne A - (B - C)
  • Distributivity
    • Sometimes called the distributive law of multiplication and division.
      • Example in algebra: Given 3 numbers a, b, c: a(b+c)=ab+aca(b + c) = ab + ac
    • Set union is distributive over set intersection:
      • A(BC)=(AB)(AC)A \cup (B \cap C) = (A \cup B) \cap (A \cup C)
    • Set intersection is distributive over set union
      • A(BC)=(AB)(AC)A \cap (B \cup C) = (A \cap B) \cup (A \cap C)
  • Set Identities

    Set identities table

    • Set identities can be used to simplify set expressions.
      • Example:
        • Show that (AB)B=BA\overline{(A \cap B) \cup \overline{B}} = B \cap \overline{A}
        • =(AB)B=(AB)B= \overline{(A \cap B) \cup \overline{B}} = \overline{(A \cap B)} \cap \overline{\overline{B}} -- De Morgan's law.
        • =(AB)B=\overline{(A \cap B)} \cap B -- double complement
        • =(AB)B=(\overline{A} \cup \overline{B}) \cap B -- De Morgan's law.
        • =B(AB)=B \cap (\overline{A} \cup \overline{B}) -- commutative.
        • =(BA)(BB)=(B \cap \overline{A}) \cup (B \cap \overline{B}) -- distributive.
        • =(BA)= (B \cap \overline{A}) \cup \emptyset -- identity
        • =BA= B \cap \overline{A} -- complement

1.207 Partition of a set

  • Partition
    • To partition an object is to separate it into parts so each parts are separate from each other, but together make up the whole object.
    • A partition of a set AA is a set of subsets of AA such that:
      • all the subsets of A are disjointed.
      • the union of all subsets AiA_i is equal to AA.
    • Example:

      Partition Example

      • A1A2=A2A3=....A4A5=A_1 \cap A_2 = A_2 \cap A_3 = .... A_4 \cap A_5 = \emptyset
      • A=A1A2A3A4A5A = A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5
      • {A1,A2,A3,A4,A5}\{A_1, A_2, A_3, A_4, A_5\} is a partition on AA
      • Disjoint Sets
        • Two sets are considered disjointed if and only if their intersection is an empty set.
      • AB=A \cap B = \emptyset

Peer-graded Assignment: 1.209 Sets

Part 1

Question

Given three sets A, B and C, prove that: ABC=A+B+CABACBC+ABC|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - | A \cap C| - |B \cap C|+ |A\cap B\cap C|

Proof

$$ \begin{align} |A \cup B \cup C| &= |A \cup (B \cup C)| \ & = |A| + |B \cup C| - | A \cap (B \cup C)| \text{ --- IEP} \ & = |A| + |B \cup C| - |(A \cap B) \cup (A \cap C)| \text{ \ \ \ --- distributive law} \ & = |A| + (|B| + |C| - |B \cap C|) - (|A \cap B| + |A \cap C| - |(A \cap B) \cap (A \cap C)|) \ & = |A| + |B| + |C| - |B \cap C| - |A \cap B| - |A \cap C| + |(A \cap B) \cap (A \cap C)| \ & = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \ \

\text{ since } |(A \cap B) \cap (A \cap C)| &= |A \cap B \cap C| \end{align} $$

Part 2

Question

Let A and B two subsets of the universal set U={x:xZ and 0x<20}U = \{ x: x \in \mathbb{Z} \text{ and } 0 \leq x<20\}. AA is the set of even numbers in UU, where BB is the set of odd numbers in UU.

Use the listing method to list the elements of the following sets: ABA \cap \overline{B}, AB\overline{A\cap B} , AB\overline{A\cup B} and AB\overline{A\oplus B}

Answer

ABA \cap \overline{B} = {0,2,4,6,8,10,12,14,16,18}\{0, 2, 4, 6, 8, 10, 12, 14, 16, 18\}

AB\overline{A \cap B} = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19\}

AB\overline{A \cup B} = {}\{\}

AB\overline{A \oplus B} = {}\{\}