Thanks Defunkt, that was what I was looking for. Just another quick question, along the same lines. If I'm asked to prove that the injection relationship is reflexive and transitive - but i'm not given a domain or range with it - how would i go about proving this? Can I just make up my own domain and range that it works for and then prove that?
Thanks
You don't "make up" your domain and range -- you have to show that it holds for any domain and range, ie. that:
if there exist injections , then there exists an injection (this is transitivity).
and that for any set X, there exists an injection
Can you finish from here?
I have trouble coming up with the formal ways of explaining it..
For transitivity:
If f:X->Y and g:Y->Z are injections..
For all x in X, y in Y and z in Z s.t f(x) = y and f(y) = z, ???
I get that xRz as no other unique value from X can relate to z but can't explain it
For symmetric:
Should the identity function be used again here? Seems like it should be
To show transitivity, you need to show that given that there are injections , there is an injection .
Easily enough, let , then . Can you show that h is an injection?
For reflexivity: The identity function is an injection from X to X.
The relation is not symmetric, though. Can you see why?
No, that is incorrect. The relation is between whole sets, ie. if then is in the relation and so is since there is an injection from X to Y and also an injection from Y to X.
A proper counterexample to symmetry would be . Obviously, there is an injection from X to Y however there is no injection from Y to X, and so would be in the relation but would not be.
Can you come up with an example to anti-symmetry now?
Right, well for anti-symmetry I think that you just need the two sets to have the same cardinality and different elements to prove that it is not antisymmetric.
E.g X = {1,2,3}, Y={4,5,6}
There exists an injection from X->Y and Y->X, however X != Y. Hence the relation is not antisymmetric.
?