I'm confused with Cartesian product and Relation.

As in Cartesian product, the number of ordered pair possible are $n(A)n(B)$.

In relation the number of relation possible are $2^{n(A) n(B)}$.

Also, it is said that Relation is a subset of the Cross Product. But what I see is the opposite.

Ex: if $n(A) = 2$, $n(B) = 3$.

then $n(A \times B) = 6$.

Relation is $2^6 = 64$

  • 1
    $\begingroup$ The number of possible relations is equal to the number of subsets of the Cartesian product. $\endgroup$ – amd Jul 12 '18 at 18:38
  • $\begingroup$ A relation is a subset of a Cartesian product. $\endgroup$ – William Elliot Jul 19 '18 at 3:06
  • $\begingroup$ @amd So what you mean is that, $2^n$ is the no. of possible relations, i.e., how many distinct relations can be formed. Each relation is a subset of cartesian product. Isn't? $\endgroup$ – Kaushik Sep 12 at 9:10

Reiterating what was already said with a concrete example

Take a slightly smaller example of $A=\{a,b\}$ and $B=\{1,2\}$

One has $A\times B=\{(a,1),(a,2),(b,1),(b,2)\}$

A relation is a subset of $A\times B$, for example the relation $\{(a,1),(b,2)\}$

One will always have a specific relation having cardinality at most that of $|A\times B|$.

Now... the set of all relations (which is itself not a relation in this context) for this example would be:

$$\left\{\emptyset,\{(a,1)\},\{(a,2)\},\{(b,1)\},\{(b,2)\},\{(a,1),(a,2)\},\{(a,1),(b,1)\},\{(a,1),(b,2)\},\{(a,2),(b,1)\},\dots \{(a,1),(a,2),(b,1),(b,2)\}\right\}$$ and for this specific example would have $2^4=16$ elements, elements in this context meaning relations like $\{(a,1),(a,2)\}$


You appear to be confusing the set of all relations with the relations themselves. Every relation is a subset of the Cartesian product, and in fact every subset is a relation. Thus, the cardinality of the set of relations is equal to the cardinality of the power set of the Cartesian product, which is precisely $2^{|A\times B|}$.


In your example, the set $A\times B$ has six elements (each of which is an ordered pair). A relation between $A$ and $B$ is an arbitrary subset of $A\times B$. There are $2^6$ subsets of $A\times B$; so it seems you count the cardinality of the set of relations between $A$ and $B$ - but each element of this set is a relation (i.e., a set of pairs of elements of $A$ and $B$, in other words a subset of $A\times B$)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.