Exercises 12.4 Exercises
1.
Write the relation \(R = \{(x,y) \; | \; y=x^2 \}\) on \(\{-10, -9, -8, \ldots, 8, 9, 10\}\) as a set of ordered pairs.
2.
Write the relation
on the set \(\{1,2,\ldots,10\}\) as a set of ordered pairs.
3.
Write the relation
where \(X=\{a,b\}\) as a set of ordered pairs.
4.
Consider the relation on \(\{1,2,3,4,5\}\) where \(x\) is related to \(y\) if \(x=y\text{.}\) Write this relation as a set of ordered pairs.
5.
Consider the relation on \(\{1,2,3,4,5\}\) where \(x\) is related to \(y\) if \(x \lt y\text{.}\) Write this relation as a set of ordered pairs.
6.
Let \(X\) and \(Y\) be subsets of \(\{a,b\}\text{.}\) Write the relation where \(X\) is related to \(Y\) if \(|X|=|Y|\) as a set of ordered pairs.
7.
Let \(R = \{(a,a), (a,c), (b,b), (c,b), (c,c)\}\) be a relation on the set \(\{a,b,c\}\text{.}\) Tell what properties this relation has. If the relation does not have a property, provide an example showing why not. If the relation does have a property, there is no need to prove why.
8.
Give the properties of the relation \(R = \{(x,y) \; | \; y=x^2 \}\) on \(\mathbb{Z}\text{.}\) If the relation does not have a property, provide an example showing why not. If the relation does have a property, there is no need to prove why.
For any of these problems, consider the set of ordered pairs on the finite set described in a problem above. It won't tell the whole story, but it could give you an idea.
9.
Give the properties of the relation
If the relation does not have a property, provide an example showing why not. If the relation does have a property, there is no need to prove why.
10.
Give the properties of the relation
where \(X\) is any finite, nonempty set. If the relation does not have a property, provide an example showing why not. If the relation does have a property, there is no need to prove why.
11.
Consider the relation on \(\mathbb{Z}\) where \(x\) is related to \(y\) if \(x=y\text{.}\) Give the properties of this relation. If the relation does not have a property, provide an example showing why not. If the relation does have a property, there is no need to prove why.
12.
Consider the relation on \(\mathbb{Z}\) where \(x\) is related to \(y\) if \(x \lt y\text{.}\) Give the properties of this relation. If the relation does not have a property, provide an example showing why not. If the relation does have a property, there is no need to prove why.
13.
Let \(X\) and \(Y\) be subsets of any finite, nonempty set. Give the properties of the relation where \(X\) is related to \(Y\) if \(|X|=|Y|\text{.}\) If the relation does not have a property, provide an example showing why not. If the relation does have a property, there is no need to prove why.
14.
Give the properties of the relation \(R = \{(x,y) \; | \; y = 3x+5 \}\) on the set \(\mathbb{Z}\text{.}\) If the relation does not have a property, provide an example showing why not. If the relation does have a property, there is no need to prove why.
15.
Give the properties of the successor relation \(S = \{(n, n+1)\;|\;n \in \mathbb{N}\,\}\text{.}\) If the relation does not have a property, provide an example showing why not. If the relation does have a property, there is no need to prove why.
16.
Consider the relation \(A = \{(f,g)\;|\; f = O(g) \text{ and } g = O(f) \}\) where \(f\) and \(g\) are sequences. Recall \(f=O(g)\) means that there exist integers \(k\) and \(C\) where for all \(n > k\text{,}\) \(|f(n)| \le Cg(n)\text{.}\) Tell what properties this relation has. If the relation does not have a property, provide an example showing why not. If the relation does have a property, there is no need to prove why.
By definition, \(f=O(f)\text{,}\) so the relation is reflexive. Since the space of sequences is nonempty the relation is not also antireflexive. Symmetry is baked into the definition (both \(f=O(g)\) and \(g=O(f)\)). It is not antisymmetric because different functions can be big-O of one another.
For transitivity, suppose \(f = O(g)\) and \(g = O(h)\text{.}\) There thus exist positive integers \(k_1, k_2, C_1, C_2\) where for all \(n \ge k_1\text{,}\) \(|f(n)| \le C_1g(n)\text{,}\) and for all \(n \ge k_2\text{,}\) \(|g(n)| \le C_2h(n)\text{.}\) Let \(k\) be the bigger of \(k_1, k_2\) and define \(C=C_1C_2\text{.}\) Therefore, for all \(n \ge k\text{,}\)
implying that \(f=O(h)\text{.}\)
Here, the moral is that the set of functions that are big-O of one another form an equivalence class.
17.
(Requires calculus) Fix an open interval \(I\) and consider the relation of differentiable functions \(\{(F,G) \; | \; F'(x) = G'(x) \text{ for all } x \in I \}\) where \(F'\) represents the derivative of \(F\text{.}\) Tell what properties this relation has. If the relation does not have a property, provide an example showing why not. If the relation does have a property, there is no need to prove why.
\(F'=F'\text{,}\) if \(F'=G'\) then \(G'=F'\text{,}\) and if \(F'=G'\) and \(G'=H'\) then \(F'=H'\text{.}\) So, the relation is reflexive, symmetric, and transitive. The broader moral is that different antiderivatives of a function are equivalent. It is not antireflexive because the underlying set of functions is nonempty and it is not antisymmetric because different functions can share the same derivative if they differ by a constant.
18.
Let \(X=\{a,b,c,d\}\) and the relation \(R\) on \(X\) be defined by
Write down a matrix for \(R\) where the rows and columns are arranged alphabetically.
Draw a digraph for \(R\text{.}\)
19.
Let \(Y=\{a,b,c,d,e\}\) and the relation \(S\) on \(Y\) be defined by
Write down a matrix for \(S\) where the rows and columns are arranged alphabetically.
Draw a digraph for \(S\text{.}\)
20.
Let \(Y=\{x_1, x_2, x_3, x_4, x_5\}\) and \(S\) be the relation on \(Y\) defined by \(S = \{(x_1,x_4),(x_2,x_3),(x_3,x_2), (x_4,x_5),(x_5,x_1)\}\text{.}\)
Write down a matrix for \(S\) where the rows and columns are arranged numerically.
Draw a digraph for \(S\text{.}\)
21.
Let \(R\) and \(S\) be represented by the matrices \(M_R\) and \(M_S\) respectively:
Is \(R \subseteq S\text{?}\)
Is \(S \subseteq R\text{?}\)
Write down the matrix for \(R \cup S\text{.}\)
Write down the matrix for \(R \cap S\text{.}\)
22.
Can a relation be both reflexive and antireflexive? If so, give an example; if not, give a reason.
23.
Can a relation be both symmetric and antisymmetric? If so, give an example; if not, give a reason.
24.
(This problem assumes that you have already read Part III.) Let \(X\) be a set with \(n\) elements. Count the number of:
reflexive relations on \(X\text{.}\)
antireflexive relations on \(X\text{.}\)
symmetric relations on \(X\text{.}\)
antisymmetric relations on \(X\text{.}\)
The key is to note that every relation is a subset of \(X\times X\text{.}\) There are \(n^2\) elements of \(X\times X\text{,}\) and hence \(2^{n^2}\) subsets/relation. This is the number of all relations. This formula will change slightly depending on the restrictions of the given property.
The \(n\) elements “on the diagonal” are forced upon our relation. Therefore, this removes \(n\) choices from the \(n^2\) choices we were otherwise going to have to make. So, there are \(2^{n^2-n}\) reflexive relations on the set.
On the other hand, requiring that the diagonal elements not be in the relation also takes away \(n\) choices. Therefore there are also \(2^{n^2-n}\) antireflexive relations.
If the relation is symmetric, the choice of an off-diagonal pair automatically forces us to include the inverse of that pair. There are \({{n}\choose{2}}\) ways to choose a non-diagonal pair irrespective of its order (because we're getting both). We are free to choose any diagonal pairs we like. Thus, there are \(2^n 2^{{n}\choose{2}}\) symmetric relations.
If the relation is antisymmetric, things get a little weird. First, we can choose any diagonal pairs freely. Otherwise, if a pair is off the diagonal, we get three choices: include it, include its inverse, or include neither. Therefore the number of antisymmetric relations is \(2^n 3^{{n}\choose{2}}\text{.}\)
25.
Verbally describe the matrix for a relation that is:
diagonal.
symmetric.
antireflexive.
antisymmetric.