[Ross321]

Say I have a set A with 5 elements in it. I want to make a relation of A onto itself. I know there are 5^2 possible pairs, so there are 2^(5^2) possible relations.

Now lets say A = {a,b,c,d,e}

How would I find the number of relations that contain (a,b), (c,d), and (d,e)?

I'm pretty sure that (2^25 - 2^22) would give me the number of relations that contain at least one of (a,b), (c,d), (d,e), wouldn't it? And then from there, how could I get the number of relations that contains all 3 of the pairs?

Thanks.

[ebaines]

Please clarify - what do you mean by the term "relations?" Give us an example of a "relation" using your set of {a,b,c,d,e}. I agree that there are 5^2 possible pairs from this set, but only if duplicates are allowed - such as (a,a) - and also only if the order of the pair matters - that is the pair (a,b) is considered to be different from (b,a).

[Ross321]

A relation is similar to a function, except unlike in a function where each element in the domain can only map to one element in the co-domain, in a relation the elements in the co-domain can map to multiple elements in the co-domain.

So when I say a relation of A onto itself, we are mapping {a,b,c,d,e} to {a,b,c,d,e}

An example relation from this is R = {(a,a),(a,b),(b,a)}, or R = {(a,a)}

That's why we have 2^5^2 relations, for each pair (which we have (5^2) of, you make the choice "is this pair in my relation or not?".

I figured out the answer to this last night, if we're trying to find how many relations contain (a,b) and (c,d) and (d,e), it'd be 2^22 (the 22 coming from the total number of pairs minus the ones we want)

[Ross321]

One little mistake, the line at the top should read:

In a relation the elements in the domain can map to multiple elements in the co-domain

[ebaines]

OK - thanks for the explanation! I agree that if you require 3 specific pairs to be present in the relation set, then that means there are 22 other pairs that either may, or may not, be present in that set as well. Hence you have 2^22 combinations of pairs are possible. Some examples you could have are:

{(a,b), (c,d), (d,e), (a,a), (d,c)}, or
{(a,b), (c,d), (d,e), (a,a), (d,c), (e,e)}