Discrete Structures - Set Theory and Set Operations

Fundamentals of Set Theory

  • Definition of a Set:

    • A set is the fundamental discrete structure upon which all other discrete structures are built.

    • Sets are used to group objects together. Frequently, the objects grouped within a set share similar properties.

    • Formally, a set is defined as an unordered collection of objects.

    • The objects contained within a set are designated as the elements or members of the set.

  • Fundamental Membership Notation:

    • Uppercase letters (e.g., AA, BB, SS) are used to represent sets.

    • Lowercase letters (e.g., xx, aa, bb) are used to represent elements.

    • The expression x∈Ax \in A denotes that xx is an element of set AA (read as "xx is a member of AA" or "xx is in AA").

    • The expression x∉Ax \notin A denotes that xx is not an element of set AA.

Important Numerical Sets

  • The Set of Natural Numbers:

    • N={0,1,2,3,… }\mathbb{N} = \{0, 1, 2, 3, \dots\}

  • The Set of Integers:

    • Z={…,−2,−1,0,1,2,… }\mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}

  • The Set of Positive Integers:

    • Z+={1,2,3,… }\mathbb{Z}^+ = \{1, 2, 3, \dots\}

  • The Set of Rational Numbers (Fractions):

    • Q={0,12,−12,−5,7813,… }\mathbb{Q} = \{0, \frac{1}{2}, -\frac{1}{2}, -5, \frac{78}{13}, \dots\}

    • Expressed in set-builder notation: Q={pq∣p∈Z,q∈Z, and q≠0}\mathbb{Q} = \{\frac{p}{q} \mid p \in \mathbb{Z}, q \in \mathbb{Z}, \text{ and } q \neq 0\}

  • The Set of Real Numbers:

    • R={−32,0,e,π2,5,… }\mathbb{R} = \{-\frac{3}{2}, 0, e, \pi^2, \sqrt{5}, \dots\}

Set Equality and Description Methods

  • Set Equality:

    • Two sets are equal if and only if they contain precisely the same elements.

    • Logical notation: A=B  ⟺  ∀x(x∈A↔x∈B)A = B \iff \forall x (x \in A \leftrightarrow x \in B).

    • Alternative criterion: Two sets AA and BB are equal if and only if A⊆BA \subseteq B and B⊆AB \subseteq A.

    • To formally prove that set AA equals set BB, one must demonstrate two sub-proofs:

    • A⊆BA \subseteq B

    • B⊆AB \subseteq A

    • Order independence: The set {1,3,5}\{1, 3, 5\} is equal to {3,5,1}\{3, 5, 1\}.

    • Repetition invariance: The set {1,3,3,3,5,5,5,5}\{1, 3, 3, 3, 5, 5, 5, 5\} is equal to {1,3,5}\{1, 3, 5\} because both sets contain the exact same distinct elements.

  • Methods for Describing Sets:

    • Roster or Listing Notation:

    • Explicitly listing all members between curly braces {}\{\}.

    • Example: {dog,cat,horse}\{\text{dog}, \text{cat}, \text{horse}\}

    • Example: The set OO of odd positive integers less than 1010 is represented as O={1,3,5,7,9}O = \{1, 3, 5, 7, 9\}.

    • Ellipsis Notation:

    • Used when a set contains many elements or is infinite, provided the underlying pattern is clear.

    • Example: The set AA of positive integers less than 100100 is denoted as A={1,2,3,…,99}A = \{1, 2, 3, \dots, 99\}.

    • Set-Builder Notation:

    • Characterizes elements by specifying the precise condition or property required for membership.

    • Example: O={x∣x is an odd positive integer <10}O = \{x \mid x \text{ is an odd positive integer } < 10\}

    • Example specifying the universal domain: O={x∈Z+∣x is odd and x<10}O = \{x \in \mathbb{Z}^+ \mid x \text{ is odd and } x < 10\}

    • Summary of Set Characterization Approaches:

    • Explicitly: {John,Paul,George,Ringo}\{\text{John}, \text{Paul}, \text{George}, \text{Ringo}\}

    • Implicitly: {1,2,3,… }\{1, 2, 3, \dots\} or {2,3,5,7,11,13,17,… }\{2, 3, 5, 7, 11, 13, 17, \dots\}

    • Set-builder: {x:x is prime}\{x : x \text{ is prime}\}, {x∣x is odd}\{x \mid x \text{ is odd}\}, or generally {x:P(x) is true}\{x : P(x) \text{ is true}\} where P(x)P(x) represents a predicate statement.

Special Sets and Computer Science Applications

  • The Empty Set (Null Set):

    • The unique set containing no elements, denoted by ∅\emptyset or {}\{\}.

    • Example: The set of all positive integers that are strictly greater than their squares is the null set ∅\emptyset.

  • Singleton Set:

    • Any set that contains exactly one element.

  • Set Concepts in Computer Science:

    • The concept of a data type (or type) in computer programming and computer science is constructed directly upon the set concept.

    • A data type is defined as the name of a set together with a set of operations that can be performed on objects from that set.

    • Example: The Boolean data type is the name of the set {0,1}\{0, 1\} combined with logical operators defined on elements of this set, such as ANDAND, OROR, and NOTNOT.

Venn Diagrams

  • Graphical Representation:

    • Sets can be depicted visually using Venn diagrams.

    • The Universal Set (UU) encompasses all objects under consideration and is depicted as a rectangle.

    • Individual sets within the universal set are depicted as circles or closed geometric shapes inside the rectangle.

    • Individual elements inside sets may be represented as labeled points.

    • Example: A Venn diagram representing V={a,e,i,o,u}V = \{a, e, i, o, u\}, the set of vowels in the English alphabet, positioned within the universal set UU.


Venn diagram representing the set of vowels V = {a, e, i, o, u} inside the universal set U

Subsets and Proper Subsets

  • Subsets:

    • A set AA is a subset of set BB if and only if every element of AA is also an element of BB

    • Notation: A⊆BA \subseteq B

    • Predicate logic representation: A⊆B  ⟺  ∀x(x∈A→x∈B)A \subseteq B \iff \forall x (x \in A \rightarrow x \in B)

    • Example: The set of odd positive integers less than 1010 is a subset of the set of all positive integers.

    • Example: The set of rational numbers Q\mathbb{Q} is a subset of the set of real numbers R\mathbb{R}.


Venn diagram representing set A as a subset of set B within universal set U
  • Universal Subset Theorems:

    • For any arbitrary set SS:

    • ∅⊆S\emptyset \subseteq S (The empty set is a subset of every set)

    • S⊆SS \subseteq S (Every set is a subset of itself)

  • Proper Subsets:

    • Set AA is a proper subset of set BB if AA is a subset of BB but A≠BA \neq B.

    • Notation: A⊂BA \subset B

    • Predicate logic representation: A⊂B  ⟺  ∀x((x∈A)→(x∈B))∧∃x((x∈B)∧(x∉A))A \subset B \iff \forall x ((x \in A) \rightarrow (x \in B)) \land \exists x ((x \in B) \land (x \notin A))

  • Subset Evaluation Examples:

    • {1,2,3}⊆{1,2,3,4,5}\{1, 2, 3\} \subseteq \{1, 2, 3, 4, 5\} is True.

    • {1,2,3}⊂{1,2,3,4,5}\{1, 2, 3\} \subset \{1, 2, 3, 4, 5\} is True.

    • Is ∅⊆{1,2,3}\emptyset \subseteq \{1, 2, 3\}? Yes.

    • Is ∅∈{1,2,3}\emptyset \in \{1, 2, 3\}? No.

    • Is ∅⊆{∅,1,2,3}\emptyset \subseteq \{\emptyset, 1, 2, 3\}? Yes.

    • Is ∅∈{∅,1,2,3}\emptyset \in \{\emptyset, 1, 2, 3\}? Yes.

    • Is {x}∈{x,{x}}\{x\} \in \{x, \{x\}\}? Yes.

    • Is {x}⊆{x,{x}}\{x\} \subseteq \{x, \{x\}\}? Yes.

    • Is {x}⊆{x}}\{x\} \subseteq \{x\}\}? Yes.

    • Is {x}∈{x}}\{x\} \in \{x\}\}? No.

Finite Sets, Infinite Sets, and Cardinality

  • Finite Sets:

    • Let SS be a set. If there are exactly nn distinct elements in SS, where nn is a nonnegative integer, SS is a finite set.

    • The integer nn is called the cardinality of SS.

    • Symbol for cardinality: ∣S∣|S|

  • Infinite Sets:

    • A set is infinite if it is not finite (e.g., the set of positive integers Z+\mathbb{Z}^+).

  • Cardinality Rules and Formulas:

    • When evaluating cardinality, only distinct, unrepeated elements are counted.

    • Inclusion-Exclusion Principle for two finite sets: ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A \cup B| = |A| + |B| - |A \cap B|

  • Cardinality Evaluation Examples:

    • For S={1,2,3}S = \{1, 2, 3\}, ∣S∣=3|S| = 3

    • For S={3,3,3,3,3}S = \{3, 3, 3, 3, 3\}, ∣S∣=1|S| = 1

    • For S=∅S = \emptyset, ∣S∣=0|S| = 0

    • For S={∅,{∅},{∅,{∅}}}S = \{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}, ∣S∣=3|S| = 3

    • For S={0,1,2,3,… }S = \{0, 1, 2, 3, \dots\}, ∣S∣|S| is infinite

Power Sets

  • Definition and Purpose:

    • Many computational problems require evaluating all combinations of elements of a set to test if they satisfy specific conditions.

    • Given a set SS, the power set of SS is the set of all subsets of SS.

    • Notation: P(S)\mathcal{P}(S) or P(S)P(S).

    • Cardinality of a Power Set: If a set SS has nn elements (∣S∣=n|S| = n), its power set P(S)\mathcal{P}(S) contains 2n2^n elements.

    • Minimal cardinality property: The power set of any set contains at least two elements (the empty set ∅\emptyset and the set SS itself), except when S=∅S = \emptyset, in which case P(∅)={∅}\mathcal{P}(\emptyset) = \{\emptyset\} containing 11 element (20=12^0 = 1).

  • Worked Power Set Examples:

    • Power set of S={0,1,2}S = \{0, 1, 2\}:

    • P({0,1,2})={∅,{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2}}\mathcal{P}(\{0, 1, 2\}) = \{\emptyset, \{0\}, \{1\}, \{2\}, \{0, 1\}, \{0, 2\}, \{1, 2\}, \{0, 1, 2\}\} (total of 23=82^3 = 8 subsets)

    • Power set of empty set S=∅S = \emptyset, P(∅)={∅}\mathcal{P}(\emptyset) = \{\emptyset\}

    • Power set of S={∅}S = \{\emptyset\}, P({∅})={∅,{∅}}\mathcal{P}(\{\emptyset\}) = \{\emptyset, \{\emptyset\}\}

    • Quick Quiz Exercises:

    • If S={a}S = \{a\}, P(S)={∅,{a}}\mathcal{P}(S) = \{\emptyset, \{a\}\}

    • If S={a,b}S = \{a, b\}, P(S)={∅,{a},{b},{a,b}}\mathcal{P}(S) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}

    • If S=∅S = \emptyset, P(S)={∅}\mathcal{P}(S) = \{\emptyset\}

    • If S={∅,{∅}}S = \{\emptyset, \{\emptyset\}\}, P(S)={∅,{∅},{{∅}},{∅,{∅}}}\mathcal{P}(S) = \{\emptyset, \{\emptyset\}, \{\{\emptyset\}\}, \{\emptyset, \{\emptyset\}\}\}

Ordered Tuples and Cartesian Products

  • Ordered nn-tuples:

    • Because sets are unordered, a distinct structure is necessary to represent ordered collections.

    • An ordered nn-tuple (a1,a2,…,an)(a_1, a_2, \dots, a_n) is an ordered collection having a1a_1 as its first element, a2a_2 as its second element, …, and ana_n as its nn-th element.

    • Two ordered nn-tuples are equal if and only if each corresponding pair of elements is equal: (a1,a2,…,an)=(b1,b2,…,bn)  ⟺  ai=bi(a_1, a_2, \dots, a_n) = (b_1, b_2, \dots, b_n) \iff a_i = b_i for all i=1,2,…,ni = 1, 2, \dots, n.

  • Cartesian Product:

    • Let AA and BB be sets. The Cartesian product of AA and BB, denoted by A×BA \times B, is the set of all ordered pairs (a,b)(a, b) such that a∈Aa \in A and b∈Bb \in B

    • Set-builder definition: A×B={(a,b)∣a∈A∧b∈B}A \times B = \{(a, b) \mid a \in A \land b \in B\}

    • Extension to nn sets: A1×A2×⋯×An={(a1,a2,…,an)∣ai∈Ai for i=1,2,…,n}A_1 \times A_2 \times \dots \times A_n = \{(a_1, a_2, \dots, a_n) \mid a_i \in A_i \text{ for } i = 1, 2, \dots, n\}

    • Non-commutativity: In general, A×B≠B×AA \times B \neq B \times A unless A=BA = B or one of the sets is empty.

  • Cartesian Product Examples:

    • Let A={1,2}A = \{1, 2\} and B={3,4}B = \{3, 4\}:

    • A×B={(1,3),(1,4),(2,3),(2,4)}A \times B = \{(1, 3), (1, 4), (2, 3), (2, 4)\}

    • B×A={(3,1),(3,2),(4,1),(4,2)}B \times A = \{(3, 1), (3, 2), (4, 1), (4, 2)\}

    • Let A={0,1}A = \{0, 1\}, B={1,2}B = \{1, 2\}, and C={0,1,2}C = \{0, 1, 2\}, find A×B×CA \times B \times C:

    • A×B×C={(0,1,0),(0,1,1),(0,1,2),(0,2,0),(0,2,1),(0,2,2),(1,1,0),(1,1,1),(1,1,2),(1,2,0),(1,2,1),(1,2,2)}A \times B \times C = \{(0,1,0), (0,1,1), (0,1,2), (0,2,0), (0,2,1), (0,2,2), (1,1,0), (1,1,1), (1,1,2), (1,2,0), (1,2,1), (1,2,2)\}

Set Operations

  • Union:

    • The union of sets AA and BB is the set containing elements in AA, in BB, or in both.

    • Definition: A∪B={x∣x∈A∨x∈B}A \cup B = \{x \mid x \in A \lor x \in B\}

    • Example: If A={1,2,3}A = \{1, 2, 3\} and B={2,4}B = \{2, 4\}, then A∪B={1,2,3,4}A \cup B = \{1, 2, 3, 4\}.

  • Intersection:

    • The intersection of sets AA and BB is the set containing elements present in both AA and B$.\n - Definition: A \cap B = {x \mid x \in A \land x \in B}\n - Example 1: If A = {\text{Charlie}, \text{Lucy}, \text{Linus}}andandB = {\text{Lucy}, \text{Desi}}$, then A∩B={Lucy}A \cap B = \{\text{Lucy}\}.

    • Example 2: If A={x∣x is a US president}A = \{x \mid x \text{ is a US president}\} and B = \{x \mid x \text{ is deceased}\}$, then A \cap B = {x \mid x \text{ is a deceased US president}}.\n\n- Disjoint Sets:\n - Two sets AandandBaredisjointiftheirintersectionisempty:are disjoint if their intersection is empty:A \cap B = \emptyset.\n - Example: If A = {x \mid x \text{ is a US president}}andandB = {x \mid x \text{ is in this room}}$, then A∩B=∅A \cap B = \emptyset.

  • Complement:

    • The complement of a set AA consists of all elements in the universal set UU that are not in A$.\n - Definition: \bar{A} = A' = {x \mid x otin A}\n - Example: If A = {x \mid x \text{ is bored}}$, then Aˉ={x∣x is not bored}\bar{A} = \{x \mid x \text{ is not bored}\}.

    • Properties of Complements:

    • ∅ˉ=U\bar{\emptyset} = U

    • Uˉ=∅\bar{U} = \emptyset

    • A⊆B  ⟺  Bˉ⊆AˉA \subseteq B \iff \bar{B} \subseteq \bar{A}

  • Difference (Relative Complement):

    • The set difference A−BA - B consists of elements in AA that are not in B$.\n - Definition: A - B = {x \mid x \in A \land x otin B}\n - Identity relationship: A - B = A \cap \bar{B}\n\n- Symmetric Difference:\n - The symmetric difference A \oplus Bcontainselementsbelongingtocontains elements belonging toAororB, but not both.\n - Definition: A \oplus B = {x \mid (x \in A \land x otin B) \lor (x \in B \land x otin A)}\n - Alternative formulation: A \oplus B = (A - B) \cup (B - A)\n - Behavior: Operates identically to logical "exclusive or" (XOR).\n - Example: Let A = {1, 2, 3, 4, 5, 6, 7}andandB = {3, 4, p, q, r, s}.\n - A \cup B = {1, 2, 3, 4, 5, 6, 7, p, q, r, s}\n - A \cap B = {3, 4}\n - A \oplus B = {1, 2, 5, 6, 7, p, q, r, s}\n\n# Set Identities and Proofs\n\n- Important Set Identities:\n - Identity Laws: A \cup \emptyset = A,,A \cap U = A\n - Domination Laws: A \cup U = U,,A \cap \emptyset = \emptyset\n - Idempotent Laws: A \cup A = A,,A \cap A = A\n - Complementation Law: \overline{(\bar{A})} = A\n - Commutative Laws: A \cup B = B \cup A,,A \cap B = B \cap A\n - Associative Laws: A \cup (B \cup C) = (A \cup B) \cup C,,A \cap (B \cap C) = (A \cap B) \cap C\n - Distributive Laws:\n - A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\n - A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\n - De Morgan's Laws:\n - \overline{A \cup B} = \bar{A} \cap \bar{B}\n - \overline{A \cap B} = \bar{A} \cup \bar{B}\n - Absorption Laws: A \cup (A \cap B) = A,,A \cap (A \cup B) = A\n - Complement Laws: A \cup \bar{A} = U,,A \cap \bar{A} = \emptyset\n\n- Proving Set Identities Using Membership Tables:\n - A membership table records a 1ifanelementbelongstoagivensetexpressionandif an element belongs to a given set expression and0 if it does not.\n - Proof of Distributive Property A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\n\n![Membership table for the distributive property A \cap (B \cup C) = (A \cap B) \cup (A \cap C)](https://assets.knowt.com/pdf-flow-prod/d90b889e-7ffd-49c2-b55c-e2c32c1d3363-figures/27.png)\n\n - Detailed Truth Table Values:\n - Row 1 (A=1, B=1, C=1):):B \cup C = 1,,A \cap (B \cup C) = 1,,A \cap B = 1,,A \cap C = 1,,(A \cap B) \cup (A \cap C) = 1\n - Row 2 (A=1, B=1, C=0):):B \cup C = 1,,A \cap (B \cup C) = 1,,A \cap B = 1,,A \cap C = 0,,(A \cap B) \cup (A \cap C) = 1\n - Row 3 (A=1, B=0, C=1):):B \cup C = 1,,A \cap (B \cup C) = 1,,A \cap B = 0,,A \cap C = 1,,(A \cap B) \cup (A \cap C) = 1\n - Row 4 (A=1, B=0, C=0):):B \cup C = 0,,A \cap (B \cup C) = 0,,A \cap B = 0,,A \cap C = 0,,(A \cap B) \cup (A \cap C) = 0\n - Row 5 (A=0, B=1, C=1):):B \cup C = 1,,A \cap (B \cup C) = 0,,A \cap B = 0,,A \cap C = 0,,(A \cap B) \cup (A \cap C) = 0\n - Row 6 (A=0, B=1, C=0):):B \cup C = 1,,A \cap (B \cup C) = 0,,A \cap B = 0,,A \cap C = 0,,(A \cap B) \cup (A \cap C) = 0\n - Row 7 (A=0, B=0, C=1):):B \cup C = 1,,A \cap (B \cup C) = 0,,A \cap B = 0,,A \cap C = 0,,(A \cap B) \cup (A \cap C) = 0\n - Row 8 (A=0, B=0, C=0):):B \cup C = 0,,A \cap (B \cup C) = 0,,A \cap B = 0,,A \cap C = 0,,(A \cap B) \cup (A \cap C) = 0\n - Conclusion: Since the column for A \cap (B \cup C)matchesthecolumnformatches the column for(A \cap B) \cup (A \cap C) identically across all 8 possible combinations, the identity is verified.\n\n# Practice Exercises and Complete Solutions\n\n- Exercise 1: List the members of these sets:\n - a) {x \mid x \text{ is a real number such that } x^2 = 1}\n - Solution: {-1, 1}\n - b) {x \mid x \text{ is a positive integer less than } 12}\n - Solution: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}\n - c) {x \mid x \text{ is the square of an integer and } x < 100}\n - Solution: {0, 1, 4, 9, 16, 25, 36, 49, 64, 81}\n - d) {x \mid x \text{ is an integer such that } x^2 = 2}\n - Solution: \emptyset(since(since\sqrt{2} is irrational)\n\n- Exercise 2: Determine whether each pair of sets is equal:\n - a) {4, 3, 3, 7, 4, 7, 7, 3}andand{4, 3, 7}\n - Solution: Equal (repetition of elements does not alter set equality).\n - b) {{1}}andand{1, {2}}\n - Solution: Not equal (the first set contains one element: the set {1};thesecondsetcontainstwoelements:integer; the second set contains two elements: integer1andsetand set{2}).\n - c) \emptysetandand{\emptyset}\n - Solution: Not equal (\emptysetcontains0elements;contains 0 elements;{\emptyset} is a singleton set containing 1 element).\n\n- Exercise 3: Determine whether these statements are true or false:\n - a) 0 \in \emptyset: False\n - b) \emptyset \in {0}: False\n - c) {0} \subset \emptyset: False\n - d) \emptyset \subset {0}: True\n - e) {0} \in {0}: False\n - f) {0} \subset {0}:False(itisasubset: False (it is a subset\subseteq,butnotapropersubset, but not a proper subset\subset)\n - g) {\emptyset} \subseteq {\emptyset}: True\n\n- Exercise 4: Use a Venn diagram to illustrate the relationships A \subset BandandB \subset C\n - Solution: Draw universal set Uasaboundingrectanglecontainingthreenestedconcentriccircles,withinnermostcircleas a bounding rectangle containing three nested concentric circles, with innermost circleAinsidemiddlecircleinside middle circleB,whichislocatedinsideoutercircle, which is located inside outer circleC.\n\n- Exercise 5: What is the cardinality of each of these sets?\n - a) {a}:Cardinalityis: Cardinality is1\n - b) {{a}}:Cardinalityis: Cardinality is1\n - c) {\emptyset, {\emptyset}}:Cardinalityis: Cardinality is2\n - d) {a, {a}, {a, {a}}}:Cardinalityis: Cardinality is3\n\n- Exercise 6: Let A = {1, 2, 3, 4, 5}andandB = {0, 3, 6}. Find:\n - a) A \cup B = {0, 1, 2, 3, 4, 5, 6}\n - b) A \cap B = {3}\n - c) A - B = {1, 2, 4, 5}\n - d) B - A = {0, 6}\n\n- Exercise 7: For U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10},let, letA = {1, 2, 3, 4, 5},,B = {1, 2, 4, 8},,C = {1, 2, 3, 5, 7},and, andD = {2, 4, 6, 8}. Determine:\n - a) (A \cup B) \cap C:\n - A \cup B = {1, 2, 3, 4, 5, 8}\n - (A \cup B) \cap C = {1, 2, 3, 5}\n - b) A \cup (B \cap C):\n - B \cap C = {1, 2}\n - A \cup (B \cap C) = {1, 2, 3, 4, 5}\n - c) C \cup D = {1, 2, 3, 4, 5, 6, 7, 8}\n - d) (A \cup B) - C:\n - A \cup B = {1, 2, 3, 4, 5, 8}\n - (A \cup B) - C = {4, 8}\n - e) A \cup (B - C):\n - B - C = {4, 8}\n - A \cup (B - C) = {1, 2, 3, 4, 5, 8}\n - f) (B - C) - D:\n - B - C = {4, 8}\n - (B - C) - D = \emptyset\n - g) B - (C - D):\n - C - D = {1, 3, 5, 7}\n - B - (C - D) = {2, 4, 8}\n - h) (A \cup B) - (C \cap D):\n - A \cup B = {1, 2, 3, 4, 5, 8}\n - C \cap D = {2}\n - (A \cup B) - (C \cap D) = {1, 3, 4, 5, 8}\n - i) A \oplus B:\n - A \oplus B = (A - B) \cup (B - A) = {3, 5} \cup {8} = {3, 5, 8}\n\n- Exercise 8: Draw the Venn diagram of these sets and find (A \cup B) - CandandB'\n - Solution: In a three-set Venn diagram (A, B, CwithinwithinU):\n - (A \cup B) - Cisrepresentedbyshadingallregionsincircleis represented by shading all regions in circleAorcircleor circleBthatlieoutsidecirclethat lie outside circleC\n - B'(or(or\bar{B})isrepresentedbyshadingeveryregionoutsidecircle) is represented by shading every region outside circleB\n\n- Exercise 9: Given Universal set U = {\text{positive integers not larger than } 12} = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12},,A = {\text{positive integers not more than } 6} = {1, 2, 3, 4, 5, 6},,B = {3, 4, 6, 7},and, andC = {5, 6, 7, 8, 9, 10}. Find:\n - i) A \cup B = {1, 2, 3, 4, 5, 6, 7}\n - ii) |A - B|:\n - A - B = {1, 2, 5}\n - |A - B| = 3\n - iii) \mathcal{P}(A - B)(Powersetof(Power set ofA - B):\n - Since A - B = {1, 2, 5},,\mathcal{P}(A - B) = {\emptyset, {1}, {2}, {5}, {1, 2}, {1, 5}, {2, 5}, {1, 2, 5}}</p></li></ul></li></ul><p></p><p>HereisapracticetestbasedonyournotesandsourcesonSetTheory:</p><h5>SetTheoryPracticeTest</h5><ol><li><p><strong>MultipleChoice:</strong>Whatisthepowerset</p></li></ul></li></ul><p></p><p>Here is a practice test based on your notes and sources on Set Theory:</p><h5>Set Theory Practice Test</h5><ol><li><p><strong>Multiple Choice:</strong> What is the power setℳ(S)ofthesetof the setS = {a, b}?</p><ul><li><p>A)?</p><ul><li><p>A){\emptyset, {a}, {b}}</p></li><li><p>B)</p></li><li><p>B){{a}, {b}, {a, b}}</p></li><li><p>C)</p></li><li><p>C){\emptyset, {a}, {b}, {a, b}}</p></li><li><p>D)</p></li><li><p>D){\emptyset, {a, b}}</p></li></ul></li><li><p><strong>SetOperations:</strong>Given</p></li></ul></li><li><p><strong>Set Operations:</strong> GivenA = {1, 2, 3, 4, 5, 6, 7}andandB = {3, 4, p, q, r, s},compute:</p><ul><li><p>a), compute:</p><ul><li><p>a)A \cap B</p></li><li><p>b)</p></li><li><p>b)A \cup B</p></li><li><p>c)</p></li><li><p>c)A \oplus B</p></li></ul></li><li><p><strong>CartesianProduct:</strong>Given</p></li></ul></li><li><p><strong>Cartesian Product:</strong> GivenA = {1, 2}andandB = {3, 4},determine:</p><ul><li><p>a), determine:</p><ul><li><p>a)A \times B</p></li><li><p>b)</p></li><li><p>b)B \times A</p></li></ul></li><li><p><strong>TrueorFalse:</strong></p><ul><li><p>a)</p></li></ul></li><li><p><strong>True or False:</strong></p><ul><li><p>a)\emptyset \subseteq {1, 2, 3}</p></li><li><p>b)</p></li><li><p>b){0} \in \emptyset</p></li><li><p>c)</p></li><li><p>c){1, 3, 5} = {3, 5, 1}</p></li><li><p>d)Ifaset</p></li><li><p>d) If a setShashasn = 4distinctelements,thenitspowersetcontainsdistinct elements, then its power set contains16elements.</p></li></ul></li><li><p><strong>SetDifference:</strong>Giventheuniversalsetelements.</p></li></ul></li><li><p><strong>Set Difference:</strong> Given the universal setU = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10},,A = {1, 2, 3, 4, 5},and, andB = {1, 2, 4, 8},determine, determineA - B.</p></li></ol><divdata−type="horizontalRule"><hr></div><h5>AnswerKey</h5><ol><li><p><strong>C)</strong>.</p></li></ol><div data-type="horizontalRule"><hr></div><h5>Answer Key</h5><ol><li><p><strong>C)</strong>{\emptyset, {a}, {b}, {a, b}}</p></li><li><p></p></li></ol><ul><li><p>a)</p></li><li><p></p></li></ol><ul><li><p>a)A \cap B = {3, 4}</p></li><li><p>b)</p></li><li><p>b)A \cup B = {1, 2, 3, 4, 5, 6, 7, p, q, r, s}</p></li><li><p>c)</p></li><li><p>c)A \oplus B = {1, 2, 5, 6, 7, p, q, r, s}</p></li></ul><ul><li><p></p></li></ul><ul><li><p>a)</p></li></ul><ul><li><p></p></li></ul><ul><li><p>a)A \times B = {(1, 3), (1, 4), (2, 3), (2, 4)}</p></li><li><p>b)</p></li><li><p>b)B \times A = {(3, 1), (3, 2), (4, 1), (4, 2)}</p></li></ul><ul><li><p></p></li></ul><ul><li><p>a)True</p></li><li><p>b)False</p></li><li><p>c)True</p></li><li><p>d)True</p></li></ul><ul><li><p></p></li></ul><ul><li><p></p></li></ul><ul><li><p>a) True</p></li><li><p>b) False</p></li><li><p>c) True</p></li><li><p>d) True</p></li></ul><ul><li><p>A - B = {3, 5}$$