# Reflexive and Symmetric Relations

1. Oct 1, 2010

### fuzzywolf

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. Oct 1, 2010

### Dick

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

3. Oct 1, 2010

### 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|?

4. Oct 2, 2010

### Dick

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).

5. Oct 2, 2010

### fuzzywolf

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. Oct 2, 2010

### Dick

Sure. Except you HAVE to pick the diagonal elements if you want it to be reflexive, right? The only elements you have a choice about are in the lower triangular part.

7. Oct 10, 2012

### Ghosh

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)
-
-
-
(n-1,1) .......................(n-1,n-1) (n-1, n)
(n ,1) ...........................(n ,n-1) (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