1. ## Relations help..

I am new to discrete math, and am having trouble with a couple problems..

What is the inverse of the following relations:
Rsub1 = {(a, b) | a < b}
Rsub2 = {(a, b) | a divides b}

Also, i need help with composition.. :
What is Rsub3 of Rsub4 if
Rsub3 = {(a, b) | a > b}
Rsub4 = {(a, b) | a >= b}

2. ## Inverse Relations

Hello Manizzle
Originally Posted by Manizzle
I am new to discrete math, and am having trouble with a couple problems..

What is the inverse of the following relations:
Rsub1 = {(a, b) | a < b}
Rsub2 = {(a, b) | a divides b}

Also, i need help with composition.. :
What is Rsub3 of Rsub4 if
Rsub3 = {(a, b) | a > b}
Rsub4 = {(a, b) | a >= b}
When a relation is defined on a set, it forms a set of ordered pairs, like $\displaystyle (a, b)$. (An ordered pair is just a pair of 'things' - often, but not always, numbers - in a certain order.) The 'things', $\displaystyle a$ and $\displaystyle b$, that make up the ordered pair, are related in the way that is described in the definition of the relation.

So, for instance, if on the set $\displaystyle \{0, 1, 2, 3\}$ the relation $\displaystyle R_1 = \{(a, b) | a < b\}$ is defined, then $\displaystyle R_1$ will form a set of ordered pairs $\displaystyle (a, b)$ in which the first number, $\displaystyle a$, is less than the second number, $\displaystyle b$. So the set that's formed is:

$\displaystyle \{(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)\}$

(Obviously, if $\displaystyle R_1$ is defined on a different set of numbers - all the integers, for instance - then you'll get a different, but similar, set of ordered pairs.)

Now the inverse relationship simply reverses the order of the numbers in the ordered pair. So if $\displaystyle R_1$ is

$\displaystyle \{(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)\}$, then

$\displaystyle R_1^{-1} = \{(1, 0), (2, 0), (3, 0), (2, 1), (3, 1), (3, 2)\}$.

So your job in finding $\displaystyle R_1^{-1}$ is to define this new set of ordered pairs using a rule, so that it looks like:

$\displaystyle R_1^{-1} = \{(a, b) | a$ and $\displaystyle b$ are related by such-and-such a rule$\displaystyle \}$

Clearly, then, if $\displaystyle R_1 = \{(a, b) | a < b\}$, then $\displaystyle R_1^{-1} = \{(a, b) | a > b\}$

For $\displaystyle R_2$, where the rule is "$\displaystyle a$ divides $\displaystyle b$" typical ordered pairs might be (depending on which numbers are in the original set)

$\displaystyle (2, 10), (3, 15), (6, 6), ...$

because in each ordered pair, the first number divides into the second without leaving a remainder.

When we reverse these to form some typical ordered pairs in $\displaystyle R_2^{-1}$ we get:

$\displaystyle (10, 2), (15, 3), (6, 6), ...$

So, can you see how we could describe the inverse rule? (The word 'multiple' comes to mind!)

Yes, it's $\displaystyle R_2^{-1} = \{(a, b) | a$ is a multiple of $\displaystyle b\}$

Combining relations means first forming one set of ordered pairs using the first relation (which, confusingly is written down second, because we don't work from left to right!), and then using the second relation to form a second set of ordered pairs from the first.

So, for instance, we might start with $\displaystyle a$, and form the ordered pair $\displaystyle (a, b)$ using the first relation $\displaystyle R_4$. Then use the $\displaystyle b$ from this ordered pair with the relation $\displaystyle R_3$ to form another ordered pair $\displaystyle (b, c)$.

Finally, if we're going to say what's happened when these relations are combined, we will need to describe the relation that gives all the ordered pairs like $\displaystyle (a, c)$

$\displaystyle R_3 = \{(a, b) | a > b\}$ and

$\displaystyle R_4 = \{(a, b) | a >= b\}$

and we want to know what $\displaystyle R_3 \circ R_4$ is. So we do $\displaystyle R_4$ first, getting ordered pairs like:

$\displaystyle (3, 1), (3, 2), (3, 3), ...$ where the second number in the pair is never greater than the first.

Then we take the second number from each ordered pair, and with it form a new ordered pair using $\displaystyle R_3$. For instance, we could get:

$\displaystyle (1, 0), (2, 1), (3, 2), ...$ where the second number in the pair is now definitely smaller than the first.

Looking at the overall effect, using these examples, we get the ordered pairs:

$\displaystyle (3, 0), (3, 1), (3, 2), ...$

Notice that we can't get $\displaystyle (3, 3)$ now, because $\displaystyle R_3$ insists that the first number is strictly greater than the second. So the combined relation is simply:

$\displaystyle \{(a, b) | a > b\}$

In other words, it's the same as $\displaystyle R_3$.

Sorry if that was a bit long, but I hope you understand it a bit better now.