Reflexive and Symmetric Relations

In summary, there are 2^(25) total relations on the set A with 5 elements. Of those, there are 2^(n^2 - n) or 2^(20) relations that are reflexive and symmetric.
  • #1
fuzzywolf
15
0

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?
 
Physics news on Phys.org
  • #2
R = {(1,1), (1,5), (5,1)} isn't reflexive because (5,5) isn't in it. Nor is (2,2). Keep thinking.
 
  • #3
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
fuzzywolf said:
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).
 
  • #5
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
fuzzywolf said:
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.
 
  • #7
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
 
Last edited:

FAQ: Reflexive and Symmetric Relations

1. What is a reflexive relation?

A reflexive relation is a type of mathematical relationship between two elements where every element in the set is related to itself. In other words, if (a, b) is a reflexive relation, then a is related to a for all values of a in the set.

2. What is a symmetric relation?

A symmetric relation is a type of mathematical relationship between two elements where for every pair of elements (a, b), if a is related to b, then b is also related to a. In other words, the order of the elements in the relation does not matter.

3. How can you determine if a relation is reflexive?

To determine if a relation is reflexive, you can check if every element in the set is related to itself. This can be done by examining the ordered pairs in the relation and verifying that the first and second elements are the same for each pair.

4. How can you determine if a relation is symmetric?

To determine if a relation is symmetric, you can check if for every pair of elements (a, b), if a is related to b, then b is also related to a. This can be done by examining the ordered pairs in the relation and checking if the pairs are symmetrical.

5. What is the difference between a reflexive and symmetric relation?

The main difference between a reflexive and symmetric relation is that a reflexive relation requires every element to be related to itself, while a symmetric relation only requires that for every pair of elements, if one element is related to the other, then the other element is also related to the first.

Back
Top