Log In
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
15 votes

The number of binary relations on a set with $n$ elements is:

  1. $n^2$

  2. $2^n$

  3. $2^{n^2}$

  4. None of the above

in Set Theory & Algebra
retagged by

Same question was asked in 1987, see below :-

1 Answer

21 votes
Best answer
Answer: $C$

In a binary relation two elements are chosen from the set. So, with $n$ elements $n^2$ pairings are possible. Now, a relation can be any subset of these $n^2$ pairings and thus we get $2^{n^2}$ binary relations.

edited by
@shaik could you pls explain more
Think of the boolean matrix of the relation, where an element is related to another element if the matrix entry for that pair is 1. If unrelated, 0.

There are $n^2$ entries in this matrix. Each entry can be $1$ or $0$. Therefore there are $2^{n^{2}}$ possible choices and that many relations.
what if binary word is removed

Related questions

11 votes
3 answers
Let $L$ be a set with a relation $R$ which is transitive, anti-symmetric and reflexive and for any two elements $a, b \in L$, let the least upper bound $lub (a, b)$ and the greatest lower bound $glb (a, b)$ exist. Which of the following is/are true? $L$ is a poset $L$ is a Boolean algebra $L$ is a lattice None of the above
asked Sep 23, 2014 in Set Theory & Algebra Kathleen 1.6k views
12 votes
4 answers
Mr. X claims the following: If a relation R is both symmetric and transitive, then R is reflexive. For this, Mr. X offers the following proof: “From xRy, using symmetry we get yRx. Now because R is transitive xRy and yRx together imply xRx. Therefore, R is reflexive”. Give an example of a relation R which is symmetric and transitive but not reflexive.
asked Sep 24, 2014 in Set Theory & Algebra Kathleen 1.1k views
3 votes
1 answer
Let $G$ be a finite group and $H$ be a subgroup of $G$. For $a \in G$, define $aH=\left\{ah \mid h \in H\right\}$. Show that $|aH| = |bH|.$ Show that for every pair of elements $a, b \in G$, either $aH = bH$ or $aH$ and $bH$ are disjoint. Use the above to argue that the order of $H$ must divide the order of $G.$
asked Sep 23, 2014 in Set Theory & Algebra Kathleen 754 views
27 votes
1 answer
Which of the following is/are correct? An SQL query automatically eliminates duplicates An SQL query will not work if there are no indexes on the relations SQL permits attribute names to be repeated in the same relation None of the above
asked Sep 23, 2014 in Databases Kathleen 6.9k views