3.8: Exercises

Q	A
Let \(A\) be the set { Chuck, Julie, Sam } and \(S\) be the set { basketball, volleyball }. Is { (Julie, basketball), (Sam, basketball), (Julie, volleyball) } a relation between \(A\) and \(S\)?	Yes it is, since it is a subset of \(A \times S\).
Is the above relation an endorelation?	No, because an endorelation involves one set with itself, not two different sets (like \(A\) and \(S\) are.)
Is { (Chuck, basketball), (basketball, volleyball) } a relation between \(A\) and \(S\)?	No, since the first element of one of the ordered pairs is not from the set \(A\).
Is \(\varnothing\) a relation between \(A\) and \(S\)?	Yes it is, since it is a subset of \(A \times S\).
How large could a relation between \(A\) and \(S\) be?	The maximum cardinality is 6, if all three athletes played all three sports. (I’m assuming that the meaning of the relation is “plays" instead of “isAFanOf" or “knowsTheRulesFor" or something else. In any case, the maximum cardinality is 6.)
Let \(T\) be the set { Spock, Kirk, McCoy, Scotty, Uhura }. Let \(O\) be an endorelation on \(T\), defined as follows: { (Kirk, Scotty), (Spock, Scotty), (Kirk, Spock), (Scotty, Spock) }. Is \(T\) reflexive?	No, since it doesn’t have any of the elements of \(T\) appearing with themselves.
Is \(T\) symmetric?	No, since it contains (Kirk, Scotty) but not (Scotty, Kirk).
Is \(T\) antisymmetric?	No, since it contains (Spock, Scotty) and also (Scotty, Spock).
Is \(T\) transitive?	Yes, since for every \((x,y)\) and \((y,z)\) present, the corresponding \((x,z)\) is also present. (The only example that fits this is \(x\)=Kirk, \(y\)=Spock, \(z\)=Scotty, and the required ordered pair is indeed present.)
Let \(H\) be an endorelation on \(T\), defined as follows: { (Kirk, Kirk), (Spock, Spock), (Uhura, Scotty), (Scotty, Uhura), (Spock, McCoy), (McCoy, Spock), (Scotty, Scotty), (Uhura, Uhura) }. Is \(H\) reflexive?	No, since it’s missing (McCoy, McCoy).
Is \(H\) symmetric?	Yes, since for every \((x,y)\) it contains, the corresponding \((y,x)\) is also present.
Is \(H\) antisymmetric?	No, since it contains (Uhura, Scotty) and also (Scotty, Uhura).
Is \(H\) transitive?	Yes, since there aren’t any examples of \((x,y)\) and \((y,z)\) pairs both being present.
Let outranks be an endorelation on the set of all crew members of the Enterprise, where \((x,y) \in\) outranks if character \(x\) has a higher Star Fleet rank than \(y\). Is outranks reflexive?	No, since no officer outranks him/herself.
Is outranks symmetric?	No, since an officer cannot outrank an officer who in turn outranks him/her.
Is outranks antisymmetric?	Yes, since if one officer outranks a second, the second one cannot also outrank the first.
Is outranks transitive?	Yes, since if one officer outranks a second, and that officer outranks a third, the first obviously also outranks the third.
Is outranks a partial order?	No, but close. It satisfies antisymmetry and transitivity, which are crucial. The only thing it doesn’t satisfy is reflexivity, since none of the members appear with themselves. If we changed this relation to ranksAtLeastAsHighAs, then we could include these “double" pairs and have ourselves a partial order.
Let sameShirtColor be an endorelation on the set of all crew members of the Enterprise, where \((x,y) \in\) sameShirtColor if character \(x\) ordinarily wears the same shirt color as character \(y\). Is sameShirtColor reflexive?	Yes, since you can’t but help wear the same shirt color as you’re wearing.
Is sameShirtColor symmetric?	Yes, since if a crew member wears the same shirt color as another, then that second crew member also wears the same shirt color as the first. If Scotty and Uhura both wear red, then Uhura and Scotty both wear red, duh.
Is sameShirtColor antisymmetric?	No, for probably obvious reasons.
Is sameShirtColor transitive?	Yes. If Kirk and Sulu wear the same color (yellow), and Sulu and Chekov wear the same color (yellow), then Kirk and Chekov most certainly will wear the same color (yellow).
Above, we defined \(A\) as the set { Chuck, Julie, Sam } and \(S\) as the set { basketball, volleyball }. Then we defined the relation { (Julie, basketball), (Sam, basketball), (Julie, volleyball) }. Is this relation a function?	No, because it’s missing Chuck entirely.
Suppose we added the ordered pair (Chuck, basketball) to it. Now is it a function?	No, because Julie appears twice, mapping to two different values.
Okay. Suppose we then remove (Julie, volleyball). We now have { (Julie, basketball), (Sam, basketball), (Chuck, basketball) }. Is this a function?	Yes. Congratulations.
Let’s call this function “faveSport," which suggests that its meaning is to indicate which sport is each athlete’s favorite. What’s the domain of faveSport?	{ Julie, Chuck, Sam }.
What’s the codomain of faveSport?	{ basketball, volleyball }.
What’s the range of faveSport?	{ basketball }.
Is faveSport injective?	No, because Julie and Sam (and Chuck) all map to the same value (basketball). For a function to be injective, there must be no two domain elements that map to the same codomain element.
Is there any way to make it injective?	Not without altering the underlying sets. There are three athletes and two sports, so we can’t help but map multiple athletes to the same sport.
Fine. Is faveSport surjective?	No, because no one maps to volleyball.
Is there any way to make it surjective?	Sure, for instance change Sam from basketball to volleyball. Now both of the codomain elements are “reachable" by some domain element, so it’s surjective.
Is faveSport now also bijective?	No, because it’s still not injective.
How can we alter things so that it’s bijective?	One way is to add a third sport — say, kickboxing — and move either Julie or Chuck over to kickboxing. If we have Julie map to kickboxing, Sam map to volleyball, and Chuck map to basketball, we have a bijection.
How do we normally write the fact that “Julie maps to kickboxing"?	faveSport(Julie) = kickboxing.
What’s another name for “injective?"	one-to-one.
What’s another name for “surjective?"	onto.
What’s another name for “range?"	image.