Basic relation question

• February 15th 2011, 08:24 AM
Nforce
Basic relation question

I know how is defined a relation,
but how is defined R^2 and R^n?

If we have a relation R = {(1,2),(2,3),(3,4)}.

How do we get a R^2 and, R^n. If n is let say 504, surely we won't go calculating R * R * R... 504 times.
• February 15th 2011, 08:32 AM
Plato
Quote:

Originally Posted by Nforce
If we have a relation R = {(1,2),(2,3),(3,4)}.
How do we get a R^2 and, R^n. If n is let say 504, surely we won't go calculating R * R * R... 504 times.

Can you explain what "calculating R * R * R... 504 times" means.
What does R*R even mean in this context?
• February 15th 2011, 08:49 AM
Nforce
R is a relation. We can calculate with relations. In school we have defined R^-1 is an inverse relation, the product of two relations is R * S, and so on.
R^2 means. R times R. The product of two same relations.

I was hoping that somebody would explain to me the product of two relations and R^n.

on this example R = {(1,2),(2,3),(3,4)}.
• February 15th 2011, 08:56 AM
DrSteve
If $A$ is a set, then a relation $R$ on $A$ is a subset of $A^n$ for some $n$. In this case $R$ is an $n-$ary relation.

The relation you gave is a 2-ary or binary relation.

I don't think there is a standard definition for multiplying relations. So you will need to give us the definition you are using.
• February 15th 2011, 09:07 AM
Plato
Quote:

Originally Posted by Nforce
R is a relation. We can calculate with relations. In school we have defined R^-1 is an inverse relation, the product of two relations is R * S, and so on.
R^2 means. R times R. The product of two same relations.
I was hoping that somebody would explain to me the product of two relations and R^n.
on this example R = {(1,2),(2,3),(3,4)}.

I sorry to tell you, but that reply makes no sense whatsoever.
After teaching this material for forty+ years, I have never seen a product of a relation defined.
It is true that for $\mathcal{R}=\{(1,2),(2,3),(3,4)\}$ we can have composition of relations.

$\mathcal{R}\circ\mathcal{R}=\{(1,3),(2,4)\}$ and
$\mathcal{R}\circ(\mathcal{R}\circ\mathcal{R})=\{(1 ,4)\}$
After that the compositions are empty.

Is that what you are asking?
• February 15th 2011, 09:09 AM
Nforce
I didn't know that there's not a standard definition for calculating with relations. Hmm why is that?

http://www.shrani.si/f/2s/1W/2SFy2vXN/relations.jpg

The first is definition for a inverse relation. And second is for a product of relation R and S.
• February 15th 2011, 09:16 AM
DrSteve
Quote:

Originally Posted by Nforce
I didn't know that there's not a standard definition for calculating with relations. Hmm why is that?

http://www.shrani.si/f/2s/1W/2SFy2vXN/relations.jpg

The first is definition for a inverse relation. And second is for a product of relation R and S.

OK - now these definitions make sense. So by product you mean compositiion. Plato has then given you $R^n$ for each natural number n in his post above.
• February 15th 2011, 10:41 AM
Plato
Quote:
Does your text book really define relation composition as:
$\mathcal{R}\circ\mathcal{S}=\{(x,z):\exists y,(x,z)\in \mathcal{R} \wedge (z,y)\in \mathcal{S}\}~???$
If so I would say it is at least fifty years behind current practice.

The answer I gave you is based on this defition:
$\mathcal{R}\circ\mathcal{S}=\{(x,z):\exists y, (x,z)\in \mathcal{S} \wedge (z,y)\in \mathcal{R}\}$
That is, relation composition is like function composition right to left, inside out.
• February 15th 2011, 11:46 AM
Nforce
I still don't know if we are talking about the same thing.
I have found an example in the book. Would you be so kind to explain me. We always said the product of relations.

http://img695.imageshack.us/img695/411/relation2.jpg

The inverse relation is obvious. But the product as we defined it is (how I see it). The first element of order pair and the second element from another order pair is written in a new order pair. And so on...
• February 16th 2011, 02:40 PM
emakarov
Composition and product are sometimes the same thing, for example, when linear operators in a vector space are represented as matrices. Also, application of a mapping F to an argument x is often written just as F x, which resembles a product. For this reason, I guess, some textbooks may refer to composition of relations as a product, but the correct term is composition.

Also, the standard it to write the relation that is applied first on the right and the one applied second on the left. As Plato said, this works smoothly when relations are functions since $(f\circ g)(x)$ stands for $f(g(x))$. Using Internet lingo, there is a temptation to think that authors who don't follow this convention are trolling to create confusion, though this is unlikely, of course.

Other than that, the definition of composition you have is the standard one.
• February 16th 2011, 03:16 PM
Plato
Quote:

Originally Posted by emakarov
Other than that, the definition of composition you have is the standard one.

Do you seriously think that? Standard?
So far as I know, that has not been in use since the 1940’s.
Even Quine changed his notation from 1938 to 1951.
Can you give us a reference to a modern text using a ‘left to right’ definition for relation compositions?
I do have an algebra text by Marie Weiss at Tulane in the ’40 & 50’s that does use that notation. She was interested in permutation groups so that makes a certain amount of sense (as a product).
• February 16th 2011, 03:31 PM
emakarov
Quote:

Other than that, the definition of composition you have is the standard one.
I meant, other than the order (left/right). I guess, now it looks like it is I who is trolling to create confusion. (Sadsmile)