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.