Results 1 to 6 of 6
Like Tree2Thanks
  • 1 Post By Plato
  • 1 Post By Plato

Thread: Number of relations

  1. #1
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    238
    Thanks
    17

    Number of relations

    Hey,
    How many full relations are there on the set {1,...n}?
    A full relations is a relation R such that for every i in {1,2,...n} there exists a j in {1,...n} such that (i,j) belongs to R.
    Thank's in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,329
    Thanks
    3220
    Awards
    1

    Re: Number of relations

    Quote Originally Posted by hedi View Post
    How many full relations are there on the set {1,...n}?
    A full relations is a relation R such that for every i in {1,2,...n} there exists a j in {1,...n} such that (i,j) belongs to R.
    By that definition a full relation is one where its domain is the set and its codomain is nonempty.
    Say $N=\{1,2,\cdots, n\}$ so $\mathcal{R}=N\times B$ where $B\in\mathscr{P}(N)\setminus\emptyset$. [$\mathscr{P}(N)$ being the powerset of $N$]
    Thus you need to know how many nonempty subsets $N$ has.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    238
    Thanks
    17

    Re: Number of relations

    This is not true.For example for n=3 R={(1,1),(1,2),(2,1),(2,3),(3,3)} is full relation on {1,2,3} but there is not such B.Rather, it is the union of {i}xAi for Ai in P(N)/{empty set},i=1,...,n.How many element are in this union?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    238
    Thanks
    17

    Re: Number of relations

    I suppose it is the number of(A1,A2,...,An)'s such that Ai belong to P([n])/{empty set}, that is (2^n-1)^n
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,329
    Thanks
    3220
    Awards
    1

    Re: Number of relations

    Quote Originally Posted by hedi View Post
    This is not true.For example for n=3 R={(1,1),(1,2),(2,1),(2,3),(3,3)} is full relation on {1,2,3} but there is not such B.Rather, it is the union of {i}xAi for Ai in P(N)/{empty set},i=1,...,n.How many element are in this union?
    Thank you for the correction. Clearly I misunderstood the definition of a full relation. (BTW i have never seen this term before.)
    So if this is your example: $\{(1,1),(1,2),(2,1),(2,3),(3,3)\}=[\{1\}\times\{1,2\}] \cup[\{2\}\times \{2,3\}] \cup[\{3\}\times\{3\}]$ Do you agree?
    If you do then in this example $\mathcal{R}=[\{1\}\times A] \cup[\{2\}\times B] \cup[\{3\}\times C]$, where each of $A,~B,~\&~C $ is a nonempty subset of $\{1,2,3\}$
    Then that is a complete listing of all possible of what your course is calling a full relation.
    I make for $n=3$ the total full relations to be $(2^3-1)^3$.
    Can you explain HOW? WHY?
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    238
    Thanks
    17

    Re: Number of relations

    yes,i wrote this formula above for general n,you can see.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. number of relations between two sets
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Jan 24th 2018, 09:43 AM
  2. Number of transitive relations
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Nov 18th 2014, 03:26 AM
  3. Number of relations?
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Apr 28th 2009, 02:04 PM
  4. Number relations
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: Oct 31st 2008, 05:46 AM
  5. Number of relations
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Sep 16th 2008, 05:52 AM

/mathhelpforum @mathhelpforum