9
$\begingroup$

Is there a common notation for the set of all injections from $A$ into $B$?

Some set-theorists use $B^{(A)}$, e.g., A. Levy in his book Basic Set Theory.

But some combinatorists use $B^{\underline{A}}$ or $(B)_A$, e.g. JMoravitz's answer in this question.

Some other combinatorists also use $\mathrm{Inj}(A,B)$, e.g., M. Aigner in his book Combinatorial Theory. But I don't like a notation of this kind, since I want something similar to $B^A$ or ${}^AB$ which is commonly used to denote the set of all maps from $A$ to $B$.

Any suggestions for a notation are welcome.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ I don't think this question is suitable here.. $\endgroup$
    – Praphulla Koushik
    Oct 24, 2019 at 4:03
  • $\begingroup$ @Praphulla I'm sorry for that. If not, I will delete it tomorrow. $\endgroup$
    – Guozhen Shen
    Oct 24, 2019 at 5:07
  • 13
    $\begingroup$ Personally I think terminology and notation are worth topics. I would be curious to read the answer to this question $\endgroup$
    – Pietro Majer
    Oct 24, 2019 at 6:53
  • 1
    $\begingroup$ About $B^{(A)}$: at least in group theory, it is frequently used in another meaning. Namely $A$ is a set, $(B,o)$ is a pointed set (typically a group), and $B^{(A)}$ is the set of finitely supported functions $f:A\to B$, that is, such that $f(a)=o$ for all but finitely many $a\in A$. $\endgroup$
    – YCor
    Oct 24, 2019 at 11:29
  • $\begingroup$ @YCor A. Levy also has a similar concept in his book, but he uses $\mathrm{exp}(B,A)$. I also think $B^{(A)}$ is not good for denoting the set of injections. Besides the reason you just mentioned, some combinatorists use $B^{(A)}$ for another meaning, namely rising factorials. $\endgroup$
    – Guozhen Shen
    Oct 24, 2019 at 11:54

2 Answers 2

Reset to default
15
$\begingroup$

The notation suggested by cardinal equalities such as

\begin{array}{l|l|l} \text{concept} & \text{notation} & \text{cardinality} \\ \hline \text{disjoint union of $A$ and $B$} & A + B & |A + B| = |A| + |B| \\ \text{Cartesian product of $A$ and $B$} & A \times B & |A \times B| = |A| \times |B| \\ \text{set of functions from $A$ to $B$, also $A \rightarrow B$} & B^A & |B^A| = |B|^{|A|} \\ \text{set of permutations of $A$, also $\text{Sym}(A)$} & A! & |A!| = |A|! \\ \text{set of $k$-element subsets of $A$} & \binom{A}{k} & \left|\binom{A}{k}\right| = \binom{|A|}{k} \\ \text{set of $k$-element partitions of $A$} & \left\{{A \atop k}\right\} & \left| \left\{{A \atop k}\right\} \right| = \left\{{|A| \atop k}\right\} \end{array}

is

\begin{array}{l|l|l} \text{concept} & \text{notation} & \text{cardinality} \\ \hline \text{set of injections from $A$ to $B$} & B^{\underline{A}} & |B^{\underline{A}}| = |B|^{\underline{|A|}} \end{array}

because the falling factorial

\begin{align*} |B|^\underline{|A|} = \frac{|B|!}{(|B| - |A|)!} \end{align*}

is precisely the number of injections from $A$ to $B$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you. This is one of the notations mentioned in the post. $\endgroup$
    – Guozhen Shen
    Oct 26, 2019 at 2:06
4
$\begingroup$

If I take your question literally, it seems to me that the correct answer is simply "No". But I quite happily use $B^A_{\neq}$. Analogously, if $A$ and $B$ happen to be ordered, I write $B^A_{<}$ for the set of all strictly increasing functions from $A$ to $B$. For me, this works well.

Improve this answer
$\endgroup$
3
  • 6
    $\begingroup$ I didn't immediately notice this notation is not just arbitrary but views injections as maps between preserving the binary relation $\neq$. $\endgroup$
    – YCor
    Oct 25, 2019 at 19:11
  • $\begingroup$ With @YCor's convention, $B^A_<$ and $B^A_>$, the functions preserving $<$ and $>$, are the same. Is that really what's intended? $\endgroup$
    – LSpice
    May 19, 2021 at 20:41
  • 1
    $\begingroup$ @LSpice I think so. It might look a bit weird maybe because it uses the same notation for the binary relations at the source and target. So it might be denoted $B^A_{\neq,\neq}$, and $B^A_{<_A,<_B}=B^A_{>_A,>_B}$ would both be the set of strictly increasing maps $(A,<_A)\to (B,<_B)$. The decreasing ones would be $B^A_{<_A,>_B}=B^A_{>_A,<_B}$. More generally, if $R-$ denotes the flip of a binary relation $R$, the when $R,S$ are binary relations on $A,B$, we get $B^A_{R,S}=B^A_{R-,S-}$. $\endgroup$
    – YCor
    May 19, 2021 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.