Partial functions and fixed points

Question

Let $\Phi : [\mathbb N \rightharpoondown \mathbb N] \to [\mathbb N \rightharpoondown \mathbb N]$ be the map from the set of partial functions $\mathbb N \to \mathbb N$ to itself (what's a nice way of saying this? "endomorphism" seems too strong), defined as follows:

$\Phi(f)(n) = f(n) + 1$ if $f(n)$ is defined, undefined otherwise.

I've been asked to determine whether or not this function has any fixed points. I'd like to know if the set $[ \mathbb N \rightharpoondown \mathbb N]$ includes the entirely "undefined" function, and whether this function is unique? i.e. would the function $f : \emptyset \to \emptyset$ be a fixed point of $\Phi$?

Thanks

Answer 1

A finite partial function from $\mathbb{N}$ to $\mathbb{N}$ is simply a finite $f\subseteq\mathbb{N}^2$ with the property that $$\forall k,m,n\in\mathbb{N}\Big(\big(\langle k,m\rangle\in f\land\langle k,n\rangle\in f\big)\to m=n\Big)\;,$$ and $\varnothing$ is vacuously such a subset of $\mathbb{N}^2$, so it is indeed a finite partial function from $\mathbb{N}$ to $\mathbb{N}$. It is the unique such function with domain $\varnothing$. From a set-theoretic point of view you can derive the domain and range from the function, but not the codomain, so $f:\varnothing\to A$ remains the same function $-$ the same set of ordered pairs $-$ irrespective of what $A$ is.

As you suspect, $\varnothing$ is indeed a fixed point of $\Phi$, since $\Phi(\varnothing)(n)$ is undefined for each $n\in\mathbb{N}$ and therefore $\Phi(\varnothing)=\varnothing$. Note that if $f\ne\varnothing$, then $\operatorname{dom}f\ne\varnothing$; is it possible in that case for $f$ and $\Phi(f)$ to agree everywhere?

Answer 2

If $f$ is a fixed point of $\Phi$, then $\Phi(f)$ and $f$ have the same domain, and are equal on every element of the domain. If you consider what integers $a = f(n)$ this could hold for (for any particular $n \in \mathrm{dom}(f)$), I think you will find that you obtain a complete characterization of what functions are fixed points of $\Phi$.

(Incidentally, "endomorphism" is technically appropriate here. I'll grant that the "morphism" is not preserving very much structure, but even functions in Set are morphisms; just morphisms of a fairly relaxed category.)