4

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}

EoDmnFOr3q
  • 1,050
  • 3
    Either notation works. I’m not sure what the other person was talking about; using exponential notation to denote sets of functions is commonplace. – Mark Saving Dec 14 '22 at 17:11
  • Thank you for your comment. Why is it commonplace, then? This notation must have some origin / reason behind it... – EoDmnFOr3q Dec 14 '22 at 17:13
  • 4
    It’s commonplace because if $Y$ and $Z$ are finite, then under this definition, $|Y^Z| = |Y|^{|Z|}$, where the latter exponent is just the normal exponent of natural numbers (and $0^0 = 1$). The same thing happens with $\times$. – Mark Saving Dec 14 '22 at 17:15
  • Thank you again for your comment. I understand that the cardinality of the set $Y^X$ coincides with the cardinality of the set of all functions from $X$ to $Y$. However, I do not see how that is enough to use $Y^X$ to denote the set of all functions from $X$ to $Y$. I guess am still failing at seeing the objects in $Y^X$ as functions. – EoDmnFOr3q Dec 14 '22 at 17:19
  • 1
    @MarkSaving: Technically, that also works if $Y$ and $Z$ are infinite. – Dan Dec 14 '22 at 17:23
  • 1
    The notation has been used previously on this very website, multiple times. – Dan Dec 14 '22 at 17:26
  • 2
    To complicate it further, I have seen (no clue about the prevalence) some authors use ${}^XY$ instead! – Brian Moehring Dec 14 '22 at 17:31
  • 1
    @BrianMoehring Interesting! I suppose the rationale for $^{X}Y$ is that the sets appear in the same left-to-right order as in $X\to Y$. – paperskilltrees Dec 14 '22 at 17:32
  • 1
    @Hector "I guess am still failing at seeing the objects in $Y^X$ as functions". How do you define $Y^X$ then? I cannot think of any other way of interpreting $Y^X$, where $X,Y$ are sets. – paperskilltrees Dec 14 '22 at 17:37
  • 2
    @Dan It’s circular to say that it works for infinite cardinalities, since this is how we define cardinal exponents. By contrast, there is a pre-existing notion of natural number exponentiation, so the identity isn’t circular for finite sets. – Mark Saving Dec 14 '22 at 17:37
  • 2
    @Hector This is literally the definition of $Y^X$. It’s not a matter of “seeing” $Y^X$ as a set of functions; it’s a matter of defining it that way. My comment was simply to illustrate that it is logical to use the notation in this way, since it has a relationship to other uses of the same notation. – Mark Saving Dec 14 '22 at 17:39
  • Thank you all for your comments. Let me do an example. Let $X={a,b,c}$ and let $Y={d,e}$. Then, $Y^X={d,e}^{{a,b,d}}$. But then, I really do not know how to further expand ${d,e}^{{a,b,d}}$. Any help to see why ${d,e}^{{a,b,d}}$ is the set of all functions from ${a,b,d}$ to ${d,e}$? Or is it just a standard convention arising from the fact that $|Y^Z|=|Y|^{|Z|}$? – EoDmnFOr3q Dec 14 '22 at 17:50

1 Answers1

6

$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.

Frank
  • 2,416
  • Thank you very much for your useful answer. The reason why I was writing it as ${z\in Y^X\mid\dots}$ is because I thought that when using set-builder notation, one had to always start defining an element of a set (hence, ${z\in Y^X\mid\dots}$ rather than ${z:X\to Y\mid\dots}$). However, I am guessing from your answer that I can start to build a set of functions using set-builder notation by just writing ${z:X\to Y\mid\dots}$. Correct? – EoDmnFOr3q Dec 14 '22 at 17:28
  • 3
    Yeah, the set-builder notation is pretty flexible. When you say $z : X \to Y$, people will interpret it as $z \in Y^X$. We're doing math here, not programming :) – Frank Dec 14 '22 at 17:33
  • 1
    @Frank: Well, in programming, you'd have something more like typedef Y (*XToYFunction)(X);. – Dan Dec 14 '22 at 18:08
  • 2
    @Dan Sure. I just meant that we have a bit of room to be flexible with our notation because humans are reading our proofs, not computers. So I don't have to always use the precise syntax ${x \in S \mid x \ \text{satisfies} \ P}$ for set-builder notation, and the reader will still know what I mean. – Frank Dec 14 '22 at 19:13