1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Math proof about relations

  1. May 11, 2016 #1
    1. The problem statement, all variables and given/known data
    Let X = {1, 2, 3, 4, 5, 6}. Determine the number of relations on X which are reflexive and anti-symmetric

    2. Relevant equations

    3. The attempt at a solution
    This problem looks a little bit hard.

    consider R={(x,x),.... }
    If there is just one pair in the relation in the form (x,x), there is no way we can come up with something that is reflexive and anti-symmetric hence we are just allowed to include pairs that start with x. If add another pair that starts with x then automatically the relation becomes transitive. There is no way to destroy the transitivity hence for the same reason we are just allowed to add pairs that start with x.

    consider R={(x,x),(y,y),.......}
    If this is the case then we can come up with something like this R={(1,1),(2,2),(1,2),(2,3)}. Here the relation is reflexive and antisymmetric. The pattern that I see here is when we have two pairs in R in the form (x,x), if we add another pair that starts with x, we have to find a way to destroy the transitivity by adding another pair. This is too hard. How can you count that by using a pattern?
  2. jcsd
  3. May 12, 2016 #2


    User Avatar
    Science Advisor
    Homework Helper

    Transitivity is irrelevant to this exercise.

    For example, the following relation is reflexive and anti-symmetric:
    R = {(1,1), (2,2),(3,3), (4,4), (5,5), (6,6), (1,2), (2,3)}

    This relation is reflexive, but not anti-symmetric:
    R' = {(1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (1,2), (2,3), (3,2)}

    To determine how many reflexive and anti-symmetric relations there are on X, the first task is to determine what can happen with a pair.
    Say {1,2}. We can form two tuples: (1,2), (2,1). How many of these can be in an anti-symmetric relation? How many possibilities does that give?
    Once you have that, how many pairs do you have to consider?
  4. May 12, 2016 #3
    (1,2),(2,1) can't be in the same relation because (1,1) and (2,2) have to be as well in the relation and this creates transitivity. That's why I am saying that we have add other pairs to destroy the transitivity.
  5. May 12, 2016 #4


    User Avatar
    Science Advisor
    Homework Helper

    (1,2),(2,1) can't be in the relation because you are asked to count reflexive and anti-symmetric relations. Transitivity has nothing to do with it. Transitivity plays no role in this exercise.

    The reflexive part of the question is easy. A relation is reflexive if it includes (1,1), (2,2), ..., (6,6). Not much to count here.
    The anti-symmetric part is a little more difficult. That's why I suggested you look at a pair, {1, 2}, and see what the possibilities are for including (1,2) and/or (2,1) in a relation, while keeping the relation anti-symmetric.
    Once that is done, determine the number of available pairs.
  6. May 13, 2016 #5
    I don't know if I am misreading the question but I think that we have to count the relations
    I got the problem already. I had a very big misconception about reflexivity. I thought that for all a in a set A, if a R (to some element) then aRa, so the relation is reflexive. We have to include every possible (a,a) in the set A, so it's reflexive. At the end I came up with 3^(n choose 2) is the right answer.
  7. May 13, 2016 #6


    User Avatar
    Science Advisor
    Homework Helper

    It would have been nice for future readers of the thread to indicate how you got that result.

    For a pair of elements, say {1,2}, there are three possibilities that keep the relation anti-symmetric.
    1: (1,2) ∈ R and (2,1) ∉ R
    2: (1,2) ∉ R and (2,1) ∈ R
    3: (1,2) ∉ R and (2,1) ∉ R

    There are ##\binom {6}{2}=15## pairs available.
    There is only one way to make the relation reflexive, that is include all of (1,1), (2,2), ..., (6,6).

    So the total number of reflexive and anti-symmetric relations is 315.
  8. May 13, 2016 #7
    Ok, I will post my solution in future threads.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted