Trying to understand pathological solution(s) to $f:f\rightarrow f$

So here’s a really weird “functional equation” I came up with. Since a function $g:X\rightarrow Y$ can be defined as a subset $g\subseteq X \times Y$ such that for all $ x \in X$, there is a unique $y\in Y$ such that $(x,y)\in g$. Since a function is then just a set, we could feasibly have a function who’s domain and range is itself. So I wanted to find a function $f: f\rightarrow f$.

The first example that comes to mind is $\emptyset : \emptyset \rightarrow \emptyset$, which works, but is kind of boring. For a while, I thought that might be the only solution. But then I came up with a really pathological set that I’m not sure what to make of, but I think it works.

Let $A_0=\{0\}$, we’ll say $A_{n+1}=A_n \times A_n$. So:

$$A_1=\{(0,0)\}$$ $$A_2=\big\{\big((0,0),(0,0)\big)\big\}$$ $$A_3=\Big\{\Big(\big((0,0),(0,0)\big),\big((0,0),(0,0)\big)\Big)\Big\}$$ $$\vdots$$

None of these satisfy the functional equation as $A_n\not \subseteq A_n \times A_n = A_{n+1}$. However, I did come up with a weird idea: could there be an $A_\infty$ that does satisfy the functional equation? It would look something like this:

$$A_\infty = \{(((\cdots(((0,0),(0,0)),((0,0),(0,0))),\cdots,(0,0)))\cdots)))\}$$

Where it has a sort of “infinite binary tree” structure to it.

Another way to interpret it, is that if $a\in A_\infty$ is the sole element of $A_\infty$, then $A_\infty=\{a\}=\{(a,a)\}$. Though one thing I don’t like about using this as a definition is that it ignores the $0$s “at the end” of the ordered pairs (whatever that means.) My other issue with it is that it seems to hinge on the assumption that $A_\infty$ exists, because it doesn’t construct $A_\infty$ directly.

I can’t really wrap my head around this set, and it doesn’t feel especially rigorous, but if it does seem to satisfy my functional equation. Since $A_\infty=\{a\}=\{(a,a)\}$, it seems to be the case that $A_\infty = A_\infty \times A_\infty$. Therefore, $A_\infty : A_\infty \rightarrow A_\infty$ seems to be a valid solution to the functional equation.

I don’t know what to make of this. While the solution to the functional equation $f=\emptyset$ makes complete sense to me, I can’t even tell if I’ve created a well-defined object with $A_\infty$. Is there a way to put this set on firm ground, or is it just complete nonsense?

I’m also curious about other solutions to this functional equation. I don’t think there are any other “normal” solutions besides $\emptyset$. We’d need the really weird property that $f\subseteq f\times f$, and I can’t think of any other sets that work. What other sets, if any, work?

Solution 1:

Suppose $f \subseteq f \times f$. By the definition of $\subseteq$,

$$\forall x \in f \quad x \in f \times f$$

Thus

$$\forall x \in f \quad \exists a, b \in f \quad x = \langle a, b \rangle$$

The rank of a Kuratowski ordered pair is strictly greater than the rank of its elements. Thus

$$\forall x \in f \quad \exists a, b \in f \quad \operatorname{rank} x > \operatorname{rank} a$$

That is,

$$\forall x \in f \quad \exists a \in f \quad \operatorname{rank} a < \operatorname{rank} x$$

Thus, if there exists an element of $f$, there exists an infinite sequence of elements of $f$ with strictly decreasing rank. But ranks are well-ordered. Thus $f$ is empty.

Solution 2:

Here's a well-defined solution. Define a sequence of sets as follows:

$$A_1 = \{0\}$$

$$A_{n+1} =\bigcup_{k=1}^n A_n\times A_k$$

And finally, define

$$A_{\infty} = \bigcup_{k=1}^\infty A_k$$

The set $A_{\infty}$ has the nice property that for all $a,b\in A_{\infty}$, the ordered pair $(a,b)\in A_{\infty}$. This implies that $A_\infty\times A_\infty \subset A_{\infty}$. So since any function $f:A_{\infty} \to A_{\infty}$ is defined as a subset of $A_{\infty} \times A_{\infty}$ with certain constraints, we have that $f\subset A_{\infty}$ and $f:f\to f$.

Now you can define any function you want from $A_\infty$ to itself! Some easy examples are

$$f_1(a) = 0$$

$$f_2(a)=a$$

$$f_3(a)=(a,a)$$

Solution 3:

Working without Regularity, there may exist sets $x=\{x\}$.

Then under Kuratowski's definition of ordered pairs, $$(x,x)=\{\{x\},\{x,x\}\}=\{\{x\}\}=\{x\}=x\in\{x\}=x$$

So $x:x\to x$ sending $x\mapsto x$ would be a function: $x\times x=\{(x,x)\}=\{x\}=x$ and $x\times x$ itself is a function from $x$ to $x$.

In your construction, if you take $A_0=x$ instead of $A_0=\{0\}$, then $A_\infty=x$ as well.

Using the definition for ordered pairs from above, we can visualise the sets $A_n$ as trees.

For example, here is $A_1$, where an arrow $x\to y$ stands for $y\in x$:

and for $A_{n+1}$ we have a tree that looks identical if we don't expand the sets $A_n$:

When we do expand the sets $A_n$, we get a more complex tree:

We can describe this operation of going from $A_n$ to $A_{n+1}$ as taking the tree for $A_1$, and replacing each bottom node of the tree $A_n$ with a copy of $A_1$. If we use $T_n$ to name the tree for $A_n$, then it is clear that we can embed the tree $T_n$ into $T_{n+1}$. Therefore, without loss of generality we can find some trees $S_n$ isomorphic to $T_n$ such that $S_0\subset S_1\subset S_2\subset S_3\subset\dots$.

This way we can formalise what it means to construct $T_\infty$, namely we can let $T_\infty$ be the tree $\bigcup_{n\in\Bbb N} S_n$, which is probably the "infinite binary tree" that you refer to in your question.

To see why it's impossible to associate a set to such a tree $T_\infty$ when we assume the Axiom of Regularity, note that there exist an infinite branch in $T_\infty$: starting from the root of the tree (the top node in my pictures), going all the way down.

Let's take such a branch $x_0\to x_1\to x_2\to x_3\to\cdots$, then by $x\to y$ being equivalent to $y\in x$, we see that we get an infinite chain $\cdots \in x_3\in x_2\in x_1\in x_0$. Hence, the set $X=\{x_n\mid n\in\Bbb N\}$ has no $\in$-minimal element, since $x_{n+1}\in x_n\cap X$ for every $n\in\Bbb N$.

(I know, the above pictures can be simplified a lot, by noting that $\{0,0\}=\{0\}$, thus $(0,0)=\{\{0\}\}$, but I only remembered that when I was halfway through drawing them...)

Solution 4:

Inspired by user76284:

Suppose that we have some set $f \subseteq f \times f$. I claim $f$ is empty. That is, I claim that for all $x$, $x \notin f$.

This can be proved by $\in$-induction. The precise statement of the induction will be $\forall x, x \notin f \land x \cap f = \emptyset$.

Suppose that for all $y \in x$, $y \notin f$ and $y \cap f = \emptyset$. Then clearly $x \cap f = \emptyset$. So it remains to show that $x \notin f$.

Suppose $x \in f$. Then we can write $x = (a, b) = \{\{a\}, \{a, b\}\}$ for some $a, b \in f$. Then we have $\{a\} \cap f \neq \emptyset$. But $\{a\} \in f$; contradiction. Therefore, $x \notin f$.

If you take another definition of ordered pairs as $(a, b) = \{a, \{a, b\}\}$, the proof is even shorter. As long as you take a definition of ordered pairs such that for all $a, b$, there is some sequence $s_1, s_2, ..., s_n$ such that $a \in s_1 \in s_2 \in ... \in s_n \in (a, b)$, this proof goes through (in a modified fashion).