Thread: Urgent.. Set Theory!!!

YOUR QUESTION :

How many relations are there on {1,2,3,4,5}?

How many equivalence relations are there on {1,2,3}?

How many reflexive relations are there on {1,2,3,4,5}?

How many functions are there from {1,2,3} to {a,b,c,d}?

How many surjective functions are there from {1,2,3,4,5} to {a,b,c,d,e}?

How many bijective functions are there from {1,2,3,4} to {a,b,c}?

I know the definitions, but somehow I cant seem to apply
them.. can someone please help with the answers... it will
serve as an example... THANKYOUUU!
zee

List the definitions because
1. I don't know.
2. they may help you.

Originally Posted by zee

YOUR QUESTION :

How many relations are there on {1,2,3,4,5}?

[...]

I know the definitions, but somehow I cant seem to apply
them.. can someone please help with the answers... it will
serve as an example... THANKYOUUU!
zee

A relation on a set X is a subset of X x X.
A finite set A has 2^|A| subsets, where |A| is the number of elements in A.

In this case: X = 1,2,3,4,5}, A = X x X. So you need to determine |A| = |X x X|, the number of pairs (i,j) with i,j in {1,...,5}.

so is it correct to say that the number of relations would be
2^5 (5 elements?)

or is it 2 to the (literal number of pairs??)
So from {1,2,3,4,5} there is
{1},{2},{3},{4},{5},{1,1},{2,2},{3,3},{4,4},{5,5}
=2^10

And FYI, Im studying for a final exam and trying to get
practice with all possible questions!

Thanx for ur help!

Originally Posted by zee

so is it correct to say that the number of relations would be
2^5 (5 elements?)

or is it 2 to the (literal number of pairs??)

The second option. The number of pairs is 25 in this case.

1) A relation on a set is simply any subset of the cartesian product of that set (you may be thinking only of functions, a specific type of relation).

The cartesian product of {1,2,3,4,5} has 5*5 = 25 elements. the total number of subsets of a 25 element set is 2^25. Thus there are 2^25 possible relations.

2) an equivalence relation on the set {1,2,3 } always gives rise to a partition of the set. Thus, how many partitions are there?

{ {1,2,3} } { {1}, {2,3} } { {1,2}, {3} } { {1,3}, {2} }
{ {1}, {2}, {3} }

Thus there are 5 equivalence relations on {1,2,3}.

3) A reflexive relation just means that for every element a of the set, (a,a) is part of the relation. For the set {1,2,3,4,5}, there are 5 such pairs. The reflexive relations of {1,2,3,4,5} then can be put into bijection with the subsets of the Cartesian product of {1,2,3,4,5} minus the elements {(1,1), (2,2), ...., (5,5) }. This is a set with 5*5 - 5 = 20 elements. Thus the answer is 2^20.

4) From {1,2,3} to {a,b,c,d}, there are 4^3 = 64 possible functions (each of the three elements 1,2,3 can be assigned any one of the elements a,b,c,d).

5) This is the same as the question of how many bijections are there from {1,2,3,4,5} to itself. But a bijection between a set and itself is just a permuation of that set. Thus there are 5! = 120 possible bijections.

6) None. To sets of different cardinality (size) cannot, by definition, have a bijection between them.

Write back if this helped.