4
$\begingroup$

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}

$\endgroup$
12
  • 3
    $\begingroup$ Either notation works. I’m not sure what the other person was talking about; using exponential notation to denote sets of functions is commonplace. $\endgroup$
    – Mark Saving
    Commented Dec 14, 2022 at 17:11
  • 4
    $\begingroup$ 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$. $\endgroup$
    – Mark Saving
    Commented Dec 14, 2022 at 17:15
  • 2
    $\begingroup$ To complicate it further, I have seen (no clue about the prevalence) some authors use ${}^XY$ instead! $\endgroup$
    – Brian Moehring
    Commented Dec 14, 2022 at 17:31
  • 2
    $\begingroup$ @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. $\endgroup$
    – Mark Saving
    Commented Dec 14, 2022 at 17:37
  • 2
    $\begingroup$ @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. $\endgroup$
    – Mark Saving
    Commented Dec 14, 2022 at 17:39

1 Answer 1

Reset to default
6
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – EoDmnFOr3q
    Commented Dec 14, 2022 at 17:28
  • 3
    $\begingroup$ 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 :) $\endgroup$
    – Frank
    Commented Dec 14, 2022 at 17:33
  • 1
    $\begingroup$ @Frank: Well, in programming, you'd have something more like typedef Y (*XToYFunction)(X);. $\endgroup$
    – Dan
    Commented Dec 14, 2022 at 18:08
  • 2
    $\begingroup$ @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. $\endgroup$
    – Frank
    Commented Dec 14, 2022 at 19:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .