Combinatorics: Starting Posets/Relations

[blinktx411]

Homework Statement

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

Homework Equations

The Attempt at a Solution

At this point, I understand that there are [tex] 2^6 [/tex] 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 [tex] 2^6 [/tex] subsets, that there would be [tex] 2^6 [/tex] reflexive relations, but I know the answer to that question to be [tex] 2^{15} [/tex]. 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.