Register to reply 
Reflexive and Symmetric Relations 
Share this thread: 
#1
Oct110, 10:47 PM

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? 


#2
Oct110, 10:58 PM

Sci Advisor
HW Helper
Thanks
P: 25,243

R = {(1,1), (1,5), (5,1)} isn't reflexive because (5,5) isn't in it. Nor is (2,2). Keep thinking.



#3
Oct110, 11:14 PM

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? 


#4
Oct210, 08:21 AM

Sci Advisor
HW Helper
Thanks
P: 25,243

Reflexive and Symmetric Relations



#5
Oct210, 12:02 PM

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! 


#6
Oct210, 12:24 PM

Sci Advisor
HW Helper
Thanks
P: 25,243




#7
Oct1012, 09:26 AM

P: 1

Imagine a matrix of n rows and n columns.
(1,1) (1,2) (1,3) .......... (1,n) (2,1) (2,2) (2,3) .......... (2,n) (3,1) (3,2) (3,3) .......... (3,n)    (n1,1) .......................(n1,n1) (n1, n) (n ,1) ...........................(n ,n1) (n , n) Every element in the matrix is a possible candidate in a binary relation. However for a binary relation to be Reflexive all the n diagonal elements must be there. The rest of the n^2  n may or may not occur in the binary relation, for it to be reflexive. So, the presence or absence of x elements creates 2^x possibilities. Similarly, the presence or absence of n^2  n elements creates 2^(n^2  n ) possibilities, of reflexive relations. Aniruddha Ghosh Jadavpur University India 


Register to reply 
Related Discussions  
A symmetric, transitive relation on a set that is not reflexive  Set Theory, Logic, Probability, Statistics  4  
Symmetric relations  Precalculus Mathematics Homework  5  
A little help with symmetric, reflexive and transitive  Calculus & Beyond Homework  1  
Reflexive, Symmetric, or Transitive  Calculus & Beyond Homework  8  
Matrix relation of sets. symmetric, antisymmetric,reflexive,transitive  Precalculus Mathematics Homework  3 