Reflexive and Symmetric Relations


by fuzzywolf
Tags: reflexive, relations, symmetric
fuzzywolf
fuzzywolf is offline
#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
SensaBubble: It's a bubble, but not as we know it (w/ video)
The hemihelix: Scientists discover a new shape using rubber bands (w/ video)
Microbes provide insights into evolution of human language
Dick
Dick is online now
#2
Oct1-10, 10:58 PM
Sci Advisor
HW Helper
Thanks
P: 25,176
R = {(1,1), (1,5), (5,1)} isn't reflexive because (5,5) isn't in it. Nor is (2,2). Keep thinking.
fuzzywolf
fuzzywolf is offline
#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
Dick is online now
#4
Oct2-10, 08:21 AM
Sci Advisor
HW Helper
Thanks
P: 25,176

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
fuzzywolf is offline
#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
Dick is online now
#6
Oct2-10, 12:24 PM
Sci Advisor
HW Helper
Thanks
P: 25,176
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
Ghosh is offline
#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