Reflexive and Symmetric Relations

[fuzzywolf]

Homework Statement

The set A has 5 elements.
1. How many relations exist on A?
2. How many of those relations are symmetric and reflexive?

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?

 

[Dick]

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

 

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

 

[Dick]

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

 

[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!

 

[Dick]

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!

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.

 

[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
Jadavpur University
India