The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+9 votes

Let $A$ be a set of $n(>0)$ elements. Let $N_r$ be the number of binary relations on $A$ and let $N_f$ be the number of functions from $A$ to $A$

  1. Give the expression for $N_r,$ in terms of $n.$
  2. Give the expression for $N_f,$ terms of $n.$
  3. Which is larger for all possible $n,N_r$ or $N_f$
asked in Set Theory & Algebra by Veteran (59.7k points)
retagged by | 563 views

2 Answers

+22 votes
Best answer

A. Consider a $2D$ matrix of $n\times n$ size where each dimension represent the $n$ elements of $A.$ So, we get $n^2$ elements where each one can be viewed as an ordered pair $(i,j), 1\leq i,j \leq n.$ Now if we consider a set with these $n^2$ elements, any subset of it will be a binary relation from $A$ to $A$.

So, no. of binary relations, $N_r = 2^{n^2}$

For a function from a set of $n$ elements to a set of $m$ elements we have $m$ choice for each of the $n$ elements of the domain. Thus we get $m^n$ possibilities. Here, $m = n.$ So,

No. of functions, $N_f = n^n$

Now, number of functions must be smaller than the number of relations because every function is also a relation. We can prove this formally as follows:

$\lim_{n\to \infty} \dfrac{2^{n^2}}{n^n} $

$\dfrac{\infty}{\infty} \text{ form}.$ So, applying L'Hopital's rule (Limit remains same after taking derivative of both numerator and denominator)

$= \lim_{n \to \infty} \dfrac{2n.\log 2. 2^{n^2}}{nn^{n-1}}$

We can continue like this applying L'Hopital's rule and we should eventually get $1$ in the denominator (as after each derivation power of $n$ decreases by $1$) which gives the limit value as $\infty.$ So, $2^{n^2}$ is faster growing than $n^n.$

So, for sufficiently large $n,$ $N_r > N_f$

answered by Veteran (55.6k points)
edited by
Here, no need to do further calculation which one is greater. A function is a subset of relation.

Every function is a relation but every relation is not a function.So, clearly relation size is greater than that of number of function.

Moreover,$N_r=2^{n^2}$ is an exponential function and $N_f=n^n$ a polynomial. Exponentials grow faster than polynomials.

(as after each derivation power of n decreases by 1)

Where is this happening?

+2 votes

A.  Number of binary relations on set A = Nr = 2^(n^2)

B.  Number of functions on set A = Nf = n^n

C.  No of relation > No of function( Nr >Nf) ,because function is restricted version of relation so it is obvious.By the way, we can check by taking log at both sides.

answered by Loyal (7.1k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,200 questions
49,670 answers
65,819 users