Question

Suppose a friend asks you to list out all relations on the set S = {n|n ∈ Z+ and n≤1000}. Find the number of number of relations on S. Is your friend making a reasonable request?

Answer 1

A relation is a subset of $S\times S.$ Hence number of relations is the number of subsets of $S\times S.$ Hence number of relations=$|P(S\times S)|$ where P denotes power set.$|S|=1000.$ Hence

$|S\times S|=1000^2.$ Hence $|P(S\times S)|=2^{1000^2}.$