- #1

- 21

- 0

## 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?