Thread: Relational 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.

Originally Posted by iazz

Hi, I have a problem which says this:

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

Thanks.

Reflexsive on what?
Surjective on what?
I assume you want to prove a certain set (or all sets having this property) are totaliy ordered sets.

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.

Text is Discrete Maths By Example - Andrew Simpson. So any easier definitions which can help me solve my problem? I'd appreciate them

Thanks.

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.

Originally Posted by iazz

Text is Discrete Maths By Example - Andrew Simpson. So any easier definitions which can help me solve my problem? I'd appreciate them.

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?

Originally Posted by Plato

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.)

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.

Originally Posted by iazz

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.

For all x, (x,x) is an element of R; S requires that for all x in X there exists a y such that (x,y) is an element of R and (y,x) is an element of S.

Originally Posted by iazz

Relational Composition:
R ; S = {x :X, y:Y, z :Z | x -> y is an element of R /\ y -> z is an element of S}

Reflexivity:
for all x : X . (x,x) is an element of R

Originally Posted by Plato

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.

Yes, I've seen a few problems with them, but that Wikipedia page was clear that different authors use different definitions and the definitions it gave looked OK to me.

I agree with you on the proof.

Thank you ppl. You were of great help