Results 1 to 6 of 6

Math Help - Urgent.. Set Theory!!!

  1. #1
    zee
    zee is offline
    Newbie
    Joined
    May 2005
    Posts
    17

    Unhappy 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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Apr 2005
    Posts
    103
    List the definitions because
    1. I don't know.
    2. they may help you.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    hpe
    hpe is offline
    Member hpe's Avatar
    Joined
    Apr 2005
    Posts
    158
    Quote 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}.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    zee
    zee is offline
    Newbie
    Joined
    May 2005
    Posts
    17

    relations

    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!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    hpe
    hpe is offline
    Member hpe's Avatar
    Joined
    Apr 2005
    Posts
    158
    Quote 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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Nov 2005
    Posts
    39
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Textbooks on Galois Theory and Algebraic Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: July 8th 2011, 07:09 PM
  2. Group Theory - Sylow Theory and simple groups
    Posted in the Advanced Algebra Forum
    Replies: 16
    Last Post: May 16th 2009, 12:10 PM
  3. Number Theory-GCD and Divisibility URGENT
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 8th 2008, 11:52 AM
  4. Urgent: Measure theory
    Posted in the Calculus Forum
    Replies: 0
    Last Post: October 10th 2006, 04:23 AM
  5. [SOLVED] Urgent: Messurable set theory
    Posted in the Calculus Forum
    Replies: 0
    Last Post: October 8th 2006, 02:30 PM

Search Tags


/mathhelpforum @mathhelpforum