Ch.8: Relations

Chapter 8 of the book "Discrete Mathematics with Applications" by Susanna S. Epp (4th edition) 8.1. Relations on Sets 8.2. Reflexivity, Symmetry, and Transitivity 8.3. Equivalence Relations 8.4. Modular Arithmetic with Applications to Cryptography 8.5. Partial Order Relations

203 flashcards · Mathematics · by lakesare

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

  1. [Relations on Sets] What is a binary relation RRR from a set AAA to a set BBB ?

    A subset of the Cartesian product A×BA \times BA×B . In this book, "relation" alone means binary relation.Example: {(1,a),(2,a)}\{(1, a), (2, a)\}{(1,a),(2,a)} is a relation from {1,2}\{1, 2\}{1,2} to {a,b}\{a, b\}{a,b} .

  2. [Relations on Sets] RRR is a relation from AAA to BBB , x∈Ax \in Ax∈A and y∈By \in By∈B . What do x R yx \, R \, yxRy and xR̸yx \mathrel{\not R} yxRy mean?

    x R yx \, R \, yxRy : xxx is related to yyy by RRR , i.e. (x,y)∈R(x, y) \in R(x,y)∈R . xR̸y\;x \mathrel{\not R} yxRy : xxx is not related to yyy by RRR . Example: for R={(1,a)}R = \{(1, a)\}R={(1,a)} : 1 R a1 \, R \, a1Ra and 2R̸a2 \mathrel{\not R} a2Ra .

  3. [Relations on Sets] LLL is the relation from R\mathbf{R}R to R\mathbf{R}R with x L y⇔x<yx \, L \, y \Leftrightarrow x < yxLy⇔x<y . Which points of the plane form the graph of LLL ?

    All points (x,y)(x, y)(x,y) above the line y=xy = xy=x . The dashed line y=xy = xy=x is not part of the graph.Example: (−35) L 1(-35) \, L \, 1(−35)L1 since −35<1-35 < 1−35<1 , but 143L̸143143 \mathrel{\not L} 143143L143 since 143=143143 = 143143=143 .

  4. [Relations on Sets] EEE is the relation from Z\mathbf{Z}Z to Z\mathbf{Z}Z with m E n⇔m−nm \, E \, n \Leftrightarrow m - nmEn⇔m−n is even. Is 3 E (−3)3 \, E \, (-3)3E(−3) ? Is 5 E 25 \, E \, 25E2 ?

    Yes and no. 3−(−3)=63 - (-3) = 63−(−3)=6 is even; 5−2=35 - 2 = 35−2=3 is not even.

  5. [Relations on Sets] EEE is the relation from Z\mathbf{Z}Z to Z\mathbf{Z}Z with m E n⇔m−nm \, E \, n \Leftrightarrow m - nmEn⇔m−n is even.How do you prove that n E 1n \, E \, 1nE1 for every odd integer nnn ?

    Write n=2k+1n = 2k + 1n=2k+1 for an integer kkk ; then n−1=2kn - 1 = 2kn−1=2k is even. So n E 1n \, E \, 1nE1 by definition of EEE .

  6. [Relations on Sets] Integers mmm and nnn with m−nm - nm−n even (equivalently, m mod 2=n mod 2m \bmod 2 = n \bmod 2mmod2=nmod2 ) are said to be congruent modulo 2.

    Example: 333 and −1-1−1 , since 3−(−1)=43 - (-1) = 43−(−1)=4 is even.

  7. [Relations on Sets] X={a,b,c}X = \{a, b, c\}X={a,b,c} , and SSS is the relation on the power set P(X)\mathcal{P}(X)P(X) with A S B⇔AA \, S \, B \Leftrightarrow AASB⇔A has at least as many elements as BBB . Is {b,c} S {a,b,c}\{b, c\} \, S \, \{a, b, c\}{b,c}S{a,b,c} ? Is {a} S ∅\{a\} \, S \, \emptyset{a}S∅ ?

    No and yes. {b,c}\{b, c\}{b,c} has 2 elements and {a,b,c}\{a, b, c\}{a,b,c} has 3, and 2<32 < 32<3 . {a}\{a\}{a} has 1 element and ∅\emptyset∅ has 0, and 1≥01 \ge 01≥0 .

  8. [Relations on Sets] RRR is a relation from AAA to BBB . What is the inverse relation R−1R^{-1}R−1 ?

    R−1={(y,x)∈B×A∣(x,y)∈R}\boldsymbol{R^{-1} = \{(y, x) \in B \times A \mid (x, y) \in R\}}R−1={(y,x)∈B×A∣(x,y)∈R} , a relation from BBB to AAA . So (y,x)∈R−1⇔(x,y)∈R(y, x) \in R^{-1} \Leftrightarrow (x, y) \in R(y,x)∈R−1⇔(x,y)∈R : the two elements of every ordered pair of RRR are interchanged.Example: R={(1,a),(2,a)}R = \{(1, a), (2, a)\}R={(1,a),(2,a)} gives R−1={(a,1),(a,2)}R^{-1} = \{(a, 1), (a, 2)\}R−1={(a,1),(a,2)} .

  9. [Relations on Sets] A={2,3,4}A = \{2, 3, 4\}A={2,3,4} , B={2,6,8}B = \{2, 6, 8\}B={2,6,8} , and RRR is the "divides" relation from AAA to BBB : x R y⇔x∣yx \, R \, y \Leftrightarrow x \mid yxRy⇔x∣y . Which ordered pairs are in RRR and in R−1R^{-1}R−1 ?

    R={(2,2),(2,6),(2,8),(3,6),(4,8)}\boldsymbol{R = \{(2, 2), (2, 6), (2, 8), (3, 6), (4, 8)\}}R={(2,2),(2,6),(2,8),(3,6),(4,8)} , R−1={(2,2),(6,2),(8,2),(6,3),(8,4)}\;\boldsymbol{R^{-1} = \{(2, 2), (6, 2), (8, 2), (6, 3), (8, 4)\}}R−1={(2,2),(6,2),(8,2),(6,3),(8,4)} Arrow diagram of RRR . Arrow diagram of R−1R^{-1}R−1 : the arrows of RRR with their directions reversed.

  10. [Relations on Sets] A={2,3,4}A = \{2, 3, 4\}A={2,3,4} , B={2,6,8}B = \{2, 6, 8\}B={2,6,8} , and RRR is the "divides" relation from AAA to BBB : x R y⇔x∣yx \, R \, y \Leftrightarrow x \mid yxRy⇔x∣y .Describe R−1R^{-1}R−1 in words.

    For all (y,x)∈B×A(y, x) \in B \times A(y,x)∈B×A : y R−1 x⇔\;y \, R^{-1} \, x \LeftrightarrowyR−1x⇔ yyy is a multiple of xxx . Example: 8 R−1 48 \, R^{-1} \, 48R−14 , since 8=2⋅48 = 2 \cdot 48=2⋅4 .

  11. [Relations on Sets] RRR is the relation from R\mathbf{R}R to R\mathbf{R}R with x R y⇔y=2∣x∣x \, R \, y \Leftrightarrow y = 2|x|xRy⇔y=2∣x∣ . Is R−1R^{-1}R−1 a function?

    No: both (2,1)(2, 1)(2,1) and (2,−1)(2, -1)(2,−1) are in R−1R^{-1}R−1 . (v,u)(v, u)(v,u) is on the graph of R−1R^{-1}R−1 exactly when (u,v)(u, v)(u,v) is on the graph of RRR .

  12. [Relations on Sets] What is a relation on a set AAA ?

    A relation from AAA to AAA . The relation and the set on which it is defined are two different things.Example: <<< is a relation on R\mathbf{R}R ; as a set, it is {(x,y)∈R×R∣x<y}\{(x, y) \in \mathbf{R} \times \mathbf{R} \mid x < y\}{(x,y)∈R×R∣x<y} .

  13. [Relations on Sets] RRR is a relation on a set AAA . What is the directed graph of RRR ?

    Each element of AAA drawn once as a point, with an arrow from xxx to yyy exactly when x R yx \, R \, yxRy . When x R xx \, R \, xxRx , the arrow is a loop from xxx back to xxx .Example: R={(1,2),(2,2)}R = \{(1, 2), (2, 2)\}R={(1,2),(2,2)} on {1,2}\{1, 2\}{1,2} : an arrow from 1 to 2 and a loop at 2.

  14. [Relations on Sets] A={3,4,5,6,7,8}A = \{3, 4, 5, 6, 7, 8\}A={3,4,5,6,7,8} and RRR is the relation on AAA with x R y⇔2∣(x−y)x \, R \, y \Leftrightarrow 2 \mid (x - y)xRy⇔2∣(x−y) . Which arrows does the directed graph of RRR have?

    A loop at every point, and arrows in both directions between any two numbers of the same parity. 3 R 33 \, R \, 33R3 since 3−3=0=2⋅03 - 3 = 0 = 2 \cdot 03−3=0=2⋅0 ; 3 R 53 \, R \, 53R5 since 3−5=2⋅(−1)3 - 5 = 2 \cdot (-1)3−5=2⋅(−1) ; 5 R 35 \, R \, 35R3 since 5−3=2⋅15 - 3 = 2 \cdot 15−3=2⋅1 .

  15. [Relations on Sets] Given sets A1,A2,…,AnA_1, A_2, \dots, A_nA1​,A2​,…,An​ , what is an nnn -ary relation on A1×A2×⋯×AnA_1 \times A_2 \times \dots \times A_nA1​×A2​×⋯×An​ ?

    A subset of A1×A2×⋯×AnA_1 \times A_2 \times \dots \times A_nA1​×A2​×⋯×An​ . Example: {(1,2,3),(2,2,2)}\{(1, 2, 3), (2, 2, 2)\}{(1,2,3),(2,2,2)} is a 3-ary relation on Z×Z×Z\mathbf{Z} \times \mathbf{Z} \times \mathbf{Z}Z×Z×Z .

  16. [Relations on Sets] 2-ary, 3-ary and 4-ary relations are called binary, ternary and quaternary relations.

  17. [Relations on Sets] How is an nnn -ary relation written as a table in a relational database?

    Each row is one nnn -tuple; the header of each column names the attribute of the elements in that column. nnn -ary relations are the mathematical foundation of relational database theory.Example: a hospital database is a 4-ary relation with columns patient ID, name, admission date, diagnosis, and rows such as (011985, John Schmidt, 020710, asthma).

  18. [Relations on Sets] A hospital database SSS is a 4-ary relation on A1×A2×A3×A4A_1 \times A_2 \times A_3 \times A_4A1​×A2​×A3​×A4​ : tuples (patient ID, name, admission date, diagnosis).In terms of sets, how is the result of the query "SELECT Patient ID, Name FROM SSS WHERE Admission Date = 010310" obtained?

    Intersect SSS with A1×A2×{010310}×A4A_1 \times A_2 \times \{010310\} \times A_4A1​×A2​×{010310}×A4​ , then project onto the first two coordinates. Example: from the tuples (466581, Mary Lazars, 010310, appendicitis) and (244388, Sarah Wu, 010310, broken leg), the result is (466581, Mary Lazars) and (244388, Sarah Wu).

  19. [Reflexivity, Symmetry, and Transitivity] A={2,3,4,6,7,9}A = \{2, 3, 4, 6, 7, 9\}A={2,3,4,6,7,9} and RRR is the relation on AAA with x R y⇔3∣(x−y)x \, R \, y \Leftrightarrow 3 \mid (x - y)xRy⇔3∣(x−y) . Its directed graph: Which three properties does this directed graph have?

    Loops Each point has an arrow from itself back to itself. Example: 2 R 22 \, R \, 22R2 , since 2−2=02 - 2 = 02−2=0 and 3∣03 \mid 03∣0 . Arrows in both directions Whenever there is an arrow from one point to a second, there is an arrow from the second point back to the first. Example: 6 R 36 \, R \, 36R3 and 3 R 63 \, R \, 63R6 , since 3∣33 \mid 33∣3 and 3∣(−3)3 \mid (-3)3∣(−3) . No incomplete directed triangles Whenever there are arrows from a first point to a second and from the second to a th…

  20. [Reflexivity, Symmetry, and Transitivity] RRR is a relation on a set AAA . When is RRR reflexive?

    For all x∈Ax \in Ax∈A , x R xx \, R \, xxRx , i.e. (x,x)∈R(x, x) \in R(x,x)∈R . Each element is related to itself; the directed graph has a loop at every point.Example: ≤\le≤ on R\mathbf{R}R is reflexive, since x≤xx \le xx≤x for every real xxx .

  21. [Reflexivity, Symmetry, and Transitivity] RRR is a relation on a set AAA . When is RRR symmetric?

    For all x,y∈Ax, y \in Ax,y∈A , if x R yx \, R \, yxRy then y R xy \, R \, xyRx . The definition does not say that x R yx \, R \, yxRy holds; only that if x R yx \, R \, yxRy holds, then y R xy \, R \, xyRx holds too.Example: {(1,2),(2,1)}\{(1, 2), (2, 1)\}{(1,2),(2,1)} on {1,2,3}\{1, 2, 3\}{1,2,3} is symmetric.

  22. [Reflexivity, Symmetry, and Transitivity] RRR is a relation on a set AAA . When is RRR transitive?

    For all x,y,z∈Ax, y, z \in Ax,y,z∈A , if x R yx \, R \, yxRy and y R zy \, R \, zyRz then x R zx \, R \, zxRz . In the directed graph: there are no incomplete directed triangles.Example: <<< on R\mathbf{R}R is transitive: x<yx < yx<y and y<zy < zy<z give x<zx < zx<z .

  23. [Reflexivity, Symmetry, and Transitivity] RRR is transitive if, for all x,y,z∈Ax, y, z \in Ax,y,z∈A , x R yx \, R \, yxRy and y R zy \, R \, zyRz imply x R zx \, R \, zxRz .Must xxx , yyy and zzz here be distinct?

    No. Example: R={(0,1),(1,0)}R = \{(0, 1), (1, 0)\}R={(0,1),(1,0)} on {0,1}\{0, 1\}{0,1} is not transitive: with x=z=0x = z = 0x=z=0 and y=1y = 1y=1 , 0 R 10 \, R \, 10R1 and 1 R 01 \, R \, 01R0 , but 0R̸00 \mathrel{\not R} 00R0 .

  24. [Reflexivity, Symmetry, and Transitivity] RRR is a relation on a set AAA . What does it mean that RRR is not reflexive, not symmetric, not transitive?

    Not reflexive There is an element x∈Ax \in Ax∈A such that xR̸xx \mathrel{\not R} xxRx . Example: <<< on R\mathbf{R}R , since 0≮00 \not< 00<0 . Not symmetric There are elements x,y∈Ax, y \in Ax,y∈A such that x R yx \, R \, yxRy but yR̸xy \mathrel{\not R} xyRx . Example: <<< on R\mathbf{R}R , since 0<10 < 10<1 but 1≮01 \not< 01<0 . Not transitive There are elements x,y,z∈Ax, y, z \in Ax,y,z∈A such that x R yx \, R \, yxRy and y R zy \, R \, zyRz but xR̸zx \mathrel{\not R} zxRz . Example: {…

  25. [Reflexivity, Symmetry, and Transitivity] The definitions of reflexive, symmetric and transitive are universal statements. Which methods prove that a relation has one of these properties?

    The method of exhaustion, or generalizing from the generic particular. Exhaustion checks every element (pair, triple) of a finite set; the generic particular argues for an arbitrarily chosen element.

  26. [Reflexivity, Symmetry, and Transitivity] A={0,1,2,3}A = \{0, 1, 2, 3\}A={0,1,2,3} and R={(0,0),(0,1),(0,3),(1,0),(1,1),(2,2),(3,0),(3,3)}R = \{(0, 0), (0, 1), (0, 3), (1, 0), (1, 1), (2, 2), (3, 0), (3, 3)\}R={(0,0),(0,1),(0,3),(1,0),(1,1),(2,2),(3,0),(3,3)} . Is RRR reflexive? symmetric? transitive?

    Reflexive and symmetric, but not transitive. 1 R 01 \, R \, 01R0 and 0 R 30 \, R \, 30R3 , but 1R̸31 \mathrel{\not R} 31R3 .

  27. [Reflexivity, Symmetry, and Transitivity] A={0,1,2,3}A = \{0, 1, 2, 3\}A={0,1,2,3} and S={(0,0),(0,2),(0,3),(2,3)}S = \{(0, 0), (0, 2), (0, 3), (2, 3)\}S={(0,0),(0,2),(0,3),(2,3)} . Is SSS reflexive? symmetric? transitive?

    Transitive, but neither reflexive nor symmetric. (1,1)∉S(1, 1) \notin S(1,1)∈/S ; (0,2)∈S(0, 2) \in S(0,2)∈S but (2,0)∉S(2, 0) \notin S(2,0)∈/S .Transitive: (0,2),(2,3)∈S(0, 2), (2, 3) \in S(0,2),(2,3)∈S and (0,3)∈S(0, 3) \in S(0,3)∈S ; every other pair (x,y),(y,z)(x, y), (y, z)(x,y),(y,z) in SSS has (x,y)=(0,0)(x, y) = (0, 0)(x,y)=(0,0) , so (x,z)=(y,z)∈S(x, z) = (y, z) \in S(x,z)=(y,z)∈S .

  28. [Reflexivity, Symmetry, and Transitivity] A={0,1,2,3}A = \{0, 1, 2, 3\}A={0,1,2,3} and T={(0,1),(2,3)}T = \{(0, 1), (2, 3)\}T={(0,1),(2,3)} . Is TTT reflexive? symmetric? transitive?

    Transitive, but neither reflexive nor symmetric. (0,0)∉T(0, 0) \notin T(0,0)∈/T ; (0,1)∈T(0, 1) \in T(0,1)∈T but (1,0)∉T(1, 0) \notin T(1,0)∈/T .

  29. [Reflexivity, Symmetry, and Transitivity] A relation RRR on AAA has no two ordered pairs (x,y)(x, y)(x,y) and (y,z)(y, z)(y,z) in which the second element of one is the first element of the other. Is RRR transitive?

    Yes, vacuously: the hypothesis " x R yx \, R \, yxRy and y R zy \, R \, zyRz " is never true. To be not transitive, RRR would need (x,y)∈R(x, y) \in R(x,y)∈R , (y,z)∈R(y, z) \in R(y,z)∈R and (x,z)∉R(x, z) \notin R(x,z)∈/R .Example: T={(0,1),(2,3)}T = \{(0, 1), (2, 3)\}T={(0,1),(2,3)} on {0,1,2,3}\{0, 1, 2, 3\}{0,1,2,3} is transitive.

  30. [Reflexivity, Symmetry, and Transitivity] RRR is a relation on a finite set AAA , stored as an array a[1],…,a[n]a[1], \dots, a[n]a[1],…,a[n] . How can an algorithm check whether RRR is reflexive, symmetric, transitive?

    Reflexive A loop over iii : if (a[i],a[i])∉R(a[i], a[i]) \notin R(a[i],a[i])∈/R for some iii , then RRR is not reflexive. Example: for n=4n = 4n=4 , 4 elements are checked. Symmetric A nested loop over all pairs (i,j)(i, j)(i,j) : if (a[i],a[j])∈R(a[i], a[j]) \in R(a[i],a[j])∈R and (a[j],a[i])∉R(a[j], a[i]) \notin R(a[j],a[i])∈/R for some i,ji, ji,j , then RRR is not symmetric. Example: for n=4n = 4n=4 , 42=164^2 = 1642=16 pairs are checked. Transitive A triply nested loop over all triples (i,j…

  31. [Reflexivity, Symmetry, and Transitivity] RRR is a relation on an infinite set AAA . To prove that RRR is reflexive, symmetric or transitive, what do you suppose and what do you show?

    Reflexive Suppose xxx is any element of AAA ; show x R xx \, R \, xxRx . Example: for === on R\mathbf{R}R : every real xxx satisfies x=xx = xx=x . Symmetric Suppose xxx and yyy are any elements of AAA with x R yx \, R \, yxRy ; show y R xy \, R \, xyRx . Example: for === on R\mathbf{R}R : if x=yx = yx=y , then y=xy = xy=x . Transitive Suppose xxx , yyy and zzz are any elements of AAA with x R yx \, R \, yxRy and y R zy \, R \, zyRz ; show x R zx \, R \, zxRz . Example: for === on R\mathbf{R}R :…

  32. [Reflexivity, Symmetry, and Transitivity] RRR is the relation on R\mathbf{R}R with x R y⇔x=yx \, R \, y \Leftrightarrow x = yxRy⇔x=y . Is RRR reflexive? symmetric? transitive?

    All three. x=xx = xx=x ; if x=yx = yx=y then y=xy = xy=x ; if x=yx = yx=y and y=zy = zy=z then x=zx = zx=z .

  33. [Reflexivity, Symmetry, and Transitivity] RRR is the relation on R\mathbf{R}R with x R y⇔x<yx \, R \, y \Leftrightarrow x < yxRy⇔x<y . Is RRR reflexive? symmetric? transitive?

    Transitive, but neither reflexive nor symmetric. 0≮00 \not< 00<0 ; 0<10 < 10<1 but 1≮01 \not< 01<0 ; x<yx < yx<y and y<zy < zy<z give x<zx < zx<z (transitive law of order).

  34. [Reflexivity, Symmetry, and Transitivity] Besides giving a counterexample, how else can you show that <<< on R\mathbf{R}R is not reflexive?

    Show that the property fails for every element: x≮xx \not< xx<x for all real xxx (by the trichotomy law). When a property is false for every element of its domain, proving this "universal falseness" can be more natural than picking one counterexample.

  35. [Reflexivity, Symmetry, and Transitivity] The relation TTT on Z\mathbf{Z}Z with m T n⇔3∣(m−n)m \, T \, n \Leftrightarrow 3 \mid (m - n)mTn⇔3∣(m−n) is called congruence modulo 3.

    Example: 7 T 17 \, T \, 17T1 , since 7−1=6=3⋅27 - 1 = 6 = 3 \cdot 27−1=6=3⋅2 .

  36. [Reflexivity, Symmetry, and Transitivity] TTT is the relation on Z\mathbf{Z}Z with m T n⇔3∣(m−n)m \, T \, n \Leftrightarrow 3 \mid (m - n)mTn⇔3∣(m−n) .Why is TTT reflexive?

    For every integer mmm : m−m=0=3⋅0m - m = 0 = 3 \cdot 0m−m=0=3⋅0 , so 3∣(m−m)3 \mid (m - m)3∣(m−m) . Example: 5 T 55 \, T \, 55T5 , since 5−5=0=3⋅05 - 5 = 0 = 3 \cdot 05−5=0=3⋅0 .

  37. [Reflexivity, Symmetry, and Transitivity] TTT is the relation on Z\mathbf{Z}Z with m T n⇔3∣(m−n)m \, T \, n \Leftrightarrow 3 \mid (m - n)mTn⇔3∣(m−n) .Why is TTT symmetric?

    If m−n=3km - n = 3km−n=3k , then n−m=−(m−n)=3(−k)n - m = -(m - n) = 3(-k)n−m=−(m−n)=3(−k) , and −k-k−k is an integer, so 3∣(n−m)3 \mid (n - m)3∣(n−m) . Example: 7−1=3⋅27 - 1 = 3 \cdot 27−1=3⋅2 , so 1−7=3⋅(−2)1 - 7 = 3 \cdot (-2)1−7=3⋅(−2) .

  38. [Reflexivity, Symmetry, and Transitivity] TTT is the relation on Z\mathbf{Z}Z with m T n⇔3∣(m−n)m \, T \, n \Leftrightarrow 3 \mid (m - n)mTn⇔3∣(m−n) .Why is TTT transitive?

    If m−n=3rm - n = 3rm−n=3r and n−p=3sn - p = 3sn−p=3s , adding gives m−p=3(r+s)m - p = 3(r + s)m−p=3(r+s) , and r+sr + sr+s is an integer, so 3∣(m−p)3 \mid (m - p)3∣(m−p) . The key observation: (m−n)+(n−p)=m−p(m - n) + (n - p) = m - p(m−n)+(n−p)=m−p .Example: 10−7=3⋅110 - 7 = 3 \cdot 110−7=3⋅1 and 7−1=3⋅27 - 1 = 3 \cdot 27−1=3⋅2 , so 10−1=3⋅310 - 1 = 3 \cdot 310−1=3⋅3 .

  39. [Reflexivity, Symmetry, and Transitivity] A relation RRR contains (1,3)(1, 3)(1,3) and (3,4)(3, 4)(3,4) but not (1,4)(1, 4)(1,4) . How can you obtain a transitive relation from RRR ?

    Add ordered pairs, here at least (1,4)(1, 4)(1,4) . Adding the fewest pairs that make the relation transitive gives the transitive closure of RRR .

  40. [Reflexivity, Symmetry, and Transitivity] RRR is a relation on a set AAA . Which three properties define the transitive closure RtR^tRt of RRR ?

    Transitive RtR^tRt is transitive. Contains RRR R⊆RtR \subseteq R^tR⊆Rt . Smallest If SSS is any other transitive relation that contains RRR , then Rt⊆SR^t \subseteq SRt⊆S . So RtR^tRt is the smallest transitive relation on AAA that contains RRR .Example: R={(0,1),(1,2)}R = \{(0, 1), (1, 2)\}R={(0,1),(1,2)} has Rt={(0,1),(1,2),(0,2)}R^t = \{(0, 1), (1, 2), (0, 2)\}Rt={(0,1),(1,2),(0,2)} .

  41. [Reflexivity, Symmetry, and Transitivity] A={0,1,2,3}A = \{0, 1, 2, 3\}A={0,1,2,3} and R={(0,1),(1,2),(2,3)}R = \{(0, 1), (1, 2), (2, 3)\}R={(0,1),(1,2),(2,3)} : What is the transitive closure RtR^tRt of RRR ?

    Rt={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}\boldsymbol{R^t = \{(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)\}}Rt={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)} (0,1),(1,2)(0, 1), (1, 2)(0,1),(1,2) give (0,2)(0, 2)(0,2) ; then (0,2),(2,3)(0, 2), (2, 3)(0,2),(2,3) give (0,3)(0, 3)(0,3) ; (1,2),(2,3)(1, 2), (2, 3)(1,2),(2,3) give (1,3)(1, 3)(1,3) . The result is transitive, so it equals RtR^tRt .

  42. [Equivalence Relations] What is a partition of a set AAA ?

    A finite or infinite collection of nonempty, mutually disjoint subsets of AAA whose union is AAA . A partition of AAA into A1,…,A6A_1, \dots, A_6A1​,…,A6​ .Example: {0,3,4},{1},{2}\{0, 3, 4\}, \{1\}, \{2\}{0,3,4},{1},{2} is a partition of {0,1,2,3,4}\{0, 1, 2, 3, 4\}{0,1,2,3,4} .

  43. [Equivalence Relations] Given a partition of a set AAA , what is the relation induced by the partition?

    The relation RRR on AAA with xRyx \mathrel{R} yxRy ⇔\Leftrightarrow⇔ some subset AiA_iAi​ of the partition contains both xxx and yyy . Example: for the partition {0,3,4},{1},{2}\{0, 3, 4\}, \{1\}, \{2\}{0,3,4},{1},{2} of {0,1,2,3,4}\{0, 1, 2, 3, 4\}{0,1,2,3,4} : 0R40 \mathrel{R} 40R4 , but not 0R10 \mathrel{R} 10R1 .

  44. [Equivalence Relations] A={0,1,2,3,4}A = \{0, 1, 2, 3, 4\}A={0,1,2,3,4} has the partition {0,3,4},{1},{2}\{0, 3, 4\}, \{1\}, \{2\}{0,3,4},{1},{2} . List the relation RRR induced by this partition.

    R={(0,0),(0,3),(0,4),(3,0),(3,3),(3,4),(4,0),(4,3),(4,4),(1,1),(2,2)}\boldsymbol{R = \{(0,0), (0,3), (0,4), (3,0), (3,3), (3,4), (4,0), (4,3), (4,4), (1,1), (2,2)\}}R={(0,0),(0,3),(0,4),(3,0),(3,3),(3,4),(4,0),(4,3),(4,4),(1,1),(2,2)} Every ordered pair of elements of {0,3,4}\{0, 3, 4\}{0,3,4} ( 3⋅3=93 \cdot 3 = 93⋅3=9 pairs), plus (1,1)(1, 1)(1,1) and (2,2)(2, 2)(2,2) : 11 pairs.Pairs like (0,0)(0, 0)(0,0) belong to RRR because "both 0 and 0 are in {0,3,4}\{0, 3, 4\}{0,3,4} " is true.

  45. [Equivalence Relations] Theorem 8.3.1 Let AAA be a set with a partition, and let RRR be the relation induced by the partition. Then … ?

    RRR is reflexive, symmetric, and transitive. So the relation induced by a partition is an equivalence relation.

  46. [Equivalence Relations] RRR is the relation induced by a partition A1,A2,…A_1, A_2, \dotsA1​,A2​,… of a set AAA : xRyx \mathrel{R} yxRy ⇔\Leftrightarrow⇔ some AiA_iAi​ contains both xxx and yyy .Why is RRR reflexive?

    The union of the AiA_iAi​ is AAA , so each x∈Ax \in Ax∈A is in some AiA_iAi​ ; then " x∈Aix \in A_ix∈Ai​ and x∈Aix \in A_ix∈Ai​ " holds, so xRxx \mathrel{R} xxRx .

  47. [Equivalence Relations] RRR is the relation induced by a partition A1,A2,…A_1, A_2, \dotsA1​,A2​,… of a set AAA : xRyx \mathrel{R} yxRy ⇔\Leftrightarrow⇔ some AiA_iAi​ contains both xxx and yyy .Why is RRR symmetric?

    If xxx and yyy are both in AiA_iAi​ , then yyy and xxx are both in AiA_iAi​ , so xRyx \mathrel{R} yxRy gives yRxy \mathrel{R} xyRx . " x∈Aix \in A_ix∈Ai​ and y∈Aiy \in A_iy∈Ai​ " is logically equivalent to " y∈Aiy \in A_iy∈Ai​ and x∈Aix \in A_ix∈Ai​ " ( p∧q≡q∧pp \wedge q \equiv q \wedge pp∧q≡q∧p ).

  48. [Equivalence Relations] RRR is the relation induced by a partition A1,A2,…A_1, A_2, \dotsA1​,A2​,… of a set AAA : xRyx \mathrel{R} yxRy ⇔\Leftrightarrow⇔ some AiA_iAi​ contains both xxx and yyy .Why is RRR transitive?

    If x,y∈Aix, y \in A_ix,y∈Ai​ and y,z∈Ajy, z \in A_jy,z∈Aj​ , then y∈Ai∩Ajy \in A_i \cap A_jy∈Ai​∩Aj​ , so Ai=AjA_i = A_jAi​=Aj​ (distinct sets of a partition are disjoint). Hence x,z∈Aix, z \in A_ix,z∈Ai​ and xRzx \mathrel{R} zxRz . The proof assumes Ai≠AjA_i \ne A_jAi​=Aj​ and derives the contradiction Ai∩Aj≠∅A_i \cap A_j \ne \emptysetAi​∩Aj​=∅ .

  49. [Equivalence Relations] When is a relation RRR on a set AAA an equivalence relation?

    Reflexive For all x∈Ax \in Ax∈A : xRxx \mathrel{R} xxRx . Example: for congruence modulo 3 on Z\mathbb{Z}Z , 5≡5(mod3)5 \equiv 5 \pmod 35≡5(mod3) . Symmetric For all x,y∈Ax, y \in Ax,y∈A : if xRyx \mathrel{R} yxRy then yRxy \mathrel{R} xyRx . Example: 5≡2(mod3)5 \equiv 2 \pmod 35≡2(mod3) , so 2≡5(mod3)2 \equiv 5 \pmod 32≡5(mod3) . Transitive For all x,y,z∈Ax, y, z \in Ax,y,z∈A : if xRyx \mathrel{R} yxRy and yRzy \mathrel{R} zyRz then xRzx \mathrel{R} zxRz . Example: 7≡47 \equiv 47≡4 and 4≡1(mod…

  50. [Equivalence Relations] Is the relation ≤\le≤ on Z\mathbb{Z}Z an equivalence relation?

    No: it is reflexive and transitive, but not symmetric. 1≤21 \le 21≤2 , but 2≰12 \not\le 12≤1 .

  51. [Equivalence Relations] XXX is the set of nonempty subsets of {1,2,3}\{1, 2, 3\}{1,2,3} , and for A,B∈XA, B \in XA,B∈X : ARBA \mathrel{R} BARB ⇔\Leftrightarrow⇔ the least element of AAA equals the least element of BBB . Is RRR an equivalence relation, and why?

    Yes: "the least element of AAA equals the least element of BBB " is an equality of numbers, and equality is reflexive, symmetric and transitive. Transitivity: min⁡A=min⁡B\min A = \min BminA=minB and min⁡B=min⁡C\min B = \min CminB=minC give min⁡A=min⁡C\min A = \min CminA=minC .Example: {1,3}R{1,2}\{1, 3\} \mathrel{R} \{1, 2\}{1,3}R{1,2} , since both have least element 1.

  52. [Equivalence Relations] SSS is the set of digital logic circuits with nnn inputs, and C1EC2C_1 \mathrel{E} C_2C1​EC2​ ⇔\Leftrightarrow⇔ C1C_1C1​ has the same input/output table as C2C_2C2​ . Is EEE an equivalence relation?

    Yes. Each circuit has the same table as itself; "same table" is symmetric; and if C1,C2C_1, C_2C1​,C2​ have the same table and C2,C3C_2, C_3C2​,C3​ do, then C1,C3C_1, C_3C1​,C3​ do. If C1EC2C_1 \mathrel{E} C_2C1​EC2​ , the circuits C1C_1C1​ and C2C_2C2​ are called equivalent.

  53. [Equivalence Relations] A compiler ignores all but the first eight characters of an identifier. Why does it treat NumberOfScrews\texttt{NumberOfScrews}NumberOfScrews and NumberOfBolts\texttt{NumberOfBolts}NumberOfBolts as the same identifier?

    Both start with the same eight characters, NumberOf\texttt{NumberOf}NumberOf . The relation " sss and ttt have the same first eight characters" is an equivalence relation on the set of identifiers, and the compiler regards related identifiers as one.

  54. [Equivalence Relations] RRR is an equivalence relation on a set AAA , and a∈Aa \in Aa∈A . What is the equivalence class [a][a][a] of aaa ?

    [a]={x∈A∣xRa}\boldsymbol{[a] = \{x \in A \mid x \mathrel{R} a\}}[a]={x∈A∣xRa} : the set of all elements of AAA related to aaa . Also called the class of aaa . Written [a]R[a]_R[a]R​ when several equivalence relations are under discussion.Example: for congruence modulo 3 on Z\mathbb{Z}Z , [1]={…,−5,−2,1,4,7,… }[1] = \{\dots, -5, -2, 1, 4, 7, \dots\}[1]={…,−5,−2,1,4,7,…} .

  55. [Equivalence Relations] RRR is an equivalence relation on a set AAA , and a,x∈Aa, x \in Aa,x∈A . How do you show that x∈[a]x \in [a]x∈[a] ?

    Show that xRax \mathrel{R} axRa . Procedural version of the definition: for all x∈Ax \in Ax∈A , x∈[a]⇔xRax \in [a] \Leftrightarrow x \mathrel{R} ax∈[a]⇔xRa .

  56. [Equivalence Relations] RRR is an equivalence relation on a set AAA , and a∈Aa \in Aa∈A . What kind of object is each of AAA , RRR and [a][a][a] ?

    AAA : the underlying set; RRR : a set of ordered pairs, a subset of A×AA \times AA×A ; [a][a][a] : a subset of AAA . Example: A={0,1,2}A = \{0, 1, 2\}A={0,1,2} , R={(0,0),(1,1),(2,2),(0,2),(2,0)}R = \{(0,0), (1,1), (2,2), (0,2), (2,0)\}R={(0,0),(1,1),(2,2),(0,2),(2,0)} , [0]={0,2}[0] = \{0, 2\}[0]={0,2} .

  57. [Equivalence Relations] A={0,1,2,3,4}A = \{0, 1, 2, 3, 4\}A={0,1,2,3,4} and R={(0,0),(0,4),(1,1),(1,3),(2,2),(3,1),(3,3),(4,0),(4,4)}R = \{(0,0), (0,4), (1,1), (1,3), (2,2), (3,1), (3,3), (4,0), (4,4)\}R={(0,0),(0,4),(1,1),(1,3),(2,2),(3,1),(3,3),(4,0),(4,4)} is an equivalence relation on AAA . Find the distinct equivalence classes of RRR .

    {0,4}, {1,3}, {2}\boldsymbol{\{0, 4\}, \ \{1, 3\}, \ \{2\}}{0,4}, {1,3}, {2} [0]=[4]={0,4}[0] = [4] = \{0, 4\}[0]=[4]={0,4} , [1]=[3]={1,3}[1] = [3] = \{1, 3\}[1]=[3]={1,3} , [2]={2}[2] = \{2\}[2]={2} . The directed graph of RRR .

  58. [Equivalence Relations] What are the two steps for finding the distinct equivalence classes of an equivalence relation on a set AAA ?

    Find every class Construct (or, for infinite AAA , imagine constructing) the class [a][a][a] of every element a∈Aa \in Aa∈A . Example: for R={(0,0),(0,4),(4,0),(4,4),(1,1),(1,3),(3,1),(3,3),(2,2)}R = \{(0,0), (0,4), (4,0), (4,4), (1,1), (1,3), (3,1), (3,3), (2,2)\}R={(0,0),(0,4),(4,0),(4,4),(1,1),(1,3),(3,1),(3,3),(2,2)} on {0,1,2,3,4}\{0, 1, 2, 3, 4\}{0,1,2,3,4} : [0]={0,4}[0] = \{0, 4\}[0]={0,4} , [1]={1,3}[1] = \{1, 3\}[1]={1,3} , [2]={2}[2] = \{2\}[2]={2} , [3]={1,3}[3] = \{1, 3\}[3]={1,3}…

  59. [Equivalence Relations] On the nonempty subsets of {1,2,3}\{1, 2, 3\}{1,2,3} , ARBA \mathrel{R} BARB ⇔\Leftrightarrow⇔ AAA and BBB have the same least element. What are the distinct equivalence classes of RRR ?

    [{1}]={{1},{1,2},{1,3},{1,2,3}}, [{2}]={{2},{2,3}}, [{3}]={{3}}\boldsymbol{[\{1\}] = \{\{1\}, \{1,2\}, \{1,3\}, \{1,2,3\}\}, \ [\{2\}] = \{\{2\}, \{2,3\}\}, \ [\{3\}] = \{\{3\}\}}[{1}]={{1},{1,2},{1,3},{1,2,3}}, [{2}]={{2},{2,3}}, [{3}]={{3}} One class per possible least element 1, 2, 3. Together they contain all 7 nonempty subsets.

  60. [Equivalence Relations] On the set LLL of identifiers of a programming language, sRts \mathrel{R} tsRt ⇔\Leftrightarrow⇔ sss and ttt have the same first eight characters. Describe the distinct equivalence classes of RRR .

    One class for each string of first eight characters: all identifiers that start with that string. Identifiers in two distinct classes differ somewhere in their first eight characters. [s]={t∈L∣[s] = \{t \in L \mid[s]={t∈L∣ the first eight characters of ttt equal those of s}s\}s} .Example: NumberOfScrews\texttt{NumberOfScrews}NumberOfScrews and NumberOfBolts\texttt{NumberOfBolts}NumberOfBolts are in the same class.

  61. [Equivalence Relations] On a set AAA , xRyx \mathrel{R} yxRy ⇔\Leftrightarrow⇔ x=yx = yx=y (the identity relation). What are the distinct equivalence classes of RRR ?

    All the one-element subsets {a}\{a\}{a} of AAA . [a]={x∈A∣x=a}={a}[a] = \{x \in A \mid x = a\} = \{a\}[a]={x∈A∣x=a}={a} , and {x}≠{a}\{x\} \ne \{a\}{x}={a} when x≠ax \ne ax=a .Example: for A={1,2,3}A = \{1, 2, 3\}A={1,2,3} the classes are {1},{2},{3}\{1\}, \{2\}, \{3\}{1},{2},{3} .

  62. [Equivalence Relations] Lemma 8.3.2 RRR is an equivalence relation on a set AAA , and a,b∈Aa, b \in Aa,b∈A . If aRba \mathrel{R} baRb , then … ?

    [a]=[b]\boldsymbol{[a] = [b]}[a]=[b] Example: for congruence modulo 3, 3≡0(mod3)3 \equiv 0 \pmod 33≡0(mod3) , so [3]=[0][3] = [0][3]=[0] .

  63. [Equivalence Relations] RRR is an equivalence relation on AAA , and aRba \mathrel{R} baRb . To show [a]=[b][a] = [b][a]=[b] , show [a]⊆[b][a] \subseteq [b][a]⊆[b] and [b]⊆[a][b] \subseteq [a][b]⊆[a] .Why is [a]⊆[b][a] \subseteq [b][a]⊆[b] ?

    For x∈[a]x \in [a]x∈[a] : xRax \mathrel{R} axRa and aRba \mathrel{R} baRb , so xRbx \mathrel{R} bxRb by transitivity, i.e. x∈[b]x \in [b]x∈[b] .

  64. [Equivalence Relations] RRR is an equivalence relation on AAA , and aRba \mathrel{R} baRb . To show [a]=[b][a] = [b][a]=[b] , show [a]⊆[b][a] \subseteq [b][a]⊆[b] and [b]⊆[a][b] \subseteq [a][b]⊆[a] .Why is [b]⊆[a][b] \subseteq [a][b]⊆[a] ?

    For x∈[b]x \in [b]x∈[b] : xRbx \mathrel{R} bxRb , and bRab \mathrel{R} abRa by symmetry, so xRax \mathrel{R} axRa by transitivity, i.e. x∈[a]x \in [a]x∈[a] .

  65. [Equivalence Relations] Lemma 8.3.3 RRR is an equivalence relation on a set AAA , and a,b∈Aa, b \in Aa,b∈A . Then either [a]=[b][a] = [b][a]=[b] or … ?

    [a]∩[b]=∅\boldsymbol{[a] \cap [b] = \emptyset}[a]∩[b]=∅ Two equivalence classes are either identical or disjoint.Example: for congruence modulo 3, [1]=[4][1] = [4][1]=[4] , while [1]∩[2]=∅[1] \cap [2] = \emptyset[1]∩[2]=∅ .

  66. [Equivalence Relations] How can you prove a statement of the form "if ppp then ( qqq or rrr )"?

    Prove "if ( ppp and not qqq ) then rrr " (or, equally, "if ( ppp and not rrr ) then qqq "). p→(q∨r)≡(p∧∼q)→rp \to (q \vee r) \equiv (p \wedge \sim q) \to rp→(q∨r)≡(p∧∼q)→r .Example: to show " [a]∩[b]=∅[a] \cap [b] = \emptyset[a]∩[b]=∅ or [a]=[b][a] = [b][a]=[b] ", assume [a]∩[b]≠∅[a] \cap [b] \ne \emptyset[a]∩[b]=∅ and show [a]=[b][a] = [b][a]=[b] .

  67. [Equivalence Relations] RRR is an equivalence relation on AAA , and aRba \mathrel{R} baRb implies [a]=[b][a] = [b][a]=[b] .Why do two equivalence classes [a][a][a] and [b][b][b] with [a]∩[b]≠∅[a] \cap [b] \ne \emptyset[a]∩[b]=∅ have to be equal?

    Take x∈[a]∩[b]x \in [a] \cap [b]x∈[a]∩[b] : xRax \mathrel{R} axRa and xRbx \mathrel{R} bxRb , so aRxa \mathrel{R} xaRx (symmetry) and aRba \mathrel{R} baRb (transitivity); hence [a]=[b][a] = [b][a]=[b] .

  68. [Equivalence Relations] Theorem 8.3.4 (The Partition Induced by an Equivalence Relation) If AAA is a set and RRR is an equivalence relation on AAA , then the distinct equivalence classes of RRR … ?

    form a partition of AAA : their union is AAA , and any two distinct classes are disjoint. Example: congruence modulo 3 partitions Z\mathbb{Z}Z into [0],[1],[2][0], [1], [2][0],[1],[2] .

  69. [Equivalence Relations] RRR is an equivalence relation on AAA with distinct equivalence classes A1,…,AnA_1, \dots, A_nA1​,…,An​ .Why is A=A1∪⋯∪AnA = A_1 \cup \dots \cup A_nA=A1​∪⋯∪An​ ?

    ⊆\subseteq⊆ : by reflexivity xRxx \mathrel{R} xxRx , so x∈[x]x \in [x]x∈[x] , which is one of the AiA_iAi​ . ⊇\ \supseteq ⊇ : each class is a subset of AAA .

  70. [Equivalence Relations] RRR is an equivalence relation on AAA . For all a,b∈Aa, b \in Aa,b∈A : [a]∩[b]=∅[a] \cap [b] = \emptyset[a]∩[b]=∅ or [a]=[b][a] = [b][a]=[b] .Why are two distinct equivalence classes Ai≠AjA_i \ne A_jAi​=Aj​ of RRR disjoint?

    Write Ai=[a]A_i = [a]Ai​=[a] , Aj=[b]A_j = [b]Aj​=[b] ; since [a]≠[b][a] \ne [b][a]=[b] , the alternative [a]∩[b]=∅[a] \cap [b] = \emptyset[a]∩[b]=∅ must hold.

  71. [Equivalence Relations] How are partitions of a set AAA and equivalence relations on AAA connected?

    The relation induced by a partition is an equivalence relation, and the distinct equivalence classes of an equivalence relation form a partition. Example: the partition {0,4},{1,3},{2}\{0, 4\}, \{1, 3\}, \{2\}{0,4},{1,3},{2} of {0,1,2,3,4}\{0, 1, 2, 3, 4\}{0,1,2,3,4} induces R={(0,0),(0,4),(4,0),(4,4),(1,1),(1,3),(3,1),(3,3),(2,2)}R = \{(0,0), (0,4), (4,0), (4,4), (1,1), (1,3), (3,1), (3,3), (2,2)\}R={(0,0),(0,4),(4,0),(4,4),(1,1),(1,3),(3,1),(3,3),(2,2)} , whose classes are {0,4},{1,3},{2}\{0,…

  72. [Equivalence Relations] SSS is the set of digital logic circuits with two inputs and one output, and C1EC2C_1 \mathrel{E} C_2C1​EC2​ ⇔\Leftrightarrow⇔ C1C_1C1​ and C2C_2C2​ have the same input/output table. How many distinct equivalence classes does EEE have?

    16\boldsymbol{16}16 , one for each input/output table. A table has 4 rows (inputs 11, 10, 01, 00), so a table is determined by its output column, a binary string of length 4: 24=162^4 = 1624=16 choices.Each class contains infinitely many circuits.

  73. [Equivalence Relations] Why are these two circuits in the same class of the relation "has the same input/output table"?

    Both output R=1R = 1R=1 exactly when P=Q=0P = Q = 0P=Q=0 , so both have the same input/output table. PQR110100010001\begin{array}{cc|c} P & Q & R \\ \hline 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}P1100​Q1010​R0001​​ (∼P)∧(∼Q)≡ ∼(P∨Q)(\sim P) \wedge (\sim Q) \equiv \ \sim(P \vee Q)(∼P)∧(∼Q)≡ ∼(P∨Q) by De Morgan's law.

  74. [Equivalence Relations] RRR is congruence modulo 3 on Z\mathbb{Z}Z : mRnm \mathrel{R} nmRn ⇔\Leftrightarrow⇔ 3∣(m−n)3 \mid (m - n)3∣(m−n) . What are the distinct equivalence classes of RRR ?

    [0][0][0] {x∈Z∣x=3k\{x \in \mathbb{Z} \mid x = 3k{x∈Z∣x=3k for some integer k}k\}k} : the integers divisible by 3. Example: {…,−6,−3,0,3,6,… }\{\dots, -6, -3, 0, 3, 6, \dots\}{…,−6,−3,0,3,6,…} [1][1][1] {x∈Z∣x=3k+1\{x \in \mathbb{Z} \mid x = 3k + 1{x∈Z∣x=3k+1 for some integer k}k\}k} : the integers with remainder 1 when divided by 3. Example: {…,−5,−2,1,4,7,… }\{\dots, -5, -2, 1, 4, 7, \dots\}{…,−5,−2,1,4,7,…} [2][2][2] {x∈Z∣x=3k+2\{x \in \mathbb{Z} \mid x = 3k + 2{x∈Z∣x=3k+2 for some integer k…

  75. [Equivalence Relations] For congruence modulo 3 on Z\mathbb{Z}Z , which of [0],[1],[2][0], [1], [2][0],[1],[2] is the class [−1][-1][−1] , and why?

    [−1]=[2]\boldsymbol{[-1] = [2]}[−1]=[2] , because −1≡2(mod3)-1 \equiv 2 \pmod 3−1≡2(mod3) , and related elements have equal classes. −1−2=−3=3⋅(−1)-1 - 2 = -3 = 3 \cdot (-1)−1−2=−3=3⋅(−1) . Likewise [2]=[5]=[8]=[−4][2] = [5] = [8] = [-4][2]=[5]=[8]=[−4] .

  76. [Equivalence Relations] For congruence modulo 3, [0]=[3]=[−6][0] = [3] = [-6][0]=[3]=[−6] . Is this one equivalence class or three?

    One class with several names: the set {x∈Z∣x=3k\{x \in \mathbb{Z} \mid x = 3k{x∈Z∣x=3k for some integer k}k\}k} . What a class is called differs from what it is. The section's opening quote (the Knight's song in Lewis Carroll's Through the Looking Glass) jokes about this distinction.

  77. [Equivalence Relations] If RRR is an equivalence relation and SSS is an equivalence class of RRR , any element aaa with [a]=S[a] = S[a]=S is called a representative of SSS .

    Every element of SSS is a representative of SSS : if a∈Sa \in Sa∈S then S=[a]S = [a]S=[a] . Example: for congruence modulo 3, 0, 3 and −6-6−6 are representatives of {…,−3,0,3,6,… }\{\dots, -3, 0, 3, 6, \dots\}{…,−3,0,3,6,…} .

  78. [Equivalence Relations] Let m,nm, nm,n be integers and ddd a positive integer. What does m≡n(modd)m \equiv n \pmod dm≡n(modd) mean, and how is it read?

    d∣(m−n)\boldsymbol{d \mid (m - n)}d∣(m−n) ; read " mmm is congruent to nnn modulo ddd ". Example: 17≡2(mod5)17 \equiv 2 \pmod 517≡2(mod5) , since 17−2=15=5⋅317 - 2 = 15 = 5 \cdot 317−2=15=5⋅3 .

  79. [Equivalence Relations] m≡n(modd)m \equiv n \pmod dm≡n(modd) ( d>0d > 0d>0 ) holds if and only if which equation of remainders holds?

    m mod d=n mod d\boldsymbol{m \bmod d = n \bmod d}mmodd=nmodd Example: 17 mod 5=2=2 mod 517 \bmod 5 = 2 = 2 \bmod 517mod5=2=2mod5 , and 17≡2(mod5)17 \equiv 2 \pmod 517≡2(mod5) .

  80. [Equivalence Relations] Which of these congruences are true? 12≡7(mod5)12 \equiv 7 \pmod 512≡7(mod5) , 6≡−8(mod4)\quad 6 \equiv -8 \pmod 46≡−8(mod4) , 3≡3(mod7)\quad 3 \equiv 3 \pmod 73≡3(mod7)

    True, false, true. 12−7=5=5⋅112 - 7 = 5 = 5 \cdot 112−7=5=5⋅1 , so 5∣(12−7)5 \mid (12 - 7)5∣(12−7) . 6−(−8)=146 - (-8) = 146−(−8)=14 and 4∤144 \nmid 144∤14 , so 6≢−8(mod4)6 \not\equiv -8 \pmod 46≡−8(mod4) . 3−3=0=7⋅03 - 3 = 0 = 7 \cdot 03−3=0=7⋅0 , so 7∣(3−3)7 \mid (3 - 3)7∣(3−3) .

  81. [Equivalence Relations] Who introduced the notation m≡n(modd)m \equiv n \pmod dm≡n(modd) , and where?

    Carl Friedrich Gauss, in the first chapter of Disquisitiones Arithmeticae. Gauss (1777 to 1855) published the book at age 24. It laid the foundation for modern number theory.

  82. [Equivalence Relations] A=Z×(Z−{0})A = \mathbb{Z} \times (\mathbb{Z} - \{0\})A=Z×(Z−{0}) and (a,b)R(c,d)(a, b) \mathrel{R} (c, d)(a,b)R(c,d) ⇔\Leftrightarrow⇔ ad=bcad = bcad=bc . What are the equivalence classes of RRR ?

    One class for each rational number: [(a,b)][(a, b)][(a,b)] is the set of pairs (c,d)(c, d)(c,d) with cd=ab\frac{c}{d} = \frac{a}{b}dc​=ba​ . ab=cd\frac{a}{b} = \frac{c}{d}ba​=dc​ exactly when the cross products are equal: ad=bcad = bcad=bc .Example: [(1,2)]={(1,2),(−1,−2),(2,4),(−2,−4),(3,6),(−3,−6),… }[(1, 2)] = \{(1, 2), (-1, -2), (2, 4), (-2, -4), (3, 6), (-3, -6), \dots\}[(1,2)]={(1,2),(−1,−2),(2,4),(−2,−4),(3,6),(−3,−6),…} .

  83. [Equivalence Relations] A=Z×(Z−{0})A = \mathbb{Z} \times (\mathbb{Z} - \{0\})A=Z×(Z−{0}) and (a,b)R(c,d)(a, b) \mathrel{R} (c, d)(a,b)R(c,d) ⇔\Leftrightarrow⇔ ad=bcad = bcad=bc .How does the proof that RRR is transitive go?

    From ad=bcad = bcad=bc and cf=decf = decf=de : multiply by fff and by bbb to get adf=bcf=bdeadf = bcf = bdeadf=bcf=bde , then cancel d≠0d \ne 0d=0 to get af=beaf = beaf=be . So (a,b)R(c,d)(a, b) \mathrel{R} (c, d)(a,b)R(c,d) and (c,d)R(e,f)(c, d) \mathrel{R} (e, f)(c,d)R(e,f) give (a,b)R(e,f)(a, b) \mathrel{R} (e, f)(a,b)R(e,f) . The cancellation needs d≠0d \ne 0d=0 , which holds because second coordinates are nonzero.Example: (1,2)R(2,4)(1, 2) \mathrel{R} (2, 4)(1,2)R(2,4) and (2,4)R(3,6)(2,…

  84. [Equivalence Relations] How can the real numbers be defined using only logic and set theory?

    Positive integers Defined in terms of sets (Frege and Peano, late nineteenth century). Integers Equivalence classes of ordered pairs of positive integers. Example: (a,b)R(c,d)⇔a+d=c+b(a, b) \mathrel{R} (c, d) \Leftrightarrow a + d = c + b(a,b)R(c,d)⇔a+d=c+b ; the class of (1,3)(1, 3)(1,3) stands for 1−3=−21 - 3 = -21−3=−2 . Rational numbers Equivalence classes of pairs (a,b)∈Z×(Z−{0})(a, b) \in \mathbb{Z} \times (\mathbb{Z} - \{0\})(a,b)∈Z×(Z−{0}) under ad=bcad = bcad=bc , with suitably defined…

  85. [Modular Arithmetic, Cryptography] In cryptography, what are plaintext and ciphertext?

    Plaintext: the original message. Ciphertext: the converted form of the message that is sent. Ciphertext may be sent over channels that outside parties can see.Example: plaintext HI, ciphertext KL (Caesar cipher).

  86. [Modular Arithmetic, Cryptography] Converting plaintext into ciphertext is called encryption; converting ciphertext back into plaintext is called decryption.

    Example: encrypting HI with the Caesar cipher gives KL; decrypting KL gives HI.

  87. [Modular Arithmetic, Cryptography] How does the Caesar cipher encrypt a letter, with the letters numbered A = 01, B = 02, …, Z = 26?

    C=(M+3) mod 26C = (M + 3) \bmod 26C=(M+3)mod26 : each letter is replaced by the letter three places farther along, with X, Y, Z wrapping around to A, B, C. MMM is the number of the plaintext letter and CCC the number of the ciphertext letter; a result of 0 stands for Z (26). ABCDEFGHIJKLM01020304050607080910111213NOPQRSTUVWXYZ14151617181920212223242526\begin{array}{ccccccccccccc}\text{A} & \text{B} & \text{C} & \text{D} & \text{E} & \text{F} & \text{G} & \text{H} & \text{I} & \text{J} & \text{K…

  88. [Modular Arithmetic, Cryptography] How does the receiver decrypt a Caesar cipher message, with A = 01, …, Z = 26?

    M=(C−3) mod 26M = (C - 3) \bmod 26M=(C−3)mod26 : each letter is replaced by the letter three places earlier. Example: A = 01 gives (1−3) mod 26=24(1 - 3) \bmod 26 = 24(1−3)mod26=24 = X.

  89. [Modular Arithmetic, Cryptography] Encrypt HOW ARE YOU with the Caesar cipher (A = 01, …, Z = 26, C=(M+3) mod 26C = (M + 3) \bmod 26C=(M+3)mod26 ).

    KRZ DUH BRX Numbers: 08 15 23, 01 18 05, 25 15 21.Add 3: 11 18 26, 04 21 08, 02 18 24 (Y = 25 gives 28 mod 26=228 \bmod 26 = 228mod26=2 = B).

  90. [Modular Arithmetic, Cryptography] Decrypt L DP ILQH, which was encrypted with the Caesar cipher (A = 01, …, Z = 26, C=(M+3) mod 26C = (M + 3) \bmod 26C=(M+3)mod26 ).

    I AM FINE Numbers: 12, 04 16, 09 12 17 08.Subtract 3: 09, 01 13, 06 09 14 05.

  91. [Modular Arithmetic, Cryptography] What are the two weaknesses of the Caesar cipher?

    Letter frequencies Given enough ciphertext, someone who knows how often each letter occurs in the language can work out the cipher. Example: E is the most frequent letter in English, so the most frequent ciphertext letter (H) probably stands for E. Encryption reveals decryption Whoever knows how to encrypt also knows how to decrypt, so the encryption method cannot be passed over an insecure channel. Example: knowing C=(M+3) mod 26C = (M + 3) \bmod 26C=(M+3)mod26 gives M=(C−3) mod 26M = (C - 3)…

  92. [Modular Arithmetic, Cryptography] What is public-key cryptography?

    The receiver publishes the encryption information (the public key), but only the receiver knows how to decrypt. The public key gives practically no information about decryption, so it does not matter how many people learn it.Example: in RSA the public key is pqpqpq and eee ; decrypting needs ppp and qqq themselves.

  93. [Modular Arithmetic, Cryptography] Who developed the first public-key cryptosystem, and when?

    Ronald Rivest, Adi Shamir and Leonard Adleman, at M.I.T. in 1976–1977. It is called the RSA cipher after their initials. From left: Rivest (born 1948), Shamir (born 1952), Adleman (born 1945).

  94. [Modular Arithmetic, Cryptography] Let aaa , bbb , nnn be integers with n>1n > 1n>1 . Besides n∣(a−b)n \mid (a - b)n∣(a−b) , what are four equivalent ways to state this fact?

    a≡b(modn)a \equiv b \pmod{n}a≡b(modn) Example: 25≡19(mod3)25 \equiv 19 \pmod{3}25≡19(mod3) , since 3∣63 \mid 63∣6 . a=b+kna = b + kna=b+kn for some integer kkk Example: 25=19+2⋅325 = 19 + 2 \cdot 325=19+2⋅3 . aaa and bbb have the same nonnegative remainder when divided by nnn Example: 25=8⋅3+125 = 8 \cdot 3 + 125=8⋅3+1 and 19=6⋅3+119 = 6 \cdot 3 + 119=6⋅3+1 . a mod n=b mod na \bmod n = b \bmod namodn=bmodn Example: 25 mod 3=19 mod 3=125 \bmod 3 = 19 \bmod 3 = 125mod3=19mod3=1 .

  95. [Modular Arithmetic, Cryptography] To prove that five statements (1), …, (5) are all equivalent, which implications does it suffice to prove?

    A cycle: (1) ⇒\Rightarrow⇒ (2) ⇒\Rightarrow⇒ (3) ⇒\Rightarrow⇒ (4) ⇒\Rightarrow⇒ (5) ⇒\Rightarrow⇒ (1). By transitivity of if-then, each statement then implies every other.Example: (3) ⇒\Rightarrow⇒ (1) follows from (3) ⇒\Rightarrow⇒ (4) ⇒\Rightarrow⇒ (5) ⇒\Rightarrow⇒ (1).

  96. [Modular Arithmetic, Cryptography] Let n>1n > 1n>1 . Why does a=b+kna = b + kna=b+kn (for an integer kkk ) imply that aaa and bbb have the same remainder when divided by nnn ?

    If a=qn+ra = qn + ra=qn+r with 0≤r<n0 \le r < n0≤r<n , then b=(q−k)n+rb = (q - k)n + rb=(q−k)n+r , so by uniqueness in the quotient-remainder theorem, rrr is also the remainder of bbb . Example: 25=19+2⋅325 = 19 + 2 \cdot 325=19+2⋅3 and 25=8⋅3+125 = 8 \cdot 3 + 125=8⋅3+1 , so 19=(8−2)⋅3+119 = (8 - 2) \cdot 3 + 119=(8−2)⋅3+1 .

  97. [Modular Arithmetic, Cryptography] Let n>1n > 1n>1 . Why does a mod n=b mod na \bmod n = b \bmod namodn=bmodn imply n∣(a−b)n \mid (a - b)n∣(a−b) ?

    a=q1n+ra = q_1 n + ra=q1​n+r and b=q2n+rb = q_2 n + rb=q2​n+r , so a−b=(q1−q2)na - b = (q_1 - q_2)na−b=(q1​−q2​)n . Example: 25=8⋅3+125 = 8 \cdot 3 + 125=8⋅3+1 and 19=6⋅3+119 = 6 \cdot 3 + 119=6⋅3+1 , so 25−19=(8−6)⋅325 - 19 = (8 - 6) \cdot 325−19=(8−6)⋅3 .

  98. [Modular Arithmetic, Cryptography] Given integers aaa and nnn with n>1n > 1n>1 , what is the residue of aaa modulo nnn ?

    a mod na \bmod namodn , the nonnegative remainder obtained when aaa is divided by nnn . Also called the least nonnegative residue. There are exactly nnn residues modulo nnn : 0,1,…,n−10, 1, \dots, n - 10,1,…,n−1 .Example: the residue of −7-7−7 modulo 3 is 2, since −7=(−3)⋅3+2-7 = (-3) \cdot 3 + 2−7=(−3)⋅3+2 .

  99. [Modular Arithmetic, Cryptography] For n>1n > 1n>1 , the numbers 0,1,2,…,n−10, 1, 2, \dots, n - 10,1,2,…,n−1 are called a complete set of residues modulo nnn .

    To reduce a number modulo nnn means to replace it by its residue modulo nnn . Example: reducing 17 modulo 5 gives 2.

  100. [Modular Arithmetic, Cryptography] For n>1n > 1n>1 , what kind of relation is congruence modulo nnn on Z\mathbb{Z}Z , and what are its distinct equivalence classes?

    An equivalence relation, with distinct classes [0],[1],…,[n−1][0], [1], \dots, [n - 1][0],[1],…,[n−1] [a]={m∈Z∣m=a+kn for some integer k}[a] = \{m \in \mathbb{Z} \mid m = a + kn \text{ for some integer } k\}[a]={m∈Z∣m=a+kn for some integer k} . The classes correspond one-to-one to the residues 0,1,…,n−10, 1, \dots, n - 10,1,…,n−1 .Example: modulo 3, [0]={…,−3,0,3,6,… }[0] = \{\dots, -3, 0, 3, 6, \dots\}[0]={…,−3,0,3,6,…} , [1]={…,−2,1,4,7,… }[1] = \{\dots, -2, 1, 4, 7, \dots\}[1]={…,−2,1,4,7,…}…