Let A be a set with |A|  n, and let  be a relation on A that is antisymmetric.

Question

Let A be a set with |A|  n, and let  be a relation on A that is antisymmetric. What is the maximum value for ||? How many antisymmetric relations can have this size?

Explanation / Answer

this will solve your problem If the relation is symmetric, we can think of it slightly differently. Let P2(R) be all subsets of R with 2 elements, and P1(R) be all the subsets of R with a single element. Then all symmetric relations will correspond exactly to the subsets of P2(R) U P1(R). Notice that P2(R) is exactly like RxR, except the pairs aren't ordered, and it only considers pairs with distinct x and y (the pairs where they aren't distinct are covered by P1(R)). How many elements does P2(R) have in it? Well, we are looking for all pairs of the form: {x, y} where x and y are distinct and in R. They correspond to an unordered selection of 2 objects from n objects, giving us: n C 2 = (1/2)n(n - 1) How many elements of P1(R) are there? Well, clearly, there will be n elements. So, the total number of elements in P2(R) U P1(R) will be: (1/2)n(n - 1) + n = (1/2)n[(n - 1) + 2] = (1/2)n(n + 1) And, we want the number of subsets of this, so we get: 2^[(1/2)n(n + 1)] As for all relations that are antisymmetric, that's a bit more tricky. I'll have to think about that one. The relations that are neither reflexive nor irreflexive are not too difficult to count. Assuming that n > 0, it's impossible for a relation to be simultaneously reflexive and irreflexive, so if we count the number of reflexive relations, and the number of irreflexive relations, then we will not have counted the same relation twice, and we can just subtract this number from 2^(n^2). In both the reflexive and irreflexive cases, essentially membership in the relation is decided for all pairs of the form {x, x}. This leaves n^2 - n pairs to decide, giving us, in each case: 2^(n^2 - n) choices of relation. That is the number of reflexive relations, and also the number of irreflexive relations. The number of relations that are either reflexive or irreflexive will be the sum: 2^(n^2 - n) + 2^(n^2 - n) = 2^(n^2 - n + 1) If we subtract this from the total number of relations, 2^(n^2), then we get the number of relations that are neither reflexive or irreflexive: 2^(n^2) - 2^(n^2 - n + 1) Hope that helps! EDIT: (Fixed a small mistake previously) OK, I've just thought of a way to deal with the antisymmetric case. Again, we will consider P2(R) U P1(R). We can choose freely which pairs of the form (x, x) we want in our relation, so we can choose freely our subset of P1(R), giving us 2^n possible contributions from P1(R). As for our contribution from P2(R), for each {x, y} pair in P2(R), we must have exactly one of the following three possibilities: 1) Neither (x, y) nor (y, x) is in our relation. 2) Only (x, y) is in our relation. 3) Only (y, x) is in our relation. Each choice for each {x, y} can be made independently of the other choices chosen previously. Also, making two distinct choices will result in two distinct relations, i.e. we are not counting anything twice. Therefore, the number of contributions from P2(R) will be: 3^(n C 2) = 3^[(1/2)n(n - 1)] The contributions of P2(R) and P1(R) are independent, so the total number of antisymmetric relations will be: 2^n * 3^[(1/2)n(n - 1)]

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.