2

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.

mudri
  • 271

2 Answers2

1

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.

AlexR
  • 24,905
  • 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. – mudri Aug 28 '14 at 15:30
  • 1
    @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$) – AlexR Aug 28 '14 at 15:38
  • My original conditions were right, but my deductions were wrong. Thanks for the counterexample! – mudri Aug 28 '14 at 15:46
0

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

Najib Idrissi
  • 54,185
  • Yep. $;!$ Or onto, but I prefer surjective. – goblin GONE Aug 28 '14 at 14:09
  • 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. – mudri Aug 28 '14 at 14:22
  • @JamesWood What do you mean by "Integer without $0$ representation"? What would $100$ map to and what would map to $100$? – AlexR Aug 28 '14 at 14:47
  • @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. – Najib Idrissi Aug 28 '14 at 15:03
  • @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. – mudri Aug 28 '14 at 15:22
  • @JamesWood Well, that's not even a function of $S\to S$, since the domain and codomain are different (${0,\ldots,9}^{\mathbb N} \to {1, \ldots, 9, A}^{\mathbb N}$) – AlexR Aug 28 '14 at 15:41
  • @AlexR It's a non-example, but surjective. Hence, “surjective” alone is not what I wanted. – mudri Aug 28 '14 at 15:54
  • @JamesWood Ah okay I see the problem. NB that using the bijection of "relabelling" $A$ to $0$, you get a function wich fulfills your requirements. – AlexR Aug 28 '14 at 15:56