Counting Reflexive and Anti-Symmetric Relations on a Finite Set

[Danielm]

Homework Statement

Let X = {1, 2, 3, 4, 5, 6}. Determine the number of relations on X which are reflexive and anti-symmetric

Homework Equations

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?

 

[Samy_A]

Homework Statement

Let X = {1, 2, 3, 4, 5, 6}. Determine the number of relations on X which are reflexive and anti-symmetric

Homework Equations

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?

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?

 

[Danielm]

Transitivity is irrelevant to this exercise.

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?

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

 

[Samy_A]

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

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

 

[Danielm]

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

I don't know if I am misreading the question but I think that we have to count the relations

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

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.

 

[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 3¹⁵.

 

[Danielm]

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 3¹⁵.

Ok, I will post my solution in future threads.