Hi, I have a problem which says this:

Prove that if r;s is reflexive, then r is total and s is surjective.

Thanks.

Printable View

- September 10th 2006, 12:36 AMiazzRelational Composition Problem - Please help!
Hi, I have a problem which says this:

Prove that if r;s is reflexive, then r is total and s is surjective.

Thanks. - September 10th 2006, 06:28 AMThePerfectHacker
- September 10th 2006, 08:55 AMPlato
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.] - September 10th 2006, 10:03 AMiazz
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. - September 10th 2006, 10:20 AMPlato
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. - September 10th 2006, 10:32 AMiazz
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. - September 10th 2006, 11:20 AMPlato
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. - September 10th 2006, 11:28 AMiazz
Text is Discrete Maths By Example - Andrew Simpson. So any easier definitions which can help me solve my problem? I'd appreciate them :)

Thanks. - September 10th 2006, 12:16 PMiazz
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. - September 10th 2006, 12:20 PMJakeD
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?

- September 10th 2006, 12:26 PMPlato
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. - September 10th 2006, 12:33 PMJakeD
- September 10th 2006, 12:40 PMJakeD
- September 10th 2006, 12:51 PMiazz
Thank you ppl. You were of great help :)