Results 1 to 6 of 6

Math Help - Relations

  1. #1
    Newbie
    Joined
    Dec 2009
    Posts
    4

    Relations

    Let A be the set with n elements. How many elements does the set of relations on A have? (How to calculate tihs?)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    A relation R on A is a subset of the carthesian product of A with itself, that is: R\subset A\times A. How many elements does \mathcal{P}(A\times A) have?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2009
    Posts
    4
    I am not sure you're right.
    We don't talk about sets but about ordered pairs:

    now I have to found all relation: I think that I have to do something like this

    R_1={(a,b)} there are n*n different options
    R_2={(a,b),(c,d)} I think there are (n*n)*((n-1)*n + (n-1)) = n^2*(n-1)*(n+1)
    .
    .
    .

    (this is something about combinatorics-I think so)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,639
    Thanks
    1592
    Awards
    1
    Quote Originally Posted by tinaa View Post
    I am not sure you're right.
    We don't talk about sets but about ordered pairs:
    The first reply is absolutely correct.
    As for you statement “We don't talk about sets but about ordered pairs” that is incorrect.
    Almost all of basic ideas in mathematics are about sets.
    An ordered pair is a set of sets.
    A relation on a set is a subset of the cross product of the set with itself as was stated.

    If we have a finite set A then the number of relations on A is 2^{|A|^2}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    What you are basically doing is trying to find all R\subset A\times A.


    you start out by looking for all R_1\subset A\times A then R_2 \subset A\times A etc...

    So you're trying to find all elements of \mathcal{P}(A\times A)

    A\times A is the set of all ordered pairs  (a,b) wich has n^2 elements. Thus \mathcal{P}(A\times A) has 2^{n^2} elements.

    (edit: Sorry, I see Plato allready responded)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Dec 2009
    Posts
    4
    thank you
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Relations and Functions - Inverse Relations Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 13th 2011, 12:20 PM
  2. Replies: 1
    Last Post: September 19th 2011, 01:09 PM
  3. [SOLVED] Relations on A
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: November 21st 2010, 11:25 AM
  4. Relations in a set
    Posted in the Algebra Forum
    Replies: 3
    Last Post: September 5th 2010, 10:03 PM
  5. relations help (3)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 18th 2010, 04:49 AM

Search Tags


/mathhelpforum @mathhelpforum