# Relation

• Oct 12th 2011, 01:59 PM
Hartlw
Relation
Given the definition that a relation on AXA is a subset of AXA, what does "R is a relation on a set A" mean?

a) R is a subset of AXA every member of which satisfies R (aRb).

or

b) R is a subset of AXA consisting of all (a,b) belonging to AXA st aRb.

Note both statements satisfy the definition that R is a subset of AXA.
• Oct 12th 2011, 02:08 PM
Plato
Re: Relation
Quote:

Originally Posted by Hartlw
Given the definition that a relation on AXA is a subset of AXA, what does "R is a relation on a set A" mean?

You have that wrong.
The statement that $\displaystyle \mathcal{R}$ is a relation on $\displaystyle A$ means $\displaystyle \mathcal{R}\subseteq(A\times A)$.

So statement that $\displaystyle \mathcal{S}$ is a relation on $\displaystyle A\times A$ means $\displaystyle \mathcal{S}\subseteq[(A\times A)\times(A\times A)]$.
• Oct 12th 2011, 02:20 PM
Hartlw
Re: Relation
Sorry about confusion. The book I am looking at takes "R is a relation on A" to mean "R is a subset of AXA" as self-evident.

R is a relation on AXB means R is a subset of AXB. So back to my original question.
• Oct 12th 2011, 02:31 PM
Plato
Re: Relation
Quote:

Originally Posted by Hartlw
R is a relation on AXB means R is a subset of AXB. So back to my original question.

That is a false statement.
Read my reply again about $\displaystyle \mathcal{S}$.
• Oct 12th 2011, 02:32 PM
Deveno
Re: Relation
Quote:

Originally Posted by Hartlw
Sorry about confusion. The book I am looking at takes "R is a relation on A" to mean "R is a subset of AXA" as self-evident.

R is a relation on AXB means R is a subset of AXB. So back to my original question.

again, no. R is a relation on AxB means R is a subset of (AxB) x (AxB).

(sorry, Plato, didn't see you post. i edited this to make it clear i was responding the the thread starter, and not you)
• Oct 12th 2011, 02:45 PM
Hartlw
Re: Relation
Quote:

Originally Posted by Plato
You have that wrong.
The statement that $\displaystyle \mathcal{R}$ is a relation on $\displaystyle A$ means $\displaystyle \mathcal{R}\subseteq(A\times A)$.

So statement that $\displaystyle \mathcal{S}$ is a relation on $\displaystyle A\times A$ means $\displaystyle \mathcal{S}\subseteq[(A\times A)\times(A\times A)]$.

OK. Even better.

What does R is a relation on a set A mean?

a) R is a subset of AXA every member of which satisfies R (aRb).

or

b) R is a subset of AXA consisting of all (a,b) belonging to AXA st aRb.

Note both statements satisfy the definition that R $\displaystyle \subseteq$ AXA.

EDIT: I'm trying to sort out statements like "Suppose R is a partial ordering on a set B and A is a subset of B." Then comes def of lub, which is clear if you take def b) above.
• Oct 12th 2011, 03:07 PM
Plato
Re: Relation
Quote:

Originally Posted by Hartlw
I'm trying to sort out statements like "Suppose R is a partial ordering on a set B and A is a subset of B." Then comes def of lub, which is clear if you take def b) above.

Study this webpage
• Oct 12th 2011, 03:40 PM
Hartlw
Re: Relation
I did. It has the same ambiguity:

"A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the set, one of the elements precedes the other."

My question still stands. Is the set an arbitrary subset for which aRb or is it a subset of ALL menbers of A st aRb?
• Oct 12th 2011, 03:55 PM
Plato
Re: Relation
Quote:

Originally Posted by Hartlw
"A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the set, one of the elements precedes the other." My question still stands. Is the set an arbitrary subset for which aRb or is it a subset of ALL menbers of A st aRb?

You are clearly have difficulty with basic set theory do you not?
If $\displaystyle \mathcal{R}$ is a partial order on $\displaystyle B$ then $\displaystyle \mathcal{R}$ is a relation on $\displaystyle B$ which is reflexive, anti-symmetric, and transitive.
Now if $\displaystyle A\subseteq B$ the partial order applies to $\displaystyle A$.
So WHAT is your problem with that?
• Oct 12th 2011, 04:11 PM
Hartlw
Re: Relation
Quote:

Originally Posted by Plato
You are clearly have difficulty with basic set theory do you not?
If $\displaystyle \mathcal{R}$ is a partial order on $\displaystyle B$ then $\displaystyle \mathcal{R}$ is a relation on $\displaystyle B$ which is reflexive, anti-symmetric, and transitive.
Now if $\displaystyle A\subseteq B$ the partial order applies to $\displaystyle A$.
So WHAT is your problem with that?

If R is a subset of AXA, does R consist of a subset of AXA for which aRb (possibly partially ordered) or does it consist of ALL elements of AXA for which aRb?

I could give a very simple example: for A = {1,2,3}. R= {(1,1), (1,2), (2,2)} or R ={(1,1), (1,2), (2,2), (2,3), (3,3)}. Both satisfy the definition of a poset for R, ie, the definition is ambiguous.

EDIT: Clarified the wording.
• Oct 12th 2011, 08:04 PM
Hartlw
Re: Relation
"If R is a subset of AXA, does R consist of a subset of AXA for which aRb (possibly partially ordered) or does it consist of ALL elements of AXA for which aRb?

I could give a very simple example: for A = {1,2,3}. R= {(1,1), (1,2), (2,2)} or R ={(1,1), (1,2), (2,2), (2,3), (3,3)}. Both satisfy the definition of a poset for R, ie, the definition is ambiguous."

I think this qestion got off track originally with some loose wording on my part. So my question is, based on the above, is the standard definition of relation ambiguous? If not, which of the above interpretations is correct

The question is serious because I don't know how to interpret it used in a theorem, and it isn't obvious to me (shoudn't be necessary if defined unambiguously).
• Oct 12th 2011, 08:50 PM
Deveno
Re: Relation
a relation R on A is a subset of AxA. that's very simple. the following 2 statements are equivalent:

aRb and (a,b) is in R.

a partial order (on A) is a relation with certain extra conditions (not every subset of AxA qualifies).

these extra conditions are:

1. reflexivity: aRa <=> (a,a) is in R, for all a in A (R contains the diagonal ΔA).
2. transitivity: aRb & bRc ---> aRc <=> if (a,b) is in R, and (b,c) is in R, then (a,c) is in R (you can "cut out the middle man").
3. antisymmetry aRb & bRa --> a=b <=> if (a,b) and (b,a) are in R, a=b

now let's look at your relations on A = {1,2,3}.

first we'll consider R = {(1,1), (1,2), (2,2)}. right away, we see R is not reflexive. 3 is in A, but (3,3) is not in R. (A,R) is not a poset.

now we'll consider R' = {(1,1), (1,2), (2,2), (2,3), (3,3)} since ΔA = {(1,1), (2,2), (3,3)} is a subset of R', R' is reflexive.

transitivity is a bother to check, but here goes:

the only elements in R' that are of the form (1,a) are (1,1) and (1,2). if we pick (1,1) as our aR'b, we have two choices for bR'c, (1,1) and (1,2).

(1,1)&(1,2) in R' -->? (1,2) in R'? yes.
(1,1)&(1,1) in R' -->? (1,1) in R'? yes. we'll just continue....
(1,2)&(2,2) in R' --> (1,2) in R'? yes.
(1,2)&(2,3) in R' --> (1,3) in R'? no. well, R' is not transitive. (A,R') is not a poset.

well, let's just add (1,3) to R', and call this R". R" is still reflexive, no need to re-check that.

(1,3)&(3,3) in R" --> (3,3) in R"? yes.
(2,2)&(2,2) in R" --> (2,2) in R"? yes.
(2,2)&(2,3) in R" --> (2,3) in R"? yes.
(2,3)&(3,3) in R" --> (2,3) in R"? yes.
(3,3)&(3,3) in R" --> (3,3) in R"? yes.

so R" is reflexive and transitive. is R" anti-symmetric? we only need to check the off-diagonal elements (1,2), (1,3), and (2,3).

since (2,1), (3,1) and (3,2) are not in R we see that the only pairs (a,b) for which (b,a) is also in R, are the diagonal elements (a,a),

that is, when a = b. R" is anti-symmetric. so (A,R") IS a poset.

(in fact, R" is the partial order we usually call ≤).
• Oct 13th 2011, 06:18 AM
Hartlw
Re: Relation
Thanks. Reference previous post.

Sorry you had to go through all that. I should have checked it myself. But my question still stands about the ambiguity of definition of a relation:

If R is a subset of AXA, does R consist of a subset of AXA for which aRb (possibly partially ordered) or does it consist of ALL elements of AXA for which aRb?

Hopefully this is a better example for poset. ab means (a,b) to save typing

A = (1,2,3,4,5), AXA=
11 12 13 14 15
21 22 23 24 25
31 32 33 34 35
41 42 44 44 45
51 52 53 54 55

R'
11 12 13 14 15
----22 23 24 25
-------33 34 35
----------44 45
--------------55
R''
11 12 13 14
----22 23 24
--------33 34
------------44
R'''
11 12 13
----22 23
-------33
R''''
11 12
----22

R'''''
11

All of the above satisfy R $\displaystyle \subseteq$ AXA. Which one is it? The question stands regardless of R being a poset. The question is about R.

EDITED A should obviously be (1,2,3,4,5), not (1,2,3). I point out the typo so someone doesn't pick it up and take the post into never- never land.
• Oct 14th 2011, 02:54 PM
Hartlw
Re: Relation
Def: R $\displaystyle \subseteq$ AXA
Def: aRb iff (a,b) in R
Def: "Total R": for all a,b $\displaystyle \epsilon$ A, aRb or bRa
• Oct 18th 2011, 06:55 AM
Hartlw
Re: Relation
The cleanest definition which removes all ambiquities is:

R $\displaystyle \subseteq$ AXA iff aRb

ie, Picking R defines aRb, or picking aRb defines R