Relation in a power set
By Arun Iyer on Wednesday, October 02, 2002 - 05:26 pm:

Question:

Let r be the relation on the power set P(S) of a finite set S of cardinality n. Define r by (A,B) Î r iff AÇB=Æ.

What is the cardinality of r for any arbitrary n??
love arun

By Dan Goodman on Wednesday, October 02, 2002 - 06:43 pm:

Arun, here are some hints (full solution available on request), see if you can get it without reading all of them.

1. Given a set A (a subset of S) with m elements, how many sets B are there so that A and B are related, in terms of n and m?

2. How many sets are there of size m?

3. Suppose you know there are f(n) ordered pairs (A,B) with A and B disjoint sets (that is, 0 intersection) - how many unordered pairs are there? Think about how many times an unordered pair (A,B) is counted as an ordered pair, there is a general case and a special case.

By Dan Goodman on Thursday, October 03, 2002 - 07:59 pm:

Arun, here's another hint: fix a particular set A with m elements (we may as well assume that S={1,...,n} and A={n-m+1,...,n}). If we want A intersect B = {} then B has to be contained in S-A (which we can assume is {1,...,n-m}). But any subset of S-A will work. How many such subsets are there?

By Arun Iyer on Saturday, October 05, 2002 - 06:01 pm:

Dan,
the number of such subsets(that u mention) would be 2n-m

now number of such m element subsets(or number of A's that can be formed) would be n Cm

therefore total number of such subsets would be,
n Cm *2n-m


therefore cardinality of r is,
n
å
m=0 
  n Cm×2n-m=3n


Am i right???

love arun
P.S-> thanks that was a big hint you gave there:)
By Dan Goodman on Saturday, October 05, 2002 - 08:40 pm:

Arun, you're either very close or actually right, depending on how you read the question. Now that I think back, I think that a relation, even if it is symmetric like this one, is defined in terms of ordered, rather than unordered, pairs. So you've got it!

My hint (3) was assuming that you were counting unordered pairs which were related, which is a misinterpretation of the question. If you were doing this, then you'd have counted (A,B) and (B,A) twice (for A =/= B). Since A is only related to A when A={} you've double counted every relation except {{},{}} which you've counted once. So, the number of unordered relations is (3n -1)/2+1=(1/2)(3n +1).

By Arun Iyer on Sunday, October 06, 2002 - 06:03 pm:

Dan,
actually i never read your hint no.2 and 3!!! your first one itself was a big help(Thanks again!!)

as for your hint 3...
how would the question be if i were to consider that hint

love arun

By Dan Goodman on Sunday, October 06, 2002 - 06:11 pm:

Arun, that's good. The second paragraph of my last post explains what would have been different if you'd been looking for unordered pairs (which is what hint 3 was about).

By Arun Iyer on Sunday, October 06, 2002 - 07:23 pm:

Dan,
i understood why u stressed upon hint 3 ...

i only wanted to know if i were supposed to be looking for unordered pairs in my solution then how would the question be (or what changes would be there in the already given question)??

sorry for the trouble!!i am just being a bit cautious ... bcos in my exams ,i might get a question wherein i would be required to look for unordered pairs...(so your hint3 would be quite useful for me in that case)

love arun

By Dan Goodman on Sunday, October 06, 2002 - 07:59 pm:
Arun, so, you're asking how would the question be phrased if they were asking about unordered pairs rather than ordered ones? That's tricky. The way they asked the question, they asked what the cardinality of r was. The usual definition of a relation (set theoretically) is the set of ordered pairs (A,B) of elements for which the relation ArB holds. So, the cardinality of r according to this definition of a relation will be the number of ordered pairs 3n. However, since your particular relation r is symmetric, saying ArB implies BrA, so there is some sense in which ArB is the same as BrA. If they were going to ask about the number of unordered pairs, I think they would probably make it clear by using some phrase like ''how many pairs satisfying the relation are there?'' or ''assuming that the pair (A,B) and (B,A) are the same, how many pairs are there?''. I think, by asking about the cardinality of r rather than the number of pairs, they meant to specify ordered pairs.

It's difficult to know. If there's any doubt, and if it is relatively easy to do so, you could include both answers. However, if you're clear about exactly what question you're asking and there is some ambiguity in their question I shouldn't think it would matter too much. The only case where this would matter is if it was much more work to find the number of unordered pairs. If this were the case, I hope they would be more clear about what was expected.

By Arun Iyer on Tuesday, October 08, 2002 - 07:22 pm:

Ah!!!!
now i understood..:)

DAN,
thanks for all the help!!!:)

love arun