Combinatorics: Starting Posets/Relations

[blinktx411]

Homework Statement

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?

Homework Equations

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!

 

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

 

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

 

[HallsofIvy]

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