Why is the set of all function from $X$ to $Y$ denoted $Y^X$

notation

Let $X$ and $Y$ be finite sets, and let $P$ be some property. I am defining the set $Z$ to be the set of all functions with domain $X$ and codomain $Y$ that satisfy property $P$ as follows:
\begin{gather}
Z=\{z\in Y^X\mid z\text{ satisfies property }P\}
\end{gather}
Following both Wikipedia and some authoritative sources in my field, I have been using the notation $Y^X$ to denote the set of all functions $z$ with domain $X$ and codomain $Y$, but someone recently challenged this notation and suggested it is not correct, as the objects in $Y^X$ are technically not functions.

Hence, my doubts:

  1. If $Y^X$ is commonplace notation to denote the set of all functions from $X$ to $Y$, could someone explain why?

  2. If $Y^X$ is not commonplace notation to denote the set of all functions from $X$ to $Y$, could someone tell me how to denote the set of all functions from $X$ to $Y$?

  3. Would the following expression be better to denote the set I am interested in?
    \begin{gather}
    Z=\{z:X\to Y\mid z\text{ satisfies property }P\}
    \end{gather}

Best Answer

$Y^X$ is pretty standard notation for the set of functions from $X$ to $Y$. The motivation behind this notation is that if $X$ and $Y$ have finite cardinalities, the set $Y^X$ has the cardinality $|Y|^{|X|}$. (Another time this "arithmetic" notation is used is in the cartesian product $X \times Y$.) This explains why the notation is written $Y^X$ rather than $X^Y$. This notation is also commonly used for the power set of a set $X$, written as $2^X$. Notice that if $2$ is a set with two elements, a function $f : X \to 2$ can be thought of as a subset of $X$.

That said, the notation $Y^X$ is not used very often, at least in my experience. Unless you are doing set theory, you aren't usually working with completely arbitrary functions, but rather, functions that preserve some kind of "structure". In linear algebra, you work with linear maps; in topology, you work with continuous maps; in algebra, you work with homomorphisms. There is often specific notation for the set of all _____ maps. For example, the set of all linear maps is written $\mathcal{L}(X, Y)$.

To address your last question, you should write $Z = \{z : X \to Y \mid \text{$z$ satisfies property $P$}\}$. It is much, much more common to declare a function as $z : X \to Y$ rather than $z \in Y^X$, and you should always try to choose notation that is more familiar to the reader.

Related Question