Register to reply

Reflexive and Symmetric Relations

by fuzzywolf
Tags: reflexive, relations, symmetric
Share this thread:
fuzzywolf
#1
Oct1-10, 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?
Phys.Org News Partner Science news on Phys.org
Scientists develop 'electronic nose' for rapid detection of C. diff infection
Why plants in the office make us more productive
Tesla Motors dealing as states play factory poker
Dick
#2
Oct1-10, 10:58 PM
Sci Advisor
HW Helper
Thanks
P: 25,228
R = {(1,1), (1,5), (5,1)} isn't reflexive because (5,5) isn't in it. Nor is (2,2). Keep thinking.
fuzzywolf
#3
Oct1-10, 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|?

Dick
#4
Oct2-10, 08:21 AM
Sci Advisor
HW Helper
Thanks
P: 25,228
Reflexive and Symmetric Relations

Quote Quote by fuzzywolf View Post
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
#5
Oct2-10, 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!
Dick
#6
Oct2-10, 12:24 PM
Sci Advisor
HW Helper
Thanks
P: 25,228
Quote Quote by fuzzywolf View Post
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
#7
Oct10-12, 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)
-
-
-
(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


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