Hi, I have a problem which says this:
Prove that if r;s is reflexive, then r is total and s is surjective.
Thanks.
It appears that both each of R and S is a relation on some set A: that is, each is a subset of AXA. Some authors say a relation is total if each element of A is the first term of some pair in the relation. (Now that may not be meant here! But it fits.)
Suppose that we are given that SoR is reflexive. Thus if t is an element of A then the pair (t,t) belongs to SoR. That means that there exists an element w in A such that the pair (t,w) belongs to R and the pair (w,t) belongs to S. This means that t is comparable to some element is A by way of R making R total. And t is the second term of some pair is S making S surjective.
[Now, I know that the problem is written as “r;s”. But the statement is true only for SoR. Again, the author may have meant something else entirely.]
That is how the problem is exactly written. It is taken from a past paper of our type of examination. These are the type of problems we are given. So plato that is the type of answer I should give?
Thanks a lot. To be honest I am more confused about how to answer these type of problems rather than not understanding them.
You do realize that that is just a guess as to what the terms mean.
This is the painful fact: There are no standard definitions in mathematics.
When you post such a problem it is helpful to include definitions were possible.
That answer may not be correct. It depends upon the definitions.
Right .. according to the book we use these are the definitions:
Relational Composition:
R ; S = {x :X, y:Y, z :Z | x -> y is an element of R /\ y -> z is an element of
S . (x,z)}
Reflexivity:
for all x : X . (x,x) is an element of R
Totality:
for all x,y : X . (x,y) is an element of R \/ (y,x) is an element of R \/ x = y
Symmetry:
for all x,y : X . (x,y) is an element of R => (y,x) is an element of R
Thanks again.
My, my; I have never seen a definition for totality like that except for posets. Reflexive and symmetric are rather standard. But composition is backward from most other texts in the field. What text is it anyway?
Now back to the problem. The above proof still works for S being surjective.
But I do not see right away how to get totally for R.
Thanks for the wiki, I am starting to understand. I have only got one question: when you have a relational composition R ; S how can you write the definition as reflexive? I can write a single relation such as R, as reflexive by using the definition (for all x : X . (x,x) is an element of R) but I can't figure how to write it as a relational composition.
Thanks.
Plato gave you a definition of total that works for this problem. This Wikpedia page talks about the different definitions for total. Are you sure you have the right one?
JakeD, you know that we have to be care with both Wikipedia and MathWorld.
That definition of ‘Left Total’ given there is the same as Ken Rosen uses for total.
Using that definition then the proof I gave above goes through. But Simpson seems to be using the later definition. I do not see a way to prove the statement using that definition. For any x & y, (x,y) or (y,x). Don’t see it.