# What is the difference between Relation and Cartesian product?

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$

• The number of possible relations is equal to the number of subsets of the Cartesian product. – amd Jul 12 '18 at 18:38
• A relation is a subset of a Cartesian product. – William Elliot Jul 19 '18 at 3:06
• @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? – 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$)