Sets

**Ideasman** · April 13th 2008, 07:59 PM

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

**Jhevon** · April 13th 2008, 08:13 PM

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?

**Ideasman** · April 13th 2008, 10:39 PM

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?)

**Jhevon** · April 13th 2008, 11:42 PM

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?

**Plato** · April 14th 2008, 04:17 AM

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}$ .

Thread: Sets

LinkBack

Thread Tools

Display

Sets

Similar Math Help Forum Discussions

Open sets and sets of interior points

Metric spaces, open sets, and closed sets

3 sets of 5 pieces of data. Compare and contrast the three sets. Comment briefly on t

Approximation of borel sets from the top with closed sets.

how to show these sets are 95% confidence sets

Search Tags