I want to describe a function $f$ which, on set $S$, satisfies these properties: $$ \forall x\in S.f\ x\in S \\ \forall y\in S.\exists x\in S.f\ x=y $$ One example is the successor function upon $\mathbb Z$, and one non-example is the successor function upon $\mathbb N$ (because $\nexists x\in\mathbb N.\text{succ}\ x=0)$.

Is there a commonly understood word for this, or should I just define my own term? In the title, I suggest “$f$ is completely closed over $S$”. As with standard closure, this term can expand to describe n-ary functions.


The two statements given in your question are precisely $$f(x) \in S \qquad \forall x\in S$$ i.e. $f: S\to S$ is a function and $$\forall y\in S \exists x\in S: f(x) = y$$ i.e. $f(S) = S$ or $f$ is surjective.

If your notation reflects what you want to call "completely closed", it is nothing other than a surjective function from a set $S$ to itself.

| cite | improve this answer | |
  • $\begingroup$ I may have missed something from the conditions. It should be the case that $f\ S=S$ and $f^{-1}\ S=S$ (and unique $f^{-1}$ exists because the function is bijective). Also, $S$ should be the image of $f$, not just the codomain. $\endgroup$ – James Wood Aug 28 '14 at 15:30
  • 1
    $\begingroup$ @JamesWood Then you're at "$f$ is a bijection of $S$ to itself". Note that the two statements do not imply injectivity (Consider $x\mapsto \lfloor \frac x2 \rfloor$ on $S=\mathbb N$) $\endgroup$ – AlexR Aug 28 '14 at 15:38
  • $\begingroup$ My original conditions were right, but my deductions were wrong. Thanks for the counterexample! $\endgroup$ – James Wood Aug 28 '14 at 15:46

Such a function is called surjective. More generally, it applies to function $f : X \to Y$ even when the codomain is not equal to the domain: $f$ is called surjective when for all $y \in Y$, there exists $x \in X$ such that $f(x) = y$.

| cite | improve this answer | |
  • $\begingroup$ Yep. $\;\!$ Or onto, but I prefer surjective. $\endgroup$ – goblin Aug 28 '14 at 14:09
  • $\begingroup$ I want something stricter than that, more related to closure than surjectiveness/injectiveness. I also consider the function that maps integers to their decimal without 0 representation to be a non-example, despite it being bijective. Would “self-bijective” work, or does that sound too much like “identity”? Thanks for the answer, though. $\endgroup$ – James Wood Aug 28 '14 at 14:22
  • $\begingroup$ @JamesWood What do you mean by "Integer without $0$ representation"? What would $100$ map to and what would map to $100$? $\endgroup$ – AlexR Aug 28 '14 at 14:47
  • $\begingroup$ @JamesWood: What do you want, exactly? What you wrote is just a surjective function from $S$ to itself. You can call it "self-surjective" (a bit ugly) or a "surjective endomorphism", if you want, but surjectivity (or "onto", or "epimorphism") is the essential word. $\endgroup$ – Najib Idrissi Aug 28 '14 at 15:03
  • $\begingroup$ @AlexR Bijective numeration. The number 100 maps to “9A”, and “100” is not in the range of the function. As for the argument for “surjective”, I'll think more about it. $\endgroup$ – James Wood Aug 28 '14 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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