# Homework Help: Combinatorics: Starting Posets/Relations

1. Jun 1, 2009

1. The problem statement, all variables and given/known data

We say that a relation $$R$$ on a set X is symmetric if $$(x, y) \in R$$ implies $$(y, x) \in R$$ for all $$x, y \in X.$$ If $$X = \{a, b, c, d, e, f \}$$, how many symmetric relations are there on $$X$$? How many of these are reflexive?

2. Relevant equations

3. The attempt at a solution

At this point, I understand that there are $$2^6$$ subsets of X. I don't understand how to count the number of relations that are symmetric though. Also, I would have thought that since there are $$2^6$$ subsets, that there would be $$2^6$$ reflexive relations, but I know the answer to that question to be $$2^{15}$$. All help is appreciated!

2. Jun 1, 2009

### matt grime

Try with a smaller example, like 3 elements {a,b,c} to begin with - or just try writing out a few symmetric relations and trying to see what needs to be true about them.

You notion of 2^6 implies that a relation (of some type) is purely defined by being a subset - if that were true then it wouldn't be a very interesting property.

3. Jun 1, 2009

### JCVD

You mean to say that there are 2^15 relations on X that are both reflexive and symmetric (there are 2^30 reflexive relations). If you want to think about relations as sets, you should be looking at sets of ordered pairs whose entries come from X.

4. Jun 2, 2009

### HallsofIvy

A relation on X is NOT a subset of X. It is a subset of the Cartesian product of X with iteself.