# Reflexive and Symmetric Relations

by fuzzywolf
Tags: reflexive, relations, symmetric
 P: 15 1. The problem statement, all variables and given/known data The set A has 5 elements. 1. How many relations exist on A? 2. How many of those relations are symmetric and reflexive? 3. The attempt at a solution Some of the parts of this question are harder than others. 1. By simple counting, there are 2^(5^2) or 2^25 total relations. Some 33 million 2. This is the one I'm having the most trouble with, and I think its a confusion with definition. A relation is symmetric if it maps an element back onto itself. Since there are 5 elements, there are 2^5 relations, just by this consideration, which are reflexive. They are also symmetric, by virtue of mapping only onto themselves. My question is, is a relation still considered reflexive if it maps onto itself AND another element? For example, if I index the elements of A 1 through 5, is: R = {(1,1), (5,5), (1,5), (5,1)} a reflexive relation?
 Sci Advisor HW Helper Thanks P: 25,235 R = {(1,1), (1,5), (5,1)} isn't reflexive because (5,5) isn't in it. Nor is (2,2). Keep thinking.
 P: 15 I realized my mistake right after I posted. OP now shows {(1,1),(5,5),(1,5),(5,1)} Here's my new thought. If I let x be the subset of A that I am using for any given relation, then I have |x| identical mappings + some pairs of symmetric maps. If |x| = 1, then I just have 5 possible relations, one for each element. If |x| = 2, then I have 5 choose 2 ways of picking the elements, and one possible pair of reflexive relations. If |x| = 3, then I have 5 choose 3 ways of picking the elements and 6 possible pairs of reflexive relations. Then I add up the number of possible relations for all possible |x|?
HW Helper
Thanks
P: 25,235
Reflexive and Symmetric Relations

 Quote by fuzzywolf I realized my mistake right after I posted. OP now shows {(1,1),(5,5),(1,5),(5,1)} Here's my new thought. If I let x be the subset of A that I am using for any given relation, then I have |x| identical mappings + some pairs of symmetric maps. If |x| = 1, then I just have 5 possible relations, one for each element. If |x| = 2, then I have 5 choose 2 ways of picking the elements, and one possible pair of reflexive relations. If |x| = 3, then I have 5 choose 3 ways of picking the elements and 6 possible pairs of reflexive relations. Then I add up the number of possible relations for all possible |x|?
Sounds complicated. Approach it like you did 1. There were 5^2 things to choose from so 2^(25) ways to make a subset. You have to choose all of the (i,i) pairs. Ok, so think about the (i,j) pairs with i<j. If you choose (i,j) you have to also choose (j,i), so you don't have any independent choice for them. But you can choose any subset of the pairs (i,j) i<j, right? How may pairs is that and how many subsets? (I visualize it as symmetrically choosing squares in a 5x5 grid, if that's any help).
 P: 15 That does make sense. If you think of the relation space as a 5x5 matrix, then you can choose a diagonal element or any element in the strictly lower triangular part. Thank you!