Exercises 15.3 Exercises
1.
Let \(X=\{a,b,c,d,e,f\}\) and \(R\) be the relation on \(X\) defined by
Is \(R\) an equivalence relation? If so, draw a digraph and give the equivalence classes. If not, give an example showing why.
2.
Let \(X=\{1,2,3,4,5,6\}\) and let \(R\) be the relation on \(X\) defined by
Is \(R\) an equivalence relation? If so, draw a digraph and give the equivalence classes. If not, give an example showing why.
3.
Let \(X=\{a,b,c,d,e,f\}\) and \(S\) be the relation on \(X\) defined by
Is \(S\) an equivalence relation? If so, draw a digraph and give the equivalence classes. If not, give an example showing why.
4.
Let \(X=\{a,b,c,d,e,f\}\) and \(T\) be the relation on \(X\) defined by
Is \(T\) an equivalence relation? If so, draw a digraph and give the equivalence classes. If not, give an example showing why.
5.
Let \(X\) be any finite set and define the relation \(R\) on \(\mathscr{P}(X)\) by
If \(X = \{a,b,c\}\text{,}\) give the equivalence classes of the relation. Name each equivalence class with the correct notation, and list the elements of each.
6.
Define the floor \(\lfloor x \rfloor\) of a real number \(x\) to be “\(x\) rounded down”, in other words, the greatest integer less than or equal to \(x\text{:}\)
For instance, \(\lfloor -2 \rfloor = -2\text{,}\) \(\lfloor 1.74 \rfloor= 1 \text{,}\) and \(\lfloor \pi \rfloor = 3\text{.}\)
Define the relation \(S\) on the set \(\mathbb{R}\) of all real numbers:
For instance, \((\pi, 3.7) \in S\text{,}\) because the floor of both is \(3\text{.}\)
Describe the equivalence classes of \(\mathbb{R}\) under \(S\text{.}\) You will not be able to list them out, but you should be able to name a few and tell that there is one equivalence class for each...
7.
The notation \([n]\) is used as shorthand for the set \(\{1, 2, \ldots, n\}\text{.}\) Now we are using \([x]\) to refer to the set of all elements equivalent to \(x\) in a given equivalence relation. Briefly discuss the relationship between the two notations.
Consider the equivalence relation on a family of sets described by \(|X|=|Y|\text{.}\) Given a set \(A\text{,}\) what is \([A]\text{?}\) Is there a relationship between \([A]\) and \([n]\text{?}\)
8.
Let \(\mathscr{S}^2\) be the space of all well-formed formulas consisting of at most two different letters. In other words, \(\mathscr{S}^2\) is the set consisting of all statements correctly formed from \(p\text{,}\) \(q\text{,}\) and some logical connectives. Examples include \(p\text{,}\) \(p \wedge \neg q\text{,}\) and \((\neg p \vee \neg q) \to (p \wedge q)\text{.}\) Define the relation \(\equiv\) on \(\mathscr{S}^2\) by saying \(\varphi \equiv \psi\) whenever \(\varphi \leftrightarrow \psi\) is a tautology. (In other words, \(\equiv\) on \(\mathscr{S}^2\) is the familiar logical equivalence.)
Prove there are \(16\) equivalence classes. (This requires a little bit of combinatorics.)
List the \(16\) equivalence classes. In other words, choose a representative for each of the classes of equivalent statement. For example, you'd choose between \(p \to q\) and \(\neg p \vee q\) as a representative for their equivalence class. If you chose \(p \to q\text{,}\) then \([p \to q]\) would be the set of all statements equivalent to \(p \to q\text{.}\)
For the following problems, simplify the expression (which means, write the smallest non-negative member of the appropriate equivalence class).
9.
Simplify \((-50) \; (\text{mod } 23)\text{.}\)
10.
Simplify \((-17) \; (\text{mod } 3)\text{.}\)
11.
Simplify \(-21\;(\text{mod }4)\text{.}\)
12.
Simplify \((302^5-97\times 108) \; (\text{mod } 5)\text{.}\)
13.
Simplify \((7^{14} - 28 \times 20) \; (\text{mod } 6)\text{.}\)
14.
Simplify \((105^2 - 41 \times 20) \;(\text{mod }9)\text{.}\)
15.
Simplify \((19^{73} + 38 \times 68) \;(\text{mod }3)\text{.}\)
16.
Let \(X\) be the set \(\{0,1,2,3,4,5,6,7,8,9,10\}\text{.}\) Write down the equivalence classes of this set under the relation \(\equiv\, (\text{mod } 3)\text{.}\) Name each and list the elements using the correct notation.
17.
Simplify \(2^{27}\, (\text{mod } 5)\) by hand in the following way. (This method is used to simplify large numbers of the form \(b^c \, (\text{mod } n)\text{,}\) which is used in certain encryption protocols.)
Express \(2^{27}\) as a product of factors of the form \(2^{2^n}\) by writing \(27\) as a sum of powers of 2 (basically, in binary).
Use the arithmetic properties of the modulus function to simplify \(2^{2^n}\, (\text{mod } 5)\) for each of the powers of 2 in the product you found in the preceding part. (Notice that each power of 2 is a square of the preceding part. So to simplify \(2^{16}\, (\text{mod } 5)\text{,}\) you could simplify simplify \(2^{8}\, (\text{mod } 5)\text{,}\) square that, and then take its remainder modulo 5.)
Multiply the remainders you found in the preceding part, taking one last remainder mod \(5\) if necessary.
\(27 = 16 + 8 + 2 + 1\text{,}\) so \(2^{27} = 2^{16}2^82^22^1\text{.}\) Therefore,
Calculate the powers of \(2\) mod \(5\text{.}\) Eventually a pattern emerges:
\(\displaystyle 2\, (\text{mod } 5) = 2\)
\(\displaystyle 2^2\, (\text{mod } 5) = 4\)
\(\displaystyle 2^4\, (\text{mod } 5) = 4^2\, (\text{mod } 5) = 16\, (\text{mod } 5) = 1\)
\(\displaystyle 2^8\, (\text{mod } 5) = 1^2\, (\text{mod } 5) = 1\)
\(\displaystyle 2^{16}\, (\text{mod } 5) = 1^2\, (\text{mod } 5) = 1\)
So,
Hence, \(2^{27}\) is equivalent to \(3\) mod \(5\text{.}\)