In each of the following, describe the requested combination of relations in words (i.e. in the form “a is related to b if …”). Try to “simplify” your description, if possible.
In Task h and Task i, the symbol \(\mathord{\equiv}_k\) represents a relation on \(\Z\text{,}\) where \(m \equiv_k n\) means that \(m\) and \(n\) have the same remainder when divided by \(k\text{.}\) (It may help to know that this is equivalent to \(k\) dividing the difference \(m - n\text{.}\))
(a)
\(\mathord{\lt} \cup \mathord{\gt}\) on \(\R\text{.}\)
(b)
Union of “longer than” and “shorter than” on \(\words{\Sigma}\) for some alphabet \(\Sigma\text{.}\)
(c)
Union of “longer than”, “shorter than”, and “same length as” on \(\words{\Sigma}\) for some alphabet \(\Sigma\text{.}\)
(d)
Intersection of “longer than” and “shorter than” on \(\words{\Sigma}\) for some alphabet \(\Sigma\text{.}\)
(e)
The complement of \(\mathord{\le}\) on \(\R\text{.}\)
(f)
The inverse of \(\mathord{\le}\) on \(\R\text{.}\)
(g)
The inverse of “\(x \mathrel{R} y\) if \(2 x + 3 y = 0\)” on \(\R\text{.}\)
(h)
The intersection of \(\mathord{\equiv_5}\) and \(\mathord{\equiv_7}\) on \(\Z\text{.}\)
(i)
The intersection of \(\mathord{\equiv_2}\) and \(\mathord{\equiv_4}\) on \(\Z\text{.}\)
Activity17.2.
In each of the following, you are given a set \(A\) and a relation \(R\) on \(A\text{.}\) Determine which of the properties reflexive, symmetric, antisymmetric, and transitive\(R\) possesses.
(a)
\(A = \R\text{,}\)\(R\) is \(\mathord{\lt}\text{.}\)
(b)
\(A\) is the set of all straight lines in the plane, \(R\) means “is parallel to.”
(c)
\(A\) is the set of all straight lines in the plane, \(R\) means “is perpendicular to.”
(d)
\(A = \words{\Sigma}\) for some alphabet \(\Sigma\text{,}\)\(R\) means “is the same length as.”
(e)
\(A = \words{\Sigma}\) for some alphabet \(\Sigma\text{,}\)\(R\) means “is shorter than.”
(f)
\(A = \words{\Sigma}\) for some alphabet \(\Sigma\text{,}\)\(x\) is some fixed choice of letter in \(\Sigma\text{,}\)\(R\) means “contains the same number of occurrences of \(x\) as.”
Suppose \(R\) is a relation on a set \(A\text{.}\) Convince yourself that \(R \union \inv{R}\) is symmetric. (See the Symmetric Relation Test.)
(b)
Recall that \(\mathord{\mid}\) represents the relation “divides” on sets of integers. Draw the directed graph for \(\mathord{\mid}\) on the set \(A = \{2,4,6,8,10,12,14,16\}\text{.}\) Then describe how to obtain the graph for the symmetric relation \(\mathord{\mid} \cup \inv{\mathord{\mid}}\) as an undirected graph from the graph of \(R\) using only an eraser.
Assume that \(R\) and \(S\) are nonempty relations on a set \(A\) that both have the property. For each of \(\cmplmnt{R}\text{,}\)\(R \union S\text{,}\)\(R \intersection S\text{,}\) and \(\inv{R}\text{,}\) determine whether the new relation
must also have that property;
might have that property, but might not; or
cannot have that property.
Any time you answer Statement i or Statement iii, outline a proof. Any time you answer Statement ii, provide two examples: one where the new relation has the property, and one where the new relation does not. (You may use graphs to describe your examples.)
