Properties of RelationDate: 05/28/2003 at 16:07:37 From: Idiot Subject: Properties of Relation What are reflexive, symmetric, anti-symmetric, and transitive relations? I do have some understanding about the definition of these relations. But I have this feeling I need to clarify few things. Reflexive Relation From the definition we know a relation is reflexive if every element of it is related with itself. For example, R={(1,1),(2,2), (3,3)}. But if we have a relation like R={} (the null set), how are we going to define reflexivity? Antisymmetric Relation We know if in a relation a pair (1,2) is present and a pair (2,1) is never present, then we call it antisymmetric. If, say, we have a relation such as R={(1,1),(2,2)}, is it antisymmetric? Is R={(1,1),(1,2)} antisymmetric? Symmetric Relation From the definition, we know that if (1,2) and (2,1) are both present, then it is symmetric. So if we have something like R={(1,1)}, is that symmetric? And is there any relation which is symmetric and antisymmetric both? Transitive Relation Again the definition says if (a,b) and (b,c) is present then (a,c) has to be present to make the relation transitive. Let's say we have a relation R={(1,2)}. The defintion says if (a,b) and (b,c) are both present, but here we can only safely say (a,b) is present. So is R still a transitive relation? I hope I didn't take too much of your time. Thank you in advance. Date: 05/29/2003 at 06:39:26 From: Doctor Jacques Subject: Re: Properties of Relation Hi, I think we should first clarify a few issues about mathematical logic, and, in particular, the meaning of statements related to the empty set. When we say "If P then Q", or "P -> Q" this simply means that P is false or Q is true (or both). This has some consequences that may appear surprising (until you get used to them). For example: "If 6 is prime, then 11 is negative" is a true statement, because the "If" part is false. A statement like P -> Q does not mean that there is any "logical relationship" between P and Q. Consider now what happens when we make statements about elements of a set. Let us say we have a statement: "For all x in S, P(x)" where P(x) is some statement about x. This is equivalent to saying: x is in S -> P(x) What does this mean if S happens to be the empty set? In that case, the left part ("x is in S") is false, and therefore the complete statement is true, (whatever P(x) may mean). We can say that any property is true when applied to the elements of the empty set. For example, in a universe without birds, both statements: "All birds are green" "All birds are red" are true, and this does not create a contradiction. Another way to see this is the following example. Assume that you have to inspect bags that may contain red and blue balls, and you want a procedure to decide whether or not all the balls in a given bag are red. This means that, given a bag B, you want to decide whether or not it is true that: "For all x in B, x is red" The procedure would be executed as follows: (1) if there are no more balls in the bag, exit and return TRUE (i.e. declare that the statement is true) (2) pick a ball from the bag (3) if the ball is not red, exit and return FALSE (4) otherwise, go back to step (1) Note that you must execute step (1) at the beginning, because step (2) is illegal if there are no more balls. Now, you can see that, if a particular bag is empty, the procedure will immediately terminate at step (1), and declare the statement true. This shows that this interpretation is consistent. On the other hand (we will not use that here), a statement like: "There exists x in S such that P(x)" means "(There exists x in S) AND (P(x))" and, if S happens to be the empty set, this statement is false (whatever P(x) may mean), because the first part of the AND statement is false. To sumarize: * "If P then Q", or "P -> Q" means "P is false or Q is true" (and nothing else). * The statement "For all x in S, P(x)" is always true when S is the empty set. * The statement "There exists x in S such that P(x)" is always false if S is the empty set. The latter two statements do not depend on the definition of P(x). Let us now go back to your questions. First, note that a relation may be pictured as a table. For example, in a set A = {a,b,c}, we can describe a particular relation as: | a | b | c | --+---+---+---+ a | * | | * | --+---+---+---+ b | * | | | --+---+---+---+ c | | | * | --+---+---+---+ This is the relation {(a,a), (a,c), (b,a), (c,c)} Reflexivity ----------- A relation R on a set A is reflexive if: "For all x in A, (x,x) belongs to R" which is equivalent to: "x is in A -> (x,x) is in R" or "(x is not in A) OR ((x,x) is in R)" By what we said above, we can immediately see that, if A is the empty set, _any_ relation is reflexive. (There is nothing to check, since the bag is empty). If now we have the empty relation R = {}: * If A is empty, the relation is reflexive, as said before. * If A is not empty, we can find an element x in A, and (x,x) is not in R. This means that "x is in A" is true, and "(x,x) is in R" is false, and the relation is not relfexive in this case. To summarize, the empty relation is reflexive if and only if the related set is empty. In the table representation, a relation is reflexive if it contains "*" on all the diagonal squares. Antisymmetry ------------ A relation R on a set A is antisymmetric if: "For all x,y in A, ((x <> y) AND ((x,y) in R)) -> ((y,x) not in R)" R is not antisymmetric if we can find x and y in A, with x <> y, such that (x,y) and (y,x) are both in R. As the property is of the form: "For all x,y in A, (...)" any relation is antisymmetric if A is the empty set. The empty relation {} is antisymmetric, because "(x,y) in R" is always false. Furthermore, if A contains only one element, the proposition "x <> y" is always false, and the relation is also always antisymmetric. In the example: {(1,1), (2,2)} the statement "x <> y AND (x,y in R)" is always false, so the relation is antisymmetric. In the example: R = {(1,1), (1,2)} the statement "x <> y AND (x,y in R)" is true only for (x,y) = (1,2), but, in that case, the statement "(y,x) not in R" is also true, so the relation is also antisymmetric. In the table representation, a relation is antisymmetric if it does not contain two "*" in symmetrical off-diagonal squares. Symmetry -------- A relation R on a set A is symmetric if: "For all x,y in A, ((x,y) in R) -> ((y,x) in R)" In the table representation, this means that the table is symmetrical with respect to the main diagonal. Note that we do not use the condition x <> y here, since, if x = y, the condition will always be satisfied. As before, as the statement is of the form "For all x,y in A, (...)", any relation on the empty set is symmetric. The empty relation {} on any set is symmetric, because "(x,y) in R" is always false. The relation {(1,1), (1,2)} is not symmetric, because it contains (1,2) but not (2,1). The relation {(1,1)} is symmetric, since (x,y) in R is only true for x = y = 1, and, in that case, we also have (y,x) in R (it's the same pair). Note that this relation is also antisymmetric, because the proposition x <> y AND (x,y) in R is always false, which means that ((x <> y) AND ((x,y) in R)) -> ((y,x) not in R) is always true. This shows that a relation can be symmetric and antisymmetric at the same time - this will be the case if there are no "*" in off-diagonal positions. This is independent of the fact that the relation is or is not reflexive. Transitivity ------------ A relation R on a set A is transitive if: "For all x,y,z in A, ((x,y) in R) AND ((y,z) in R)) -> (x,z) in R" Note that x,y,z need not be different. Once again, any relation on the empty set is transitive, as is the empty relation on any set, for the same reasons as above. In the relation {(1,2)}, we cannot find x,y,z such that R contains (x,y) and (y,z) but not (x,z), so the relation is transitive. Consider now the relation: R = {(1,2),(2,1)} In this case, if we let x = 1, y = 2, z = 1, we see that (x,y) = (1,2) is in R (y,z) = (2,1) is in R (x,z) = (1,1) is not in R and this shows that the relation is not transitive. General remarks --------------- It is often easier to approach those questions using the opposite properties. It is like in a trial - you are presumed innocent unless proven guilty. In this case, you can assume that a relation is reflexive (or symmetric, ...) unless you can prove that it is not. If you cannot prove that it is not reflexive, then it is reflexive (well, this does not mean "if you are unable to find a proof," but "if a counterexample does not exist"). To show that a relation is: * not reflexive, you must find an element x of A such that (x,x) is not in R * not antisymmetric, you must find distinct elements x and y of A such that both (x,y) and (y,x) are in R * not symmetric, you must find elements x and y of A such that R contains (x,y) but not (y,x) * not transitive, you must find elements x,y,z of A (not necessarily distinct) such that R contains (x,y) and (y,z) but not (x,z) In any case, if no such elements exist, the relation has the corresponding property. 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/ |
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/