Set and Element RelationsDate: 03/23/2003 at 15:24:36 From: John Subject: Discrete Maths, specifically, relations On a set of n elements, how many relations are there that are - reflexive and antisymmetric? - irreflexive and symmetric? First, I'm having trouble understanding what relation is. When you say relation do you just mean a relationship between a and b? e.g. (a,b) belong to R and so do (e,f). Are (a,b) and (e,f) two relations or the same one (since they both belong to R)? Date: 03/24/2003 at 04:48:21 From: Doctor Jacques Subject: Re: Discrete Maths, specifically, relations Hi John, A relation on a set A is just a set of pairs of elements of A, i.e. expressions (x,y) where x and y are elements of A (possibly the same). Note that we consider ordered pairs - (x,y) is not the same as (y,x). An important point is that you can define relations quite arbitrarily. For every possible pair (x,y), you can decide whether or not you include it in the relation - a relation has nothing to do with properties or "logical relationships." A relation is just a set. In the case of a finite set A (say of n elements), there is a simple interpretation of a relation. We simply draw an n by n table, representing all the possible pairs (x,y), and we put a '*' in a cell when the corresponding pair belongs to the relation. For example, with the set A = {a,b,c}, we could have the following relation: | a | b | c | --+---+---+---+ a | | * | | b | | | | c | * | | * | --+---+---+---+ In this case, the relation contains the pairs (a,b), (c,a), and (c,c). In general, for every way you can put stars in the above table (including none at all), you get a relation on A. Before tackling your question, we will first examine a few simpler problems. All relations ------------- As a first exercise, let us count how many relations are possible on this set. We have 3*3 = 9 squares to fill. For each square, we can decide either to include it (put a '*' in it), or not. This makes two possibilities for each square. When you combine the nine squares, you have a total of 2^9 = 512 possibilities - there are 512 possible relations on A. In general, for a set of n elements, there are n^2 squares in the table, and 2^(n^2) possible relations. Reflexive relations ------------------- A relation is reflexive if it contains all the pairs (x,x) for every x in A. In the example above, this means that we must have '*' in all squares of the main diagonal - the smallest possible reflexive relation is: | a | b | c | --+---+---+---+ a | * | | | b | | * | | c | | | * | --+---+---+---+ In a reflexive relation, the three squares of the diagonal are fixed. You are still free to include or not any of the 6 remaining squares - this gives a total of 2^6 = 64 possibilities. For a set of n elements, you would have: 2^(n^2 - n) = 2^(n*(n-1)) possible reflexive relations. Irreflexive relations --------------------- A relation is irreflexive if it contains none of the pairs (x,x). This means that you must have no '*' on the main diagonal, and you are still free to do whatever you want with the other squares. The number of irreflexive relations is therefore the same as the number of reflexive relations. Note that "irreflexive" is not the same as "not reflexive." "Irreflexive" means you have no squares on the diagonal; "not reflexive" means you don't have all the squares on the diagonal. The very first example of this message is neither reflexive (since it does not contain (a,a)) nor irreflexive (since it contains (c,c)). Symmetric relations ------------------- A relation is symmetric if, whenever it contains the pair (x,y), it also contains the pair (y,x). This means that the table must be symmetric with respect to the main diagonal. For example, the following is a symmetric relation: | a | b | c | --+---+---+---+ a | | * | | b | * | | * | c | | * | * | --+---+---+---+ We note that the off-diagonal elements come in pairs: (a,b) and (b,a), (b,c) and (c,b). The diagonal elements are not taken into account. To build a symmetric relation, we can freely choose all the squares on and above the diagonal. There are n(n+1)/2 such squares, and two possibilities for each of them, so the number of symmetric relations is: 2^(n(n+1)/2) Antisymmetric relations ----------------------- A relation is antisymmetric if, whenever it contains both (x,y) and (y,x), x = y (x and y are the same element). This is equivalent to saying that, if x and y are distinct elements, you cannot have at the same time (x,y) and (y,x) in the relation. The following is an example of an antisymmetric relation: | a | b | c | --+---+---+---+ a | * | * | | b | | | | c | * | | * | --+---+---+---+ Note that the relation contains (a,b) but not (b,a), and (c,a) but not (a,c). Also, it contains neither of (b,c) and (c,b). Elements on the diagonal can be selected freely. How many antisymmetric relations are there? We count separately the possibilities for diagonal and off-diagonal elements. For diagonal elements, there are two possibilities for each of them, and there are n such elements. This gives 2^n possibilities. For each pair of off-diagonal elements x and y, we have three possibilities: (x,y) (y,x) ----------- out out in out out in since we cannot have both (x,y) and (y,x) in the relation. The number of pairs of distinct elements is "n choose 2": C(n,2) = n(n-1)/2 and, as there are three possibilities for each pair, we have 3^(n(n-1)/2) possibilities for off-diagonal elements. The total number of antisymmetric relations is thus: 2^n * 3^(n(n-1)/2) Note that "antisymmetric" is not the same as "not symmetric." For example, the following relation is neither symmetric nor antisymmetric: | a | b | c | --+---+---+---+ a | | * | * | b | | | | c | * | | * | --+---+---+---+ It is not symmetric, because it contains (a,b) but not (b,a), and it is not antisymmetric because it contains both (a,c) and (c,a). Now, let us come to your specific questions - they are, in fact, a little easier. Reflexive and antisymmetric --------------------------- If you compare that with the antisymmetric case, the only difference is that you must have '*' in all diagonal squares - you are no longer free to select them. You still have 3 possibilities for each of the n(n-1)/2 pairs of distinct elements (off-diagonal squares), and the the total number is therefore: 3^(n(n-1)/2) Irreflexive and symmetric ------------------------- In this case, you cannot include any square on the diagonal, and you can still select freely all the squares strictly above the diagonal; the squares below the diagonal will be their mirror images. You should now be able to compute the number of such relations using the technique outlined above. Does this help? Write back if you'd like to talk about this some more, or if you have any other questions. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ Date: 03/24/2003 at 07:55:11 From: John Subject: Discrete Maths, specifically, relations First of all, I just like to thank you for a speedy and helpful response. I find it very clear and helpful. Second, while we are on the subject of relations, I have another somewhat related question. Let S be the set of all character strings made from lower case letters. For two strings a and b we say that (a,b) belong to R if b=p.a.q where p and q are (possibly empty) character strings. Determine if the relation R is reflexive, symmetric, antisymmetric and transitive. The problem I'm having with this question is that most of the properties seem to hold if p and q are empty. For example, if p and q are empty then the statement b=p.a.q simply says that b = a which makes it reflexive, symmetric, (possible also antisymmetric) and transitive. Surely this can't be how I'm supposed to do this question. Please help. Date: 03/24/2003 at 09:05:37 From: Doctor Jacques Subject: Re: Discrete Maths, specifically, relations Hi John, Indeed, you cannot assume that p and q are empty. Given any strings a and b, you have to ask if there exist strings p and q that verify the relation - these strings will depend on the particular strings a and b. We must assume that S is the set of _finite_ strings over the given alphabet, because, if we allow infinite strings, we can no longer concatenate them. (What would it mean to write a string at the end of an infinite string?) It may be useful to try to see if the relation has an intuitive meaning. As I explained before, this will not always be the case (relations can be defined arbitrarily). However, in this case and in plain English, (a,b) in R means that a is a substring of b. You would not use that as such in a formal proof (well, maybe...), but it helps understanding what one is talking about. Is R reflexive? We must check that, for every string a, we can find strings p and q such that a = paq. Of course, we may take p and q as the empty string, and this shows that R is reflexive. R is not symmetric. To prove it, it is sufficient to exhibit two strings a and b such that (a,b) is in R and (b,a) is not. We can take, for example, a = x and b = xy. To check for transitivity, we assume that R contains (a,b) and (b,c). This means that there exist strings p,q,r,s such that: b = paq c = rbs and we must check that R contains (a,c), i.e. that there exist strings u and v such that c = uav This is indeed the case, as we can write c = rpaqs, and we can take u = rp and v = qs. Let us now check for antisymmetry. Each string has a length, i.e. an integer >= 0 and equal to the number of characters in the string. If R contains (a,b), we have b = paq. This shows that length(b) >= length(a). More precisely, we can write: L(b) = L(paq) = L(p) + L(a) + L(q) Assume that R contains (a,b) and (b,a), i.e. we have: b = paq a = rbs This shows that: L(b) = L(p) + L(a) + L(q) L(a) = L(r) + L(b) + L(s) and, adding these relations together: 0 = L(p) + L(q) + L(r) + L(s) and, as lengths are non-negative, this shows that all lengths are 0, i.e. p, q, r, s are empty strings, and a = b. To summarize, we have shown that, if R contains (a,b) and (b,a), then a = b; i.e. R is antisymmetric. Does this make sense? - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/