Thread: Sets

1. Sets

Given $A$ is a set with 6 elements,

a.) Determine the number of relations on $A$ there are

b.) Determine the number of symmetric relations on $A$ there are

c.) Determine the number of reflexive relations on $A$ there are

2. Originally Posted by Ideasman
Given $A$ is a set with 6 elements,

a.) Determine the number of relations on $A$ there are
well, we have 6 elements in A. How many choices are there to map the first element to? After that, how many choices are there to map the second element to...continue this procedure. The product of all the choices is what you seek.

b.) Determine the number of symmetric relations on $A$ there are
are you aware of what symmetric means?

here is a symmetric mapping. try to untangle it's secrets:

let the elements of A be a,b,c,d,e,f, the mapping defined by:

a --> b

b --> a

c --> d

d --> c

e --> f

f --> e

is symmetric

c.) Determine the number of reflexive relations on $A$ there are
this is only the identity, right?

3. Originally Posted by Jhevon
well, we have 6 elements in A. How many choices are there to map the first element to? After that, how many choices are there to map the second element to...continue this procedure. The product of all the choices is what you seek.

are you aware of what symmetric means?

here is a symmetric mapping. try to untangle it's secrets:

let the elements of A be a,b,c,d,e,f, the mapping defined by:

a --> b

b --> a

c --> d

d --> c

e --> f

f --> e

is symmetric

this is only the identity, right?
For the first one,

If I have 6 elements, say a b c d e f, then wouldn't it be something like:

a -> b, c, d, e, f
b -> a, c, d, e, f
c -> a, b, d, e, f
d -> a, b, c, e, f
e -> a, b, c, d, f
f -> a, b, c, d, e

So you're saying that there'd be 5^5 relations on A?

For b, I don't quite understand how there's only 6 symmetrical mappings.

Why can't a -> f and then f -> a, etc.

And for c, what do you mean by just the identity? Itself? So a -> a, b -> b, etc. (so an onto mapping?)

4. Originally Posted by Ideasman
For the first one,

If I have 6 elements, say a b c d e f, then wouldn't it be something like:

a -> b, c, d, e, f
b -> a, c, d, e, f
c -> a, b, d, e, f
d -> a, b, c, e, f
e -> a, b, c, d, f
f -> a, b, c, d, e

So you're saying that there'd be 5^5 relations on A?
no.

there are 6 elements in A, each of which have 6 choices of what to map to. Let A and B be sets, the number of mappings from the set A to the set B is $|B|^{|A|}$

(it is possible for an element to map to itself)

For b, I don't quite understand how there's only 6 symmetrical mappings.

Why can't a -> f and then f -> a, etc.
i posted a SINGLE mapping. please look up what a mapping is, for you to think that was 6 mappings is really bad. I merely gave you ONE of the possible mappings so that you could see some sort of pattern. For example, note that when we made the choice a --> b, we automatically made the choice b --> a, there was no choice for what b could map to, it had to be a for the mapping to be symmetric. so that means, when we get to the element c, it only has 4 choices of what to map to, since a and b are taken. continue with this logic and generalize to complete the problem.

And for c, what do you mean by just the identity? Itself? So a -> a, b -> b, etc. (so an onto mapping?)
reflexive means, every element maps to itself. can you think of any other map besides the identity that does this?

5. Originally Posted by Ideasman
Given $A$ is a set with 6 elements,
a.) Determine the number of relations on $A$ there are
b.) Determine the number of symmetric relations on $A$ there are
c.) Determine the number of reflexive relations on $A$ there are
Recall that a relation no a set $A$ is simply a subset of $A \times A$. Because $\left| {A \times A} \right| = 36$ there are $2^{36}$ possible relations on $A$ (CAREFUL, some mathematicians will not allow an empty relation so you may have to subtract one from that.)

To answer part (b), think of a table that represents $A \times A$.
There are 21 pairs ‘on or below the diagonal’, call that set $L$ for the ‘lower triangle’. Now if $S \subseteq L$ then $S \cup S^{ - 1}$ is a symmetric relation on $A$ (again be careful of an empty set). So that gives $2^{21}$ possible symmetric relations.

Any reflexive relation on $A$ must contain the diagonal $\Delta _A$.
Then if $R \subseteq (A \times A)\backslash \Delta _A$ then $R \cup \Delta _A$ is a reflexive relation on $A$ or $2^{30}$.