Greatest Hits on HW 7
- (4.3) 25 was often skipped/done wrong. Will do in class on 4/11.
A binary relation on A is a different object from a function from A to A. This occurred a lot in the proof-based questions.
- Please review the definition of the composition of two relations.
Suppose R\subseteq A\times B and S\subseteq B\times C are two relations.
Then R\circ S=\{(a,c) : a\in A \land c\in C \land \exists b\in B, (a,b)\in R \land (b,c) \in S\}.
Graphically, R\circ S consists of all endpoints in A\times C that can be connected via B using arrows in the relations R and S.
If R\subseteq A\times A is composed with itself: R\circ R consists of all endpoints of "paths of length 2" that can be formed in the arrow diagram.
Not every set has an order relation ('<') defined on it (i.e. be sure not to confuse an ordered set like the natural numbers and any set in general).
- When trying to come up with examples, try to keep it simple. E.g. the simplest example of a transitive and symmetric relation is the empty relation.
The grader recommended you guys don't use the proof techniques on this page. He said proof by illegibility and proof mumbo-jumbo were especially popular.