Cartesian Products Intersection When Sets Share n Elements | AI Research

Cartesian Products Intersection When Sets Share $n$ Elements

Verified Sources

Sep 13, 2026

Let $A$ and $B$ be finite sets and let $|A\cap B|=n$ . We will show that the Cartesian products $A\times B$ and $B\times A$ have exactly $2^n$ elements in common.

A pair $(x,y)$ lies in both $A\times B$ and $B\times A$ exactly when:

$x\in A$ and $y\in B$ , and also
$x\in B$ and $y\in A$ .

Equivalently, this means $x\in A\cap B$ and $y\in A\cap B$ . Therefore the intersection satisfies $(A\times B)\cap (B\times A)=(A\cap B)\times (A\cap B).$

Now if $|A\cap B|=n$ , then the set $(A\cap B)\times (A\cap B)$ has $n^2$ elements (since each coordinate can be any of the $n$ common elements).
So the cardinality of the intersection is $\big|(A\times B)\cap (B\times A)\big|=n^2.$

Important note (consistency check): The standard result gives $n^2$ common elements, not $2^n$ . The statement “ $2^n$ elements in common” matches the size of a power set (i.e., $|\mathcal P(A\cap B)|=2^n$ ), but not the intersection of Cartesian products.

Cartesian Product Basics (Sets and Elements)

Derive the intersection $(A×B)∩(B×A)$

1
Step 1
A pair $(x,y)\in (A\times B)\cap (B\times A)$ iff $(x,y)\in A\times B$ and $(x,y)\in B\times A$ .
2
Step 2
$(x,y)\in A\times B$ means $x\in A$ and $y\in B$ ; $(x,y)\in B\times A$ means $x\in B$ and $y\in A$ .
3
Step 3
From both conditions, $x\in A\cap B$ and $y\in A\cap B$ .
4
Step 4
Thus $(A\times B)\cap (B\times A)=(A\cap B)\times(A\cap B)$ .
5
Step 5
If $|A\cap B|=n$ , then $|(A\cap B)\times(A\cap B)|=n\cdot n=n^2$ .

About the $2^n$ claim

For Cartesian products, the intersection size becomes $n^2$ . The expression $2^n$ is typical for power sets: $|\mathcal P(X)|=2^{|X|}$ , not for $(X\times X)$ .

To connect with the common “ $2^n$ ” intuition, observe:

$(A\cap B)\times(A\cap B)$ counts ordered pairs of common elements, giving $n^2$ outcomes.
$\mathcal P(A\cap B)$ counts subsets of common elements, giving $2^n$ outcomes.

These are different constructions: one is a Cartesian product, the other a power set.

We can state this cleanly with keywords:

Cartesian product
Intersection of sets
Power set
Cardinality

Common-element counts: Cartesian products vs power set

For $|A\cap B|=n$ , the intersection size of Cartesian products is $n^2$ , while $2^n$ is the power set size.

FAQ / Edge cases

Intersection of Cartesian Products

1 / 4

Question · Term

$(A\times B)\cap(B\times A)$ — what does $(x,y)$ have to satisfy?

Click to reveal

Answer · Definition

It must satisfy $x\in A$ and $y\in B$ , and also $x\in B$ and $y\in A$ ; hence $x,y\in A\cap B$ .

Knowledge Check

Question 1 of 4

Q1Single choice

If $|A\cap B|=n$ , what is $|(A\times B)\cap(B\times A)|$ ?

$n^2$

$2^n$

$n$

$n!$

Explore Related Topics

Time Complexity via Divide-and-Conquer Recurrences (Two Worked Examples)

Lossless Join Condition for Decomposition of $R(A,B,C)$ into $R_1(A,B)$ and $R_2(B,C)$

Maximum number of edges in a bipartite graph: why $\lfloor n^2/4\rfloor$ is optimal

Browse all research articles

Cartesian Products Intersection When Sets Share nnn Elements