Ch.6: Set Theory

Chapter 6 of the book "Discrete Mathematics with Applications" by Susanna S. Epp (4th edition) 6.1. Set Theory: Definitions and the Element Method of Proof 6.2. Properties of Sets 6.3. Disproofs, Algebraic Proofs, and Boolean Algebras 6.4. Boolean Algebras, Russell’s Paradox, and the Halting Problem

122 flashcards · Mathematics · by lakesare

Part of Textbooks › Discrete Mathematics with Applications (Susanna Epp) · 12 courses

  1. [Set Theory: Element Method of Proof] How did Georg Cantor, the founder of set theory, describe a set?

    A collection into a whole MMM of definite and separate objects of our intuition or our thought, called the elements of MMM . "Set" and "element" are undefined terms of set theory, as "sentence", "true" and "false" are in logic. Cantor wrote MMM for the German word for set, Menge.

  2. [Set Theory: Element Method of Proof] SSS is a set and P(x)P(x)P(x) is a property that elements of SSS may or may not satisfy. How is {x∈S∣P(x)}\{x \in S \mid P(x)\}{x∈S∣P(x)} read?

    "The set of all xxx in SSS such that PPP of xxx ." Example: {x∈Z∣x2=4}={−2,2}\{x \in \mathbf{Z} \mid x^2 = 4\} = \{-2, 2\}{x∈Z∣x2=4}={−2,2} .

  3. [Set Theory: Element Method of Proof] Write A⊆BA \subseteq BA⊆B ( AAA is a subset of BBB ) as a formal statement.

    A⊆B ⟺ ∀x, if x∈A then x∈B\boldsymbol{A \subseteq B \iff \forall x, \text{ if } x \in A \text{ then } x \in B}A⊆B⟺∀x, if x∈A then x∈B A universal conditional statement: every element of AAA is also an element of BBB .Example: {1,3}⊆{1,2,3}\{1, 3\} \subseteq \{1, 2, 3\}{1,3}⊆{1,2,3} .

  4. [Set Theory: Element Method of Proof] Write A⊈BA \not\subseteq BA⊆B ( AAA is not a subset of BBB ) as a formal statement.

    A⊈B ⟺ ∃x such that x∈A and x∉B\boldsymbol{A \not\subseteq B \iff \exists x \text{ such that } x \in A \text{ and } x \notin B}A⊆B⟺∃x such that x∈A and x∈/B The negation of a universal conditional statement is existential.Example: {1,4}⊈{1,2,3}\{1, 4\} \not\subseteq \{1, 2, 3\}{1,4}⊆{1,2,3} because 4∈{1,4}4 \in \{1, 4\}4∈{1,4} and 4∉{1,2,3}4 \notin \{1, 2, 3\}4∈/{1,2,3} .

  5. [Set Theory: Element Method of Proof] When is AAA a proper subset of BBB ?

    A⊆BA \subseteq BA⊆B , and at least one element of BBB is not in AAA . Example: {1}\{1\}{1} is a proper subset of {1,2}\{1, 2\}{1,2} ; {1,2}\{1, 2\}{1,2} is a subset of {1,2}\{1, 2\}{1,2} but not a proper one.

  6. [Set Theory: Element Method of Proof] A set with exactly one element, such as {1}\{1\}{1} , is called a singleton set.

  7. [Set Theory: Element Method of Proof] A={1}A = \{1\}A={1} and B={1,{1}}B = \{1, \{1\}\}B={1,{1}} . Is A⊆BA \subseteq BA⊆B ? Is AAA a proper subset of BBB ?

    Yes and yes. The only element of AAA is 111 , and 1∈B1 \in B1∈B , so A⊆BA \subseteq BA⊆B . BBB has two distinct elements, 111 and the set {1}\{1\}{1} . Since 1≠{1}1 \neq \{1\}1={1} , the element {1}\{1\}{1} of BBB is not in AAA , so AAA is a proper subset of BBB .

  8. [Set Theory: Element Method of Proof] What is the element argument for proving that X⊆YX \subseteq YX⊆Y ?

    Suppose xxx is a particular but arbitrarily chosen element of XXX , and show that xxx is an element of YYY . It is the method of direct proof applied to ∀x\forall x∀x , if x∈Xx \in Xx∈X then x∈Yx \in Yx∈Y . It is the fundamental proof technique of set theory.Example: to show {n∈Z∣n=4k for some k∈Z}⊆{n∈Z∣n is even}\{n \in \mathbf{Z} \mid n = 4k \text{ for some } k \in \mathbf{Z}\} \subseteq \{n \in \mathbf{Z} \mid n \text{ is even}\}{n∈Z∣n=4k for some k∈Z}⊆{n∈Z∣n is even} , suppose n=4kn = 4kn=4…

  9. [Set Theory: Element Method of Proof] How do you disprove that a set XXX is a subset of a set YYY ?

    Find an element of XXX that is not in YYY . Example: {1,2}⊈{2,3}\{1, 2\} \not\subseteq \{2, 3\}{1,2}⊆{2,3} , shown by 111 .

  10. [Set Theory: Element Method of Proof] A={m∈Z∣m=6r+12 for some r∈Z}A = \{m \in \mathbf{Z} \mid m = 6r + 12 \text{ for some } r \in \mathbf{Z}\}A={m∈Z∣m=6r+12 for some r∈Z} and B={n∈Z∣n=3s for some s∈Z}B = \{n \in \mathbf{Z} \mid n = 3s \text{ for some } s \in \mathbf{Z}\}B={n∈Z∣n=3s for some s∈Z} .How does an element argument prove A⊆BA \subseteq BA⊆B ?

    For x=6r+12∈Ax = 6r + 12 \in Ax=6r+12∈A , let s=2r+4s = 2r + 4s=2r+4 : then sss is an integer and 3s=6r+12=x3s = 6r + 12 = x3s=6r+12=x , so x∈Bx \in Bx∈B . sss is an integer because products and sums of integers are integers.

  11. [Set Theory: Element Method of Proof] A={m∈Z∣m=6r+12 for some r∈Z}A = \{m \in \mathbf{Z} \mid m = 6r + 12 \text{ for some } r \in \mathbf{Z}\}A={m∈Z∣m=6r+12 for some r∈Z} and B={n∈Z∣n=3s for some s∈Z}B = \{n \in \mathbf{Z} \mid n = 3s \text{ for some } s \in \mathbf{Z}\}B={n∈Z∣n=3s for some s∈Z} .Disprove B⊆AB \subseteq AB⊆A .

    3∈B3 \in B3∈B (since 3=3⋅13 = 3 \cdot 13=3⋅1 ), but 3∉A3 \notin A3∈/A . 6r+12=36r + 12 = 36r+12=3 gives 6r=−96r = -96r=−9 , so r=−32r = -\frac{3}{2}r=−23​ , which is not an integer.

  12. [Set Theory: Element Method of Proof] How is set equality A=BA = BA=B defined in terms of subsets?

    A=B ⟺ A⊆B and B⊆A\boldsymbol{A = B \iff A \subseteq B \text{ and } B \subseteq A}A=B⟺A⊆B and B⊆A This restates the axiom of extension: AAA and BBB are equal if, and only if, they have exactly the same elements.Example: {1,2}={2,1,1}\{1, 2\} = \{2, 1, 1\}{1,2}={2,1,1} , since each is a subset of the other.

  13. [Set Theory: Element Method of Proof] A={m∈Z∣m=2a for some integer a}A = \{m \in \mathbf{Z} \mid m = 2a \text{ for some integer } a\}A={m∈Z∣m=2a for some integer a} and B={n∈Z∣n=2b−2 for some integer b}B = \{n \in \mathbf{Z} \mid n = 2b - 2 \text{ for some integer } b\}B={n∈Z∣n=2b−2 for some integer b} .Is A=BA = BA=B ? How do you prove it?

    Yes: prove A⊆BA \subseteq BA⊆B and B⊆AB \subseteq AB⊆A . A⊆BA \subseteq BA⊆B : for x=2ax = 2ax=2a , let b=a+1b = a + 1b=a+1 ; then 2b−2=2a+2−2=x2b - 2 = 2a + 2 - 2 = x2b−2=2a+2−2=x . B⊆AB \subseteq AB⊆A : for x=2b−2x = 2b - 2x=2b−2 , let a=b−1a = b - 1a=b−1 ; then 2a=2b−2=x2a = 2b - 2 = x2a=2b−2=x .

  14. [Set Theory: Element Method of Proof] What are Venn diagrams, and who introduced them?

    Pictures of sets as regions in the plane, introduced by John Venn in 1881. Two Venn diagrams for A⊆BA \subseteq BA⊆B : (a) AAA inside BBB , (b) A=BA = BA=B . Diagram (b) is the case of (a) where the part of BBB outside AAA contains no points.

  15. [Set Theory: Element Method of Proof] In the Venn diagrams for A⊈BA \not\subseteq BA⊆B , what must be specified in every case?

    That there is a point in AAA that is not in BBB . Three Venn diagrams for A⊈BA \not\subseteq BA⊆B . Diagrams (a) and (c) are cases of (b): in (a) the overlap contains no points, in (c) the part of BBB outside AAA contains no points.

  16. [Set Theory: Element Method of Proof] How are Z\mathbf{Z}Z , Q\mathbf{Q}Q and R\mathbf{R}R related by subset relations?

    Z\boldsymbol{\mathbf{Z}}Z is a proper subset of Q\boldsymbol{\mathbf{Q}}Q , which is a proper subset of R\boldsymbol{\mathbf{R}}R . Every integer nnn equals n1\frac{n}{1}1n​ , but 12∉Z\frac{1}{2} \notin \mathbf{Z}21​∈/Z . Every rational number is real, but 2∉Q\sqrt{2} \notin \mathbf{Q}2​∈/Q .

  17. [Set Theory: Element Method of Proof] The set that contains all sets considered in a discussion (for example R\mathbf{R}R , when all sets considered are sets of real numbers) is called a universal set or a universe of discourse.

    Written UUU .

  18. [Set Theory: Element Method of Proof] AAA and BBB are subsets of a universal set UUU . What is the union A∪BA \cup BA∪B ?

    The set of all elements that are in at least one of AAA or BBB : A∪B={x∈U∣x∈A or x∈B}A \cup B = \{x \in U \mid x \in A \text{ or } x \in B\}A∪B={x∈U∣x∈A or x∈B} . Example: {1,2}∪{2,3}={1,2,3}\{1, 2\} \cup \{2, 3\} = \{1, 2, 3\}{1,2}∪{2,3}={1,2,3} .

  19. [Set Theory: Element Method of Proof] AAA and BBB are subsets of a universal set UUU . What is the intersection A∩BA \cap BA∩B ?

    The set of all elements common to both AAA and BBB : A∩B={x∈U∣x∈A and x∈B}A \cap B = \{x \in U \mid x \in A \text{ and } x \in B\}A∩B={x∈U∣x∈A and x∈B} . Example: {1,2}∩{2,3}={2}\{1, 2\} \cap \{2, 3\} = \{2\}{1,2}∩{2,3}={2} .

  20. [Set Theory: Element Method of Proof] AAA and BBB are subsets of a universal set UUU . What is the difference B−AB - AB−A (the relative complement of AAA in BBB )?

    The set of all elements that are in BBB and not in AAA : B−A={x∈U∣x∈B and x∉A}B - A = \{x \in U \mid x \in B \text{ and } x \notin A\}B−A={x∈U∣x∈B and x∈/A} . Example: {2,3}−{1,2}={3}\{2, 3\} - \{1, 2\} = \{3\}{2,3}−{1,2}={3} .

  21. [Set Theory: Element Method of Proof] AAA is a subset of a universal set UUU . What is the complement AcA^cAc ?

    The set of all elements of UUU that are not in AAA : Ac={x∈U∣x∉A}A^c = \{x \in U \mid x \notin A\}Ac={x∈U∣x∈/A} . Example: with U={1,2,3}U = \{1, 2, 3\}U={1,2,3} , {1}c={2,3}\{1\}^c = \{2, 3\}{1}c={2,3} .

  22. [Set Theory: Element Method of Proof] Who introduced the symbols ∈\in∈ , ∪\cup∪ and ∩\cap∩ , and when?

    Giuseppe Peano, in 1889.

  23. [Set Theory: Element Method of Proof] U={a,b,c,d,e,f,g}U = \{a, b, c, d, e, f, g\}U={a,b,c,d,e,f,g} , A={a,c,e,g}A = \{a, c, e, g\}A={a,c,e,g} , B={d,e,f,g}B = \{d, e, f, g\}B={d,e,f,g} . Find A∪BA \cup BA∪B , A∩BA \cap BA∩B , B−AB - AB−A and AcA^cAc .

    A∪B={a,c,d,e,f,g}\boldsymbol{A \cup B = \{a, c, d, e, f, g\}}A∪B={a,c,d,e,f,g} , A∩B={e,g}\boldsymbol{A \cap B = \{e, g\}}A∩B={e,g} , B−A={d,f}\boldsymbol{B - A = \{d, f\}}B−A={d,f} , Ac={b,d,f}\boldsymbol{A^c = \{b, d, f\}}Ac={b,d,f}

  24. [Set Theory: Element Method of Proof] For real numbers a≤ba \le ba≤b , what sets do (a,b)(a, b)(a,b) , [a,b][a, b][a,b] , (a,b](a, b](a,b] and [a,b)[a, b)[a,b) denote?

    (a,b)={x∈R∣a<x<b}\boldsymbol{(a, b) = \{x \in \mathbf{R} \mid a < x < b\}}(a,b)={x∈R∣a<x<b} , [a,b]={x∈R∣a≤x≤b}\boldsymbol{[a, b] = \{x \in \mathbf{R} \mid a \le x \le b\}}[a,b]={x∈R∣a≤x≤b} , (a,b]={x∈R∣a<x≤b}\boldsymbol{(a, b] = \{x \in \mathbf{R} \mid a < x \le b\}}(a,b]={x∈R∣a<x≤b} , [a,b)={x∈R∣a≤x<b}\boldsymbol{[a, b) = \{x \in \mathbf{R} \mid a \le x < b\}}[a,b)={x∈R∣a≤x<b} A square bracket includes the endpoint, a round one excludes it. The interval (a,b)(a, b)(a,b) has the same notation…

  25. [Set Theory: Element Method of Proof] What sets do (a,∞)(a, \infty)(a,∞) , [a,∞)[a, \infty)[a,∞) , (−∞,b)(-\infty, b)(−∞,b) and (−∞,b](-\infty, b](−∞,b] denote?

    {x∈R∣x>a}\boldsymbol{\{x \in \mathbf{R} \mid x > a\}}{x∈R∣x>a} , {x∈R∣x≥a}\boldsymbol{\{x \in \mathbf{R} \mid x \ge a\}}{x∈R∣x≥a} , {x∈R∣x<b}\boldsymbol{\{x \in \mathbf{R} \mid x < b\}}{x∈R∣x<b} , {x∈R∣x≤b}\boldsymbol{\{x \in \mathbf{R} \mid x \le b\}}{x∈R∣x≤b} The symbol ∞\infty∞ is not a number; it indicates that the interval is unbounded.Example: [0,∞)[0, \infty)[0,∞) is the set of nonnegative real numbers.

  26. [Set Theory: Element Method of Proof] The universal set is R\mathbf{R}R , A=(−1,0]A = (-1, 0]A=(−1,0] and B=[0,1)B = [0, 1)B=[0,1) . Find A∪BA \cup BA∪B , A∩BA \cap BA∩B , B−AB - AB−A and AcA^cAc .

    A∪B=(−1,1)\boldsymbol{A \cup B = (-1, 1)}A∪B=(−1,1) , A∩B={0}\boldsymbol{A \cap B = \{0\}}A∩B={0} , B−A=(0,1)\boldsymbol{B - A = (0, 1)}B−A=(0,1) , Ac=(−∞,−1]∪(0,∞)\boldsymbol{A^c = (-\infty, -1] \cup (0, \infty)}Ac=(−∞,−1]∪(0,∞) x∉(−1,0]x \notin (-1, 0]x∈/(−1,0] means: not ( −1<x-1 < x−1<x and x≤0x \le 0x≤0 ), which by De Morgan's law is x≤−1x \le -1x≤−1 or x>0x > 0x>0 .

  27. [Set Theory: Element Method of Proof] A0,A1,A2,…A_0, A_1, A_2, \dotsA0​,A1​,A2​,… are subsets of a universal set UUU . How are ⋃i=0nAi\displaystyle\bigcup_{i=0}^{n} A_ii=0⋃n​Ai​ and ⋂i=0nAi\displaystyle\bigcap_{i=0}^{n} A_ii=0⋂n​Ai​ defined?

    ⋃i=0nAi\displaystyle\bigcup_{i=0}^{n} A_ii=0⋃n​Ai​ = the x∈Ux \in Ux∈U with x∈Aix \in A_ix∈Ai​ for at least one i=0,…,ni = 0, \dots, ni=0,…,n ; ⋂i=0nAi\ \displaystyle\bigcap_{i=0}^{n} A_i i=0⋂n​Ai​ = the x∈Ux \in Ux∈U with x∈Aix \in A_ix∈Ai​ for all i=0,…,ni = 0, \dots, ni=0,…,n Alternative notation: A0∪A1∪⋯∪AnA_0 \cup A_1 \cup \dots \cup A_nA0​∪A1​∪⋯∪An​ and A0∩A1∩⋯∩AnA_0 \cap A_1 \cap \dots \cap A_nA0​∩A1​∩⋯∩An​ . For ⋃i=0∞Ai\displaystyle\bigcup_{i=0}^{\infty} A_ii=0⋃∞​Ai​ and ⋂i=0∞Ai\display…

  28. [Set Theory: Element Method of Proof] For each positive integer iii , Ai=(−1i,1i)A_i = \left(-\frac{1}{i}, \frac{1}{i}\right)Ai​=(−i1​,i1​) .Find A1∪A2∪A3A_1 \cup A_2 \cup A_3A1​∪A2​∪A3​ and A1∩A2∩A3A_1 \cap A_2 \cap A_3A1​∩A2​∩A3​ .

    A1∪A2∪A3=(−1,1)\boldsymbol{A_1 \cup A_2 \cup A_3 = (-1, 1)}A1​∪A2​∪A3​=(−1,1) and A1∩A2∩A3=(−13,13)\boldsymbol{A_1 \cap A_2 \cap A_3 = \left(-\frac{1}{3}, \frac{1}{3}\right)}A1​∩A2​∩A3​=(−31​,31​) (−13,13)⊆(−12,12)⊆(−1,1)\left(-\frac{1}{3}, \frac{1}{3}\right) \subseteq \left(-\frac{1}{2}, \frac{1}{2}\right) \subseteq (-1, 1)(−31​,31​)⊆(−21​,21​)⊆(−1,1) , so the union is the largest interval and the intersection the smallest.

  29. [Set Theory: Element Method of Proof] For each positive integer iii , Ai=(−1i,1i)A_i = \left(-\frac{1}{i}, \frac{1}{i}\right)Ai​=(−i1​,i1​) .Find ⋃i=1∞Ai\displaystyle\bigcup_{i=1}^{\infty} A_ii=1⋃∞​Ai​ and ⋂i=1∞Ai\displaystyle\bigcap_{i=1}^{\infty} A_ii=1⋂∞​Ai​ .

    ⋃i=1∞Ai=(−1,1)\boldsymbol{\displaystyle\bigcup_{i=1}^{\infty} A_i = (-1, 1)}i=1⋃∞​Ai​=(−1,1) and ⋂i=1∞Ai={0}\boldsymbol{\displaystyle\bigcap_{i=1}^{\infty} A_i = \{0\}}i=1⋂∞​Ai​={0} Every AiA_iAi​ is contained in A1=(−1,1)A_1 = (-1, 1)A1​=(−1,1) . The only element of every interval is 000 : a real number x≠0x \neq 0x=0 is not in AiA_iAi​ once 1i≤∣x∣\frac{1}{i} \le |x|i1​≤∣x∣ .

  30. [Set Theory: Element Method of Proof] What is the empty set ∅\varnothing∅ , and why does set theory allow a set with no elements?

    The unique set with no elements. Without it, every intersection or set defined by a property would first need a check that it has elements. Example: {1,3}∩{2,4}=∅\{1, 3\} \cap \{2, 4\} = \varnothing{1,3}∩{2,4}=∅ and {x∈R∣x2=−1}=∅\{x \in \mathbf{R} \mid x^2 = -1\} = \varnothing{x∈R∣x2=−1}=∅ .

  31. [Set Theory: Element Method of Proof] Describe the set D={x∈R∣3<x<2}D = \{x \in \mathbf{R} \mid 3 < x < 2\}D={x∈R∣3<x<2} .

    D=∅\boldsymbol{D = \varnothing}D=∅ 3<x<23 < x < 23<x<2 means 3<x3 < x3<x and x<2x < 2x<2 , and no real number is both greater than 3 and less than 2.

  32. [Set Theory: Element Method of Proof] When are two sets AAA and BBB disjoint?

    When they have no elements in common: A∩B=∅A \cap B = \varnothingA∩B=∅ . Example: {1,3,5}\{1, 3, 5\}{1,3,5} and {2,4,6}\{2, 4, 6\}{2,4,6} are disjoint.

  33. [Set Theory: Element Method of Proof] When are sets A1,A2,A3,…A_1, A_2, A_3, \dotsA1​,A2​,A3​,… mutually disjoint (or pairwise disjoint, nonoverlapping)?

    When Ai∩Aj=∅A_i \cap A_j = \varnothingAi​∩Aj​=∅ for all i≠ji \neq ji=j : no two of the sets with distinct subscripts have an element in common. Example: {3,5}\{3, 5\}{3,5} , {1,4,6}\{1, 4, 6\}{1,4,6} , {2}\{2\}{2} are mutually disjoint.

  34. [Set Theory: Element Method of Proof] B1={2,4,6}B_1 = \{2, 4, 6\}B1​={2,4,6} , B2={3,7}B_2 = \{3, 7\}B2​={3,7} , B3={4,5}B_3 = \{4, 5\}B3​={4,5} . Are B1,B2,B3B_1, B_2, B_3B1​,B2​,B3​ mutually disjoint?

    No: B1B_1B1​ and B3B_3B3​ both contain 4. B1∩B2∩B3=∅B_1 \cap B_2 \cap B_3 = \varnothingB1​∩B2​∩B3​=∅ , but mutually disjoint requires every pair to have empty intersection.

  35. [Set Theory: Element Method of Proof] When is a collection of nonempty sets {A1,A2,A3,… }\{A_1, A_2, A_3, \dots\}{A1​,A2​,A3​,…} a partition of a set AAA ?

    AAA is the union of all the AiA_iAi​ , and the sets A1,A2,A3,…A_1, A_2, A_3, \dotsA1​,A2​,A3​,… are mutually disjoint. Example: {{1,2},{3,4},{5,6}}\{\{1, 2\}, \{3, 4\}, \{5, 6\}\}{{1,2},{3,4},{5,6}} is a partition of {1,2,3,4,5,6}\{1, 2, 3, 4, 5, 6\}{1,2,3,4,5,6} .

  36. [Set Theory: Element Method of Proof] T0={n∈Z∣n=3k}T_0 = \{n \in \mathbf{Z} \mid n = 3k\}T0​={n∈Z∣n=3k} , T1={n∈Z∣n=3k+1}T_1 = \{n \in \mathbf{Z} \mid n = 3k + 1\}T1​={n∈Z∣n=3k+1} , T2={n∈Z∣n=3k+2}T_2 = \{n \in \mathbf{Z} \mid n = 3k + 2\}T2​={n∈Z∣n=3k+2} , each for some integer kkk .Is {T0,T1,T2}\{T_0, T_1, T_2\}{T0​,T1​,T2​} a partition of Z\mathbf{Z}Z ? Why?

    Yes, by the quotient-remainder theorem: every integer has exactly one of the forms 3k3k3k , 3k+13k + 13k+1 , 3k+23k + 23k+2 . "At least one" gives Z=T0∪T1∪T2\mathbf{Z} = T_0 \cup T_1 \cup T_2Z=T0​∪T1​∪T2​ ; "at most one" makes T0,T1,T2T_0, T_1, T_2T0​,T1​,T2​ mutually disjoint.Example: 7=3⋅2+1∈T17 = 3 \cdot 2 + 1 \in T_17=3⋅2+1∈T1​ , and −1=3⋅(−1)+2∈T2-1 = 3 \cdot (-1) + 2 \in T_2−1=3⋅(−1)+2∈T2​ .

  37. [Set Theory: Element Method of Proof] What is the power set P(A)\mathcal{P}(A)P(A) of a set AAA ?

    The set of all subsets of AAA . The power set axiom guarantees that it is a set.Example: P({x,y})={∅,{x},{y},{x,y}}\mathcal{P}(\{x, y\}) = \{\varnothing, \{x\}, \{y\}, \{x, y\}\}P({x,y})={∅,{x},{y},{x,y}} .

  38. [Set Theory: Element Method of Proof] What is an ordered nnn -tuple (x1,x2,…,xn)(x_1, x_2, \dots, x_n)(x1​,x2​,…,xn​) , and when are two ordered nnn -tuples equal?

    The elements x1,…,xnx_1, \dots, x_nx1​,…,xn​ together with the ordering x1x_1x1​ first, x2x_2x2​ second, ..., xnx_nxn​ last. (x1,…,xn)=(y1,…,yn) ⟺ x1=y1,…,xn=yn(x_1, \dots, x_n) = (y_1, \dots, y_n) \iff x_1 = y_1, \dots, x_n = y_n(x1​,…,xn​)=(y1​,…,yn​)⟺x1​=y1​,…,xn​=yn​ . Unlike a set, an ordered nnn -tuple takes order and repetition into account. An ordered 2-tuple is an ordered pair, an ordered 3-tuple an ordered triple.Example: (1,2,3,4)≠(1,2,4,3)(1, 2, 3, 4) \neq (1, 2, 4, 3)(1,2,3,4)=(1,…

  39. [Set Theory: Element Method of Proof] What is the Cartesian product A1×A2×⋯×AnA_1 \times A_2 \times \dots \times A_nA1​×A2​×⋯×An​ ?

    The set of all ordered nnn -tuples (a1,a2,…,an)(a_1, a_2, \dots, a_n)(a1​,a2​,…,an​) with a1∈A1,a2∈A2,…,an∈Ana_1 \in A_1, a_2 \in A_2, \dots, a_n \in A_na1​∈A1​,a2​∈A2​,…,an​∈An​ . Example: {x,y}×{1,2,3}={(x,1),(x,2),(x,3),(y,1),(y,2),(y,3)}\{x, y\} \times \{1, 2, 3\} = \{(x, 1), (x, 2), (x, 3), (y, 1), (y, 2), (y, 3)\}{x,y}×{1,2,3}={(x,1),(x,2),(x,3),(y,1),(y,2),(y,3)} .

  40. [Set Theory: Element Method of Proof] A1={x,y}A_1 = \{x, y\}A1​={x,y} , A2={1,2,3}A_2 = \{1, 2, 3\}A2​={1,2,3} , A3={a,b}A_3 = \{a, b\}A3​={a,b} . How do (A1×A2)×A3(A_1 \times A_2) \times A_3(A1​×A2​)×A3​ and A1×A2×A3A_1 \times A_2 \times A_3A1​×A2​×A3​ differ?

    (A1×A2)×A3(A_1 \times A_2) \times A_3(A1​×A2​)×A3​ is a set of ordered pairs whose first element is an ordered pair; A1×A2×A3A_1 \times A_2 \times A_3A1​×A2​×A3​ is a set of ordered triples. Example: ((x,1),a)∈(A1×A2)×A3((x, 1), a) \in (A_1 \times A_2) \times A_3((x,1),a)∈(A1​×A2​)×A3​ and (x,1,a)∈A1×A2×A3(x, 1, a) \in A_1 \times A_2 \times A_3(x,1,a)∈A1​×A2​×A3​ . Both sets have 2⋅3⋅2=122 \cdot 3 \cdot 2 = 122⋅3⋅2=12 elements.

  41. [Set Theory: Element Method of Proof] Finite sets AAA and BBB are given as arrays a[1],…,a[m]a[1], \dots, a[m]a[1],…,a[m] and b[1],…,b[n]b[1], \dots, b[n]b[1],…,b[n] . How does the algorithm for testing whether A⊆BA \subseteq BA⊆B work?

    Compare each a[i]a[i]a[i] with b[1],b[2],…b[1], b[2], \dotsb[1],b[2],… in turn. If some a[i]a[i]a[i] equals no b[j]b[j]b[j] , the answer is " A⊈BA \not\subseteq BA⊆B "; otherwise " A⊆BA \subseteq BA⊆B ". The variable found is set to "no" before each search and to "yes" when a[i]=b[j]a[i] = b[j]a[i]=b[j] . The outer loop stops as soon as the answer becomes " A⊈BA \not\subseteq BA⊆B ".

  42. [Set Theory: Element Method of Proof] Algorithm testing A⊆BA \subseteq BA⊆B : for each a[i]a[i]a[i] in turn, compare a[i]a[i]a[i] with b[1],b[2],…b[1], b[2], \dotsb[1],b[2],… until it is found; if some a[i]a[i]a[i] equals no b[j]b[j]b[j] , answer " A⊈BA \not\subseteq BA⊆B " and stop.Run it on a=(u,v,w)a = (u, v, w)a=(u,v,w) and b=(w,x,y,u)b = (w, x, y, u)b=(w,x,y,u) . What is the answer, and at which iii is it decided?

    " A⊈BA \not\subseteq BA⊆B ", decided at i=2i = 2i=2 . i=1i = 1i=1 : uuu is compared with w,x,yw, x, yw,x,y and found equal to b[4]=ub[4] = ub[4]=u . i=2i = 2i=2 : vvv equals none of b[1],…,b[4]b[1], \dots, b[4]b[1],…,b[4] , so found stays "no" and the answer becomes " A⊈BA \not\subseteq BA⊆B ". The element www is never checked.

  43. [Properties of Sets] Does A∩B⊆CA \cap B \subseteq CA∩B⊆C mean (A∩B)⊆C(A \cap B) \subseteq C(A∩B)⊆C or A∩(B⊆C)A \cap (B \subseteq C)A∩(B⊆C) ?

    (A∩B)⊆C\boldsymbol{(A \cap B) \subseteq C}(A∩B)⊆C Union, intersection and difference take precedence over set inclusion.

  44. [Properties of Sets] What subset relations hold for all sets AAA , BBB , CCC (named properties)?

    Inclusion of Intersection A∩B⊆AA \cap B \subseteq AA∩B⊆A and A∩B⊆BA \cap B \subseteq BA∩B⊆B Example: {2}⊆{1,2}\{2\} \subseteq \{1, 2\}{2}⊆{1,2} for A={1,2}A = \{1, 2\}A={1,2} , B={2,3}B = \{2, 3\}B={2,3} . Inclusion in Union A⊆A∪BA \subseteq A \cup BA⊆A∪B and B⊆A∪BB \subseteq A \cup BB⊆A∪B Example: {1,2}⊆{1,2,3}\{1, 2\} \subseteq \{1, 2, 3\}{1,2}⊆{1,2,3} for A={1,2}A = \{1, 2\}A={1,2} , B={2,3}B = \{2, 3\}B={2,3} . Transitive Property of Subsets If A⊆BA \subseteq BA⊆B and B⊆CB \subseteq CB⊆C ,…

  45. [Properties of Sets] XXX and YYY are subsets of a universal set UUU , and x,y∈Ux, y \in Ux,y∈U . What are the procedural versions of the set definitions?

    Union x∈X∪Y ⟺ x∈Xx \in X \cup Y \iff x \in Xx∈X∪Y⟺x∈X or x∈Yx \in Yx∈Y Intersection x∈X∩Y ⟺ x∈Xx \in X \cap Y \iff x \in Xx∈X∩Y⟺x∈X and x∈Yx \in Yx∈Y Difference x∈X−Y ⟺ x∈Xx \in X - Y \iff x \in Xx∈X−Y⟺x∈X and x∉Yx \notin Yx∈/Y Complement x∈Xc ⟺ x∉Xx \in X^c \iff x \notin Xx∈Xc⟺x∈/X Cartesian product (x,y)∈X×Y ⟺ x∈X(x, y) \in X \times Y \iff x \in X(x,y)∈X×Y⟺x∈X and y∈Yy \in Yy∈Y They turn each statement " xxx is in this set" into a statement about xxx that a proof can use, and back.

  46. [Properties of Sets] How does an element argument prove A∩B⊆AA \cap B \subseteq AA∩B⊆A for all sets AAA and BBB ?

    Suppose x∈A∩Bx \in A \cap Bx∈A∩B . Then x∈Ax \in Ax∈A and x∈Bx \in Bx∈B by definition of intersection; in particular x∈Ax \in Ax∈A . The step is the valid argument form p∧qp \wedge qp∧q , ∴p\therefore p∴p .

  47. [Properties of Sets] What is Douglas Hofstadter's fantasy rule for mathematical proof (from Gödel, Escher, Bach)?

    A "suppose" (or "if", "let") enters a fantasy world where everything true stays true and the supposition is true too. Further suppositions enter subfantasy worlds. Each conclusion that makes a whole if-then or universal statement true returns one level; a proof ends back in the world of the first supposition.

  48. [Properties of Sets] A problem says: "Suppose (statement 1). Prove that (statement 2)." How does the proof begin?

    With the starting point for a proof of statement 2; statement 1 is taken as known and is not restated. Example: "Suppose AAA and BBB are arbitrarily chosen sets. Prove that A∩B⊆AA \cap B \subseteq AA∩B⊆A ." The proof begins "Suppose x∈A∩Bx \in A \cap Bx∈A∩B ."

  49. [Properties of Sets] For which numbers nnn of sets can a symmetric Venn diagram showing every possible intersection be drawn?

    Exactly when nnn is prime. Impossibility for nonprime nnn was known; the existence for every prime nnn was proved in 2002 by Jerrold Griggs, Charles Killian and Carla Savage.Example: such diagrams exist for 2, 3, 5 and 7 sets, but not for 4 or 6 sets.

  50. [Properties of Sets] What is an identity?

    An equation that is true for all elements of some set. Example: a+b=b+aa + b = b + aa+b=b+a is an identity for real numbers. The set identities are equations true for all subsets of a universal set.

  51. [Properties of Sets] State the commutative and associative laws for sets.

    Commutative laws A∪B=B∪AA \cup B = B \cup AA∪B=B∪A and A∩B=B∩AA \cap B = B \cap AA∩B=B∩A Example: {1}∪{2}={2}∪{1}={1,2}\{1\} \cup \{2\} = \{2\} \cup \{1\} = \{1, 2\}{1}∪{2}={2}∪{1}={1,2} . Associative laws (A∪B)∪C=A∪(B∪C)(A \cup B) \cup C = A \cup (B \cup C)(A∪B)∪C=A∪(B∪C) and (A∩B)∩C=A∩(B∩C)(A \cap B) \cap C = A \cap (B \cap C)(A∩B)∩C=A∩(B∩C) Example: ({1}∪{2})∪{3}={1}∪({2}∪{3})={1,2,3}(\{1\} \cup \{2\}) \cup \{3\} = \{1\} \cup (\{2\} \cup \{3\}) = \{1, 2, 3\}({1}∪{2})∪{3}={1}∪({2}∪{3})={1,2,3…

  52. [Properties of Sets] State the two distributive laws for sets.

    A∪(B∩C)=(A∪B)∩(A∪C)\boldsymbol{A \cup (B \cap C) = (A \cup B) \cap (A \cup C)}A∪(B∩C)=(A∪B)∩(A∪C) and A∩(B∪C)=(A∩B)∪(A∩C)\boldsymbol{A \cap (B \cup C) = (A \cap B) \cup (A \cap C)}A∩(B∪C)=(A∩B)∪(A∩C) Example: A={1}A = \{1\}A={1} , B={1,2}B = \{1, 2\}B={1,2} , C={2,3}C = \{2, 3\}C={2,3} : A∪(B∩C)={1,2}A \cup (B \cap C) = \{1, 2\}A∪(B∩C)={1,2} and (A∪B)∩(A∪C)={1,2}∩{1,2,3}={1,2}(A \cup B) \cap (A \cup C) = \{1, 2\} \cap \{1, 2, 3\} = \{1, 2\}(A∪B)∩(A∪C)={1,2}∩{1,2,3}={1,2} .

  53. [Properties of Sets] State the identity laws and the universal bound laws for a set AAA in a universal set UUU .

    Identity laws A∪∅=AA \cup \varnothing = AA∪∅=A and A∩U=AA \cap U = AA∩U=A Example: {1}∪∅={1}\{1\} \cup \varnothing = \{1\}{1}∪∅={1} . Universal bound laws A∪U=UA \cup U = UA∪U=U and A∩∅=∅A \cap \varnothing = \varnothingA∩∅=∅ Example: with U={1,2}U = \{1, 2\}U={1,2} , {1}∪U={1,2}\{1\} \cup U = \{1, 2\}{1}∪U={1,2} .

  54. [Properties of Sets] State the complement laws, the double complement law and the laws for the complements of UUU and ∅\varnothing∅ .

    Complement laws A∪Ac=UA \cup A^c = UA∪Ac=U and A∩Ac=∅A \cap A^c = \varnothingA∩Ac=∅ Example: with U={1,2,3}U = \{1, 2, 3\}U={1,2,3} , {1}∪{2,3}=U\{1\} \cup \{2, 3\} = U{1}∪{2,3}=U and {1}∩{2,3}=∅\{1\} \cap \{2, 3\} = \varnothing{1}∩{2,3}=∅ . Double complement law (Ac)c=A(A^c)^c = A(Ac)c=A Example: with U={1,2,3}U = \{1, 2, 3\}U={1,2,3} , ({1}c)c={2,3}c={1}(\{1\}^c)^c = \{2, 3\}^c = \{1\}({1}c)c={2,3}c={1} . Complements of UUU and ∅\varnothing∅ Uc=∅U^c = \varnothingUc=∅ and ∅c=U\varnothing^c = U…

  55. [Properties of Sets] State the idempotent laws and the absorption laws for sets.

    Idempotent laws A∪A=AA \cup A = AA∪A=A and A∩A=AA \cap A = AA∩A=A Example: {1,2}∪{1,2}={1,2}\{1, 2\} \cup \{1, 2\} = \{1, 2\}{1,2}∪{1,2}={1,2} . Absorption laws A∪(A∩B)=AA \cup (A \cap B) = AA∪(A∩B)=A and A∩(A∪B)=AA \cap (A \cup B) = AA∩(A∪B)=A Example: A={1,2}A = \{1, 2\}A={1,2} , B={2,3}B = \{2, 3\}B={2,3} : A∪{2}=AA \cup \{2\} = AA∪{2}=A and A∩{1,2,3}=AA \cap \{1, 2, 3\} = AA∩{1,2,3}=A .

  56. [Properties of Sets] State De Morgan's laws for sets.

    (A∪B)c=Ac∩Bc\boldsymbol{(A \cup B)^c = A^c \cap B^c}(A∪B)c=Ac∩Bc and (A∩B)c=Ac∪Bc\boldsymbol{(A \cap B)^c = A^c \cup B^c}(A∩B)c=Ac∪Bc Example: U={1,2,3}U = \{1, 2, 3\}U={1,2,3} , A={1}A = \{1\}A={1} , B={2}B = \{2\}B={2} : (A∪B)c={3}={2,3}∩{1,3}(A \cup B)^c = \{3\} = \{2, 3\} \cap \{1, 3\}(A∪B)c={3}={2,3}∩{1,3} .

  57. [Properties of Sets] State the set difference law: A−B= ?A - B = \; ?A−B=?

    A−B=A∩Bc\boldsymbol{A - B = A \cap B^c}A−B=A∩Bc Example: U={1,2,3}U = \{1, 2, 3\}U={1,2,3} , A={1,2}A = \{1, 2\}A={1,2} , B={2,3}B = \{2, 3\}B={2,3} : A−B={1}={1,2}∩{1}A - B = \{1\} = \{1, 2\} \cap \{1\}A−B={1}={1,2}∩{1} .

  58. [Properties of Sets] What is the basic method for proving that two sets XXX and YYY are equal?

    Prove X⊆YX \subseteq YX⊆Y , then prove Y⊆XY \subseteq XY⊆X . Two sets are equal if, and only if, each is a subset of the other.

  59. [Properties of Sets] How do you prove that a set XXX does not equal a set YYY ?

    Find an element that is in XXX and not in YYY , or one that is in YYY and not in XXX . Example: {1,2}≠{1,2,3}\{1, 2\} \neq \{1, 2, 3\}{1,2}={1,2,3} , shown by 333 .

  60. [Properties of Sets] How do you prove that a set XXX is a subset of A∩BA \cap BA∩B , and that XXX is a subset of A∪BA \cup BA∪B ?

    Take any x∈Xx \in Xx∈X ; for A∩BA \cap BA∩B show x∈Ax \in Ax∈A and x∈Bx \in Bx∈B , for A∪BA \cup BA∪B show x∈Ax \in Ax∈A or x∈Bx \in Bx∈B . Example: {2}⊆{1,2}∩{2,3}\{2\} \subseteq \{1, 2\} \cap \{2, 3\}{2}⊆{1,2}∩{2,3} since 222 is in both sets.

  61. [Properties of Sets] How do you prove that A∪BA \cup BA∪B is a subset of a set XXX , and that A∩BA \cap BA∩B is a subset of XXX ?

    For A∪BA \cup BA∪B : take any x∈A∪Bx \in A \cup Bx∈A∪B and show x∈Xx \in Xx∈X in both cases x∈Ax \in Ax∈A and x∈Bx \in Bx∈B . For A∩BA \cap BA∩B : suppose x∈Ax \in Ax∈A and x∈Bx \in Bx∈B , and show x∈Xx \in Xx∈X .

  62. [Properties of Sets] To prove: A∪(B∩C)=(A∪B)∩(A∪C)A \cup (B \cap C) = (A \cup B) \cap (A \cup C)A∪(B∩C)=(A∪B)∩(A∪C) for all sets AAA , BBB , CCC .How does the proof of A∪(B∩C)⊆(A∪B)∩(A∪C)A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)A∪(B∩C)⊆(A∪B)∩(A∪C) go?

    Suppose x∈A∪(B∩C)x \in A \cup (B \cap C)x∈A∪(B∩C) and split into the cases x∈Ax \in Ax∈A and x∈B∩Cx \in B \cap Cx∈B∩C ; in each, x∈A∪Bx \in A \cup Bx∈A∪B and x∈A∪Cx \in A \cup Cx∈A∪C . Case x∈Ax \in Ax∈A : xxx is in both unions because it is in AAA .Case x∈B∩Cx \in B \cap Cx∈B∩C : x∈Bx \in Bx∈B gives x∈A∪Bx \in A \cup Bx∈A∪B , and x∈Cx \in Cx∈C gives x∈A∪Cx \in A \cup Cx∈A∪C .

  63. [Properties of Sets] To prove: A∪(B∩C)=(A∪B)∩(A∪C)A \cup (B \cap C) = (A \cup B) \cap (A \cup C)A∪(B∩C)=(A∪B)∩(A∪C) for all sets AAA , BBB , CCC .How does the proof of (A∪B)∩(A∪C)⊆A∪(B∩C)(A \cup B) \cap (A \cup C) \subseteq A \cup (B \cap C)(A∪B)∩(A∪C)⊆A∪(B∩C) go?

    Suppose x∈A∪Bx \in A \cup Bx∈A∪B and x∈A∪Cx \in A \cup Cx∈A∪C , and split into the cases x∈Ax \in Ax∈A and x∉Ax \notin Ax∈/A . Case x∈Ax \in Ax∈A : then x∈A∪(B∩C)x \in A \cup (B \cap C)x∈A∪(B∩C) by definition of union.Case x∉Ax \notin Ax∈/A : x∈A∪Bx \in A \cup Bx∈A∪B forces x∈Bx \in Bx∈B , and x∈A∪Cx \in A \cup Cx∈A∪C forces x∈Cx \in Cx∈C ; so x∈B∩C⊆A∪(B∩C)x \in B \cap C \subseteq A \cup (B \cap C)x∈B∩C⊆A∪(B∩C) .

  64. [Properties of Sets] What are backward chaining and forward chaining (terms from artificial intelligence) in finding a proof?

    Backward chaining From the goal, find a subgoal SG1SG_1SG1​ that suffices for it, then a subgoal SG2SG_2SG2​ that suffices for SG1SG_1SG1​ , and so on. Example: for A∪(B∩C)=(A∪B)∩(A∪C)A \cup (B \cap C) = (A \cup B) \cap (A \cup C)A∪(B∩C)=(A∪B)∩(A∪C) , SG1SG_1SG1​ is to show that each side is a subset of the other. Forward chaining From the starting point, deduce facts I1,I2,…I_1, I_2, \dotsI1​,I2​,… until one of the subgoals is reached. Example: from x∈B∩Cx \in B \cap Cx∈B∩C deduce x∈Bx \in Bx∈…

  65. [Properties of Sets] How does an element argument prove (A∪B)c⊆Ac∩Bc(A \cup B)^c \subseteq A^c \cap B^c(A∪B)c⊆Ac∩Bc ?

    x∈(A∪B)cx \in (A \cup B)^cx∈(A∪B)c means: not ( x∈Ax \in Ax∈A or x∈Bx \in Bx∈B ). By De Morgan's laws of logic, x∉Ax \notin Ax∈/A and x∉Bx \notin Bx∈/B , so x∈Ac∩Bcx \in A^c \cap B^cx∈Ac∩Bc . The reverse inclusion Ac∩Bc⊆(A∪B)cA^c \cap B^c \subseteq (A \cup B)^cAc∩Bc⊆(A∪B)c runs the same steps backwards. Together they prove De Morgan's law (A∪B)c=Ac∩Bc(A \cup B)^c = A^c \cap B^c(A∪B)c=Ac∩Bc for sets.

  66. [Properties of Sets] Theorem 6.2.3 (Intersection and Union with a Subset) For any sets AAA and BBB , if A⊆BA \subseteq BA⊆B , then … ?

    A∩B=A\boldsymbol{A \cap B = A}A∩B=A and A∪B=B\boldsymbol{A \cup B = B}A∪B=B The intersection is the smaller of the two sets and the union the larger.Example: {1}⊆{1,2}\{1\} \subseteq \{1, 2\}{1}⊆{1,2} , so {1}∩{1,2}={1}\{1\} \cap \{1, 2\} = \{1\}{1}∩{1,2}={1} and {1}∪{1,2}={1,2}\{1\} \cup \{1, 2\} = \{1, 2\}{1}∪{1,2}={1,2} .

  67. [Properties of Sets] If A⊆BA \subseteq BA⊆B , why is A⊆A∩BA \subseteq A \cap BA⊆A∩B ?

    Any x∈Ax \in Ax∈A is also in BBB because A⊆BA \subseteq BA⊆B , so x∈A∩Bx \in A \cap Bx∈A∩B . With A∩B⊆AA \cap B \subseteq AA∩B⊆A (inclusion of intersection) this proves A∩B=AA \cap B = AA∩B=A .

  68. [Properties of Sets] Why is a set EEE with no elements a subset of every set AAA ?

    E⊈AE \not\subseteq AE⊆A would require an element of EEE that is not in AAA , and EEE has no elements. Equivalently: " ∀x\forall x∀x , if x∈Ex \in Ex∈E then x∈Ax \in Ax∈A " is vacuously true, since x∈Ex \in Ex∈E is false for every xxx .

  69. [Properties of Sets] Why is there only one set with no elements?

    If E1E_1E1​ and E2E_2E2​ have no elements, then E1⊆E2E_1 \subseteq E_2E1​⊆E2​ and E2⊆E1E_2 \subseteq E_1E2​⊆E1​ (a set with no elements is a subset of every set), so E1=E2E_1 = E_2E1​=E2​ . This uniqueness justifies the name "the empty set" and the symbol ∅\varnothing∅ . Example: the set of pink elephants equals {x∈R∣x2=−1}\{x \in \mathbf{R} \mid x^2 = -1\}{x∈R∣x2=−1} .

  70. [Properties of Sets] How many elements do ∅\varnothing∅ and {∅}\{\varnothing\}{∅} have?

    ∅\boldsymbol{\varnothing}∅ has 0 elements; {∅}\boldsymbol{\{\varnothing\}}{∅} has 1 element, namely ∅\varnothing∅ . In LISP and Scheme, likewise, ( ) is the empty list and (( )) is the list whose one element is the empty list.

  71. [Properties of Sets] What is the element method for proving that a set XXX equals ∅\varnothing∅ ?

    Suppose XXX has an element and derive a contradiction. There is only one set with no elements, so a set with no elements equals ∅\varnothing∅ .Example: {x∈Z∣2x=1}=∅\{x \in \mathbf{Z} \mid 2x = 1\} = \varnothing{x∈Z∣2x=1}=∅ : an element xxx would give x=12∉Zx = \frac{1}{2} \notin \mathbf{Z}x=21​∈/Z .

  72. [Properties of Sets] Prove that A∩∅=∅A \cap \varnothing = \varnothingA∩∅=∅ for every set AAA .

    Suppose x∈A∩∅x \in A \cap \varnothingx∈A∩∅ . Then x∈Ax \in Ax∈A and x∈∅x \in \varnothingx∈∅ ; but ∅\varnothing∅ has no elements, a contradiction. So A∩∅A \cap \varnothingA∩∅ has no elements and equals ∅\varnothing∅ (universal bound law).

  73. [Properties of Sets] Prove: for all sets AAA , BBB , CCC , if A⊆BA \subseteq BA⊆B and B⊆CcB \subseteq C^cB⊆Cc , then A∩C=∅A \cap C = \varnothingA∩C=∅ .

    Suppose x∈A∩Cx \in A \cap Cx∈A∩C . Then x∈A⊆B⊆Ccx \in A \subseteq B \subseteq C^cx∈A⊆B⊆Cc , so x∉Cx \notin Cx∈/C , but also x∈Cx \in Cx∈C : a contradiction. Hence A∩CA \cap CA∩C has no elements, so A∩C=∅A \cap C = \varnothingA∩C=∅ .Example: A={1}A = \{1\}A={1} , B={1,2}B = \{1, 2\}B={1,2} , U={1,2,3}U = \{1, 2, 3\}U={1,2,3} , C={3}C = \{3\}C={3} : B⊆Cc={1,2}B \subseteq C^c = \{1, 2\}B⊆Cc={1,2} and A∩C=∅A \cap C = \varnothingA∩C=∅ .

  74. [Properties of Sets] State the generalized distributive law A∪⋂i=1nBi= ?A \cup \displaystyle\bigcap_{i=1}^{n} B_i = \; ?A∪i=1⋂n​Bi​=?

    ⋂i=1n(A∪Bi)\boldsymbol{\displaystyle\bigcap_{i=1}^{n} (A \cup B_i)}i=1⋂n​(A∪Bi​) Proof as for A∪(B∩C)=(A∪B)∩(A∪C)A \cup (B \cap C) = (A \cup B) \cap (A \cup C)A∪(B∩C)=(A∪B)∩(A∪C) : for ⊆\subseteq⊆ , the cases x∈Ax \in Ax∈A and x∈x \inx∈ every BiB_iBi​ ; for ⊇\supseteq⊇ , the cases x∈Ax \in Ax∈A and x∉Ax \notin Ax∈/A (then x∈A∪Bix \in A \cup B_ix∈A∪Bi​ forces x∈Bix \in B_ix∈Bi​ for every iii ).Example: A={0}A = \{0\}A={0} , B1={1,2}B_1 = \{1, 2\}B1​={1,2} , B2={2,3}B_2 = \{2, 3\}B2​={2,3} : both…

  75. [Disproofs and Algebraic Proofs] How do you show that a proposed set identity "for all sets AAA , BBB , CCC , (left side) = (right side)" is false?

    Find one counterexample: concrete sets AAA , BBB , CCC that make the left side unequal to the right side. The identity is a universal statement, so one case where it fails is enough.

  76. [Disproofs and Algebraic Proofs] Is it true that for all sets AAA , BBB and CCC , (A−B)∪(B−C)=A−C(A - B) \cup (B - C) = A - C(A−B)∪(B−C)=A−C ?

    No. Left: (A−B)∪(B−C)(A - B) \cup (B - C)(A−B)∪(B−C) shaded. Right: A−CA - CA−C shaded. The two shaded regions differ.

  77. [Disproofs and Algebraic Proofs] Which elements lie in (A−B)∪(B−C)(A - B) \cup (B - C)(A−B)∪(B−C) but not in A−CA - CA−C ?

    An element of BBB that is in neither AAA nor CCC , and an element of AAA and CCC that is not in BBB . The first is in B−CB - CB−C but outside AAA ; the second is in A−BA - BA−B but also in CCC .Example: A=C={4}A = C = \{4\}A=C={4} , B=∅B = \emptysetB=∅ : (A−B)∪(B−C)={4}(A - B) \cup (B - C) = \{4\}(A−B)∪(B−C)={4} , while A−C=∅A - C = \emptysetA−C=∅ .

  78. [Disproofs and Algebraic Proofs] How do you turn a Venn diagram of three sets AAA , BBB , CCC into a concrete counterexample?

    Write the numbers 1 to 7 in the seven regions inside the circles (and 8 outside), and let each set consist of the numbers in its circle. Example: here A={1,2,4,5}A = \{1, 2, 4, 5\}A={1,2,4,5} , B={2,3,5,6}B = \{2, 3, 5, 6\}B={2,3,5,6} , C={4,5,6,7}C = \{4, 5, 6, 7\}C={4,5,6,7} , U={1,…,8}U = \{1, \dots, 8\}U={1,…,8} . The 8 is needed only when the identity involves complements.

  79. [Disproofs and Algebraic Proofs] Let A={1,2,4,5}A = \{1, 2, 4, 5\}A={1,2,4,5} , B={2,3,5,6}B = \{2, 3, 5, 6\}B={2,3,5,6} , C={4,5,6,7}C = \{4, 5, 6, 7\}C={4,5,6,7} . Compute (A−B)∪(B−C)(A - B) \cup (B - C)(A−B)∪(B−C) and A−CA - CA−C .

    (A−B)∪(B−C)={1,2,3,4}\boldsymbol{(A - B) \cup (B - C) = \{1, 2, 3, 4\}}(A−B)∪(B−C)={1,2,3,4} , A−C={1,2}\ \boldsymbol{A - C = \{1, 2\}} A−C={1,2} A−B={1,4}A - B = \{1, 4\}A−B={1,4} and B−C={2,3}B - C = \{2, 3\}B−C={2,3} . So these sets disprove (A−B)∪(B−C)=A−C(A - B) \cup (B - C) = A - C(A−B)∪(B−C)=A−C .

  80. [Disproofs and Algebraic Proofs] Give a counterexample to "for all sets AAA , BBB , CCC : (A−B)∪(B−C)=A−C(A - B) \cup (B - C) = A - C(A−B)∪(B−C)=A−C " with only one element in total.

    A=∅, B={3}, C=∅\boldsymbol{A = \emptyset, \ B = \{3\}, \ C = \emptyset}A=∅, B={3}, C=∅ (A−B)∪(B−C)=∅∪{3}={3}(A - B) \cup (B - C) = \emptyset \cup \{3\} = \{3\}(A−B)∪(B−C)=∅∪{3}={3} , while A−C=∅A - C = \emptysetA−C=∅ .Any BBB with an element outside AAA works, whatever else the sets contain.

  81. [Disproofs and Algebraic Proofs] What two approaches does Epp describe for deciding whether a universal statement about sets is true or false?

    Optimistic approach Start proving the statement: "What do I need to show?" and "How do I show it?" Pessimistic approach Search for conditions that a counterexample must fulfill. Switch to the other approach when the one you are trying does not look promising; hard questions can need several switches.

  82. [Disproofs and Algebraic Proofs] Theorem 6.3.1 For all integers n≥0n \ge 0n≥0 , if a set XXX has nnn elements, then P(X)\mathcal{P}(X)P(X) (the power set of XXX ) has … ?

    2n\boldsymbol{2^n}2n elements Example: P({x,y})={∅,{x},{y},{x,y}}\mathcal{P}(\{x, y\}) = \{\emptyset, \{x\}, \{y\}, \{x, y\}\}P({x,y})={∅,{x},{y},{x,y}} has 22=42^2 = 422=4 elements.

  83. [Disproofs and Algebraic Proofs] XXX is a set and z∈Xz \in Xz∈X . Why does XXX have as many subsets that contain zzz as subsets that do not contain zzz ?

    Matching each subset AAA without zzz to A∪{z}A \cup \{z\}A∪{z} pairs them up one for one. Example: X={x,y,z}X = \{x, y, z\}X={x,y,z} : ∅↔{z}\ \emptyset \leftrightarrow \{z\} ∅↔{z} , {x}↔{x,z}\ \{x\} \leftrightarrow \{x, z\} {x}↔{x,z} , {y}↔{y,z}\ \{y\} \leftrightarrow \{y, z\} {y}↔{y,z} , {x,y}↔{x,y,z}\ \{x, y\} \leftrightarrow \{x, y, z\} {x,y}↔{x,y,z} .

  84. [Disproofs and Algebraic Proofs] Proof by induction that every set with nnn elements has 2n2^n2n subsets: why is the basis step n=0n = 0n=0 true?

    The only set with 0 elements is ∅\emptyset∅ , and its only subset is ∅\emptyset∅ : one subset, and 1=201 = 2^01=20 .

  85. [Disproofs and Algebraic Proofs] Inductive hypothesis: every set with kkk elements has 2k2^k2k subsets.How does the inductive step show that a set XXX with k+1k + 1k+1 elements has 2k+12^{k+1}2k+1 subsets?

    Pick z∈Xz \in Xz∈X . Subsets without zzz are the subsets of X−{z}X - \{z\}X−{z} , and there are equally many with zzz , so XXX has 2⋅2k=2k+12 \cdot 2^k = 2^{k+1}2⋅2k=2k+1 subsets. X−{z}X - \{z\}X−{z} has kkk elements, so it has 2k2^k2k subsets by the inductive hypothesis. The subsets with zzz are the sets A∪{z}A \cup \{z\}A∪{z} for A⊆X−{z}A \subseteq X - \{z\}A⊆X−{z} .

  86. [Disproofs and Algebraic Proofs] What is an algebraic proof of a set identity?

    A derivation of the identity from set properties already known to be true, without element arguments. Example: A−(A∩B)=A∩(A∩B)c=⋯=A−BA - (A \cap B) = A \cap (A \cap B)^c = \dots = A - BA−(A∩B)=A∩(A∩B)c=⋯=A−B , each step justified by a known property.

  87. [Disproofs and Algebraic Proofs] Which set properties suffice to prove algebraically every identity involving only ∪\cup∪ , ∩\cap∩ and complement?

    The commutative, associative, distributive, identity and complement laws. Identity laws: A∪∅=AA \cup \emptyset = AA∪∅=A , A∩U=AA \cap U = AA∩U=A . Complement laws: A∪Ac=UA \cup A^c = UA∪Ac=U , A∩Ac=∅A \cap A^c = \emptysetA∩Ac=∅ .Adding the set difference law A−B=A∩BcA - B = A \cap B^cA−B=A∩Bc covers identities with set differences too.

  88. [Disproofs and Algebraic Proofs] Distributive law: for all sets AAA , BBB , CCC , A∩(B∪C)=(A∩B)∪(A∩C)A \cap (B \cup C) = (A \cap B) \cup (A \cap C)A∩(B∪C)=(A∩B)∪(A∩C) .What does this law give for (W∩X)∩(Y∪Z)(W \cap X) \cap (Y \cup Z)(W∩X)∩(Y∪Z) , and which set plays which role?

    ((W∩X)∩Y)∪((W∩X)∩Z)\boldsymbol{((W \cap X) \cap Y) \cup ((W \cap X) \cap Z)}((W∩X)∩Y)∪((W∩X)∩Z) , with W∩XW \cap XW∩X in the role of AAA , YYY of BBB , ZZZ of CCC . A set property is a universal statement, so any sets (also composite ones) can be substituted for its variables.

  89. [Disproofs and Algebraic Proofs] In an algebraic proof of a set identity, you must cite one of the known set properties for every step.

    Example: (A∪B)−C=(A∪B)∩Cc(A \cup B) - C = (A \cup B) \cap C^c(A∪B)−C=(A∪B)∩Cc , by the set difference law.

  90. [Disproofs and Algebraic Proofs] When you apply a set property in an algebraic proof, you must use it exactly as it is stated.

    The distributive law is stated as A∩(B∪C)=(A∩B)∪(A∩C)A \cap (B \cup C) = (A \cap B) \cup (A \cap C)A∩(B∪C)=(A∩B)∪(A∩C) . Example: to expand (A∪B)∩Cc(A \cup B) \cap C^c(A∪B)∩Cc , first rewrite it as Cc∩(A∪B)C^c \cap (A \cup B)Cc∩(A∪B) by the commutative law, then apply the distributive law.

  91. [Disproofs and Algebraic Proofs] Set difference law: X−Y=X∩YcX - Y = X \cap Y^cX−Y=X∩Yc . Distributive law: X∩(Y∪Z)=(X∩Y)∪(X∩Z)X \cap (Y \cup Z) = (X \cap Y) \cup (X \cap Z)X∩(Y∪Z)=(X∩Y)∪(X∩Z) .Give an algebraic proof that (A∪B)−C=(A−C)∪(B−C)(A \cup B) - C = (A - C) \cup (B - C)(A∪B)−C=(A−C)∪(B−C) for all sets AAA , BBB , CCC .

    Set difference law, commutative law, distributive law, commutative law, set difference law: (A∪B)−C=(A∪B)∩Ccset difference law=Cc∩(A∪B)commutative law for ∩=(Cc∩A)∪(Cc∩B)distributive law=(A∩Cc)∪(B∩Cc)commutative law for ∩=(A−C)∪(B−C)set difference law\begin{array}{rll} (A \cup B) - C &= (A \cup B) \cap C^c & \text{set difference law} \\ &= C^c \cap (A \cup B) & \text{commutative law for } \cap \\ &= (C^c \cap A) \cup (C^c \cap B) & \text{distributive law} \\ &= (A \cap C^c) \cup (B \cap C^c) &…

  92. [Disproofs and Algebraic Proofs] Set difference law: X−Y=X∩YcX - Y = X \cap Y^cX−Y=X∩Yc .Give an algebraic proof that A−(A∩B)=A−BA - (A \cap B) = A - BA−(A∩B)=A−B for all sets AAA and BBB .

    Rewrite as A∩(A∩B)cA \cap (A \cap B)^cA∩(A∩B)c , apply De Morgan, distribute, and A∩Ac=∅A \cap A^c = \emptysetA∩Ac=∅ drops out: A−(A∩B)=A∩(A∩B)cset difference law=A∩(Ac∪Bc)De Morgan’s law=(A∩Ac)∪(A∩Bc)distributive law=∅∪(A∩Bc)complement law=(A∩Bc)∪∅commutative law for ∪=A∩Bcidentity law for ∪=A−Bset difference law\begin{array}{rll} A - (A \cap B) &= A \cap (A \cap B)^c & \text{set difference law} \\ &= A \cap (A^c \cup B^c) & \text{De Morgan&#x27;s law} \\ &= (A \cap A^c) \cup (A \cap B^c) & \t…

  93. [Disproofs and Algebraic Proofs] Give an element argument that A−(A∩B)=A−BA - (A \cap B) = A - BA−(A∩B)=A−B .

    xxx is in AAA and not in both AAA and BBB , which for x∈Ax \in Ax∈A means exactly that xxx is not in BBB . Here the element argument is shorter than the seven-step algebraic proof: an algebraic proof is often not the simpler one.

  94. [Disproofs and Algebraic Proofs] Associative law for ∪\cup∪ : (A∪B)∪C=A∪(B∪C)(A \cup B) \cup C = A \cup (B \cup C)(A∪B)∪C=A∪(B∪C) for all sets AAA , BBB , CCC .How do you prove ((A1∪A2)∪A3)∪A4=A1∪((A2∪A3)∪A4)((A_1 \cup A_2) \cup A_3) \cup A_4 = A_1 \cup ((A_2 \cup A_3) \cup A_4)((A1​∪A2​)∪A3​)∪A4​=A1​∪((A2​∪A3​)∪A4​) ?

    Apply the associative law twice: ((A1∪A2)∪A3)∪A4=(A1∪(A2∪A3))∪A4((A_1 \cup A_2) \cup A_3) \cup A_4 = (A_1 \cup (A_2 \cup A_3)) \cup A_4((A1​∪A2​)∪A3​)∪A4​=(A1​∪(A2​∪A3​))∪A4​ , with A1,A2,A3A_1, A_2, A_3A1​,A2​,A3​ in the roles of A,B,CA, B, CA,B,C . (A1∪(A2∪A3))∪A4=A1∪((A2∪A3)∪A4)(A_1 \cup (A_2 \cup A_3)) \cup A_4 = A_1 \cup ((A_2 \cup A_3) \cup A_4)(A1​∪(A2​∪A3​))∪A4​=A1​∪((A2​∪A3​)∪A4​) , with A1A_1A1​ , A2∪A3A_2 \cup A_3A2​∪A3​ , A4A_4A4​ in the roles of A,B,CA, B, CA,B,C .

  95. [Boolean Algebras, Russell's Paradox] Logical equivalences and set identities have the same form. Which set notion corresponds to each of ∨\vee∨ , ∧\wedge∧ , t\mathbf{t}t (tautology), c\mathbf{c}c (contradiction), ∼\sim∼ ?

    ∨↔\vee \leftrightarrow∨↔ ∪\cup∪ , ∧↔\ \wedge \leftrightarrow ∧↔ ∩\cap∩ , t↔\ \mathbf{t} \leftrightarrow t↔ UUU , c↔\ \mathbf{c} \leftrightarrow c↔ ∅\emptyset∅ , ∼↔\ \sim \leftrightarrow ∼↔ complement c^cc Example: p∨∼p≡tp \vee \sim p \equiv \mathbf{t}p∨∼p≡t corresponds to A∪Ac=UA \cup A^c = UA∪Ac=U .

  96. [Boolean Algebras, Russell's Paradox] Which set identities correspond to the logical equivalences p∨(p∧q)≡pp \vee (p \wedge q) \equiv pp∨(p∧q)≡p and ∼t≡c\sim \mathbf{t} \equiv \mathbf{c}∼t≡c ?

    A∪(A∩B)=A\boldsymbol{A \cup (A \cap B) = A}A∪(A∩B)=A (absorption) and Uc=∅\boldsymbol{U^c = \emptyset}Uc=∅ Replace ∨,∧,∼,t,c\vee, \wedge, \sim, \mathbf{t}, \mathbf{c}∨,∧,∼,t,c by ∪,∩,c,U,∅\cup, \cap, {}^c, U, \emptyset∪,∩,c,U,∅ .

  97. [Boolean Algebras, Russell's Paradox] What is a Boolean algebra?

    Set with two operations A set BBB with operations +++ and ⋅\cdot⋅ such that a+b∈Ba + b \in Ba+b∈B and a⋅b∈Ba \cdot b \in Ba⋅b∈B for all a,b∈Ba, b \in Ba,b∈B , satisfying the five laws below. Commutative laws a+b=b+aa + b = b + aa+b=b+a and a⋅b=b⋅aa \cdot b = b \cdot aa⋅b=b⋅a Associative laws (a+b)+c=a+(b+c)(a + b) + c = a + (b + c)(a+b)+c=a+(b+c) and (a⋅b)⋅c=a⋅(b⋅c)(a \cdot b) \cdot c = a \cdot (b \cdot c)(a⋅b)⋅c=a⋅(b⋅c) Distributive laws a+(b⋅c)=(a+b)⋅(a+c)a + (b \cdot c) = (a + b) \cdot (a +…

  98. [Boolean Algebras, Russell's Paradox] In a Boolean algebra, a+(b⋅c)= ?a + (b \cdot c) = \; ?a+(b⋅c)=?

    (a+b)⋅(a+c)\boldsymbol{(a + b) \cdot (a + c)}(a+b)⋅(a+c) (distributive law for +++ over ⋅\cdot⋅ ) Unlike for real numbers, +++ distributes over ⋅\cdot⋅ as well as ⋅\cdot⋅ over +++ .Example: for sets, A∪(B∩C)=(A∪B)∩(A∪C)A \cup (B \cap C) = (A \cup B) \cap (A \cup C)A∪(B∩C)=(A∪B)∩(A∪C) .

  99. [Boolean Algebras, Russell's Paradox] The operations +++ and ⋅\cdot⋅ of a Boolean algebra generalize or and and on statement forms, and union and intersection on the subsets of a set.

    Example: p∨qp \vee qp∨q and A∪BA \cup BA∪B are both instances of a+ba + ba+b .

  100. [Boolean Algebras, Russell's Paradox] Who introduced the essential idea of a Boolean algebra, and where?

    George Boole, in 1847, in his book "The Mathematical Analysis of Logic". Boole was a self-taught English mathematician and logician.