CS 135: Problem Set 4
Due: 2024-10-11
Problem 1 (10 points): Let S be the set of students at Stevens, R be the set of dorm rooms, P be the set of
professors at Stevens, and C be the set of courses offered at Stevens.
Furthermore, let L ⊆ S × R be the relation consisting of ordered pairs (s, r) such that student s lives in dorm
room r. Similarly, let E ⊆ S × C be the relation of ordered pairs (s, c) such that student s is enrolled in course
c. Finally, let T ⊆ C × P be the relation of ordered pairs (c, p) such that c is taught by professor p.
Describe, in English, the following relations:
a. E −
b. E ◦ L−
c. E − ◦ E
d. E ◦ E −
e. T ◦ (E ◦ L− )
f. (T ◦ E) ◦ L−
Problem 2 (10 points): Suppose that R1 and R2 are two relations over some set A. For each statement
below, either give a proof that it is true, or give a counterexample.
a. If R1 , R2 are both reflexive, then so is R1 ∪ R2 .
b. If R1 , R2 are both symmetric, then so is R1 ∪ R2 .
c. If R1 , R2 are both transitive, then so is R1 ∪ R2 .
Problem 3 (10 points): An interesting property of reflexivity, symmetry and transitivity is that a relation
can have any combination of these. It could be reflexive and transitive but not symmetric, it could be just
symmetric and not the other two, or any other combination of them.
However, Lem E. Hackett, self-proclaimed “future Fields Medal winner”, claims that this is false. After all, he
claims to have found a proof of the fact that a symmetric transitive relation must also necessarily be reflexive.
Proof. Suppose that relation R over set A is both symmetric and transitive.
Let (a, b) ∈ R be arbitrary. By symmetry, we get that (b, a) ∈ R. Thus, by transitivity, we see that (a, a) ∈ R.
By generalization, we thus see that R must be reflexive.
a. Find a counterexample to disprove Lem’s conclusion.
b. What is the issue in Lem’s proof?
1
Due: 2024-10-11
Problem 1 (10 points): Let S be the set of students at Stevens, R be the set of dorm rooms, P be the set of
professors at Stevens, and C be the set of courses offered at Stevens.
Furthermore, let L ⊆ S × R be the relation consisting of ordered pairs (s, r) such that student s lives in dorm
room r. Similarly, let E ⊆ S × C be the relation of ordered pairs (s, c) such that student s is enrolled in course
c. Finally, let T ⊆ C × P be the relation of ordered pairs (c, p) such that c is taught by professor p.
Describe, in English, the following relations:
a. E −
b. E ◦ L−
c. E − ◦ E
d. E ◦ E −
e. T ◦ (E ◦ L− )
f. (T ◦ E) ◦ L−
Problem 2 (10 points): Suppose that R1 and R2 are two relations over some set A. For each statement
below, either give a proof that it is true, or give a counterexample.
a. If R1 , R2 are both reflexive, then so is R1 ∪ R2 .
b. If R1 , R2 are both symmetric, then so is R1 ∪ R2 .
c. If R1 , R2 are both transitive, then so is R1 ∪ R2 .
Problem 3 (10 points): An interesting property of reflexivity, symmetry and transitivity is that a relation
can have any combination of these. It could be reflexive and transitive but not symmetric, it could be just
symmetric and not the other two, or any other combination of them.
However, Lem E. Hackett, self-proclaimed “future Fields Medal winner”, claims that this is false. After all, he
claims to have found a proof of the fact that a symmetric transitive relation must also necessarily be reflexive.
Proof. Suppose that relation R over set A is both symmetric and transitive.
Let (a, b) ∈ R be arbitrary. By symmetry, we get that (b, a) ∈ R. Thus, by transitivity, we see that (a, a) ∈ R.
By generalization, we thus see that R must be reflexive.
a. Find a counterexample to disprove Lem’s conclusion.
b. What is the issue in Lem’s proof?
1
