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

Relational Algebra Equivalence: Why $\pi_A(R) - \pi_A((\pi_A(R) \times S) - R)$ Represents Division

The expression

[ \pi_A(R)-\pi_A\big((\pi_A(R)\times S)-R\big) ]

is a derived form of the relational‑algebra division operator, returning all (A) values that pair with every tuple in (S).

Division is defined as (R\div S={a\mid\forall b\in S,;(a,b)\in R}).
The formula works by (1) projecting candidate (A) values, (2) forming all required ((A,B)) pairs with (S), (3) subtracting existing pairs to find missing ones, (4) projecting the missing (A) values, and (5) removing them from the candidates.
In the example, (R(A,B)={(1,x),(1,y),(2,x),(2,y),(3,x)}) and (S(B)={x,y}) yield (R\div S={1,2}).
This construction captures the universal (“for all”) query pattern, unlike selection, join, or simple projection.

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

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