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 $(a, b)$. (An ordered pair is just a pair of 'things' - often, but not always, numbers - in a certain order.) The 'things', $a$ and $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 $\{0, 1, 2, 3\}$ the relation $R_1 = \{(a, b) | a < b\}$ is defined, then $R_1$ will form a set of ordered pairs $(a, b)$ in which the first number, $a$, is less than the second number, $b$. So the set that's formed is:

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

(Obviously, if $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 $R_1$ is

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

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

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

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

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

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

$(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 $R_2^{-1}$ we get:

$(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 $R_2^{-1} = \{(a, b) | a$ is a multiple of $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 $a$, and form the ordered pair $(a, b)$ using the first relation $R_4$. Then use the $b$ from this ordered pair with the relation $R_3$ to form another ordered pair $(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 $(a, c)$

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

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

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

$(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 $R_3$. For instance, we could get:

$(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:

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

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

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

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

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