1. May 11, 2016

Danielm

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.

Approach:
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. May 12, 2016

Samy_A

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?

3. May 12, 2016

Danielm

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

4. May 12, 2016

Samy_A

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

5. May 13, 2016

Danielm

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.

6. May 13, 2016

Samy_A

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.

7. May 13, 2016

Danielm

Ok, I will post my solution in future threads.