Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
I guess another question I should ask is: does the map $f: \emptyset \to A$ exist for $A \neq \emptyset$? Is it unique? –  Matt Jan 24 '12 at 19:08
1  
Yes: $\varnothing$ is the unique function from $\varnothing$ to $A$, for any set $A$ (empty or nonempty). Just verify the definition of function is satisfied! –  Arturo Magidin Jan 24 '12 at 20:21

2 Answers 2

up vote 2 down vote accepted

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?

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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