Explanation: Connection Between the Cartesian Product and Functions Mapping Finite Sets into a Non-empty Set

(related to Part: Set-theoretic Prerequisites Needed For Combinatorics)

Now, we want to reverse the question and ask for the number of different maps of a finite set, say with two elements $\{a,b\},$ into an arbitrary, non-empty set $X$, i.e. $f:\{a,b\}\to X$? How many possible maps of this kind are there? In order to answer this question, observe that a given $f$ assigns uniquely $a\to f(a)$ and $b\to f(b),$ where $x:=f(a)$ and $y:=f(b)$ are some unique two elements of $x,y\in X.$ In the set theory, this is called an ordered pair $(x,y).$ Such an ordered pair is an element of the Cartesian product $X\times X.$ Vice versa, any given ordered pair $(x,y)\in X\times X$ uniquely determines a map $f$ by defining $f(a):=x$ and $f(b):=y.$

Therefore, there is a one-to-one correspondence between maps of finite sets with $n$ elements into a given non-empty set $X.$ This connection is summarized in the following proposition:

  1. Proposition: Number of Ordered n-Tuples in a Set

Thank you to the contributors under CC BY-SA 4.0!