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

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