# Can I soundly define a function which maps to itself?

A function can be defined by specifying a set of tuples. If I write the definition of a function $f = \lbrace(0, f) \rbrace$, is this function sound? Will this lead to a paradox? The domain of this function is $\lbrace 0\rbrace$, but what is its range?

• The definition proposed is not a ZF set construction. – André Nicolas Jul 8 '15 at 21:31

If I write the sentence "The table police the dog, while drinking", can I write it? Does it have any meaning?

Not everything that we can write, syntactically, must have meaning mathematically. Just like we can write utter nonsense (just look at the career Monty Python got out of it!), we can also write mathematical nonsense.

You can write $f=\{(0,f)\}$. Sure. But does it have any meaning?

Assuming $\sf ZF$, the answer is no. You can prove that such $f$ does not exist. Namely, there does not exist a set $f$ such that the unique element of $f$ is an ordered pair $(x,y)$ such that $x=0$ and $y=f$ itself. The reason is that any reasonable method for encoding ordered pairs will eventually create a cycle in the $\in$ relation.

Specifically, in the Kuratowski definition, $(0,f)=\{\{0\},\{0,f\}\}$, and then $f\in\{0,f\}\in(0,f)\in f$.

On the other hand, if you reject the axiom of regularity (also known as Foundation axiom), then it is a possibility for $x$ to be an element of an element of an element of $x$ itself. So it is possible to obtain such $f$. In that case, $f$ is indeed a function, and its range is $\{f\}$, of course. What else would it be?

• You know that man the Israelis have, who can bend his legs over his head on each step? That's not me. I'm a retired wi-window cleaner and pacifist, without doing warcrimes! I was head of Gestapo for 10 years! – Asaf Karagila Jul 8 '15 at 22:26
• Tsch tsch tsch! I was not head of Gestapo at all. I make joke! – Asaf Karagila Jul 8 '15 at 22:26
• Now I see the mistake that I made in my previous comment: I forgot that $f$ is not $(0,f)$ but $\{ (0,f) \}$. – Ian Jul 8 '15 at 23:18
• Assuming $\mathsf{NF(U)}$ as your set theory, you can find a function that takes itself as both an input and a value in a very silly way: the identity function on the universe exists. – Malice Vidrine Jul 10 '15 at 16:28
• @Malice: Right. Working with any of the anti-foundation axioms works as well, since they literally give you a way to prove the existence of (or sometimes even prove the uniqueness of) $f=\{(0,f)\}$ or $f=\{(f,0)\}$ or so on. – Asaf Karagila Jul 10 '15 at 16:33

A function can be defined by specifying a set of tuples. If I write the definition of a function $f = \lbrace(0, f) \rbrace$, is this function sound?

I don't think you will be able to prove the existence of $f$ as you have described it. To prove it exists, you would need to be able to construct it from a pair of sets $A$ and $B$ such that $A=\{0\}$ and $f\in B$.

First, let $A\times B$ be the Cartesian product of sets $A$ and $B$.

Then you would select a subset of $A\times B$ as follows:

$\exists g:[\forall a,b:[(a,b)\in g \iff (a,b)\in A\times B\land b=f]]$

Using existential specification, we could name this subset $h$ to obtain:

$\forall a,b:[(a,b)\in h \iff (a,b)\in A\times B\land b=f]$

Using set-builder notation, that would be

$h=\{(0,f)\}$

It would be a trivial exercise to prove $h$ is a function such that $h:A\to B$ and $h(0)=f$.

Due to restrictions on the use of existential specification, we could not, however, name the subset $f$ because the name $f$ is already the name of a free variable introduced in the initial assumptions. We are stuck.