Proofs in Ch 4 -
Relations
Example 1
Last modified on
We have several goals in Chapter 4. First, to learn about relations. Second, to improve our proofwriting skills. Third, good habits for learning advanced mathematics. These goals are all related and they apply to other chapters as well. This page focuses on the proofwriting. It goes pretty slow, assuming that you are having trouble, or you wouldn't be here. For Ch 4 proofs you will need to know -
Proof strategies - the ones from Ch 3.
The main definitions in Ch 4 - which you should memorize.
How to use this knowledge - which is mainly observation and practice.
Example 1: For any relation R
from A to B, Ran (R-1) = Dom (R)
[This is Exercise 4.2 - 4a, which asks you to prove Thm 4.2.5
part 3, see page 170]
First Reactions: 1) There are 3 terms from Ch 4 you must understand to do the proof, namely "Dom" and "Ran" and "R-1". If necessary, look up the definitions (all on page 166) before you start, but get in the habit of learning such definitions as you go. You may have to patiently study some definitions until they make sense. 2) We are being asked to prove two sets are equal, and we know of several possible strategies, such as, a) prove containment both ways, or b) show xÎRan (R-1) iff xÎDom (R), or c) simplify one side into the other side. 3) This time, there are actually instructions in the exercise on which strategy to use.
First Proof: [I'll put comments in brackets, like this, if they are not needed in the proof].. [The instructions ask us to imitate the proof of Thm 4.2.5, part 2, which uses strategy b) mentioned in reaction 2) above. So, after reading over the proof of part 2 a time or two, we can start....]
Proof. First note that Ran (R-1) and Dom (R) are both subsets of A. Let a be an arbitrary element of A. Then
a Î Ran (R-1)
iff $ bÎB
((b,a)Î R-1) ...
[definition of "Ran" (with a and b switched): R-1 is
a relation from B to A]
iff $ bÎB
((a,b)Î R) ... [ def of R-1
]
iff aÎDom (R) , which proves the sets
are equal..
Second Proof: [Exercise 4b asks us to write a proof that combines parts 1 and 2 of Thm 4.2.5. This uses strategy c) mentioned above.]
Proof.. Dom (R)= Dom ((R-1)-1) [by part 1)] = Ran (R-1) [by part 2) but with R-1 substituted for R]. Done. [This proof would look better organized in columns].
What have we learned? We now know that Thm 4.2.5 part 3 is true. Maybe even more important, we understand the definitions on page 166 better, and can use them again in other proofs. We practiced two proof strategies. We learned to use previous results and to imitate previous proofs when possible. Think about what knowledge and skills were required for this proof. Then think about how you want to study math to get these.
Go to Example 2 (From Ch 4.6)